Answers are grounded in this paper and cite their sources.
Unrefereed research candidate. In one sentence: the greedy row-selection rule built into every linear-algebra library, column-pivoted QR, can lose against the best possible choice by a factor of about exp(C√k), with an exact constant C, and never by the 2k allowed by the textbook guarantee. Context. Many simulation and data methods keep only k of N coordinates of an N×k matrix Q with orthonormal columns (for example the interpolation points of the discrete empirical interpolation method, DEIM). The quality of a choice I is γ = ‖Q(I,:)−1‖2, the factor by which interpolation from the chosen coordinates can be worse than the best approximation; some choice always has γ ≤ √(k(N−k+1)). The rule used in practice is column-pivoted QR (QRCP) on Q*, which repeatedly picks the coordinate least explained by those already chosen. Drmač and Gugercin (SIAM J. Sci. Comput., 2016) proved a bound that grows like 2k. Damle and Kressner asked whether QRCP meets the existence scale on orthonormal rows (Problem 4.3 of Amsel et al., arXiv:2602.05394). Chen, Liu, He and Dong (arXiv:2606.02484) gave the first answer, negative: their examples exceed every polynomial multiple of the existence scale, and their construction already gives growth of order exp(c√k) with a small c. Damle (arXiv:2607.13532) showed that the Bischof–Stewart rule meets the existence scale. Results. Let the coherence μ(Q) be the largest row energy divided by the average. (1) Theorem 2.3: if μ(Q) ≤ H, every legal QRCP selection, with any tie-breaking, has γ ≤ √(e(N−k+1)) exp(C(H)√k), with an explicit constant C(H): C(1) = 2 (equal row energies), C(2) ≈ 2.25, and C(H)2/log H → 1. This is the first bound below exponential in k for QRCP on orthonormal rows. (2) The constant is sharp: the worst case satisfies log Gk(H) = (C(H)+o(1))√k, with real examples of fewer than 3k3 rows built from a generalised Kahan matrix; for H > 1 their pivots are unique, and at H = 1 they use the smallest-label tie rule. (3) Corollary 2.6: since μ(Q) ≤ N/k, the bound holds for every input with C(N/k). (4) Theorem 2.7 and Corollary 2.8: without any coherence assumption the worst case is exp(Θ(√(k log(N/k)))) once N ≥ k2+ε (and log N = o(k)), and exp((1+o(1))√(k log N)) when log N/log k → ∞. (5) Theorem 7.1: an a posteriori bound γ ≤ (√e/dk) exp(√((k−1)L)) from the observed pivot range L, with an optimal coefficient. At k = 100 the new bound allows about 109 to 1010 where the classical bound allowed about 1030; it is smaller than the classical bound from k = 13 at H = 1. Limits. Exact arithmetic and worst cases only; typical inputs behave far better, and floating-point QRCP is not analysed. Sharpness is on the logarithmic scale: upper and lower bounds still differ by a factor polynomial in k, and the limits are approached slowly. The worst examples need N of order k3; whether growth of order exp(c√k) occurs when N is a fixed multiple of k is open. Contents. The paper (LaTeX source and PDF) and its figure; check scripts with their recorded outputs (verify.py: exact rational Kahan identities, 25 orthonormal inputs, eleven completed examples at k = 16 to 128 factorised by two QRCP implementations, a retained failed candidate as negative control, large-rank core sums against 80-digit evaluations and the endpoint constructions; check_extensions.py: 50-digit checks of C(H), Table 2, the Kahan family for k = 6 to 16 and inequality (7.5) on 779 grid points; fingerprints.py); the figure script; the bibliography; a machine-readable index; a research-gate record; a review summary; a replay receipt and SHA-256 sums. Checks raise SystemExit and stay active under python -O. Assurance. Written proofs, with finite computational checks. Internal AI-assisted review only: five reviewer roles, an adversarial review by a second AI model, a clean replay, one revision round with extensions, then a re-review and a proof audit of the new proofs by Claude verification passes (the second-model audit of the new proofs was not run because of a usage limit). Not peer review, independent reproduction or formal verification. The first answer to Problem 4.3 is due to Chen, Liu, He and Dong. Creator: Anonymous. Text and data CC0-1.0; code MIT.
No takes yet. Share an insight, caveat, or question.
A 2026 study studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: