Matrix-Vector Complexity of Low-Rank Approximation
Abstract
We establish matching polynomial query bounds for low-rank approximation from exact matrix--vector products. Given an unknown matrix A∈ℝm× n, at each step a randomized algorithm chooses either v∈ℝn and receives Av, or u∈ℝm and receives A⊤ u. The choice may depend measurably on all previous queries and replies and on the algorithm's private randomness; each vector product costs one query. The output is a rank-k right projector with Schatten-p residual at most 1+ε times optimal. Write N=min{m,n} and let Qp* denote the worst-case query budget for success probability 2/3 on every input. For every 1≤ k<N and sufficiently small ε, our lower bounds, combined with existing Krylov upper bounds, give Qp*=Θ̃ (min{N,kmin{p1/6ε−1/3,ε−1/2}}) (2≤ p<∞), Q∞*=Θ̃ (min{N,kε−1/2}). These bounds have universal constants and allow p to vary with the problem parameters, identifying the transition at pεasymp1. A complementary result for each fixed 1≤ p<2 gives Θ̃p(min{N,kε−1/3}), with constants and an accuracy threshold that may depend on p. Together, the results recover this fixed-norm rate for every fixed finite p, supplying the multiplicative rank dependence missing from previous lower bounds. Tildes suppress logarithmic factors. The proof extends adaptive Wishart deferred decisions to a rectangular factor with a k-dimensional nullspace. Posterior overlap gives a short fixed-norm argument, while persistence of small compression eigenvalues controls growing p and the spectral endpoint. Exact range recovery handles target costs of order k; the Wishart family covers the remaining regimes.
Related
- Unbiased Low-Rank Approximation for Repeated Matrix-Vector Multiplication: Stability and Optimal Sampling
- Generic factorizations and alternating direction method for fixed-rank approximation of matrix polynomials
- Rank-Optimal Sample Complexity of Riemannian Gauss-Newton for Low-Rank Matrix Recovery
- Complexity Rank of AT Algebras of Real Rank Zero
- Global L2 Approximation in the Bergman Spaces with Values in Holomorphic Vector Bundles
BibTeX
@misc{zhang2026matrixvector,
title = {{Matrix-Vector Complexity of Low-Rank Approximation}},
author = {Haihan Zhang and Wendao Wu and Chenheng Zhang and Yanyi Li and Chunyuan Zheng and Cong Fang and Haoxuan Li and Zhouchen Lin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.35840},
eprint = {2609.35840},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35840},
}
RIS
TY - UNPB
TI - Matrix-Vector Complexity of Low-Rank Approximation
AU - Haihan Zhang
AU - Wendao Wu
AU - Chenheng Zhang
AU - Yanyi Li
AU - Chunyuan Zheng
AU - Cong Fang
AU - Haoxuan Li
AU - Zhouchen Lin
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2609.35840
UR - https://arxiv.org/abs/2609.35840
AB - We establish matching polynomial query bounds for low-rank approximation from exact matrix--vector products. Given an unknown matrix A∈ℝ^m× n, at each step a randomized algorithm chooses either v∈ℝ^n and receives Av, or u∈ℝ^m and receives A^⊤ u. The choice may depend measurably on all previous queries and replies and on the algorithm's private randomness; each vector product costs one query. The output is a rank-k right projector with Schatten-p residual at most 1+ε times optimal. Write N=min{m,n} and let Q_p^* denote the worst-case query budget for success probability 2/3 on every input. For every 1≤ k<N and sufficiently small ε, our lower bounds, combined with existing Krylov upper bounds, give Q_p^*=Θ̃ (min{N,kmin{p^1/6ε^−1/3,ε^−1/2}}) (2≤ p<∞), Q_∞^*=Θ̃ (min{N,kε^−1/2}). These bounds have universal constants and allow p to vary with the problem parameters, identifying the transition at pεasymp1. A complementary result for each fixed 1≤ p<2 gives Θ̃_p(min{N,kε^−1/3}), with constants and an accuracy threshold that may depend on p. Together, the results recover this fixed-norm rate for every fixed finite p, supplying the multiplicative rank dependence missing from previous lower bounds. Tildes suppress logarithmic factors. The proof extends adaptive Wishart deferred decisions to a rectangular factor with a k-dimensional nullspace. Posterior overlap gives a short fixed-norm argument, while persistence of small compression eigenvalues controls growing p and the spectral endpoint. Exact range recovery handles target costs of order k; the Wishart family covers the remaining regimes.
ER -