mlsanityData to 7 Oct 2026

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

arXiv 2304.03191 ↗First posted 6 Apr 2023cs.DS cs.LG cs.NAcited by 2

Not on the map. Why?

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.

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

Builds on

34 of 65 references.

References · 34

  1. 2021Convex optimizationcited by 2,479
  2. 2014Sketching as a Tool for Numerical Linear Algebracited by 285
  3. 2018A quantum-inspired classical algorithm for recommendation systemscited by 70
  4. 2016Quantum Recommendation Systemscited by 69
  5. 2015Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decompositioncited by 63
  6. 2020Hutch++: Optimal Stochastic Trace Estimationcited by 62
  7. 2017Sublinear Time Low-Rank Approximation of Positive Semidefinite Matricescited by 18
  8. 2018Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimensioncited by 18
  9. 2013Toward a unified theory of sparse dimensionality reduction in Euclidean spacecited by 15
  10. 2019Sample-Optimal Low-Rank Approximation of Distance Matricescited by 15
  11. 2023Query lower bounds for log-concave samplingcited by 12
  12. 2018Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Lawcited by 11
22 more
  1. 2018Sublinear Time Low-Rank Approximation of Distance Matricescited by 11
  2. 2018Quantum-inspired sublinear classical algorithms for solving low-rank linear systemscited by 11
  3. 2021Learning a Latent Simplex in Input-Sparsity Timecited by 11
  4. 2019The gradient complexity of linear regressioncited by 9
  5. 2019Querying a Matrix through Matrix-Vector Productscited by 8
  6. 2020Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problemscited by 8
  7. 2020Quantum-Inspired Algorithms from Randomized Numerical Linear Algebracited by 8
  8. 2020Input-Sparsity Low Rank Approximation in Schatten Normcited by 7
  9. 2022Low-Rank Approximation with 1/ε1/3 Matrix-Vector Productscited by 7
  10. 2019Robust and Sample Optimal Algorithms for PSD Low-Rank Approximationcited by 6
  11. 2014Optimal query complexity for estimating the trace of a matrixcited by 5
  12. 2019Sublinear Time Numerical Linear Algebra for Structured Matricescited by 5
  13. 2021Average-Case Communication Complexity of Statistical Problemscited by 5
  14. 2022A Tight Analysis of Hutchinson's Diagonal Estimatorcited by 5
  15. 2023An Improved Classical Singular Value Transformation for Quantum Machine Learningcited by 5
  16. 2022Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddingscited by 4
  17. 2016On Approximating Functions of the Singular Values in a Streamcited by 3
  18. 2017Embeddings of Schatten Norms with Applications to Data Streamscited by 2
  19. 2019Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimensioncited by 2
  20. 2021Improved Algorithms for Low Rank Approximation from Sparsitycited by 2
  21. 2020Reduced-Rank Regression with Operator Norm Errorcited by 1
  22. 2022Testing Positive Semidefiniteness Using Linear Measurementscited by 1

Built on by

Cited by year

Citing papers per year: 2024: 1; 2025: 1.

2 papers.

  1. 2024Sharper Bounds for Chebyshev Moment Matching, with Applicationscited by 3
  2. 2025Query Efficient Structured Matrix Learningcited by 0