Convergence rates for pivoted QR and LU

Marc Aur\`ele Gilles

Convergence rates for pivoted QR and LU

T0 review · 0 major / 6 minor · reviewed 2026-07-30 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Under approximate greedy pivoting, QR and LU residuals track the geometric mean of leading singular values, matching algebraic and half-rate geometric decay.

desk verdict Clean theory paper: geometric-mean residual control via pivot products explains why pivoted QR/LU track modest SV decay, with new LU rates and solid function extensions. read the letter →

arxiv 2607.26863 v1 pith:Y2SX6INZ submitted 2026-07-29 math.NA cs.NA

Marc Aurèle Gilles This is my paper · ORCID

classification math.NAcs.NA MSC 65F5565D1541A2515A23

keywords pivotedQRLUlow-rankapproximationgreedypivotingsingular-valuedecayadaptivecrossgeometric-meanboundfunction

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Pivoted QR and LU are the everyday greedy ways to build low-rank matrix approximations from selected columns (or rows and columns). Classical worst-case bounds multiply the optimal error by factors that grow like 2^k or 4^k, so they only guarantee useful convergence when singular values decay extremely fast. This paper shows that approximate greedy pivoting alone already controls the residual by the determinant of the selected submatrix, and that determinant is at most the geometric mean of the first n singular values. Consequently, whenever the singular values themselves decay like a power of k or geometrically, the algorithm residuals inherit essentially the same rate (algebraic with the same exponent, geometric with half the base). The same determinant idea extends to continuous functions of two variables, giving algebraic rates from Hölder or mixed differentiability and geometric rates from analyticity, without needing positive-definiteness. The practical upshot is a theoretical account of why these greedy methods work well under the modest decay that actually appears in applications.

What carries the argument

The classical pivot-product identity (det of the selected submatrix equals the product of the pivots) together with the approximate-greedy lower bound on each pivot; the residual is then controlled by the geometric mean of singular values (or by interpolation/Chebyshev bounds on arbitrary sampled determinants in the function setting).

What would settle it

Construct a matrix whose singular values decay like k^{-p} (or ρ^k) yet every approximate-greedy LU or QR run produces residuals that stagnate or decay strictly slower than the predicted n^{-p} (or ρ^{n/2}) rate for large n.

Watch

Extended reading notes

Core claim

Under approximate greedy pivoting with fixed quality γ, the LU minimum residual and the QR residual after n−1 steps both satisfy ε_n ≤ γ^{-1} (∏_{j=1}^n σ_j(A))^{1/n}. Therefore algebraic singular-value decay σ_j ≤ C j^{-p} yields ε_n = O(n^{-p}), and geometric decay σ_j ≤ C ρ^j yields ε_n = O(ρ^{n/2}). Parallel uniform bounds on sampled determinants give matching Hölder/differentiable algebraic rates and analytic geometric rates for bivariate LU.

Load-bearing premise

Every pivot must stay at least a fixed positive fraction γ of the current residual’s maximum entry (or column norm); if that quality constant collapses as the iteration proceeds, the geometric-mean rates no longer follow.

Editorial extensions

If this is right

Algebraic singular-value decay of any positive order is already enough for the best LU residual and the QR residual to decay at the same algebraic order.
Geometric singular-value decay yields residual convergence at rate ρ^{n/2}, removing the classical requirement that ρ be smaller than 1/2 or 1/4.
Bivariate functions that are merely Hölder or finitely differentiable in each variable obtain explicit algebraic LU rates; joint analyticity yields geometric rates for every Bernstein parameter greater than 1.
Approximate (not exact) greedy pivoting is sufficient; the only price is a multiplicative 1/γ factor.
The same determinant control applies on any restriction of the domain, including discrete tensor-product grids.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Sketch-based or randomized pivot searches that only guarantee a uniform fraction of the true max-norm (or 2,∞-norm) pivot automatically inherit the same rates, explaining part of their observed reliability.
The half-exponent geometric rate suggests that joint analyticity in both variables is the regime where one should expect full-rate geometric convergence from cross approximation.
Extending the determinant argument to higher-dimensional tensors or to Kolmogorov-width decay would give the first non-analytic rates for greedy cross approximation in d>2.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The one thing to know is that this paper finally gives a simple reason why column-pivoted QR and complete-pivoting LU track singular-value decay in practice when the classical 2^k/4^k bounds are useless. Under approximate greedy pivoting with fixed quality γ, both residuals are controlled by |det|^{1/n} of the selected submatrix, hence by the geometric mean of the first n singular values. Algebraic decay σ_j ≲ j^{-p} then gives the same rate for the residuals (up to e^p γ^{-1}); geometric decay gives ρ^{n/2}. That is the load-bearing move, and it is elementary and correct.

What is new: the LU matrix rates under algebraic/geometric SV decay appear to be new. The QR rates improve constants and the geometric exponent relative to the reduced-basis greedy corollaries the paper cites, while remaining weaker than the sharpest exact-greedy geometric factor in one regime. The bivariate LU extension is also new in the non-analytic setting: Hölder/differentiable determinant bounds via Lagrange residuals give algebraic rates, and Chebyshev/Laurent bounds give geometric rates for every Bernstein parameter >1 (not just >4). Approximate pivoting is tracked cleanly as a γ^{-1} factor throughout.

Soft spots are minor and mostly acknowledged. The LU bound is on the running minimum residual, not necessarily the final one; under exact pivoting this is free, and under approximate pivoting the iterate before the smallest pivot still satisfies the same bound. Constants are not sharp. There are no experiments, which is fine for this kind of note. The fixed-γ hypothesis is explicit, not hidden; if pivot quality collapses with k the rates fail, but that is the right hypothesis for the algorithms people actually run. Citation pattern is honest about the reduced-basis overlap.

This is for people who use or analyze ACA, CPQR, Chebfun2-style methods, or greedy reduced bases and want rates that match observed behavior. Math is short, standard, and carefully written; appendices supply the interpolation/Chebyshev estimates in the usual style. I would send it to a serious referee and would cite the matrix geometric-mean bound and the LU rates. Bring it to reading group if the group cares about low-rank approximation theory.

Referee Report

0 major / 6 minor

Summary. The paper derives convergence rates for column-pivoted QR and completely pivoted LU (including approximate greedy pivoting with quality constant γ) that avoid the classical exponential factors 2^k and 4^k. The key step is a geometric-mean bound: under approximate greedy pivoting, the LU quantity min_{0≤k≤n−1} ∥E^{(k)}∥_max and the QR residual ∥Ê^{(n−1)}∥_{2,∞} are both controlled by γ^{−1}(∏_{j=1}^n σ_j(A))^{1/n} via classical pivot-product identities and singular-value monotonicity under restriction. Algebraic singular-value decay σ_j ≤ C j^{−p} then yields residual rates O(n^{−p}); geometric decay σ_j ≤ C ρ^j yields O(ρ^{n/2}). The LU analysis is extended to continuous bivariate functions on [−1,1]^2 by uniform bounds on sampled determinants, giving algebraic rates under one-sided or mixed Hölder/differentiability assumptions and geometric rates under one-sided or joint analyticity in Bernstein ellipses.

Significance. The contribution is a clean, load-bearing explanation of why pivoted QR/LU track singular-value decay in practice even when the classical worst-case factors are not overcome. The matrix arguments are short and standard (Wilkinson pivot-product, AM-GM, n! ≥ (n/e)^n, residual monotonicity for QR), yet they improve explicit constants and γ-dependence relative to reduced-basis greedy bounds and give a usable geometric factor for every ρ < 1. The function-side determinant bounds appear to be the first general LU rates that require neither analyticity with ρ > 4 nor positive-definiteness. Approximate greedy pivoting is tracked explicitly by γ^{−1}, which matches practical heuristics. The transparent AI-assisted discovery note and the self-contained appendices strengthen reproducibility of the analytic claims.

minor comments (6)

[§2.4, Corollary 2.5] In Corollary 2.5 and the surrounding discussion, the geometric residual rate is ρ^{(n+1)/2}, i.e., half the singular-value exponent. The comparison with Binev et al. (exact pivoting, factor (2ρ)^{k+1}) is helpful; a one-sentence remark on whether the square-root loss is known to be sharp under pure geometric SV decay (as opposed to adversarial matrices realizing 4^k) would orient the reader.
[§2.2 after Theorem 2.2] The LU residual is the running minimum over the first n iterates, not necessarily ∥E^{(n−1)}∥_max. The algorithmic recovery via the smallest pivot (exact case) and the weak-pivot predecessor (approximate case) is correct but easy to miss; a short forward pointer in the introduction or after (1) would help.
[§3.2] Theorem 3.1 / Corollary 3.2: the one-sided Hölder theory requires α_x > 1/2 for any decay, and the Hadamard √n factor produces the −1/2 in the exponent. Both are stated, but a brief comparison with what a volume or max-norm argument might recover (if anything) would clarify whether the 1/2 is an artifact.
[§2] Notation: bE vs E and bA are readable in TeX but the hat/bold distinction is easy to lose in plain text; consider a single residual symbol with a QR/LU superscript in the matrix section.
[Acknowledgements] References [8] and the GitHub link for the AI prompt are appropriate given the acknowledgements; ensure the arXiv identifier and URL remain stable at publication.
[Title page / §1] Typos/style: “Marc Aur` ele” spacing; “H¨ older” consistency; in (2) the footnote about the 2,∞ vs spectral form is useful—consider promoting the 2,∞ statement into the main display for parallel structure with (1).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: residual rates follow from classical pivot-product identities plus external singular-value/interpolation bounds under an explicit pivot-quality hypothesis.

