PaperlayerView exact revision on arXiv

Source-linked AI summary

Convergence rates of randomly pivoted methods for low-rank approximation

Ryan Divan, Marc Aurèle Gilles

arXiv:2609.06287v1math.NAcs.NA

TL;DR

Randomly pivoted Cholesky, QR, and LU need convergence guarantees that reflect the input spectrum and allow cheaper-than-exact sampling. The paper derives spectral-decay-dependent rates and extends the analysis to approximate sampling and cheaper RPLU variants. The guarantees retain their form up to a constant factor under approximate sampling, while the analysis leaves open whether a geometric-mean loss can be removed.

  • Problem

    The paper addresses convergence guarantees for randomized pivoting that depend on spectral decay and cover sampling from approximate pivot distributions.

    Source: §1 · p. 1

  • Method

    The analysis extends convergence-rate techniques for greedy pivoting to randomized Cholesky, QR, and LU, then applies an approximate-sampling framework to cheaper RPLU variants.

    Source: §1 · p. 1, §4 · p. 10, §6 · p. 16

  • Results

    The bounds depend on spectral decay and change only by a constant factor under approximate sampling, supporting analysis of cheaper RPLU schemes.

    Source: §1 · p. 1, §6 · p. 16

  • Takeaways & Limitations

    Approximate pivot distributions allow cheaper RPLU schemes, including a sketch-based variant, within the paper’s convergence analysis.

    Source: §4 · p. 10, §5.1 · p. 11, §5.2 · pp. 14–15

    The analysis leaves open whether the geometric-mean loss can be removed to recover the O(ρ^k) rate observed in practice.

    Source: §6 · p. 16

Abstract

from arXiv · show

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.

1 Introduction

Randomized pivoting samples pivots from residual-based quantities, offering potential robustness to outliers and lower cost than exhaustive greedy searches. This work extends convergence analysis to randomized Cholesky, QR, and LU, including approximate sampling.

Motivation

  • Randomized pivoting samples residual-based quantities instead of exhaustively choosing the largest pivot, and can be more robust to outliers and cheaper when exhaustive search is impractical.Greedy Cholesky and QR choose the largest diagonal entry and column norm, while complete-pivoting LU chooses the largest entry.Source: §1 · p. 1

Contributions

  • The analysis extends convergence rates for greedy pivoting to randomized methods and gives stronger bounds for RPLU variants than prior analysis, with a modest improvement for RPCholesky and RPQR over concurrent results.The rates depend on spectral decay; approximate sampling changes them only by a constant factor, enabling analysis of cheaper pivoting schemes.Source: §1 · p. 1

Convergence rates

  • For geometric singular-value decay, the expected error is O(kρ^k/2) for RPCholesky and RPLU; the RPQR rate is not fully specified in the supplied passage.The passage begins the RPQR rate but does not provide its expression.Source: §1 · p. 1

Approximate sampling

  • The paper applies approximate sampling analysis to cheaper RPLU schemes based on inexpensive estimates of residual row norms.The introduction also notes that the paper analyzes a sketch-based pivoting variant.Source: §1 · p. 1

2 Background

The background establishes notation, describes pivoted Cholesky, QR, and LU alongside approximate sampling, and introduces determinant identities used in the analysis.

2.1 Notation

  • For a matrix A, A_:,j and A_i,: denote its jth column and ith row, and A_I,J denotes the submatrix on indexed rows and columns.The text uses MATLAB-style indexing and defines [n] as {1, …, n}.Source: §2.1 · p. 2

Pivoted Cholesky

  • Pivoted Cholesky iteratively builds low-rank approximants and residuals; greedy pivoting chooses the largest diagonal entry, while RPCholesky samples a pivot index.For a PSD input, the residual and approximants remain PSD, and each nonzero-residual step raises approximation rank by one.Source: Pivoted Cholesky · pp. 2–3

Pivoted QR

  • Pivoted QR builds approximants by selecting column pivots, and its randomized variant samples pivots from a distribution.Under the Gram correspondence, RPQR and RPCholesky have matching sampling distributions, so RPCholesky error bounds transfer to RPQR.Source: Pivoted QR · p. 3

Pivoted LU

  • Pivoted LU applies to rectangular matrices and updates the residual by subtracting a rank-one outer product; randomized LU samples a pivot location.Restricting LU pivots to the diagonal for a PSD input reduces the iteration to Cholesky.Source: Pivoted LU · p. 4

