Randomized algorithms for the low-rank approximation of matrices

DOI10.1073/pnas.0709640104zbMath1215.65080WikidataQ36299805 ScholiaQ36299805MaRDI QIDQ3010073

Franco Woolfe, Mark Tygert, Edo Liberty, Per-Gunnar Martinsson, Vladimir Rokhlin

Publication date: 30 June 2011

Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1073/pnas.0709640104

zbMATH Keywords

SVD; matrix; PCA

Mathematics Subject Classification ID

65Y05: Parallel numerical computation

Related Items

Unnamed Item, Unnamed Item, Function Approximation on Arbitrary Domains Using Fourier Extension Frames, Modified truncated randomized singular value decomposition (MTRSVD) algorithms for large scale discrete ill-posed problems with general-form regularization, An approximate empirical Bayesian method for large-scale linear-Gaussian inverse problems, Computing Low-Rank Approximations of Large-Scale Matrices with the Tensor Network Randomized SVD, Literature survey on low rank approximation of matrices, Low-Rank Factorizations in Data Sparse Hierarchical Algorithms for Preconditioning Symmetric Positive Definite Matrices, On the Numerical Rank of Radial Basis Function Kernels in High Dimensions, A New Preconditioner that Exploits Low-Rank Approximations to Factorization Error, Coarse-Grained Modeling of Protein Unfolding Dynamics, ASKIT: Approximate Skeletonization Kernel-Independent Treecode in High Dimensions, Subspace Iteration Randomization and Singular Value Problems, Butterfly Factorization, Fast Updating Multipole Coulombic Potential Calculation, Fast approximate computations with Cauchy matrices and polynomials, Randomized QR with Column Pivoting, Fast Randomized Iteration: Diffusion Monte Carlo through the Lens of Numerical Linear Algebra, A Distributed-Memory Randomized Structured Multifrontal Method for Sparse Direct Solutions, Goal-Oriented Optimal Approximations of Bayesian Linear Inverse Problems, Householder QR Factorization With Randomization for Column Pivoting (HQRRP), Randomized algorithms for generalized Hermitian eigenvalue problems with application to computing Karhunen–Loève expansion, A unified framework for linear dimensionality reduction in L1, A fast nested dissection solver for Cartesian 3D elliptic problems using hierarchical matrices, Matrix probing: a randomized preconditioner for the wave-equation Hessian, Sparsified randomization algorithms for low rank approximations and applications to integral equations and inhomogeneous random field simulation, A simple filter for detecting low-rank submatrices, A fast direct solver for elliptic problems on general meshes in 2D, Detecting low-rank clusters via random sampling, FaIMS: a fast algorithm for the inverse medium problem with multiple frequencies and multiple sources for the scalar Helmholtz equation, The Fourier approximation of smooth but non-periodic functions from unevenly spaced data, A fast SVD for multilevel block Hankel matrices with minimal memory storage, Randomized estimation of spectral densities of large matrices made accurate, Fast construction of hierarchical matrix representation from matrix-vector multiplication, Efficient methods for grouping vectors into low-rank clusters, Dense fast random projections and Lean Walsh transforms, An efficient hybrid tridiagonal divide-and-conquer algorithm on distributed memory architectures, Scalable and efficient algorithms for the propagation of uncertainty from data through inference to prediction for large-scale problems, with application to flow of the antarctic ice sheet, Randomized interpolative decomposition of separated representations, A heterogeneous stochastic FEM framework for elliptic PDEs, A direct solver for elliptic PDEs in three dimensions based on hierarchical merging of Poincaré-Steklov operators, Multidomain, sparse, spectral-tau method for helically symmetric flow, Large-scale stochastic linear inversion using hierarchical matrices. Illustrated with an application to crosswell tomography in seismic imaging, Efficient methods for computing observation impact in 4D-Var data assimilation, Theory and implementation of \(\mathcal{H}\)-matrix based iterative and direct solvers for Helmholtz and elastodynamic oscillatory kernels, A cubic scaling algorithm for excited states calculations in particle-particle random phase approximation, A new fast direct solver for the boundary element method, A fast direct solver for boundary value problems on locally perturbed geometries, Optimization methods for regularization-based ill-posed problems: a survey and a multi-objective framework, On computing distributions of products of non-negative independent random variables, Post-buckling behaviour of a growing elastic rod, New tests of uniformity on the compact classical groups as diagnostics for weak-\(^{*}\) mixing of Markov chains, Multidimensional butterfly factorization, Approximation error in regularized SVD-based Fourier continuations, Fast multipole preconditioners for sparse matrices arising from elliptic equations, Randomized model order reduction, Low-rank approximations for computing observation impact in 4D-Var data assimilation, Efficient algorithms for CUR and interpolative matrix decompositions, Compression of the electron repulsion integral tensor in tensor hypercontraction format with cubic scaling cost, Effective matrix-free preconditioning for the augmented immersed interface method, Dimension-independent likelihood-informed MCMC, Scalable posterior approximations for large-scale Bayesian inverse problems via likelihood-informed parameter and state reduction, Randomized matrix-free trace and log-determinant estimators, Cluster-based generalized multiscale finite element method for elliptic PDEs with random coefficients, An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation, Fast structured LU factorization for nonsymmetric matrices, An \(O(N)\) direct solver for integral equations on the plane, Stochastic boundary methods of fundamental solutions for solving PDEs, A Fast Memory Efficient Construction Algorithm for Hierarchically Semi-Separable Representations, Fast, Adaptive, High-Order Accurate Discretization of the Lippmann--Schwinger Equation in Two Dimensions, On Low Rank Approximation of Linear Operators in p-Norms and Some Algorithms, Frequent Directions: Simple and Deterministic Matrix Sketching, Parallel Randomized and Matrix-Free Direct Solvers for Large Structured Dense Linear Systems, New fast divide-and-conquer algorithms for the symmetric tridiagonal eigenvalue problem, A fast randomized algorithm for overdetermined linear least-squares regression, Stochastic Algorithms in Linear Algebra - beyond the Markov Chains and von Neumann - Ulam Scheme, Sweeping preconditioner for the Helmholtz equation: Hierarchical matrix representation, Randomized Local Model Order Reduction, Fast Algorithms for Hyperspectral Diffuse Optical Tomography, A Technique for Updating Hierarchical Skeletonization-Based Factorizations of Integral Operators

Cites Work