Practical sketching algorithms for low-rank matrix approximation
From MaRDI portal
(Redirected from Publication:4598337)
dimension reductionmatrix approximationnumerical experimentnumerical linear algebrarandomized algorithmsingle-pass algorithmsketchingstreaming algorithmsubspace embedding
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
- 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
- scientific article; zbMATH DE number 4115838 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- Improved analysis of the subsampled randomized Hadamard transform
- Improved matrix algorithms via the subsampled randomized Hadamard transform
- Latent semantic indexing: A probabilistic analysis
- Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
- Low-Rank PSD Approximation in Input-Sparsity Time
- 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
(only showing first 100 items - show all)- Random projections for conic programs
- An efficient randomized algorithm for computing the approximate Tucker decomposition
- Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs
- Proof methods for robust low-rank matrix recovery
- Single-pass randomized QLP decomposition for low-rank approximation
- Pass-efficient methods for compression of high-dimensional turbulent flow data
- Randomized quaternion QLP decomposition for low-rank approximation
- Screening for a reweighted penalized conditional gradient method
- Scalable \textit{in situ} compression of transient simulation data using time-dependent bases
- Randomized QLP decomposition
- Distributed estimation of principal eigenspaces
- A non-Euclidean gradient descent method with sketching for unconstrained matrix minimization
- Single-pass randomized algorithms for LU decomposition
- ALORA: affine low-rank approximations
- Low-rank nonnegative tensor approximation via alternating projections and sketching
- Bounded matrix low rank approximation
- Frequent directions: simple and deterministic matrix sketching
- Improved practical matrix sketching with guarantees
- Sketching as a tool for numerical linear algebra
- Efficient randomized algorithms for the fixed-precision low-rank matrix approximation
- Practical sketching algorithms for low-rank matrix approximation
- Efficient $\widetilde{O}(n/\epsilon)$ Spectral Sketches for the Laplacian and its Pseudoinverse
- Randomized subspace iteration: analysis of canonical angles and unitarily invariant norms
- Scalable kernel \(k\)-means clustering with Nyström approximation: relative-error bounds
- scientific article; zbMATH DE number 7049775 (Why is no real title available?)
- Low-rank independence samplers in hierarchical Bayesian inverse problems
- Generalized conditional gradient with augmented Lagrangian for composite minimization
- Randomized sketching algorithms for low-memory dynamic optimization
- An Implicit Representation and Iterative Solution of Randomly Sketched Linear Systems
- Scalable semidefinite programming
- Sublinear Cost Low Rank Approximation via Subspace Sampling
- Why Are Big Data Matrices Approximately Low Rank?
- ISLET: fast and optimal low-rank tensor regression via importance sketching
- Exploiting low-rank structure in semidefinite programming by approximate operator splitting
- Low-rank Tucker approximation of a tensor from streaming data
- Randomized Spectral Clustering in Large-Scale Stochastic Block Models
- A nonlinear matrix decomposition for mining the zeros of sparse data
- Improved Variants of the Hutch++ Algorithm for Trace Estimation
- Subspaces analysis for random projection UTV framework
- The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection
- Randomized Discrete Empirical Interpolation Method for Nonlinear Model Reduction
- scientific article; zbMATH DE number 7306853 (Why is no real title available?)
- Memory-efficient structured convex optimization via extreme point sampling
- FANOK: knockoffs in linear time
- Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views
- Streaming low-rank matrix approximation with an application to scientific simulation
- On the convergence of projected-gradient methods with low-rank projections for smooth convex minimization over trace-norm balls and related problems
- Perturbations of CUR Decompositions
- A block bidiagonalization method for fixed-accuracy low-rank matrix approximation
- Randomized numerical linear algebra: Foundations and algorithms
- Extended Lanczos bidiagonalization algorithm for low rank approximation and its applications
- Sketching for a low-rank nonnegative matrix approximation: numerical study
- Contour Integral Methods for Nonlinear Eigenvalue Problems: A Systems Theoretic Approach
- Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
- An efficient randomized QLP algorithm for approximating the singular value decomposition
- Randomized algorithms for the computation of multilinear rank-(_1,_2,_3) approximations
- Robust Recovery of Low-Rank Matrices and Low-Tubal-Rank Tensors from Noisy Sketches
- Pass-efficient randomized LU algorithms for computing low-rank matrix approximation
- Streaming Tensor Train Approximation
- An efficient randomized fixed-precision algorithm for tensor singular value decomposition
- Randomized Low-Rank Approximation for Symmetric Indefinite Matrices
- An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation
- Practical sketching algorithms for low-rank Tucker approximation of large tensors
- Principled interpolation of Green's functions learned from data
- Numerical strategies for recursive least squares solutions to the matrix equation AX = B
- Solving trust region subproblems using Riemannian optimization
- Revisiting Spectral Bundle Methods: Primal-Dual (Sub)linear Convergence Rates
- Pass-efficient truncated UTV for low-rank approximations
- Approximate distance-comparison-preserving symmetric encryption
- Fast randomized numerical rank estimation for numerically low-rank matrices
- A fast randomized algorithm for computing an approximate null space
- Randomized Nyström Preconditioning
- Randomized Low-Rank Approximation of Monotone Matrix Functions
- Learning to Forecast Dynamical Systems from Streaming Data
- XT<scp>race</scp>: Making the Most of Every Sample in Stochastic Trace Estimation
- Fast and accurate randomized algorithms for linear systems and eigenvalue problems
- Random projections for linear programming: an improved retrieval phase
- Randomized compression of rank-structured matrices accelerated with graph coloring
- 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
- SketchySGD: reliable stochastic optimization via randomized curvature estimates
- A randomized algorithm to solve reduced rank operator regression
- On the randomized SVD in infinite dimensions
- Matrix perturbation analysis of methods for extracting singular values from approximate singular subspaces
- Randomized methods for dynamical low-rank approximation
- Sparse sub-Gaussian random projections for semidefinite programming relaxations
- Low-rank approximation: randomized QR with column pivoting and related methods using sparse projection and pass-efficient techniques
- Two-sided preconditioned CGLS for the solution of factorized linear systems
- A note on dimensionality reduction in deep neural networks using empirical interpolation method
- RTSMS: randomized Tucker with single-mode sketching
- Subspace methods for nonlinear optimization
- Randomized algorithm for constrained quaternion singular value decomposition and its applications
- Randomize low-rank Runge-Kutta methods
- Low-rank approximation of parameter-dependent matrices via CUR decomposition
- Efficient algorithms for Tucker decomposition via approximate matrix multiplication
- Low-rank approximation algorithm using sparse projection and its applications
- Accuracy and stability of CUR decompositions with oversampling
- Efficient randomized algorithms for fixed precision problem of approximate Tucker decomposition
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)
