A fast randomized algorithm for the approximation of matrices

DOI10.1016/j.acha.2007.12.002zbMath1155.65035OpenAlexW4213311204MaRDI QIDQ952399

Edo Liberty, Vladimir Rokhlin, Franco Woolfe, Mark Tygert

Publication date: 12 November 2008

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.acha.2007.12.002

zbMATH Keywords

numerical examples singular value decomposition Lanczos method random matrix QR factorization

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52)

Related Items

Pass-efficient methods for compression of high-dimensional turbulent flow data, Low-Rank Tucker Approximation of a Tensor from Streaming Data, Efficient Identification of Butterfly Sparse Matrix Factorizations, Efficient algorithms for CUR and interpolative matrix decompositions, Randomized numerical linear algebra: Foundations and algorithms, 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, A fast block low-rank dense solver with applications to finite-element matrices, Randomized Local Model Order Reduction, Fast Structured Direct Spectral Methods for Differential Equations with Variable Coefficients, I. The One-Dimensional Case, An accelerated, high-order accurate direct solver for the Lippmann-Schwinger equation for acoustic scattering in the plane, Randomized Complete Pivoting for Solving Symmetric Indefinite Linear Systems, An ACA-SBM for some 2D steady-state heat conduction problems, An efficient algorithm for computing the approximate t-URV and its applications, Far-field compression for fast kernel summation methods in high dimensions, Efficient preconditioning of \(hp\)-FEM matrices by hierarchical low-rank approximations, Large-scale stochastic linear inversion using hierarchical matrices. Illustrated with an application to crosswell tomography in seismic imaging, Randomized QLP decomposition, 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, RidgeSketch: A Fast Sketching Based Solver for Large Scale Ridge Regression, Fast Randomized Iteration: Diffusion Monte Carlo through the Lens of Numerical Linear Algebra, Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions, Randomized algorithms for the computation of multilinear rank-\((\mu_1,\mu_2,\mu_3)\) approximations, Robust Recovery of Low-Rank Matrices and Low-Tubal-Rank Tensors from Noisy Sketches, Randomized Low-Rank Approximation for Symmetric Indefinite Matrices, Randomized LU decomposition, Sketched approximation of regularized canonical correlation analysis, Principled interpolation of Green's functions learned from data, Randomized Sketching for Krylov Approximations of Large-Scale Matrix Functions, 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 parallel low rank matrix optimization method for recovering Internet traffic network data via link flow measurement, Practical Sketching Algorithms for Low-Rank Matrix Approximation, A simple filter for detecting low-rank submatrices, A fast randomized algorithm for computing an approximate null space, A new fast direct solver for the boundary element method, A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization, Interpolative Decomposition Butterfly Factorization, The stability of the first Neumann Laplacian eigenfunction under domain deformations and applications, A fast direct solver for the integral equations of scattering theory on planar curves with corners, Scalable Physics-Based Maximum Likelihood Estimation Using Hierarchical Matrices, Detecting low-rank clusters via random sampling, Literature survey on low rank approximation of matrices, Paved with good intentions: analysis of a randomized block Kaczmarz method, An adaptive fast direct solver for boundary integral equations in two dimensions, 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, Random Sampling and Efficient Algorithms for Multiscale PDEs, Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations, Randomized algorithms for the low multilinear rank approximations of tensors, Estimation of horizontal and vertical translations of large images based on columns and rows mean energy matching, The Fourier approximation of smooth but non-periodic functions from unevenly spaced data, Multidimensional butterfly factorization, Low-Rank Factorizations in Data Sparse Hierarchical Algorithms for Preconditioning Symmetric Positive Definite Matrices, A fast randomized algorithm for the approximation of matrices, Randomized estimation of spectral densities of large matrices made accurate, Randomized model order reduction, Approximation error in regularized SVD-based Fourier continuations, Adaptively Compressed Polarizability Operator for Accelerating Large Scale Ab Initio Phonon Calculations, Fast construction of hierarchical matrix representation from matrix-vector multiplication, Efficient methods for grouping vectors into low-rank clusters, Randomized LU decomposition using sparse projections, Unnamed Item, Fast randomized matrix and tensor interpolative decomposition using countsketch, Pass-Efficient Randomized Algorithms for Low-Rank Matrix Approximation Using Any Number of Views, A Model Reduction Method for Multiscale Elliptic Pdes with Random Coefficients Using an Optimization Approach, Randomized interpolative decomposition of separated representations, An \(O(N)\) direct solver for integral equations on the plane, Stochastic iterative projection methods for large linear systems, Stochastic Algorithms in Linear Algebra - beyond the Markov Chains and von Neumann - Ulam Scheme, Stochastic boundary methods of fundamental solutions for solving PDEs, An efficient randomized algorithm for computing the approximate Tucker decomposition, Tikhonov Regularization and Randomized GSVD, Split representation of adaptively compressed polarizability operator, Randomized Alternating Least Squares for Canonical Tensor Decompositions: Application to A PDE With Random Data, On Low Rank Approximation of Linear Operators in p-Norms and Some Algorithms, Randomized core reduction for discrete ill-posed problem, Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation, Parallel Randomized and Matrix-Free Direct Solvers for Large Structured Dense Linear Systems, IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM, Randomized Sketching Algorithms for Low-Memory Dynamic Optimization, Sparsified Randomization Algorithms for large systems of linear equations and a new version of the Random Walk on Boundary method, Fast dimension reduction using Rademacher series on dual BCH codes, A randomized method for one‐step extrapolation in reverse time migration, Simulation of two-dimensional steady-state heat conduction problems by a fast singular boundary method, Subspace Iteration Randomization and Singular Value Problems, Unnamed Item, Sublinear Cost Low Rank Approximation via Subspace Sampling, Randomized algorithms for low-rank matrix factorizations: sharp performance bounds, Bootstrapping the operator norm in high dimensions: error estimation for covariance matrices and sketching, Butterfly Factorization

Uses Software

Algorithm 844

Cites Work