{"id":"fb7d1ed0-13b0-4413-9c59-c330e42bb004","arxiv_id":"2607.06758","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":5.5,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"Adaptive matrix-free randomized QB algorithms determine rank on the fly via sketched residual indicators and pruning, meeting Frobenius or spectral tolerances to machine precision with near-optimal ranks.","lead":"The paper gives adaptive randomized algorithms that build a low-rank matrix approximation from only matrix-vector products, automatically choosing the rank to hit a user tolerance down to machine precision. This matters for large scientific operators (Hessians, PDE solvers) where storing the matrix is impossible and fixed-rank methods waste work or accuracy.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"Spectral-norm (and AF-pruning) claims rest on fixed-modest-b Gaussian sketches that are only order-of-magnitude proxies, not rigorous ε-embeddings.","rationale":"The reader correctly isolates the weakest link: the spectral (and adjoint-free pruning) indicators rest on sketches whose accuracy for fixed modest b is not covered by the ε-embedding theory of Lemma 2.4, so the “high-probability / machine-precision” language of the abstract is strictly true only for the Frobenius pair. The paper is transparent about the limitation (Thm 4.3, remarks after Algs 4.1/4.3) and the synthetic experiments still show the methods remain practically useful and far tighter than randQB_HMT. No internal inconsistency or hidden assumption that would falsify the Frobenius claims or the overall algorithmic contribution is present; the absence of large-scale PDE-operator tests is a secondary engineering gap, not a load-bearing flaw. Hence the ACCEPT verdict stands.","tokens_in":23791,"tokens_out":675,"duration_ms":24600,"concrete_test":"Using the public MATLAB drivers, re-run randQB_MF_Spec and randQB_AF_Spec on Matrix 2 (p=2) for every tabulated ε with block sizes b=32 (baseline), b=64 and b=128 (20 independent seeds each). Record the fraction of trials in which the exact relative spectral residual exceeds 2ε and the median rank gap to t-SVD. If either quantity grows or fails to shrink with larger b, the modest-b proxy is insufficient for the claimed order-of guarantee.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that the four algorithms meet a prescribed tolerance (absolute or relative) down to machine precision with high probability, returning near-optimal ranks, is fully rigorous for the Frobenius variants via the unbiased Hutchinson estimator (Thm 2.2 + Alg 3.1/3.3) and exact Pythagorean pruning (Thm 3.4). For the spectral variants the same claim is only approximate. Alg 4.1 uses the look-ahead ||B_i||_2 as proxy for ||E_{i-1}||_2; Alg 4.3 and the AF pruning step replace B_{i-1} by its sketch B̃_{i-1}=B_{i-1}Ω_i and invoke Lemma 2.4. The paper itself states (remark after Alg 4.3) that a genuine ε-subspace embedding would require b∼1/ε², far larger than the fixed b=16/32 used throughout; consequently Thm 4.3 only guarantees an error ≤√(η²+1)ε where the factor η is uncontrolled for modest b, and the spectral claim is weakened to “≲ε / on the order of the tolerance.” The numerical tables confirm occasional mild overshoots (e.g., Matrix 2, ε=10^{-3}, MF-Spec error 1.11×10^{-3}). This is the single point at which the strongest claim is least secure.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper develops a family of adaptive, matrix-free randomized QB algorithms for fixed-tolerance low-rank approximation of operators accessible only via matvecs. Four variants are proposed (matrix-free and adjoint-free, each in Frobenius and spectral norms). The main technical ingredients are (i) residual-norm indicators read from the same Gaussian sketches already used for range finding (Hutchinson-style for Frobenius; look-ahead block spectral norm for the 2-norm), remaining usable down to machine precision; (ii) a cheap post-iteration rank-pruning step that decouples BLAS-3 block size from final rank; and (iii) adjoint-free range-finder variants. Theoretical support is given via classical randomized-norm and subspace-embedding arguments (Theorems 2.2–2.3, 3.4, 4.3). Numerical experiments on three synthetic spectra (exponential, polynomial, S-shaped) compare against randQB_EI, randQB_HMT, and the truncated SVD, showing ranks near the t-SVD optimum and reliable tolerance satisfaction where prior adaptive methods fail or over-estimate rank.","tokens_in":24135,"tokens_out":1292,"duration_ms":22284,"significance":"The work closes a genuine practical gap: no previously published method is simultaneously matrix-free, rank-adaptive, and accurate to machine precision in both Frobenius and spectral norms. The rank-pruning idea is a clean, low-cost fix for the block-size dilemma that arises in blocked randomized QB, and the adjoint-free variants are useful when only Q is needed. Public MATLAB code that reproduces all experiments is a clear strength. The Frobenius algorithms rest on fully standard, parameter-free probabilistic identities and an exact Pythagorean pruning identity (Theorem 3.4); the spectral algorithms are more approximate but still produce substantially tighter ranks than the Halko–Martinsson–Tropp adaptive range finder. The contribution is therefore of immediate interest for matrix-free applications (implicit Hessians, H-matrix construction, ST-HOSVD) and is ready for use once the claim language is aligned with the spectral caveats already present in the body.","major_comments":[{"comment":"Abstract and §1 claim that the proposed methods meet the prescribed tolerance “with high probability” for both norms. For the Frobenius variants this is justified by the unbiased Hutchinson estimator and Theorem 3.4. For the spectral variants the body is more careful: Theorem 4.3 only guarantees an error ≤√(η²+1)ε, Remark 4.4 notes that η is uncontrolled for modest b, and the paragraph after Algorithm 4.3 explicitly weakens the AF spectral claim to “≲ε / on the order of the tolerance” because a genuine ε-subspace embedding would require b∼1/ε². The abstract and the opening claim should be qualified so that they match the spectral analysis already given in §4; otherwise the strongest claim overstates what is proved.","section":null},{"comment":"§4.1–4.2 and Algorithm 4.1: the look-ahead indicator ||B_i||_2 is used both as a stopping criterion and (via the pruned last block) as the basis for the final residual bound. Theorem 4.3 absorbs the gap into the factor η from Theorem 2.3, but no quantitative guidance is given on how large b must be for η to stay near 1 on the spectra of interest. The numerical tables (e.g., Matrix 2, ε=10^{-3}, MF-Spec relative error 1.11×10^{-3}) show occasional mild overshoots. A short additional experiment or remark that reports the observed ratio ||E||_2 / ||B_i||_2 across the three test matrices would make the practical reliability of the spectral indicator transparent and would strengthen the central claim for the spectral methods.","section":null}],"minor_comments":[{"comment":"Remark 3.3 and the related-work discussion of Gorman et al. [17] and Pearce et al. [37] correctly credit prior use of Hutchinson-style residual estimates; it would help the reader if the precise novelty of the pruning step (Algorithm 3.2 / 4.2) relative to those works were stated in one sentence in §1.2.","section":null},{"comment":"Figures 1–6: the right-hand panels that plot the error indicator versus iteration are useful, but the vertical axis ranges and the “fail” markers for randQB_EI could be explained more explicitly in the captions so that a reader skimming the figures understands the precision-wall phenomenon without returning to the text.","section":null},{"comment":"Notation: the residual is written both E_i and E_{i-1} in different places; a single consistent indexing convention (e.g., always the residual after i blocks) would reduce minor confusion when reading Algorithms 3.1 and 4.1 side by side.","section":null},{"comment":"§5.1: the choice p=4 (Frobenius) versus p=2 (spectral) for Matrix 2 is well motivated for stressing the baselines, but a one-sentence note that the proposed methods themselves are not restricted to these exponents would prevent a casual reader from thinking the algorithms are spectrum-specific.","section":null},{"comment":"Typographical: “Nystr¨ om” appears with a broken umlaut in §1.1; “randQB HMT” / “randQB EI” spacing is inconsistent with the later “randQB_MF_Fro” style used in the algorithms.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The spectral-norm guarantees are the only soft spot; the authors already acknowledge it in the body. Once the abstract and claim language are brought into line with Theorem 4.3 and the remark after Algorithm 4.3, the paper is a solid, usable contribution that I would expect to see cited for matrix-free adaptive QB. No novelty or citation concerns."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The useful takeaway is a clean family of adaptive matrix-free QB algorithms that actually hit machine precision and keep ranks near the truncated SVD, something the existing adaptive baselines (randQB_EI, HMT) do not deliver together. The real increments are the matrix-free rank-pruning step that lets you keep large BLAS-3 blocks without overshooting the final rank, the residual indicators that avoid Gramian cancellation, and the adjoint-free variants with relative-tolerance support. Those pieces are new in combination even if the blocked QB skeleton, Hutchinson estimator, and look-ahead ideas are already in the literature.\n\nWhat the paper does well is straightforward. The Frobenius variants rest on solid ground (Hutchinson + the Pythagorean identity in Theorem 3.4). The numerical study on three carefully chosen spectra is thorough, the code is public, and the tables show the methods tracking the prescribed tolerance down to eps_mach while staying close to the optimal ranks. The comparison with randQB_EI’s precision wall and HMT’s rank inflation is fair and useful. Citations look complete and the math is standard randomized NLA applied carefully.\n\nThe soft spot is exactly the one the stress-test flags, and the authors already flag it themselves. For the spectral variants the look-ahead ||B_i||_2 and the sketched pruning step are only order-of-magnitude proxies; a genuine ε-subspace embedding would need b ~ 1/ε², which they never use. Theorem 4.3 therefore only gives a √(η²+1) factor with η uncontrolled for modest b, and the claim is correctly weakened to “on the order of the tolerance.” Occasional mild overshoots appear in the tables. That is a real limitation, not a fatal one; it does not break the Frobenius results or the practical utility of the spectral codes.\n\nThis is for people who build H-matrices, ST-HOSVD, or Hessian approximations and need a reliable adaptive range finder that works with only matvecs. It deserves a serious referee. I would cite the Frobenius algorithms and the pruning idea; I would treat the spectral guarantees as practical heuristics. Send it to peer review.","headline":"Solid engineering paper that closes a real matrix-free gap with machine-precision residual tracking and rank pruning; spectral claims are only order-of-magnitude, as the authors themselves note.","tokens_in":24739,"tokens_out":549,"would_cite":true,"duration_ms":6614,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F55","68W20","15A23","65F30","15A18"],"pacs":[],"model":"grok-4.5","headline":"Adaptive matrix-free QB algorithms meet fixed error tolerances down to machine precision while returning near-optimal ranks.","keywords":["low-rank approximation","matrix-free algorithm","adaptive rank determination","randomised QB","fixed-precision problem","randomised norm estimation","adjoint-free range finder"],"falsifier":"Run the algorithms on a matrix whose singular values decay slowly enough that the look-ahead block of size 16–32 fails to capture the dominant residual subspace; if the returned residual then systematically exceeds the prescribed tolerance by more than the modest constant predicted by the theory, the claim is false.","tokens_in":24701,"feed_emoji":"📐","tokens_out":657,"duration_ms":6950,"temperature":0.7,"pith_summary":"When a matrix is available only through matrix-vector products, one often needs a low-rank factorisation whose rank is not known in advance but must be large enough to keep the residual below a prescribed tolerance. Existing adaptive randomised schemes either form residual Gram matrices (and therefore stall near the square root of machine precision) or rely on pessimistic probabilistic bounds that inflate the rank. This paper supplies four blocked QB algorithms that estimate the residual norm directly from the same random sketch used to enlarge the basis, remain accurate down to machine precision, and prune the final block so that a large computational block size does not force an oversized output rank. Adjoint-free variants further reduce the number of operator applications when only the orthonormal basis is required. On matrices with exponential, polynomial and S-shaped spectra the methods recover ranks close to the truncated-SVD optimum while meeting the requested tolerance with high probability.","feed_headline":"Matrix-free low-rank approx hits machine precision, near-optimal ranks","feed_subtitle":"Random sketches estimate residuals; rank pruning lets large blocks stay cheap without overshooting rank","key_machinery":"The randomised residual indicator (||Y_i||_F or ||B_i||_2 obtained from the current sketch) together with the subsequent matrix-free rank-pruning step that discards the lowest-energy rows or singular directions of the last block.","core_discovery":"A family of four adaptive, matrix-free randomised QB algorithms (two Frobenius-norm, two spectral-norm, each with an adjoint-free counterpart) solves the fixed-tolerance low-rank approximation problem to machine precision by reading residual norms from already-computed random sketches and by pruning the final block after the tolerance is crossed, thereby decoupling BLAS-3 block size from the numerical rank.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Adaptive matrix-free QB reads residuals from sketches to machine precision","Random sketches and rank pruning deliver near-optimal matrix-free low-rank","Fixed-tolerance low-rank via matrix-free randomized QB with block pruning","Sketch residual norms guide adaptive matrix-free approximation to machine eps","Adjoint-free adaptive QB decouples block size from numerical rank"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"A modest fixed block size and a single Gaussian sketch already give a reliable enough proxy for residual norms and for the singular values needed by pruning, even though a rigorous subspace embedding would demand a block size that grows like one over tolerance squared.","fun_headline_variants_meta":{"raw":{"variants":["Adaptive matrix-free QB reads residuals from sketches to machine precision","Random sketches and rank pruning deliver near-optimal matrix-free low-rank","Fixed-tolerance low-rank via matrix-free randomized QB with block pruning","Sketch residual norms guide adaptive matrix-free approximation to machine eps","Adjoint-free adaptive QB decouples block size from numerical rank"]},"model":"grok-4.5","effort":"low","cost_usd":0.004826,"raw_usage":{"total_tokens":1309,"prompt_tokens":709,"num_sources_used":0,"completion_tokens":95,"cost_in_usd_ticks":48260000,"prompt_tokens_details":{"text_tokens":709,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":505,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":709,"tokens_out":95,"duration_ms":5630,"temperature":1.0,"reasoning_tokens":505,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-10T21:56:00.762935+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Run the algorithms on a matrix whose singular values decay slowly enough that the look-ahead block of size 16–32 fails to capture the dominant residual subspace; if the returned residual then systematically exceeds the prescribed tolerance by more than the modest constant predicted by the theory, the claim is false.","supporting_citations":[],"review_version":1}