# Krylov Methods are (nearly) Optimal for Low-Rank Approximation

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 65 references that are in the map.
- First posted on arXiv 6 Apr 2023.

## Builds on (most cited first, 30 of 34)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [A quantum-inspired classical algorithm for recommendation systems](https://mlsanity.com/paper/1807.04271/) (2018)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [Hutch++: Optimal Stochastic Trace Estimation](https://mlsanity.com/paper/2010.09649/) (2020)
- [Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices](https://mlsanity.com/paper/1704.03371/) (2017)
- [Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension](https://mlsanity.com/paper/1811.04909/) (2018)
- [Toward a unified theory of sparse dimensionality reduction in Euclidean space](https://mlsanity.com/paper/1311.2542/) (2013)
- [Sample-Optimal Low-Rank Approximation of Distance Matrices](https://mlsanity.com/paper/1906.00339/) (2019)
- [Quantum-inspired sublinear classical algorithms for solving low-rank linear systems](https://mlsanity.com/paper/1811.04852/) (2018)
- [Query lower bounds for log-concave sampling](https://mlsanity.com/paper/2304.02599/) (2023)
- [Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law](https://mlsanity.com/paper/1804.01221/) (2018)
- [Sublinear Time Low-Rank Approximation of Distance Matrices](https://mlsanity.com/paper/1809.06986/) (2018)
- [Learning a Latent Simplex in Input-Sparsity Time](https://mlsanity.com/paper/2105.08005/) (2021)
- [The gradient complexity of linear regression](https://mlsanity.com/paper/1911.02212/) (2019)
- [Querying a Matrix through Matrix-Vector Products](https://mlsanity.com/paper/1906.05736/) (2019)
- [Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems](https://mlsanity.com/paper/2006.14015/) (2020)
- [Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2011.04125/) (2020)
- [Input-Sparsity Low Rank Approximation in Schatten Norm](https://mlsanity.com/paper/2004.12646/) (2020)
- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [Optimal query complexity for estimating the trace of a matrix](https://mlsanity.com/paper/1405.7112/) (2014)
- [Robust and Sample Optimal Algorithms for PSD Low-Rank Approximation](https://mlsanity.com/paper/1912.04177/) (2019)
- [Sublinear Time Numerical Linear Algebra for Structured Matrices](https://mlsanity.com/paper/1912.06060/) (2019)
- [Average-Case Communication Complexity of Statistical Problems](https://mlsanity.com/paper/2107.01335/) (2021)
- [A Tight Analysis of Hutchinson's Diagonal Estimator](https://mlsanity.com/paper/2208.03268/) (2022)
- [An Improved Classical Singular Value Transformation for Quantum Machine Learning](https://mlsanity.com/paper/2303.01492/) (2023)
- [Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings](https://mlsanity.com/paper/2202.09797/) (2022)
- [On Approximating Functions of the Singular Values in a Stream](https://mlsanity.com/paper/1604.08679/) (2016)
- [Embeddings of Schatten Norms with Applications to Data Streams](https://mlsanity.com/paper/1702.05626/) (2017)

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

- [Sharper Bounds for Chebyshev Moment Matching, with Applications](https://mlsanity.com/paper/2408.12385/) (2024)
- [Query Efficient Structured Matrix Learning](https://mlsanity.com/paper/2507.19290/) (2025)

## Abstract (arXiv)

We consider the problem of rank-1 low-rank approximation (LRA) in the matrix-vector product model under various Schatten norms:  min|u|2=1 |A (I - u u^top)|Sp ,  where |M|Sp denotes the ℓp norm of the singular values of M. Given varepsilon>0, our goal is to output a unit vector v such that  |A(I - vv^top)|Sp ≤ (1+varepsilon) min|u|2=1|A(I - u u^top)|Sp.  Our main result shows that Krylov methods (nearly) achieve the information-theoretically optimal number of matrix-vector products for Spectral (p=∞), Frobenius (p=2) and Nuclear (p=1) LRA. In particular, for Spectral LRA, we show that any algorithm requires Omegaleft(log(n)/varepsilon1/2right) matrix-vector products, exactly matching the upper bound obtained by Krylov methods [MM15, BCW22]. Our lower bound addresses Open Question 1 in [Woo14], providing evidence for the lack of progress on algorithms for Spectral LRA and resolves Open Question 1.2 in [BCW22]. Next, we show that for any fixed constant p, i.e. 1≤ p =O(1), there is an upper bound of Oleft(log(1/varepsilon)/varepsilon1/3right) matrix-vector products, implying that the complexity does not grow as a function of input size. This improves the Oleft(log(n/varepsilon)/varepsilon1/3right) bound recently obtained in [BCW22], and matches their Omegaleft(1/varepsilon1/3right) lower bound, to a log(1/varepsilon) factor.