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 (only showing first 100 items - show all)

Broadband recursive skeletonization ⋮ SVD-based algorithms for tensor wheel decomposition ⋮ Efficient bounds and estimates for canonical angles in randomized subspace approximations ⋮ Krylov subspace recycling with randomized sketching for matrix functions ⋮ 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 ⋮ A sketch-and-select Arnoldi process ⋮ 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 ⋮ Randomized low-rank approximation methods for projection-based model order reduction of large nonlinear dynamical problems ⋮ Fast and accurate randomized algorithms for linear systems and eigenvalue problems ⋮ SVD-based algorithms for fully-connected tensor network decomposition ⋮ A robust randomized indicator method for accurate symmetric eigenvalue detection ⋮ 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

Uses Software

Algorithm 844

Cites Work

This page was built for publication: A fast randomized algorithm for the approximation of matrices