Low-Rank Approximation by Randomly Pivoted LU
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})$…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.22344
curl -X POST /api/v1/records/arxiv/2601.22344/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.22344/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'