检索结果-内蒙古大学图书馆

randomized Dynamic Mode Decomposition

SIAM JOURNAL ON APPLIED DYNAMICAL SYSTEMS 2019年第4期18卷 1867-1891页

作者： Erichson, N. Benjamin Mathelin, Ionel Kutz, J. Nathan Brunton, Steven L. Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA LIMSI CNRS Campus Univ Orsay Orsay 91405 France Univ Washington Dept Appl Math Seattle WA 98195 USA

This paper presents a randomized algorithm for computing the near-optimal low-rank dynamic mode decomposition (DMD). randomized algorithms are emerging techniques to compute low-rank matrix approximations at a fraction of the cost of deterministic algorithms, easing the computational challenges arising in the area of "big data." The idea is to derive a small matrix from the high-dimensional data, which is then used to efficiently compute the dynamic modes and eigenvalues. The algorithm is presented in a modular probabilistic framework, and the approximation quality can be controlled via oversampling and power iterations. The effectiveness of the resulting randomized DMD algorithm is demonstrated on several benchmark examples of increasing complexity, providing an accurate and efficient approach to extract spatiotemporal coherent structures from big data in a framework that scales with the intrinsic rank of the data, rather than the ambient measurement dimension. For this work we assume that the dynamics of the problem under consideration is evolving on a low-dimensional subspace that is well characterized by a quickly decaying singular value spectrum.

关键词： dynamic mode decomposition randomized algorithm dimension reduction dynamical systems

来源：评论

学校读者我要写书评

暂无评论

COUNTING WEIGHTED INDEPENDENT SETS BEYOND THE PERMANENT

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2021年第2期35卷 1503-1524页

作者： Dyer, Martin Jerrum, Mark Muller, Haiko Vuskovic, Kristina Univ Leeds Sch Comp Leeds LS2 9JT W Yorkshire England Queen Mary Univ London Sch Math Sci Mile End Rd London E1 4NS England

Jerrum, Sinclair, and Vigoda [J. ACM, 51 (2004), pp. 671-697] showed that the permanent of any square matrix can be estimated in polynomial time. This computation can be viewed as approximating the partition function of edge-weighted matchings in a bipartite graph. Equivalently, this may be viewed as approximating the partition function of vertex-weighted independent sets in the line graph of a bipartite graph. Line graphs of bipartite graphs are perfect graphs and are known to be precisely the class of (claw, diamond, odd hole)-free graphs. So how far does the result of Jerrum, Sinclair, and Vigoda extend? We first show that it extends to (claw, odd hole)-free graphs, and then show that it extends to the even larger class of (fork, odd hole)-free graphs. Our techniques are based on graph decompositions, which have been the focus of much recent work in structural graph theory, and on structural results of Chvatal and Sbihi [J. Combin. Theory Ser. B, 44 (1988)], Maffray and Reed [J. Combin. Theory Ser. B, 75 (1999)], and Lozin and Milanic [J. Discrete algorithms, 6 (2008), pp. 595-604].

关键词： independent set counting randomized algorithm fully polynomial randomized approximation scheme FPRAS claw-free graph fork-free graph decomposition

来源：评论

学校读者我要写书评

暂无评论

A probabilistic algorithm for aggregating vastly undersampled large Markov chains

引用

PHYSICA D-NONLINEAR PHENOMENA 2021年 416卷 132799-132799页

作者： Bittracher, Andreas Schuette, Christof Free Univ Berlin Dept Math & Comp Sci Berlin Germany Zuse Inst Berlin Berlin Germany

Model reduction of large Markov chains is an essential step in a wide array of techniques for understanding complex systems and for efficiently learning structures from high-dimensional data. We present a novel aggregation algorithm for compressing such chains that exploits a specific low rank structure in the transition matrix which, e.g., is present in metastable systems, among others. It enables the recovery of the aggregates from a vastly undersampled transition matrix which in practical applications may gain a speedup of several orders of magnitude over methods that require the full transition matrix. Moreover, we show that the new technique is robust under perturbation of the transition matrix. The practical applicability of the new method is demonstrated by identifying a reduced model for the large-scale traffic flow patterns from real-world taxi trip data. (C) 2020 The Authors. Published by Elsevier B.V.

