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, 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, 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, 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, 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