Approximate sampling

  • Approximate sampling permits pivots to be drawn from distributions approximating the algorithms’ exact pivot distributions; exact sampling corresponds to γ = 1.The sampling distribution is specified conditionally on the current residual.Source: Approximate sampling · p. 4

2.3 Determinant identities and elementary symmetric polynomials

  • The analysis uses a pivot-product identity linking successive LU pivots to a minor of the original matrix and a principal-minor identity linking principal minors to elementary symmetric polynomials.These determinant identities are also used in work on volume sampling, DPP-based low-rank approximation, and concurrent RPCholesky bounds.Source: §2.3 · p. 5

3 Convergence rates for RPCholesky and RPQR

The section derives RPCholesky convergence bounds from determinant identities and spectral-decay estimates, then transfers corresponding rates to RPQR through the Gram correspondence. Comparisons show the relative bounds depend on the decay regime.

RPCholesky bounds

  • The RPCholesky analysis uses the pivot-product identity and estimates of elementary symmetric polynomials to obtain rates under eigenvalue decay.The proof bounds the final residual trace using the geometric mean of the first k residual traces.Source: §3 · pp. 6–7
  • The section states convergence rates for approximate RPCholesky when λ_j(A) ≤ Cj^-α for α > 1, but the supplied corollary passage omits the rate expression.The corresponding bound is presented as Corollary 3.3.Source: §3 · p. 7

Convergence-rate comparison

  • For very rapid spectral decay, the doubling bound can be strongest; with geometric decay, Corollary 3.3 gives O(kρ^k/2) versus roughly O(ρ^k/6) at best for the oversampled bound once r ≥ 10.The oversampled bound agrees with the paper’s bound up to logarithmic factors under algebraic decay, and is more general because it requires no spectral-decay assumption.Source: §3 · pp. 7–8, Figure 1 · p. 8

RPQR bounds

  • The Gram correspondence transfers RPCholesky bounds to RPQR, whose stated algebraic-decay condition is σ_j(B) ≤ Cj^-α for α > 1/2.The passage introducing Corollary 3.4 gives the condition but not its rate expression.Source: §3 · p. 8

4 Convergence rates for Randomly pivoted LU

The RPLU analysis adapts the pivot-product argument to general matrices, where residual norms need not decrease at every iteration. It provides spectral-decay rates and motivates cheaper approximate sampling schemes.

RPLU analysis

  • Because LU residual norms need not decrease at every iteration, the pivot-product argument controls the smallest residual among the first k iterates rather than the final residual.The theorem concerns the expected residual norm.Source: §4 · pp. 8–9

Convergence rates

  • Approximate RPLU rates incur an additional factor of k + 1 relative to RPQR bounds because row and column pivots have (k!)^2 possible orderings rather than RPCholesky’s single k! factor.The supplied Corollary 4.2 states the algebraic condition σ_j(A) ≤ Cj^-α for α > 1, but omits the rate expression.Source: §4 · p. 10

Approximate sampling

  • Exact RPLU sampling requires all mn residual entries and may cost O(mn) per iteration, while approximate sampling changes bounds only by a factor γ^-1.The framework motivates cheaper schemes, including one tailored to Cauchy-like matrices and another based on random sketching.Source: §4 · p. 10

5 Efficient approximate RPLU schemes

The section develops cheaper approximate RPLU schemes by approximating the row-sampling distribution while retaining exact sampling within a selected row. It presents generator-based and sketch-based variants, with convergence guarantees tied to approximate RPLU.

5 Efficient approximate RPLU schemes

  • Once residual row norms are known, exact RPLU pivots can be sampled in two stages; the proposed schemes approximate row weights while retaining exact sampling within a selected row.This design approximates the row distribution, then samples a column exactly within the selected row.Source: §5 · p. 10

5.1 Random Generator Pivoting

  • RGP samples pivots using generator-row weights instead of residual row norms, avoiding spatial trees and geometric precomputation.Each iteration costs O((m + n)p^2) operations.Source: §5.1 · p. 11
  • RGP is a γ-approximate RPLU scheme with γ = (dmin/dmax)^2, so it inherits RPLU convergence rates with a potentially large prefactor.Cauchy-like structure is preserved under elimination, allowing residual updates from generators.Source: §5.1 · pp. 11–12
  • 16× faster than RPLU and 650× faster than RSVD, RGP and RPLU have nearly identical errors within a modest constant factor of optimal, while RSVD is nearly optimal.Figure 2 compares approximation quality on two Loewner-matrix classes and timing for rank-100 approximations.Source: §5.1 · p. 12, Figure 2 · p. 13

