# Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition

arXiv: https://arxiv.org/abs/2208.09585 · HTML: https://mlsanity.com/paper/2208.09585/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 76 references that are in the map.
- First posted on arXiv 20 Aug 2022.

## Builds on (most cited first, 23 of 23)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Rates of Convergence for Sparse Variational Gaussian Process Regression](https://mlsanity.com/paper/1903.03571/) (2019)
- [Determinantal Point Processes in Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2005.03185/) (2020)
- [Exact expressions for double descent and implicit regularization via surrogate random design](https://mlsanity.com/paper/1912.04533/) (2019)
- [RSN: Randomized Subspace Newton](https://mlsanity.com/paper/1905.10874/) (2019)
- [Kernel quadrature with DPPs](https://mlsanity.com/paper/1906.07832/) (2019)
- [Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update](https://mlsanity.com/paper/2107.07480/) (2021)
- [Stochastic Subspace Cubic Newton Method](https://mlsanity.com/paper/2002.09526/) (2020)
- [Sparse sketches with small inversion bias](https://mlsanity.com/paper/2011.10695/) (2020)
- [Sampling from a k-DPP without looking at all items](https://mlsanity.com/paper/2006.16947/) (2020)
- [Sketched Newton-Raphson](https://mlsanity.com/paper/2006.12120/) (2020)
- [Fast determinantal point processes via distortion-free intermediate sampling](https://mlsanity.com/paper/1811.03717/) (2018)
- [Precise expressions for random projections: Low-rank approximation and randomized Newton](https://mlsanity.com/paper/2006.10653/) (2020)
- [Convergence Analysis of Block Coordinate Algorithms with Determinantal Sampling](https://mlsanity.com/paper/1910.11561/) (2019)
- [A Sampling Kaczmarz-Motzkin Algorithm for Linear Feasibility](https://mlsanity.com/paper/1605.01418/) (2016)
- [Randomized Kaczmarz converges along small singular vectors](https://mlsanity.com/paper/2006.16978/) (2020)
- [A Randomized Coordinate Descent Method with Volume Sampling](https://mlsanity.com/paper/1904.04587/) (2019)
- [Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designs](https://mlsanity.com/paper/2206.10291/) (2022)
- [Randomized sketch descent methods for non-separable linearly constrained optimization](https://mlsanity.com/paper/1808.02530/) (2018)

## Built on by (most cited first, 19 of 19)

- [Solving Dense Linear Systems Faster Than via Preconditioning](https://mlsanity.com/paper/2312.08893/) (2023)
- [Optimal Embedding Dimension for Sparse Subspace Embeddings](https://mlsanity.com/paper/2311.10680/) (2023)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems](https://mlsanity.com/paper/2405.05818/) (2024)
- [Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching](https://mlsanity.com/paper/2305.18379/) (2023)
- [Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning](https://mlsanity.com/paper/2405.05865/) (2024)
- [Randomized Kaczmarz with geometrically smoothed momentum](https://mlsanity.com/paper/2401.09415/) (2024)
- [Distributed Least Squares in Small Space via Sketching and Bias Reduction](https://mlsanity.com/paper/2405.05343/) (2024)
- [Cubic regularized subspace Newton for non-convex optimization](https://mlsanity.com/paper/2406.16666/) (2024)
- [Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project](https://mlsanity.com/paper/2505.13723/) (2025)
- [Iteris: Agentic Research Loops for Computational Mathematics](https://mlsanity.com/paper/2606.02484/) (2026)
- [Worth Their Weight: Randomized and Regularized Block Kaczmarz Algorithms without Preprocessing](https://mlsanity.com/paper/2502.00882/) (2025)
- [A Sketch-and-Project Analysis of Subsampled Natural Gradient Algorithms](https://mlsanity.com/paper/2508.21022/) (2025)
- [Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size](https://mlsanity.com/paper/2604.09909/) (2026)
- [One-Bit Quadratic Compressed Sensing: From Sample Abundance to Linear Feasibility](https://mlsanity.com/paper/2303.09594/) (2023)
- [Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nystr"om Method](https://mlsanity.com/paper/2506.17556/) (2025)
- [Matrix Completion from One-Bit Dither Samples](https://mlsanity.com/paper/2310.03224/) (2023)
- [Randomized batch-sampling Kaczmarz methods for solving linear systems](https://mlsanity.com/paper/2511.09872/) (2025)
- [Perfect Parallelization in Mini-Batch SGD with Classical Momentum Acceleration](https://mlsanity.com/paper/2605.18609/) (2026)

## Abstract (arXiv)

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 develop a theoretical framework for obtaining sharp guarantees on the convergence rate of sketch-and-project methods. Our approach is the first to: (1) show that the convergence rate improves at least linearly with the sketch size, and even faster when the data matrix exhibits certain spectral decays; and (2) allow for sparse sketching matrices, which are more efficient than dense sketches and more robust than sub-sampling methods. In particular, our results explain an observed phenomenon that a radical sparsification of the sketching matrix does not affect the per iteration convergence rate of sketch-and-project. To obtain our results, we develop new non-asymptotic spectral bounds for the expected sketched projection matrix, which are of independent interest; and we establish a connection between the convergence rates of iterative sketch-and-project solvers and the approximation error of randomized singular value decomposition, which is a widely used one-shot sketching algorithm for low-rank approximation. Our experiments support the theory and demonstrate that even extremely sparse sketches exhibit the convergence properties predicted by our framework.