Low-Rank Approximation by Randomly Pivoted LU
Marc Aurèle Gilles, Heather Wilber · 2026
Read Low-Rank Approximation by Randomly Pivoted LU by Marc Aurèle Gilles, Heather Wilber (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-22344.txt.
Introduction
Marc Aurèle Gilles and Heather Wilber study a fast way to shrink a big matrix while keeping its core shape. Their 2026 preprint looks at randomly pivoted LU, a form of Gaussian elimination that picks pivot points by chance, weighted by size. Low-rank shortcuts like this power fast math across science.
They show the steps close in on the true shape at a steady rate, on average. The claim holds for matrices whose key values fade fast. A sound proof lets users trust the shortcut in real codes. It can cut the cost of huge data tasks.
Catalog record
| CREATOR | Marc Aurèle Gilles, Heather Wilber |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 106 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-22344
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Low-Rank Approximation by Randomly Pivoted LU Marc Aurèle Gilles, Heather Wilber Abstract 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 𝒪 ( k 2 + m + n ) \mathcal{O}(k^{2}+m+n) storage and 𝒪 ( k ( m + n ) + k ℳ ( 𝐀 ) + k 3 ) \mathcal{O}(k(m+n)+k\mathcal{M}(\mathbf{A})+k^{3}) operations, where ℳ ( 𝐀 ) \mathcal{M}(\mathbf{A}) is the cost of a matvec with 𝐀 ∈ ℂ n × m \mathbf{A}\in\mathbb{C}^{n\times m} or its adjoint, for a rank- k 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. 1 Introduction Gaussian elimination (GE) with pivoting is the standard algorithm for solving systems of linear equations. Given \mathbf{A}\in\mathbb{C}^{n\times n} , it constructs a pivoted LU factorization \mathbf{P}\mathbf{A}\mathbf{Q}=\mathbf{{L}}\mathbf{{U}} , where \mathbf{{L}} and \mathbf{{U}} are lower and upper triangular matrices respectively, and \mathbf{P} and \mathbf{Q} are permutation matrices. The numerical stability of the computation depends on the strategy applied to sequentially choose the permutation matrices. These are called pivoting strategies . The strategy used most widely in practice is partial pivoting, which selects \mathbf{P} relatively cheaply using only the leading entries of rows of the residual matrix, and sets \mathbf{Q}=\mathbf{I} . However, complete pivoting, which permutes both rows and columns at each step, is also a popular choice and has stronger theoretical stability guarantees [ 65 , 62 ] . By stopping GE early, complete pivoting can also be used to produce structured low-rank approximations to \mathbf{A} . We set \mathbf{\hat{A}}\approx\mathbf{\hat{L}}\mathbf{\hat{U}} , where \mathbf{\hat{L}}=\mathbf{P}^{T}\mathbf{L}_{:,1:k} , \mathbf{\hat{U}}=\mathbf{U}_{1:k,:}\mathbf{Q}^{T} , and \mathbf{L}_{:,1:k} and \mathbf{U}_{1:k,:} are the first k columns and rows of \mathbf{L} and \mathbf{U} , respectively. Triangularity of the LU factors is no longer important in this setting. This idea is known in different contexts under many different names, including adaptive cross approximation [ 66 ] , GE with complete pivoting [ 60 ] , the method of Geddes–Newton series expansions [ 14 ] , and incomplete LU factorization [ 12 ] . In the special case where \mathbf{A} is square and positive semidefinite (PSD), related algorithms making use of Cholesky decompositions are known as incomplete or partial Cholesky factorizations [ 16 ] . Figure 1: Performance of RPLU and three greedy schemes CPLU, C2PLU and IterativeCUR [ 53 ] ( b=5 ) on a Cauchy matrix A_{ij}=1/(x_{i}-y_{j}) for points \{x_{i}\} (blue) and \{y_{j}\} (green) forming a smiley (top) and two spirals (bottom). Left: pivots selected by CPLU. Middle: pivots from one run of RPLU. Right: approximation error vs. rank k , with mean over 30 runs and min/max as a shaded region for RPLU and IterativeCUR. In the spiral example, greedy schemes select only “outlier” points, whereas RPLU also samples from the cluster, yielding lower error. Similar behavior is observed for PSD matrices [ 16 ] . A partial LU factorization of \mathbf{A}\in\mathbb{C}^{n\times m} produces the following sequence of matrices: \displaystyle\mathbf{A}^{(0)} \displaystyle=\mathbf{A},\quad\mathbf{A}^{(k)}=\mathbf{A}^{(k-1)}-\frac{1}{\mathbf{A}^{(k-1)}_{i_{k},j_{k}}}\mathbf{A}^{(k-1)}_{:,j_{k}}\mathbf{A}^{(k-1)}_{i_{k},:} (1) \displaystyle\mathbf{\hat{A}}^{(0)} \displaystyle=\mathbf{0},\quad\mathbf{\hat{A}}^{(k)}=\mathbf{\hat{A}}^{(k-1)}+\frac{1}{\mathbf{A}^{(k-1)}_{i_{k},j_{k}}}\mathbf{A}^{(k-1)}_{:,j_{k}}\mathbf{A}^{(k-1)}_{i_{k},:} (2) where \mathbf{A}^{(k)} is the residual matrix after k steps of GE and \mathbf{\hat{A}}^{(k)} is a rank- k approximation of \mathbf{A} . Here \mathbf{A}^{(k)}_{i,:} and \mathbf{A}^{(k)}_{:,j} denote the i -th row and j -th column of \mathbf{A}^{(k)} . We refer to the pair (i_{k},j_{k}) as the pivot chosen at step k . Complete pivoting selects (i_{k},j_{k})=\argmax_{i,j}|\mathbf{A}^{(k-1)}_{i,j}| , the largest absolute entry of the residual matrix. We call this “completely pivoted LU” (CPLU). In [ 16 ] , the authors showed that for PSD matrices, injecting randomness into pivot selection can substantially improve approximation quality over greedy schemes in some settings. In this paper we consider an analogous algorithm for the nonsymmetric setting. We apply a randomized version of complete pivoting, where the pivot (i_{k},j_{k}) at step k is sampled according to the probability distribution: \mathbb{P}(i,j\mid\mathbf{A}^{(k-1)})\;=\;\frac{|\mathbf{A}^{(k-1)}_{i,j}|^{2}}{\|\mathbf{A}^{(k-1)}\|_{F}^{2}}. (3) We call the resulting method “Randomly Pivoted LU” (RPLU), analogous to the Randomly Pivoted Cholesky (RPCholesky) method in [ 16 ] . A basic implementation is shown in Algorithm 1 . Algorithm 1 Randomly pivoted LU (Naïve implementation) Input: Matrix \mathbf{A}\in\mathbb{C}^{n\times m} ; desired rank r . Output: Matrices \mathbf{L}\in\mathbb{C}^{n\times r} and \mathbf{U}\in\mathbb{C}^{r\times m} defining the approximation \hat{\mathbf{A}}=\mathbf{L}\mathbf{U} Initialize \mathbf{L}\leftarrow\mathbf{0}_{n\times r} , \mathbf{U}\leftarrow\mathbf{0}_{r\times m} , \mathbf{A}^{(0)}\leftarrow\mathbf{A} for k=1 to r do Sample pivot \bigl(i_{k},j_{k}\bigr)\sim\bigl|\mathbf{A}^{(k-1)}\bigr|^{2}\big/\|\mathbf{A}^{(k-1)}\|_{F}^{2} \triangleright Sample pivot \mathbf{L}(:,k)\leftarrow\mathbf{A}^{(k-1)}(:,j_{k})\big/\mathbf{A}^{(k-1)}(i_{k},j_{k}) \mathbf{U}(k,:)\leftarrow\mathbf{A}^{(k-1)}(i_{k},:) \mathbf{A}^{(k)}\leftarrow\mathbf{A}^{(k-1)}-\mathbf{L}(:,k)\,\mathbf{U}(k,:) \triangleright Update residual end for Our main theoretical result (see theorem 3 ) shows that RPLU will return a good rank- k approximation to \mathbf{A} if its singular values decay at the rate \mathcal{O}(\rho^{k}) with \rho<1/2 . This is an improvement on deterministic complete pivoting, which requires \rho<1/4 in a worst-case scenario [ 18 ] . As shown in Figure 1 , there are settings where RPLU decisively outperforms CPLU and other greedy pivoting methods. Our second contribution addresses efficient implementation. Unlike the PSD case, where one only needs to consider diagonal entries for pivoting, iterations of randomly (or completely) pivoted LU are expensive: each pivot selection and residual update touches the full matrix, costing \mathcal{O}(nm) operations. However, we show that RPLU can be implemented much more efficiently for many structured matrix classes. For Cauchy-like matrices, we employ fast Schur complement updates via displacement structure [ 9 , 32 , 41 , 52 ] , along with Barnes-Hut-style row norm estimates [ 2 ] . For matrices with fast matvecs (e.g., Toeplitz, sparse, or kernel matrices), we introduce a memory-efficient variant achieving \mathcal{O}(k(n+m)+k^{3}+k\mathcal{M}(\mathbf{A})+k\mathcal{M}(\mathbf{A}^{T})) operations and \mathcal{O}(k^{2}+n+m) storage, where \mathcal{M}(\mathbf{A}) is the matvec cost. This variant is especially effective on memory-constrained hardware such as GPUs: in Section 4 , we construct rank- 1000 approximations to matrices with 30 million rows and columns in minutes, which would require half a terabyte for dense storage. The remainder of this paper is organized as follows. Section 2 reviews background on low-rank decompositions. Section 3 presents convergence results for RPLU. Section 4 describes an efficient implementation for large structured matrices with numerical experiments. Section 5 presents implementation and numerical results for Cauchy-like matrices. 2 Background 2.1 Notation Let \mathbf{A}\in\mathbb{C}^{n\times m} with entries a_{i,j} for 1\leq i\leq n and 1\leq j\leq m . Without loss of generality, we assume n\leq m . We use MATLAB-style notation where \mathbf{A}_{:,j} denotes the j -th column, \mathbf{A}_{i,:} denotes the i -th row, and \mathbf{A}_{\mathcal{I},\mathcal{J}} denotes the submatrix with rows \mathcal{I}\subset\{1,\ldots,n\} and columns \mathcal{J}\subset\{1,\ldots,m\} . Let the singular values of \mathbf{A} be given by \sigma_{1}\geq\cdots\geq\sigma_{n}\geq 0 . We define the following norms: \displaystyle\|\mathbf{A}\|_{F}=\sqrt{\sum_{i=1}^{n}\sigma_{i}^{2}},\qquad\|\mathbf{A}\|_{\star}=\sum_{i=1}^{n}\sigma_{i},\qquad\|\mathbf{A}\|_{2}=\sigma_{1}. We denote a PSD matrix \mathbf{A}\in\mathbb{C}^{n\times n} by \mathbf{A}\succeq 0 , and use \preceq as the partial order on \mathbb{C}^{n\times n} defined by \mathbf{A}\preceq\mathbf{B} if \mathbf{A}-\mathbf{B}\succeq 0 . We denote the trace of a matrix \mathbf{A} by \tr(\mathbf{A})=\sum_{i=1}^{n}a_{ii} , and recall that if \mathbf{A}\succeq 0 , then \tr(\mathbf{A})=\|\mathbf{A}\|_{\star} . 2.2 Optimal low-rank approximations The singular value decomposition of \mathbf{A} is given by \mathbf{A}=\mathbf{U}\mathbf{\Sigma}\mathbf{V}^{*} where \mathbf{U}\in\mathbb{C}^{n\times