stat.MLOct 31, 2026

Unbiased Low-Rank Approximation for Repeated Matrix-Vector Multiplication: Stability and Optimal Sampling

Authors: Kang Liu

Organizations: School of Future Technology, Xi’an Jiaotong University, Xi’an, China.

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.

Figures & tables

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Fast Length-Squared Sampling for Positive-Semidefinite Matrices

    Aug 12, 2026Rajarshi Bhattacharjee, Ethan N. Epperly, Cameron Musco +1Importance SamplingRejection Sampling

  2. Information Limits of Low-Rank Approximation Certification

    Oct 2, 2026Kang Liu, Bohao QuLow-Rank ApproximationInformation-Theoretic Lower Bounds

  3. Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time

    Feb 21, 2023Yuzhou Gu, Zhao Song, Junze Yin +1alternating minimizationMatrix Completion