Randomized algorithms for the low-rank approximation of matrices

DOI10.1073/pnas.0709640104zbMath1215.65080OpenAlexW1968691112WikidataQ36299805 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

Parallel numerical computation (65Y05)

Related Items

Pass-efficient methods for compression of high-dimensional turbulent flow data, Efficient algorithms for CUR and interpolative matrix decompositions, A fast direct singular boundary method for three-dimensional potential problems, Fast Algorithms for Hyperspectral Diffuse Optical Tomography, Sweeping preconditioner for the Helmholtz equation: Hierarchical matrix representation, 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 Local Model Order Reduction, A unified framework for linear dimensionality reduction in L1, Multidomain, sparse, spectral-tau method for helically symmetric flow, A Technique for Updating Hierarchical Skeletonization-Based Factorizations of Integral Operators, A fast nested dissection solver for Cartesian 3D elliptic problems using hierarchical matrices, Function Approximation on Arbitrary Domains Using Fourier Extension Frames, 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, 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, Enhanced image approximation using shifted rank-1 reconstruction, Randomized matrix-free trace and log-determinant estimators, Randomized generalized singular value decomposition, Randomized Quaternion Singular Value Decomposition for Low-Rank Matrix Approximation, Computing Low-Rank Approximations of Large-Scale Matrices with the Tensor Network Randomized SVD, Subspaces Analysis for Random Projection UTV Framework, 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, New fast divide-and-conquer algorithms for the symmetric tridiagonal eigenvalue problem, 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, Cluster-based generalized multiscale finite element method for elliptic PDEs with random coefficients, A simple filter for detecting low-rank submatrices, A new fast direct solver for the boundary element method, Interpolative Decomposition Butterfly Factorization, Dense fast random projections and Lean Walsh transforms, A fast direct solver for elliptic problems on general meshes in 2D, An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations, Detecting low-rank clusters via random sampling, A fast direct solver for boundary value problems on locally perturbed geometries, Literature survey on low rank approximation of matrices, FaIMS: a fast algorithm for the inverse medium problem with multiple frequencies and multiple sources for the scalar Helmholtz equation, An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation, 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, Random Sampling and Efficient Algorithms for Multiscale PDEs, Adaptive dimension reduction to accelerate infinite-dimensional geometric Markov chain Monte Carlo, Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations, Fast structured LU factorization for nonsymmetric matrices, Post-buckling behaviour of a growing elastic rod, 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, New tests of uniformity on the compact classical groups as diagnostics for weak-\(^{*}\) mixing of Markov chains, Multidimensional butterfly factorization, 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, Block-adaptive cross approximation of discrete integral operators, Robust and Effective eSIF Preconditioning for General Dense SPD Matrices, Fast Randomized Non-Hermitian Eigensolvers Based on Rational Filtering and Matrix Partitioning, A randomized exponential canonical correlation analysis method for data analysis and dimensionality reduction, Randomized estimation of spectral densities of large matrices made accurate, Randomized model order reduction, Approximation error in regularized SVD-based Fourier continuations, An improved divide-and-conquer algorithm for the banded matrices with narrow bandwidths, Fast construction of hierarchical matrix representation from matrix-vector multiplication, Efficient methods for grouping vectors into low-rank clusters, Low-rank approximations for computing observation impact in 4D-Var data assimilation, On spectral and numerical properties of random butterfly matrices, Fast randomized matrix and tensor interpolative decomposition using countsketch, Acoustic full-waveform inversion and its uncertainty estimation based on a vector-version square-root variable metric method, Pass-Efficient Randomized Algorithms for Low-Rank Matrix Approximation Using Any Number of Views, Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory, An efficient hybrid tridiagonal divide-and-conquer algorithm on distributed memory architectures, Fast multipole preconditioners for sparse matrices arising from elliptic equations, 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, A Fast Memory Efficient Construction Algorithm for Hierarchically Semi-Separable Representations, Randomized interpolative decomposition of separated representations, A heterogeneous stochastic FEM framework for elliptic PDEs, Block Basis Factorization for Scalable Kernel Evaluation, An \(O(N)\) direct solver for integral equations on the plane, A fast randomized algorithm for overdetermined linear least-squares regression, Stochastic Algorithms in Linear Algebra - beyond the Markov Chains and von Neumann - Ulam Scheme, A direct solver for elliptic PDEs in three dimensions based on hierarchical merging of Poincaré-Steklov operators, A cross-product approach for low-rank approximations of large matrices, Stochastic boundary methods of fundamental solutions for solving PDEs, 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, Scalable Gaussian Process Computations Using Hierarchical Matrices, Unnamed Item, Parallel Randomized and Matrix-Free Direct Solvers for Large Structured Dense Linear Systems, Data-driven resolvent analysis, A fast integral equation method for the two-dimensional Navier-Stokes equations, Fast and backward stable transforms between spherical harmonic expansions and bivariate Fourier series, Simulation of two-dimensional steady-state heat conduction problems by a fast singular boundary method, Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning, Unnamed Item, Unnamed Item, Single-pass randomized QLP decomposition for low-rank approximation, Bootstrapping the operator norm in high dimensions: error estimation for covariance matrices and sketching, Randomized numerical linear algebra: Foundations and algorithms, Randomized QR with Column Pivoting, Fast Randomized Iteration: Diffusion Monte Carlo through the Lens of Numerical Linear Algebra, A fast direct boundary element method for 3D acoustic problems based on hierarchical matrices, libdlr: efficient imaginary time calculations using the discrete Lehmann representation, A compact heart iteration for low-rank approximations of large matrices, Seq-SVF: an unsupervised data-driven method for automatically identifying hidden governing equations, Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions, A Distributed-Memory Randomized Structured Multifrontal Method for Sparse Direct Solutions, FMM-LU: A Fast Direct Solver for Multiscale Boundary Integral Equations in Three Dimensions, QSurfNet: a hybrid quantum convolutional neural network for surface defect recognition, Training very large scale nonlinear SVMs using alternating direction method of multipliers coupled with the hierarchically semi-separable kernel approximations, Algebraic inverse fast multipole method: a fast direct solver that is better than HODLR based fast direct solver, A class of refined preconditioners with sparse error correction for BEM linear system, A fast solver for the narrow capture and narrow escape problems in the sphere, A fast time domain solver for the equilibrium Dyson equation, Scalable Physics-Based Maximum Likelihood Estimation Using Hierarchical Matrices, Nonlinear model reduction for slow-fast stochastic systems near unknown invariant manifolds, Goal-Oriented Optimal Approximations of Bayesian Linear Inverse Problems, Unnamed Item, 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 domain decomposition preconditioning for an inverse volume scattering problem, 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 Via Randomized Matrix-Vector Multiplications, Butterfly Factorization, Fast Updating Multipole Coulombic Potential Calculation, Fast approximate computations with Cauchy matrices and polynomials

Cites Work