Practical sketching algorithms for low-rank matrix approximation
From MaRDI portal
Publication:4598337
dimension reductionmatrix approximationrandomized algorithmsketchingstreaming algorithmnumerical experimentnumerical linear algebrasubspace embeddingsingle-pass algorithm
Abstract: This paper describes a suite of algorithms for constructing low-rank approximations of an input matrix from a random linear image of the matrix, called a sketch. These methods can preserve structural properties of the input matrix, such as positive-semidefiniteness, and they can produce approximations with a user-specified rank. The algorithms are simple, accurate, numerically stable, and provably correct. Moreover, each method is accompanied by an informative error bound that allows users to select parameters a priori to achieve a given approximation quality. These claims are supported by numerical experiments with real and synthetic data.
Recommendations
- Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
- Fast monte-carlo algorithms for finding low-rank approximations
- Fast low rank approximations of matrices and tensors
- Low-rank approximation algorithms for matrix completion with random sampling
- Fast computation of low rank matrix approximations
Cites work
- scientific article; zbMATH DE number 4115838 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- A fast randomized algorithm for the approximation of matrices
- A randomized algorithm for the decomposition of matrices
- Algorithm 971
- Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
- Dimensionality reduction for \(k\)-means clustering and low rank approximation
- Fast linear algebra is stable
- Fast monte-carlo algorithms for finding low-rank approximations
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Improved analysis of the subsampled randomized Hadamard transform
- Improved matrix algorithms via the subsampled randomized Hadamard transform
- Latent semantic indexing: A probabilistic analysis
- Low-Rank PSD Approximation in Input-Sparsity Time
- Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
- Lower bounds for oblivious subspace embeddings
- Nearly tight oblivious subspace embeddings by trace inequalities
- Numerical linear algebra in the streaming model
- Online principal components analysis
- Optimal Approximate Matrix Product in Terms of Stable Rank
- Optimal principal component analysis in distributed and streaming models
- Practical sketching algorithms for low-rank matrix approximation
- Randomized Algorithms for Matrices and Data
- Sketching as a tool for numerical linear algebra
- Subspace Iteration Randomization and Singular Value Problems
- The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
- Turning big data into tiny data: constant-size coresets for \(k\)-means, PCA and projective clustering
- Turnstile streaming algorithms might as well be linear sketches
Cited in
(83)- Broadband recursive skeletonization
- A sequential multilinear Nyström algorithm for streaming low-rank approximation of tensors in Tucker format
- A multilinear Nyström algorithm for low-rank approximation of tensors in Tucker format
- Wavelet-based resolvent analysis of non-stationary flows
- Robust Recovery of Low-Rank Matrices and Low-Tubal-Rank Tensors from Noisy Sketches
- Revisiting Spectral Bundle Methods: Primal-Dual (Sub)linear Convergence Rates
- Random projections for linear programming: an improved retrieval phase
- Randomized compression of rank-structured matrices accelerated with graph coloring
- Principled interpolation of Green's functions learned from data
- Numerical strategies for recursive least squares solutions to the matrix equation AX = B
- XT<scp>race</scp>: Making the Most of Every Sample in Stochastic Trace Estimation
- Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
- Approximate distance-comparison-preserving symmetric encryption
- Memory-efficient structured convex optimization via extreme point sampling
- On the convergence of projected-gradient methods with low-rank projections for smooth convex minimization over trace-norm balls and related problems
- Fast randomized numerical rank estimation for numerically low-rank matrices
- Randomized Nyström Preconditioning
- Practical sketching algorithms for low-rank Tucker approximation of large tensors
- Fast and accurate randomized algorithms for linear systems and eigenvalue problems
- SketchySGD: reliable stochastic optimization via randomized curvature estimates
- Pass-efficient truncated UTV for low-rank approximations
- Sketching for a low-rank nonnegative matrix approximation: numerical study
- The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection
- Pass-efficient methods for compression of high-dimensional turbulent flow data
- Frequent directions: simple and deterministic matrix sketching
- Random projections for conic programs
- Randomized Discrete Empirical Interpolation Method for Nonlinear Model Reduction
- Randomized quaternion QLP decomposition for low-rank approximation
- Perturbations of CUR Decompositions
- Learning to Forecast Dynamical Systems from Streaming Data
- Efficient randomized algorithms for the fixed-precision low-rank matrix approximation
- Low-rank Tucker approximation of a tensor from streaming data
- Distributed estimation of principal eigenspaces
- Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views
- A nonlinear matrix decomposition for mining the zeros of sparse data
- Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs
- Scalable semidefinite programming
- Pass-efficient randomized LU algorithms for computing low-rank matrix approximation
- Proof methods for robust low-rank matrix recovery
- Improved Variants of the Hutch++ Algorithm for Trace Estimation
- A non-Euclidean gradient descent method with sketching for unconstrained matrix minimization
- Generalized conditional gradient with augmented Lagrangian for composite minimization
- Randomized QLP decomposition
- Single-pass randomized algorithms for LU decomposition
- Randomized subspace iteration: analysis of canonical angles and unitarily invariant norms
- Scalable kernel \(k\)-means clustering with Nyström approximation: relative-error bounds
- Contour Integral Methods for Nonlinear Eigenvalue Problems: A Systems Theoretic Approach
- Improved practical matrix sketching with guarantees
- An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation
- Streaming Tensor Train Approximation
- Low-rank independence samplers in hierarchical Bayesian inverse problems
- Streaming low-rank matrix approximation with an application to scientific simulation
- Solving trust region subproblems using Riemannian optimization
- An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems
- Sketching as a tool for numerical linear algebra
- Efficient $\widetilde{O}(n/\epsilon)$ Spectral Sketches for the Laplacian and its Pseudoinverse
- Bounded matrix low rank approximation
- scientific article; zbMATH DE number 7049775 (Why is no real title available?)
- Randomized numerical linear algebra: Foundations and algorithms
- Low-rank nonnegative tensor approximation via alternating projections and sketching
- An efficient randomized QLP algorithm for approximating the singular value decomposition
- Randomized algorithms for the computation of multilinear rank-\((\mu_1,\mu_2,\mu_3)\) approximations
- Extended Lanczos bidiagonalization algorithm for low rank approximation and its applications
- An efficient randomized algorithm for computing the approximate Tucker decomposition
- An efficient randomized fixed-precision algorithm for tensor singular value decomposition
- Single-pass randomized QLP decomposition for low-rank approximation
- Randomized sketching algorithms for low-memory dynamic optimization
- FANOK: knockoffs in linear time
- Randomized Low-Rank Approximation for Symmetric Indefinite Matrices
- Why Are Big Data Matrices Approximately Low Rank?
- A fast randomized algorithm for computing an approximate null space
- ISLET: fast and optimal low-rank tensor regression via importance sketching
- Exploiting low-rank structure in semidefinite programming by approximate operator splitting
- ALORA: affine low-rank approximations
- Practical sketching algorithms for low-rank matrix approximation
- Subspaces analysis for random projection UTV framework
- Sublinear Cost Low Rank Approximation via Subspace Sampling
- A block bidiagonalization method for fixed-accuracy low-rank matrix approximation
- scientific article; zbMATH DE number 7306853 (Why is no real title available?)
- Screening for a reweighted penalized conditional gradient method
- Randomized Spectral Clustering in Large-Scale Stochastic Block Models
- Scalable \textit{in situ} compression of transient simulation data using time-dependent bases
- Randomized Low-Rank Approximation of Monotone Matrix Functions
This page was built for publication: Practical sketching algorithms for low-rank matrix approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598337)
