A fast randomized algorithm for the approximation of matrices

DOI10.1016/j.acha.2007.12.002zbMath1155.65035MaRDI 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

15B52: Random matrices (algebraic aspects)

Related Items

Unnamed Item, Unnamed Item, Randomized Complete Pivoting for Solving Symmetric Indefinite Linear Systems, Computing Low-Rank Approximations of Large-Scale Matrices with the Tensor Network Randomized SVD, Practical Sketching Algorithms for Low-Rank Matrix Approximation, Literature survey on low rank approximation of matrices, Low-Rank Factorizations in Data Sparse Hierarchical Algorithms for Preconditioning Symmetric Positive Definite Matrices, Randomized Sketching Algorithms for Low-Memory Dynamic Optimization, Sublinear Cost Low Rank Approximation via Subspace Sampling, Low-Rank Tucker Approximation of a Tensor from Streaming Data, Randomized Quaternion Singular Value Decomposition for Low-Rank Matrix Approximation, RidgeSketch: A Fast Sketching Based Solver for Large Scale Ridge Regression, Interpolative Decomposition Butterfly Factorization, Random Sampling and Efficient Algorithms for Multiscale PDEs, Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations, 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, Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation, A randomized method for one‐step extrapolation in reverse time migration, Subspace Iteration Randomization and Singular Value Problems, Butterfly Factorization, Fast Randomized Iteration: Diffusion Monte Carlo through the Lens of Numerical Linear Algebra, Adaptively Compressed Polarizability Operator for Accelerating Large Scale Ab Initio Phonon Calculations, Efficient Identification of Butterfly Sparse Matrix Factorizations, Randomized numerical linear algebra: Foundations and algorithms, 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, 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, A parallel low rank matrix optimization method for recovering Internet traffic network data via link flow measurement, A fast randomized algorithm for computing an approximate null space, A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization, Scalable Physics-Based Maximum Likelihood Estimation 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 the integral equations of scattering theory on planar curves with corners, Detecting low-rank clusters via random sampling, 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, 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, An adaptive fast direct solver for boundary integral equations in two dimensions, Randomized interpolative decomposition of separated representations, A fast randomized algorithm for the approximation of matrices, Fast dimension reduction using Rademacher series on dual BCH codes, An ACA-SBM for some 2D steady-state heat conduction problems, Large-scale stochastic linear inversion using hierarchical matrices. Illustrated with an application to crosswell tomography in seismic imaging, Randomized LU decomposition, A new fast direct solver for the boundary element method, Optimization methods for regularization-based ill-posed problems: a survey and a multi-objective framework, Multidimensional butterfly factorization, Approximation error in regularized SVD-based Fourier continuations, Randomized model order reduction, Randomized LU decomposition using sparse projections, Fast randomized matrix and tensor interpolative decomposition using countsketch, An efficient randomized algorithm for computing the approximate Tucker decomposition, Split representation of adaptively compressed polarizability operator, Bootstrapping the operator norm in high dimensions: error estimation for covariance matrices and sketching, Pass-efficient methods for compression of high-dimensional turbulent flow data, An accelerated, high-order accurate direct solver for the Lippmann-Schwinger equation for acoustic scattering in the plane, An efficient algorithm for computing the approximate t-URV and its applications, Randomized QLP decomposition, The stability of the first Neumann Laplacian eigenfunction under domain deformations and applications, Randomized algorithms for the low multilinear rank approximations of tensors, Randomized core reduction for discrete ill-posed problem, Simulation of two-dimensional steady-state heat conduction problems by a fast singular boundary method, Randomized algorithms for low-rank matrix factorizations: sharp performance bounds, 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, A fast block low-rank dense solver with applications to finite-element matrices, Far-field compression for fast kernel summation methods in high dimensions, Efficient preconditioning of \(hp\)-FEM matrices by hierarchical low-rank approximations, Cluster-based generalized multiscale finite element method for elliptic PDEs with random coefficients, Paved with good intentions: analysis of a randomized block Kaczmarz method, An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation, An \(O(N)\) direct solver for integral equations on the plane, Stochastic boundary methods of fundamental solutions for solving PDEs, Randomized generalized singular value decomposition, Tikhonov Regularization and Randomized GSVD, 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, Parallel Randomized and Matrix-Free Direct Solvers for Large Structured Dense Linear Systems, Stochastic iterative projection methods for large linear systems, Stochastic Algorithms in Linear Algebra - beyond the Markov Chains and von Neumann - Ulam Scheme, IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM, Randomized Local Model Order Reduction, Fast Structured Direct Spectral Methods for Differential Equations with Variable Coefficients, I. The One-Dimensional Case, Sparsified Randomization Algorithms for large systems of linear equations and a new version of the Random Walk on Boundary method

Uses Software

Algorithm 844

Cites Work