Low-Rank Approximation by Randomly Pivoted LU
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918314428596224 |
|---|---|
| author | Gilles, Marc Aurèle Wilber, Heather |
| author_facet | Gilles, Marc Aurèle Wilber, Heather |
| contents | The low-rank approximation properties of Randomly Pivoted LU (RPLU), a variant of Gaussian elimination where pivots are sampled proportional to the squared entries of the Schur complement, are analyzed. It is shown that the RPLU iterates converge geometrically in expectation for matrices with rapidly decaying singular values. RPLU outperforms existing low-rank approximation algorithms in two settings: first, when memory is limited, RPLU can be implemented with $\mathcal{O}(k^2 + m + n)$ storage and $\mathcal{O}( k(m + n)+ k\mathcal{M}(\mat{A}) + k^3)$ operations, where $\mathcal{M}(\mat{A})$ is the cost of a matvec with $\mat{A}\in\mathbb{C}^{n\times m}$ or its adjoint, for a rank-$k$ approximation. Second, when the matrix and its Schur complements share exploitable structure, such as for Cauchy-like matrices. The efficacy of RPLU is illustrated with several examples, including applications in rational approximation and solving large linear systems on GPUs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_22344 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Low-Rank Approximation by Randomly Pivoted LU Gilles, Marc Aurèle Wilber, Heather Numerical Analysis The low-rank approximation properties of Randomly Pivoted LU (RPLU), a variant of Gaussian elimination where pivots are sampled proportional to the squared entries of the Schur complement, are analyzed. It is shown that the RPLU iterates converge geometrically in expectation for matrices with rapidly decaying singular values. RPLU outperforms existing low-rank approximation algorithms in two settings: first, when memory is limited, RPLU can be implemented with $\mathcal{O}(k^2 + m + n)$ storage and $\mathcal{O}( k(m + n)+ k\mathcal{M}(\mat{A}) + k^3)$ operations, where $\mathcal{M}(\mat{A})$ is the cost of a matvec with $\mat{A}\in\mathbb{C}^{n\times m}$ or its adjoint, for a rank-$k$ approximation. Second, when the matrix and its Schur complements share exploitable structure, such as for Cauchy-like matrices. The efficacy of RPLU is illustrated with several examples, including applications in rational approximation and solving large linear systems on GPUs. |
| title | Low-Rank Approximation by Randomly Pivoted LU |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/2601.22344 |