full rationale

The central chain is self-contained and non-circular. Lemmas 2.1 and 2.3 (pivot-product identities) are classical external facts relating products of pivots to det(A_n) or (det G_n)^{1/2}; they are not defined in terms of the target residual rates. Approximate greedy pivoting (fixed γ) is an explicit hypothesis that multiplies bounds by γ^{-1}, not a quantity fitted to data or smuggled from a self-citation. Theorems 2.2 and 2.4 then bound residuals by |det|^{1/n} ≤ geometric mean of leading singular values via standard monotonicity of singular values under restriction. Corollary 2.5 applies only elementary n! and geometric-mean estimates to that inequality. Function-side Theorems 3.1 and 3.3 bound arbitrary sampled determinants by Hölder interpolation residuals and Chebyshev coefficient decay—standard approximation arguments independent of the LU iteration—then feed the same identity (9). Comparisons to reduced-basis greedy Kolmogorov-width bounds are external benchmarks, not load-bearing uniqueness imports. No parameter is tuned so a ‘prediction’ reproduces a fit; no ansatz is smuggled via overlapping-author citation; no known empirical pattern is merely renamed. Score 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claims rest on standard linear-algebra and approximation facts (pivot-product identities, singular-value monotonicity, interpolation error, Chebyshev coefficient bounds) plus the modeling hypothesis of approximate greedy pivoting with fixed γ. No data-fitted constants. No new physical entities.

