Convergence rates for pivoted QR and LU

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.

Disclosure

“column information, such as row or column norms, which does not directly imply the max-norm pivot condition analyzed here for LU. Extending the determinant bounds to such settings is a natural direction for future work. Acknowledgements AI tools were used extensively in developing the results and writing this paper. In particular, GPT-5.6 Sol autonomously produced a proof of a version of corollary 3.4 and an argument close to the proof in corollary 3.2, using a prompt similar to t”

PDF page 12

Classification

Substantial proof generation

Multiplier

10

Verified

2026-08-23T19:11:51.259771Z

Structural counts