Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition
From MaRDI portal
Publication:6202283
Abstract: Sketch-and-project is a framework which unifies many known iterative methods for solving linear systems and their variants, as well as further extensions to non-linear optimization problems. It includes popular methods such as randomized Kaczmarz, coordinate descent, variants of the Newton method in convex optimization, and others. In this paper, we obtain sharp guarantees for the convergence rate of sketch-and-project methods via new tight spectral bounds for the expected sketched projection matrix. Our estimates reveal a connection between the sketch-and-project convergence rate and the approximation error of another well-known but seemingly unrelated family of algorithms, which use sketching to accelerate popular matrix factorizations such as QR and SVD. This connection brings us closer to precisely quantifying how the performance of sketch-and-project solvers depends on their sketch size. Our analysis covers not only Gaussian and sub-gaussian sketching matrices, but also a family of efficient sparse sketching methods known as LESS embeddings. Our experiments back up the theory and demonstrate that even extremely sparse sketches show the same convergence properties in practice.
Recommendations
- Adaptively sketched Bregman projection methods for linear systems
- Randomized iterative methods for linear systems
- On block Gaussian sketching for the Kaczmarz method
- Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
- RidgeSketch: a fast sketching based solver for large scale ridge regression
Cites work
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- A Hilbert Space Embedding for Distributions
- A randomized Kaczmarz algorithm with exponential convergence
- A randomized coordinate descent method with volume sampling
- A sampling Kaczmarz-Motzkin algorithm for linear feasibility
- An improved approximation algorithm for the column subset selection problem
- Block Kaczmarz method with inequalities
- Determinantal point processes in randomized numerical linear algebra
- Fast approximation of matrix coherence and statistical leverage
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
- Hanson-Wright inequality and sub-Gaussian concentration
- High-dimensional probability. An introduction with applications in data science
- Improved analysis of the subsampled randomized Hadamard transform
- Kernel Mean Embedding of Distributions: A Review and Beyond
- On Adaptive Sketch-and-Project for Solving Linear Systems
- On block Gaussian sketching for the Kaczmarz method
- On the empirical distribution of eigenvalues of a class of large dimensional random matrices
- On the equivalence between kernel quadrature rules and random feature expansions
- On the mean and variance of the generalized inverse of a singular Wishart matrix
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Randomized Kaczmarz Converges Along Small Singular Vectors
- Randomized iterative methods for linear systems
- Randomized methods for linear constraints: convergence rates and conditioning
- Randomized numerical linear algebra: Foundations and algorithms
- Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms
- Randomized sketch descent methods for non-separable linearly constrained optimization
- Sketched Newton-Raphson
- The Relaxation Method for Linear Inequalities
- The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
- Two-subspace projection method for coherent overdetermined systems
Cited in
(4)
This page was built for publication: Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202283)