assumptions (6)

standard math Pivot-product identity: for any nonzero LU pivots, det(A_{I_n,J_n})=∏ p_j (Lemma 2.1; classical/Wilkinson).
Used as the bridge from residuals to submatrix determinants; stated as classical and proved by reference pattern.
standard math QR pivot-product: (det A_{:,J_n}^T A_{:,J_n})^{1/2}=∏ ρ_j via thin QR of selected columns (Lemma 2.3).
Standard Householder/QR fact; enables the QR geometric-mean bound.
standard math Singular values are monotone under row/column restriction: ∏ σ_j(A_{I,J})≤∏ σ_j(A) (Horn & Johnson).
Converts submatrix determinants into geometric means of full-matrix singular values.
domain assumption Approximate greedy pivoting with fixed γ∈(0,1]: |p_{k+1}|≥γ||E^{(k)}||_max (LU) and ρ_{k+1}≥γ||Ê^{(k)}||_{2,∞} (QR).
Algorithmic hypothesis matching practical approximate pivot search; all rates carry γ^{-1}.
domain assumption For functions: existence of the stated one-sided/mixed Hölder seminorms or holomorphic extensions to Bernstein ellipses with finite max-norm on those ellipses.
Regularity hypotheses of Theorems 3.1 and 3.3 that feed the determinant bounds.
standard math Hadamard inequality and the paper’s product-span lemma (Lemma A.3) controlling ∏(z_i−z_{i-q})^μ.
Produce the explicit n^{1/2−(q+α)} algebraic factors in the function determinant bounds.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Convergence rates for pivoted QR and LU." pith.science (2026). https://pith.science/paper/Y2SX6INZ

@misc{pith2026260726863,
  author       = {Pith},
  title        = {Pith review of: Convergence rates for pivoted QR and LU},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Y2SX6INZ}},
  note         = {Machine review of arXiv:2607.26863}
}

read the original abstract

Pivoted QR and pivoted LU decompositions are greedy algorithms used to compute low-rank approximations of matrices from selected columns, or selected rows and columns. Despite their practical robustness, general worst-case bounds comparing their errors with those of the best corresponding low-rank approximations contain exponentially growing factors and do not explain their behavior under modest singular value decay. We prove that under approximate greedy pivoting, their error is controlled by the determinant of a submatrix, which is bounded by the geometric mean of the leading singular values. Using this bound, we establish convergence rates under algebraic and geometric singular value decay. We also extend the LU analysis to functions of two variables. By bounding the determinants of arbitrary sampled submatrices, we obtain algebraic convergence rates under differentiability assumptions and geometric convergence under analyticity.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 6 canonical work pages

[1]