关键词： Markov chain Aggregation Sparse sampling Metastability randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Low-Rank Tucker Approximation of a Tensor from Streaming Data

引用

SIAM JOURNAL ON MATHEMATICS OF DATA SCIENCE 2020年第4期2卷 1123-1150页

作者： Sun, Yiming Guo, Yang Luo, Charlene Tropp, Joel Udell, Madeleine Cornell Univ Dept Stat & Data Sci Ithaca NY 14853 USA Univ Wisconsin Madison Dept Comp Sci Madison WI 53706 USA Columbia Univ New York NY 10027 USA CALTECH Dept Comp Math Sci Pasadena CA 91125 USA Cornell Univ Sch Operat Res & Informat Engn Ithaca NY 14853 USA

This paper describes a new algorithm for computing a low-Tucker-rank approximation of a tensor. The method applies a randomized linear map to the tensor to obtain a sketch that captures the important directions within each mode, as well as the interactions among the modes. The sketch can be extracted from streaming or distributed data or with a single pass over the tensor, and it uses storage proportional to the degrees of freedom in the output Tucker approximation. The algorithm does not require a second pass over the tensor, although it can exploit another view to compute a superior approximation. The paper provides a rigorous theoretical guarantee on the approximation error. Extensive numerical experiments show that the algorithm produces useful results that improve on the state-of-the-art for streaming Tucker decomposition.

关键词： Tucker decomposition tensor compression dimension reduction sketching method randomized algorithm streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized algorithms in numerical linear algebra

引用

ACTA NUMERICA 2017年 26卷 95-135页

作者： Kannan, Ravindran Vempala, Santosh Microsoft Res Labs Bangalore 560001 Karnataka India Georgia Inst Technol North Ave NW Atlanta GA 30332 USA

This survey provides an introduction to the use of randomization in the design of fast algorithms for numerical linear algebra. These algorithms typically examine only a subset of the input to solve basic problems approximately, including matrix multiplication, regression and low-rank approximation. The survey describes the key ideas and gives complete proofs of the main results in the field. A central unifying idea is sampling the columns (or rows) of a matrix according to their squared lengths.

关键词： Regression Randomization randomized algorithm Linear algebra Matrix multiplication Numerical linear algebra algorithm Low-rank approximation

来源：评论

学校读者我要写书评

暂无评论

randomized Monte Carlo algorithms for Problems with Random Parameters ("Double Randomization" Method)

引用

NUMERICAL ANALYSIS AND APPLICATIONS 2019年第2期12卷 155-165页

作者： Mikhailov, G. A. Russian Acad Sci Inst Computat Math & Math Geophys Siberian Branch Pr Akad Laurenteva 6 Novosibirsk 630090 Russia Novosibirsk State Univ Ul Pirogova 2 Novosibirsk 630090 Russia

randomized Monte Carlo algorithms are constructed by a combination of a basic probabilistic model and its random parameters to investigate parametric distributions of linear functionals. An optimization of the algorithms with a statistical kernel estimator for the probability density is presented. A randomized projection algorithm for estimating a nonlinear functional distribution is formulated and applied to the investigation of the criticality fluctuations of a particle multiplication process in a random medium.

关键词： probabilistic model statistical modeling random parameter randomized algorithm double randomization method random medium splitting method statistical kernel estimator

来源：评论

学校读者我要写书评

暂无评论

RAPID APPLICATION OF THE SPHERICAL HARMONIC TRANSFORM VIA INTERPOLATIVE DECOMPOSITION BUTTERFLY FACTORIZATION

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2021年第6期43卷 A3789-A3808页

作者： Bremer, James Chen, Ze Yang, Haizhao Univ Calif Davis Dept Math Davis CA 95616 USA Natl Univ Singapore Dept Math Select Reg Singapore 11907 Singapore Purdue Univ Dept Math W Lafayette IN 47907 USA

We describe an algorithm for the application of the forward and inverse spherical harmonic transforms. It is based on a new method for rapidly computing the forward and inverse associated Legendre transforms by hierarchically applying the interpolative decomposition butterfly factorization. Experimental evidence suggests that the complexity of our method-including all necessary precomputations-is O(N-2 log(3) N) in terms of both flops and memory, where N is the order of the transform. This is nearly asymptotically optimal. Moreover, unlike existing algorithms which are asymptotically optimal or nearly so, the constants in the running time and memory costs of our algorithm are small enough to make it competitive with state-of-the-art O(N-3) methods at relatively small values of N (e.g., N = 1024). Numerical results are provided to demonstrate the effectiveness and numerical stability of the new framework.

