Randomized algorithms for the low-rank approximation of matrices
From MaRDI portal
Publication:3010073
DOI10.1073/pnas.0709640104zbMath1215.65080WikidataQ36299805 ScholiaQ36299805MaRDI QIDQ3010073
Vladimir Rokhlin, Mark Tygert, Edo Liberty, Per-Gunnar Martinsson, Franco Woolfe
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
65Y05: Parallel numerical computation
Related Items
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, 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, Approximation error in regularized SVD-based Fourier continuations, 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, 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
Cites Work
- On interpolation and integration in finite-dimensional spaces of bounded functions
- Incomplete cross approximation in the mosaic-skeleton method
- Estimating Extremal Eigenvalues and Condition Numbers of Matrices
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
- Efficient computation of the DFT with only a subset of input or output points
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- On the Compression of Low Rank Matrices
