Unbiased Low-Rank Approximation for Repeated Matrix-Vector Multiplication: Stability and Optimal Sampling
Abstract
Replacing the matrix in an iteration with random low-rank matrices can reduce the cost of matrix-vector multiplication. However, even if the sampled matrices equal the original matrix in expectation, the expected squared norm of the random iterates may grow while the original iteration converges. Under a fixed rank bound, we study how to choose the distribution of these random matrices to minimize this growth when sampling independently at each step. We derive an exact formula for the optimal asymptotic growth factor and use it to determine when the expected squared norm can converge to zero. We then characterize precisely when a fixed sampling distribution achieves this optimal factor and construct finite-support optimal distributions in every attainable case. These results determine the minimum rank required for stability and provide optimal sampling designs under the prescribed rank constraint.
Related
- Approximate Matrix Multiplication through Joint Leverage Score Sampling
- SAUSS: Stochastic Approximation with Unbiased Simulated Scores for Limited Dependent Variable Models
- A note on the stability of Arens products under small perturbations of multiplication
- Unbiased Gradients, Moving Stability Boundaries: Exact Mini-Batch Geometry in Linear Self-Attention
- Uniform Chebyshev asymptotics for repeated-pole rational approximation of the exponential
BibTeX
@misc{liu2026unbiased,
title = {{Unbiased Low-Rank Approximation for Repeated Matrix-Vector Multiplication: Stability and Optimal Sampling}},
author = {Kang Liu},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00787},
eprint = {2611.00787},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00787},
}
RIS
TY - UNPB
TI - Unbiased Low-Rank Approximation for Repeated Matrix-Vector Multiplication: Stability and Optimal Sampling
AU - Kang Liu
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00787
UR - https://arxiv.org/abs/2611.00787
AB - Replacing the matrix in an iteration with random low-rank matrices can reduce the cost of matrix-vector multiplication. However, even if the sampled matrices equal the original matrix in expectation, the expected squared norm of the random iterates may grow while the original iteration converges. Under a fixed rank bound, we study how to choose the distribution of these random matrices to minimize this growth when sampling independently at each step. We derive an exact formula for the optimal asymptotic growth factor and use it to determine when the expected squared norm can converge to zero. We then characterize precisely when a fixed sampling distribution achieves this optimal factor and construct finite-support optimal distributions in every attainable case. These results determine the minimum rank required for stability and provide optimal sampling designs under the prescribed rank constraint.
ER -