关键词： spherical harmonic transform Legendre transform block partitioning butterfly factorization interpolative decomposition randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Constant Factor Approximations to Edit Distance on Far Input Pairs in Nearly Linear Time 2020

Constant Factor Approximations to Edit Distance on Far Input...

引用

52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Koucky, Michal Saks, Michael Charles Univ Prague Comp Sci Inst Prague Czech Republic Rutgers State Univ Dept Math Piscataway NJ USA

ISBN: (纸本)9781450369794

For any T >= 1, there are constants R = R(T) > 1 and zeta = zeta((T) > 0 and a randomized algorithm that takes as input an integer n and two strings x, y of length at most n, and runs in time O(n(1+1/T)) and outputs an upper bound U on the edit distance of d(edit)(x, y) that with high probability, satisfies U <= R(d(edit)(x, y) + n(1-zeta)). particular, on any input with d(edit)(x, y) >= n(1-zeta) the algorithm outputs a constant factor approximation with high probability. A similar result has been proven independently by Brakensiek and Rubinstein (this proceedings).

关键词： edit distance approximation algorithm almost linear-time algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Improvement of Multidimensional randomized Monte Carlo algorithms with "Splitting"

引用

COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS 2019年第5期59卷 775-781页

作者： Mikhailov, G. A. Russian Acad Sci Inst Computat Math & Math Geophys Siberian Branch Novosibirsk 630090 Russia Novosibirsk State Univ Novosibirsk 630090 Russia

randomized Monte Carlo algorithms are constructed by jointly realizing a baseline probabilistic model of the problem and its random parameters (random medium) in order to study a parametric distribution of linear functionals. This work relies on statistical kernel estimation of the multidimensional distribution density with a homogeneous kernel and on a splitting method, according to which a certain number of baseline trajectories are modeled for each medium realization. The optimal value of is estimated using a criterion for computational complexity formulated in this work. Analytical estimates of the corresponding computational efficiency are obtained with the help of rather complicated calculations.

关键词： probabilistic model Monte Carlo method statistical modeling randomized algorithm double randomization method random medium splitting method statistical kernel estimate complexity of functional estimate

来源：评论

学校读者我要写书评

暂无评论

randomized Primal–Dual Proximal Block Coordinate Updates

引用

Journal of the Operations Research Society of China 2019年第2期7卷 205-250页

作者： Xiang Gao Yang-Yang Xu Shu-Zhong Zhang Department of Industrial and Systems Engineering University of MinnesotaMinneapolisUSA Department of Mathematical Sciences Rensselaer Polytechnic InstituteTroyUSA

In this paper,we propose a randomized primal–dual proximal block coordinate updating framework for a general multi-block convex optimization model with coupled objective function and linear *** mere convexity,we establish its O(1/t)convergence rate in terms of the objective value and feasibility *** framework includes several existing algorithms as special cases such as a primal–dual method for bilinear saddle-point problems(PD-S),the proximal Jacobian alternating direction method of multipliers(Prox-JADMM)and a randomized variant of the ADMM for multi-block convex *** analysis recovers and/or strengthens the convergence properties of several existing *** example,for PD-S our result leads to the same order of convergence rate without the previously assumed boundedness condition on the constraint sets,and for Prox-JADMM the new result provides convergence rate in terms of the objective value and the feasibility *** is well known that the original ADMM may fail to converge when the number of blocks exceeds *** result shows that if an appropriate randomization procedure is invoked to select the updating blocks,then a sublinear rate of convergence in expectation can be guaranteed for multi-block ADMM,without assuming any strong *** new approach is also extended to solve problems where only a stochastic approximation of the subgradient of the objective is available,and we establish an O(1/√t)convergence rate of the extended approach for solving stochastic programming.

关键词： Primal-dual method Alternating direction method of multipliers(ADMM) randomized algorithm Iteration complexity·First-order stochastic approximation

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：