L. N. Trefethen and D. Bau III,Numerical Linear Algebra, Society for Industrial and Applied Mathematics, Philadelphia, 1997. doi:10.1137/1.9780898719574

doi:10.1137/1.9780898719574 1997
[2]

Dong and P.-G

Y. Dong and P.-G. Martinsson,Simpler is better: A comparative study of randomized pivoting algorithms for CUR and interpolative decompositions, Advances in Computational Mathematics 49 (2023), article 66. doi:10.1007/s10444-023-10061-z

doi:10.1007/s10444-023-10061-z 2023
[3]

K. J. Pearce, C. Chen, Y. Dong, and P.-G. Martinsson,Adaptive parallelizable algorithms for interpolative decompositions via partially pivoted LU, Numerical Linear Algebra with Applications 32 (2025), no. 1, e70002. doi:10.1002/nla.70002

work page doi:10.1002/nla.70002 2025
[4]

Pritchard, T

N. Pritchard, T. Park, Y. Nakatsukasa, and P.-G. Martinsson,Fast rank adaptive CUR via a recycled small sketch, arXiv preprint arXiv:2509.21963, 2025

arXiv 2025
[5]

Melgaard and M

C. Melgaard and M. Gu,Gaussian elimination with randomized complete pivoting, arXiv preprint arXiv:1511.08528, 2015

arXiv 2015
[6]

Businger and G

P. Businger and G. H. Golub,Linear least squares solutions by Householder transformations, Numerische Mathematik 7 (1965), 269–276. doi:10.1007/BF01436084

doi:10.1007/bf01436084 1965
[7]

Townsend,Gaussian elimination corrects pivoting mistakes, arXiv preprint arXiv:1602.06602, 2016

A. Townsend,Gaussian elimination corrects pivoting mistakes, arXiv preprint arXiv:1602.06602, 2016

arXiv 2016
[8]

Kerger,Closing the oracle-complexity gap in derivative-free convex optimization: A near- quadratic lower bound from exact function values, arXiv preprint arXiv:2607.13335, 2026

P. Kerger,Closing the oracle-complexity gap in derivative-free convex optimization: A near- quadratic lower bound from exact function values, arXiv preprint arXiv:2607.13335, 2026

arXiv 2026

Show all 27 references

[9]

J. H. Wilkinson,Error analysis of direct methods of matrix inversion, J. ACM 8 (1961), 281–330. doi:10.1145/321075.321076

1961
[10]

Bebendorf,Approximation of boundary element matrices, Numer

M. Bebendorf,Approximation of boundary element matrices, Numer. Math. 86 (2000), 565–589. doi:10.1007/PL00005410. 23

2000 doi
[11]

Bebendorf,Adaptive cross approximation of multivariate functions, Constructive Approxi- mation 34 (2011), no

M. Bebendorf,Adaptive cross approximation of multivariate functions, Constructive Approxi- mation 34 (2011), no. 2, 149–179. doi:10.1007/s00365-010-9103-x

2011 doi
[12]

Townsend and L

A. Townsend and L. N. Trefethen,An extension of Chebfun to two dimensions, SIAM Journal on Scientific Computing 35 (2013), no. 6, C495–C518. doi:10.1137/130908002

2013 doi
[13]

Townsend and L

A. Townsend and L. N. Trefethen,Continuous analogues of matrix factorizations, Proceedings of the Royal Society A 471 (2015), no. 2173, article 20140585. doi:10.1098/rspa.2014.0585

2015
[14]

Hashemi and L

B. Hashemi and L. N. Trefethen,Chebfun in three dimensions, SIAM Journal on Scientific Computing 39 (2017), no. 5, C341–C363. doi:10.1137/16M1083803

2017 doi
[15]

O. A. Carvajal, F. W. Chapman, and K. O. Geddes,Hybrid symbolic-numeric integration in multiple dimensions via tensor-product series, inProceedings of the 2005 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2005, pp. 84–91. doi:10.1145/1073884.1073898

2005
[16]

Binev, A

P. Binev, A. Cohen, W. Dahmen, R. DeVore, G. Petrova, and P. Wojtaszczyk,Convergence rates for greedy algorithms in reduced basis methods, SIAM Journal on Mathematical Analysis 43 (2011), no. 3, 1457–1472. doi:10.1137/100795772

2011 doi
[17]

DeVore, G

R. DeVore, G. Petrova, and P. Wojtaszczyk,Greedy algorithms for reduced bases in Banach spaces, Constructive Approximation 37 (2013), 455–466. doi:10.1007/s00365-013-9186-2

2013 doi
[18]

Gu and S