5.2 Sketchy pivoting

  • Sketchy pivoting uses sequential sketch blocks to estimate row norms and sample pivots, while sketching can be formed upfront in a single AΩ product.Fresh blocks remain independent of the current residual for the analysis.Source: §5.2 · pp. 13–14
  • With Gaussian sketches and block size 3, sketchy pivoting is a 1/3-approximate RPLU scheme and retains its algebraic and geometric bounds up to a factor of 3.The analysis uses normalized row-norm estimates under Gaussian projection.Source: §5.2 · pp. 14–15
  • C2PLU inherits convergence rates with dimension-dependent prefactors, unlike the constant-factor guarantees for approximate RPLU sampling.The analysis does not cover blocked pivot selection or recycled sketches; these likely require new ideas and assumptions.Source: §5.2 · pp. 15–16

6 Conclusion

The paper establishes algebraic and geometric convergence rates for approximate randomly pivoted Cholesky, QR, and LU, with approximate sampling extending the analysis to cheaper LU variants. The rates are strongest under algebraic spectral decay; geometric-decay bounds leave a gap from optimal rates, and several sketch-based extensions remain open.

6 Conclusion

  • Approximate sampling changes the bounds only by a γ^-1 prefactor, enabling the same analysis for two cheaper RPLU variants introduced in the paper.The conclusion identifies the pivot-product identity and elementary symmetric polynomial estimates as the main tools.Source: §6 · p. 16
  • Under algebraic spectral decay, RPCholesky and RPQR match their greedy counterparts asymptotically and attain the optimal trace and squared Frobenius error rates, respectively.The RPLU comparison is less direct: in the model case σ_j(A) = j^-α, α > 1, its squared Frobenius error loses a factor k relative to optimal; greedy CPLU follows singular-value decay without a loss factor in max norm, though its Frobenius error can be up to √mn larger.Source: §6 · p. 16
  • For geometric decay σ_j(A) = O(ρ^j), the bounds are O(kρ^(k/2)) for RPCholesky and RPLU and O(kρ^(k/2)) for RPQR, while optimal rank-k error is O(ρ^k).The proof obtains a single-iterate bound by comparing its error with the geometric mean of preceding errors; observed errors nevertheless appear to follow O(ρ^k) in practice.Source: §6 · p. 16
  • Randomized pivoting can be more robust to outliers, while some sparse-matrix experiments find greedy pivoting more accurate; approximate randomized pivoting also has dimension-independent guarantees unavailable for greedy pivoting.The guarantees follow by converting residual-row-norm estimates into convergence guarantees.Source: §6 · p. 16
  • The conclusion leaves open whether the geometric-mean loss can be removed and whether the analysis can accommodate blocked pivot selection or recycled sketches.It also asks whether greedy sketch-based pivoting can satisfy dimension-independent guarantees.Source: §6 · pp. 16–17

AI Acknowledgement

The authors acknowledge GPT-5.6 Sol Pro's role in the sketchy-pivoting extension, writing, and figures and code; they state that the other results were proved by the authors based on [22].

AI Acknowledgement

  • GPT-5.6 Sol Pro assisted with the sketchy-pivoting extension, writing, and figures and code; the other results were proved by the authors based on [22].Source: AI Acknowledgement · p. 17

A Proof of the elementary symmetric polynomial estimates

The proof bounds elementary symmetric polynomials under algebraic and geometric eigenvalue decay using a generating function, monotonicity, and the q-binomial identity.

A Proof of the elementary symmetric polynomial estimates

  • For algebraic decay, the proof bounds e_k(λ_1, …, λ_n) by C^k e_k(1, 2^-α, …, n^-α).It uses the generating function, nonnegativity of its terms, and a choice of t minimizing the resulting upper bound.Source: A Proof of the elementary symmetric… · p. 17
  • The proof takes kth roots after applying its upper bounds to obtain the stated estimate.Source: A Proof of the elementary symmetric… · p. 18
  • For geometric decay, monotonicity under additional nonnegative arguments reduces e_k(λ_1, …, λ_n) to a geometric sequence bound, with the q-binomial identity used in the estimate.The displayed bound gives e_k(λ_1, …, λ_n)^(1/k) ≤ C/(1−ρ) ρ^((k−1)/2).Source: A Proof of the elementary symmetric… · p. 18

B Proof of the Gaussian row norm estimates

The Gaussian row-norm proof handles zero-weight rows separately, then applies a ratio estimate to sums of correlated Gaussian squares.

B Proof of the Gaussian row norm estimates

Loading 2609.06287v1…