{"id":"ab55263c-6aea-47c9-bfaf-b14931f05fd8","arxiv_id":"2607.26863","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Under approximate greedy pivoting, pivoted QR/LU residuals are bounded by the geometric mean of leading singular values, yielding algebraic and geometric convergence rates for matrices and bivariate functions.","lead":"Pivoted QR and LU low-rank approximations converge at rates matching singular-value decay under modest algebraic or geometric decay, not only when decay beats exponential worst-case factors. The same determinant idea gives algebraic and geometric rates for separable approximation of bivariate functions under smoothness or analyticity.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The paper’s strongest claim is a clean, elementary comparison of greedy residuals to geometric means of singular values, plus matching rates under power/geometric decay and analogous function rates. The proofs in §§2–3 and Appendices A–B are standard and appear correct; the main novelty (LU rates; non-analytic function rates; improved QR constants vs reduced-basis greedy) is real and not oversold. The fixed-γ approximate-greedy hypothesis is the right scope condition and is handled explicitly, so it does not undermine the theorems as stated. Minor caveats (LU min residual, non-sharp constants, √n factors in function bounds, weaker geometric exponent than σ_n itself) are already visible in the text and do not break the argument. I agree with ACCEPT / high confidence / low correctness risk; no verdict change.","tokens_in":19358,"tokens_out":526,"duration_ms":28334,"concrete_test":"Numerically check Corollary 2.5 on a diagonal matrix with σ_j = j^{-p} (p=1,2) and on σ_j = ρ^j (ρ=0.9,0.5): run exact greedy LU/QR, plot min residual (LU) and ||Ê^{(n-1)}||_{2,∞} (QR) against γ^{-1} C e^p n^{-p} and γ^{-1} C ρ^{(n+1)/2}; confirm the predicted algebraic exponent and geometric base hold and that the geo-mean bound is not violated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central chain is sound: pivot-product identities (Lemmas 2.1, 2.3) plus approximate greedy pivoting give residual control by |det|^{1/n}, then by the geometric mean of the first n singular values (Theorems 2.2, 2.4); Corollary 2.5 follows from standard n! and geometric-mean estimates. The function-side determinant bounds (Theorems 3.1, 3.3) are standard interpolation/Chebyshev arguments and correctly feed (9). The reader’s “weakest assumption” (fixed γ) is an explicit hypothesis tracked as γ^{-1}, not a hidden gap. The LU min-over-iterates formulation is stated carefully and algorithmically recoverable. No internal inconsistency or load-bearing hole in the strongest claim was found.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","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.","tokens_in":19440,"tokens_out":1041,"duration_ms":31810,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"§2.4, Corollary 2.5"},{"comment":"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.","section":"§2.2 after Theorem 2.2"},{"comment":"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.","section":"§3.2"},{"comment":"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.","section":"§2"},{"comment":"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.","section":"Acknowledgements"},{"comment":"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).","section":"Title page / §1"}],"recommendation":"accept","confidential_remarks":"I agree with the reader’s high-confidence accept: the central chain is short, classical, and correctly tracked through approximate pivoting. No load-bearing gap. Fit is strong for a NA theory journal; absence of numerics is acceptable for this style of paper. The AI-acknowledgement is unusually explicit and does not affect correctness."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","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.\n\nWhat 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.\n\nSoft 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.\n\nThis 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.","headline":"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.","tokens_in":20111,"tokens_out":581,"would_cite":true,"duration_ms":10945,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F55","65D15","41A25","15A23"],"pacs":[],"model":"grok-4.5","headline":"Under approximate greedy pivoting, QR and LU residuals track the geometric mean of leading singular values, matching algebraic and half-rate geometric decay.","keywords":["pivoted QR","pivoted LU","low-rank approximation","greedy pivoting","singular-value decay","adaptive cross approximation","geometric-mean bound","function approximation"],"falsifier":"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.","tokens_in":20173,"feed_emoji":"📉","tokens_out":924,"duration_ms":14400,"temperature":0.7,"pith_summary":"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.","feed_headline":"Greedy QR and LU residuals track singular-value decay","feed_subtitle":"Approximate pivoting alone yields algebraic rates and half-exponent geometric rates, matching practice","key_machinery":"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).","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Greedy QR/LU residuals bounded by singular-value geometric means","Approximate pivoting yields algebraic rates under singular decay","Determinant control explains pivoted QR and LU convergence","Algebraic singular decay gives O(n^{-p}) greedy QR/LU residuals","Bivariate LU inherits Hölder rates from sampled determinant bounds"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Greedy QR/LU residuals bounded by singular-value geometric means","Approximate pivoting yields algebraic rates under singular decay","Determinant control explains pivoted QR and LU convergence","Algebraic singular decay gives O(n^{-p}) greedy QR/LU residuals","Bivariate LU inherits Hölder rates from sampled determinant bounds"]},"model":"grok-4.5","effort":"low","cost_usd":0.00391,"raw_usage":{"total_tokens":1168,"prompt_tokens":720,"num_sources_used":0,"completion_tokens":65,"cost_in_usd_ticks":39104000,"prompt_tokens_details":{"text_tokens":720,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":383,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":720,"tokens_out":65,"duration_ms":7032,"temperature":1.0,"reasoning_tokens":383,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-30T18:52:11.827454+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"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.","supporting_citations":[],"review_version":1}