PreprintarXiv licencearXiv
Convergence rates of randomly pivoted methods for low-rank approximation
Abstract
Randomly pivoted Cholesky, QR, and LU are iterative algorithms that form structured low-rank approximations of a matrix by sampling columns, or rows and columns, from the residual. We give convergence rates for these methods that depend on the decay of the singular values of the original matrix. The rates hold, up to a constant, when pivots are drawn from an approximation to the exact distribution. This extra degree of freedom can be used to trade exact sampling for cheaper approximations. We use it to establish rates for variants of randomly pivoted LU, including one that picks pivots using a sketch of the input matrix.
Related
- Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift
- Weak Convergence Rates for Partial-Sum Processes of Nonlinear Stochastic Approximation
- Extension on the convergence rates of moment-SOS hierarchies via approximation of truncated moment sequences
- Finite-Time Concentration and Convergence Rates for Projected Two-Time-Scale Stochastic Approximation with Markov Noise
- Strong convergence rates of stochastic theta Milstein methods for index-1 stochastic differential algebraic equations under non-globally Lipschitz conditions
BibTeX
@misc{divan2026convergence,
title = {{Convergence rates of randomly pivoted methods for low-rank approximation}},
author = {Ryan Divan and Marc Aurèle Gilles},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.06287},
eprint = {2609.06287},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.06287},
}
RIS
TY - UNPB
TI - Convergence rates of randomly pivoted methods for low-rank approximation
AU - Ryan Divan
AU - Marc Aurèle Gilles
PY - 2026
DA - 2026/09/05
PB - arXiv
DO - 10.48550/arxiv.2609.06287
UR - https://arxiv.org/abs/2609.06287
AB - Randomly pivoted Cholesky, QR, and LU are iterative algorithms that form structured low-rank approximations of a matrix by sampling columns, or rows and columns, from the residual. We give convergence rates for these methods that depend on the decay of the singular values of the original matrix. The rates hold, up to a constant, when pivots are drawn from an approximation to the exact distribution. This extra degree of freedom can be used to trade exact sampling for cheaper approximations. We use it to establish rates for variants of randomly pivoted LU, including one that picks pivots using a sketch of the input matrix.
ER -