Randomized algorithms for the low-rank approximation of matrices
From MaRDI portal
Publication:3010073
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
Related Items (only showing first 100 items - show all)
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 ⋮ 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
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
This page was built for publication: Randomized algorithms for the low-rank approximation of matrices