M. Gu and S. C. Eisenstat,Efficient algorithms for computing a strong rank-revealing QR factor- ization, SIAM Journal on Scientific Computing 17 (1996), no. 4, 848–869. doi:10.1137/0917055

1996 doi
[19]

Harbrecht, M

H. Harbrecht, M. Peters, and R. Schneider,On the low-rank approximation by the piv- oted Cholesky decomposition, Applied Numerical Mathematics 62 (2012), no. 4, 428–440. doi:10.1016/j.apnum.2011.10.001

2012 doi
[20]

N. J. Higham,A survey of condition number estimation for triangular matrices, SIAM Review 29 (1987), no. 4, 575–596. doi:10.1137/1029112

1987 doi
[21]

Cortinovis, D

A. Cortinovis, D. Kressner, and S. Massei,On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices, Linear Algebra and its Applications 593 (2020), 251–268. doi:10.1016/j.laa.2020.02.010

2020 doi
[22]

Jeong and A

S. Jeong and A. Townsend,Convergence of pivoted Cholesky algorithm for Lipschitz kernels, arXiv preprint arXiv:2509.13582, 2025

2025
[23]

Santin and B

G. Santin and B. Haasdonk,Convergence rate of the data-independent P -greedy algorithm in kernel-based approximation, Dolomites Research Notes on Approximation 6 (2018), 83–100

2018
[24]

S¨ uli and D

E. S¨ uli and D. F. Mayers,An Introduction to Numerical Analysis, Cambridge University Press, Cambridge, 2003

2003
[25]

L. N. Trefethen,Approximation Theory and Approximation Practice, extended ed., Society for Industrial and Applied Mathematics, Philadelphia, 2019. doi:10.1137/1.9781611975949

2019 doi
[26]

Scheidemann,Introduction to Complex Analysis in Several Variables, 2nd ed., Compact Textbooks in Mathematics, Birkh¨ auser, Cham, 2023

V. Scheidemann,Introduction to Complex Analysis in Several Variables, 2nd ed., Compact Textbooks in Mathematics, Birkh¨ auser, Cham, 2023. doi:10.1007/978-3-031-26428-3

2023 doi
[27]

R. A. Horn and C. R. Johnson,Matrix Analysis, 2nd ed., Cambridge University Press, Cam- bridge, 2013. 24

2013

Pith tools

Reviewed July 30, 2026 · model on record in the stance chip above.

[1] [1]

L. N. Trefethen and D. Bau III,Numerical Linear Algebra, Society for Industrial and Applied Mathematics, Philadelphia, 1997. doi:10.1137/1.9780898719574

doi:10.1137/1.9780898719574 1997

[2] [2]

Dong and P.-G

Y. Dong and P.-G. Martinsson,Simpler is better: A comparative study of randomized pivoting algorithms for CUR and interpolative decompositions, Advances in Computational Mathematics 49 (2023), article 66. doi:10.1007/s10444-023-10061-z

doi:10.1007/s10444-023-10061-z 2023

[3] [3]

K. J. Pearce, C. Chen, Y. Dong, and P.-G. Martinsson,Adaptive parallelizable algorithms for interpolative decompositions via partially pivoted LU, Numerical Linear Algebra with Applications 32 (2025), no. 1, e70002. doi:10.1002/nla.70002

work page doi:10.1002/nla.70002 2025

[4] [4]

Pritchard, T

N. Pritchard, T. Park, Y. Nakatsukasa, and P.-G. Martinsson,Fast rank adaptive CUR via a recycled small sketch, arXiv preprint arXiv:2509.21963, 2025

arXiv 2025

[5] [5]

Melgaard and M

C. Melgaard and M. Gu,Gaussian elimination with randomized complete pivoting, arXiv preprint arXiv:1511.08528, 2015

arXiv 2015

[6] [6]

Businger and G

P. Businger and G. H. Golub,Linear least squares solutions by Householder transformations, Numerische Mathematik 7 (1965), 269–276. doi:10.1007/BF01436084

doi:10.1007/bf01436084 1965

[7] [7]

Townsend,Gaussian elimination corrects pivoting mistakes, arXiv preprint arXiv:1602.06602, 2016

A. Townsend,Gaussian elimination corrects pivoting mistakes, arXiv preprint arXiv:1602.06602, 2016

arXiv 2016

[8] [8]

Kerger,Closing the oracle-complexity gap in derivative-free convex optimization: A near- quadratic lower bound from exact function values, arXiv preprint arXiv:2607.13335, 2026

P. Kerger,Closing the oracle-complexity gap in derivative-free convex optimization: A near- quadratic lower bound from exact function values, arXiv preprint arXiv:2607.13335, 2026

arXiv 2026