# Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 84 references that are in the map.
- First posted on arXiv 10 Feb 2022.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [An Investigation into Neural Net Optimization via Hessian Eigenvalue Density](https://mlsanity.com/paper/1901.10159/) (2019)
- [PyHessian: Neural Networks Through the Lens of the Hessian](https://mlsanity.com/paper/1912.07145/) (2019)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [The Hessian Penalty: A Weak Prior for Unsupervised Disentanglement](https://mlsanity.com/paper/2008.10599/) (2020)
- [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)
- [Fast Algorithms for Robust PCA via Gradient Descent](https://mlsanity.com/paper/1605.07784/) (2016)
- [On Tensor Completion via Nuclear Norm Minimization](https://mlsanity.com/paper/1405.1773/) (2014)
- [Optimal Principal Component Analysis in Distributed and Streaming Models](https://mlsanity.com/paper/1504.06729/) (2015)
- [Sharper Bounds for Regularized Data Fitting](https://mlsanity.com/paper/1611.03225/) (2016)
- [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)
- [Average Case Column Subset Selection for Entrywise ℓ1-Norm Loss](https://mlsanity.com/paper/2004.07986/) (2020)
- [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)
- [Regularized Weighted Low Rank Approximation](https://mlsanity.com/paper/1911.06958/) (2019)
- [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)
- [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)

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

- [Query lower bounds for log-concave sampling](https://mlsanity.com/paper/2304.02599/) (2023)
- [Krylov Methods are (nearly) Optimal for Low-Rank Approximation](https://mlsanity.com/paper/2304.03191/) (2023)
- [Towards Efficient and Accurate Approximation: Tensor Decomposition Based on Randomized Block Krylov Iteration](https://mlsanity.com/paper/2211.14828/) (2022)
- [k-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation](https://mlsanity.com/paper/2507.14631/) (2025)
- [Query Efficient Structured Matrix Learning](https://mlsanity.com/paper/2507.19290/) (2025)
- [Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation](https://mlsanity.com/paper/2605.09755/) (2026)
- [Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch](https://mlsanity.com/paper/2609.18577/) (2026)

## Abstract (arXiv)

We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-p norm. Here, given access to a matrix A through matrix-vector products, an accuracy parameter ε, and a target rank k, the goal is to find a rank-k matrix Z with orthonormal columns such that | A(I -ZZ^top)|Sp ≤ (1+ε)minU^top U = Ik |A(I - U U^top)|Sp, where |M|Sp denotes the ℓp norm of the the singular values of M. For the special cases of p=2 (Frobenius norm) and p = ∞ (Spectral norm), Musco and Musco (NeurIPS 2015) obtained an algorithm based on Krylov methods that uses tildeO(k/√ε) matrix-vector products, improving on the na"ive tildeO(k/ε) dependence obtainable by the power method, where tildeO suppresses poly(log(dk/ε)) factors. Our main result is an algorithm that uses only tildeO(kp1/6/ε1/3) matrix-vector products, and works for all p ≥ 1. For p = 2 our bound improves the previous tildeO(k/ε1/2) bound to tildeO(k/ε1/3). Since the Schatten-p and Schatten-∞ norms are the same up to a (1+ ε)-factor when p ≥ (log d)/ε, our bound recovers the result of Musco and Musco for p = ∞. Further, we prove a matrix-vector query lower bound of Omega(1/ε1/3) for any fixed constant p ≥ 1, showing that surprisingly tildeTheta(1/ε1/3) is the optimal complexity for constant~k. To obtain our results, we introduce several new techniques, including optimizing over multiple Krylov subspaces simultaneously, and pinching inequalities for partitioned operators. Our lower bound for p ∈ [1,2] uses the Araki-Lieb-Thirring trace inequality, whereas for p>2, we appeal to a norm-compression inequality for aligned partitioned operators.