{"id":"09f04c10-9cc9-49e8-b82e-378885078370","arxiv_id":"2502.02721","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"New inner-product-free Krylov methods, sCMRH and sLSLU, combine Hessenberg basis construction with randomized sketch-and-solve to produce residual norms close to minimal residual methods.","lead":"This paper introduces two new Krylov methods for large-scale inverse problems that avoid inner-product computations and use randomized sketching to approximate minimal residual solutions. The methods match the accuracy of classical solvers like GMRES and LSQR while remaining compatible with parallel and low-precision computing.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1 never constructs the sketched matrix S2 A L_k: z_k = S2 A^T d_k is unused and the solve in line 31 references an undefined Z, so the reported sLSLU results may not come from the claimed method.","rationale":"The reader's weakest assumption (sketch size ell too small for the theoretical embedding bound) is real: the paper's own Eq. (14) guarantee needs ell ~ (maxiter) log m / eps^2 (not m log m as printed), while the experiments use ell = 10*(maxiter+1); for maxiter=30 and m~10^6 this is below the standard bound, and the paper concedes the guarantee cannot always be ensured. I do not treat that as fatal because the numerical claim is empirical and the curves show the behavior. The more load-bearing issue is that Algorithm 1 does not specify how the sketched matrix in Eq. (13) is formed: z_k = S2 A^T d_k is unused and line 31 references an undefined Z. A correct sketch-and-solve for sLSLU would sketch D_{k+1} (or A L_k) and use the Hessenberg relation; the printed update points to the wrong vector. If this is a typo, the fix is easy, but it must be stated and confirmed. Since no code is provided, the reported experiments may not reproduce the described method. This does not change the conditional verdict: accept if the authors supply a corrected algorithm and verification that the implemented Z equals S2 A L_k (or S2 D_{k+1} H).","tokens_in":14451,"tokens_out":11251,"duration_ms":103054,"concrete_test":"Reimplement Algorithm 1 literally on a small dense problem (e.g., A in R^{100x30}, maxiter=10) and run to the solve step; if Z is undefined, the algorithm as printed cannot be executed. Then patch the evident typo by maintaining Z = S2 D_{k+1} and solving min_y ||S2 r0 - Z H y|| (or equivalently setting z_k := S2 d_{k+1} and Z := [z_1...z_{k+1}]H), and verify that this y_k equals the dense minimizer of ||S2 r0 - S2 A L_k y|| and that the resulting residual curve reproduces Figure 4. If only the patched version works, the paper must state and justify the correction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that sCMRH/sLSLU approximate the minimal-residual Krylov solution by sketching the projected least-squares problem (Eq. (13)). In the pseudocode for sLSLU (Algorithm 1), the only sketch formed in each iteration is z_k = S2*u with u = A^T d_k (line 11), and z_k is never used. The solve step (line 31) asks for the minimizer of ||S2 r0 - S2 A L_k y|| = ||S2 r0 - Z y||, but no line builds Z, nor S2 A L_k, nor the equivalent S2 D_{k+1} H_{k+1,k}. Using the recurrence A L_k = D_{k+1} H_{k+1,k}, one would need to maintain sketches of the D columns (e.g., z_k := S2 d_{k+1}) and then multiply by H; the printed line sketches A^T d_k instead. Thus Algorithm 1 as written is non-executable at line 31, and the numerical results in Section 4 could correspond to an implementation different from the method defined by Eq. (13). This is more fundamental than the sketch-dimension gap the reader flagged: even with an ideal embedding, the algorithm does not define the sketched problem it claims to solve.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes two inner-product-free Krylov subspace methods, sCMRH and sLSLU, that combine Hessenberg/generalized-Hessenberg basis construction with randomized sketch-and-solve for the projected least-squares and Tikhonov problems. Section 3.2 derives a residual-norm approximation bound (Eq. 14), notes the unbiasedness of the sketched estimator, and gives an expected squared residual formula. Algorithms 1 and 2 provide pseudocode, and Section 4 reports experiments on deblurring, simulated neutron tomography, and two real X-ray datasets, with the conclusion that the sketched methods track GMRES/LSQR residual norms more closely than CMRH/LSLU while remaining inner-product free.","tokens_in":14745,"tokens_out":6745,"duration_ms":62328,"significance":"If the methods perform as claimed, the contribution is useful: it offers inner-product-free alternatives to GMRES and LSQR whose residual norm is closer to the true minimal residual than that of quasi-minimal residual methods, with potential benefits for parallel and low-precision computation. The theoretical derivation in Section 3.2 is standard and largely correct, and the paper honestly acknowledges that the subspace-embedding guarantee cannot always be guaranteed for the sketch sizes used in practice. However, the pseudocode as printed does not define the sketched projected problem it claims to solve, and the experiments use sketch dimensions far below the theory with no variance reporting. These issues currently prevent the numerical evidence from being verified.","major_comments":[{"comment":"The solve step is not executable from the pseudocode. Line 31 states that y_k is the minimizer of ||S2 r0 - S2 A L_k y||^2 = ||S2 r0 - Z y||^2, but no matrix Z is constructed anywhere. The only sketch computed in the loop, z_k = S2 * A^T d_k (line 11), is never used and is not a column of S2 D_{k+1} H_{k+1,k} or of S2 A L_k; similarly, Algorithm 2 computes f1 and f_{k+1} but never assembles S1 L_k. Consequently, the numerical results in Section 4 may come from an implementation different from the method defined by Eq. (13). Please specify explicitly how S2 A L_k (or an equivalent factored form) is formed, for example by maintaining sketches of the D columns and multiplying by H, and correct both algorithms accordingly.","section":"Algorithm 1, line 31; Algorithm 2, line 32"},{"comment":"The basis update contains inconsistent variable reuse that prevents verification of the generalized Hessenberg recurrence (7). Line 17 overwrites d_k with the newly computed basis vector, so d_k no longer denotes the kth column of D when it is used in line 21 and in the subsequent W update; the new vector should be stored as d_{k+1}. In addition, line 27 sets W(k+1,k+1) using u(g(i2)), although the quantity available for the L-basis update at that point is q(g(i2)). These are not mere notation slips: they make the algorithm ambiguous about which vectors enter the H and W relations.","section":"Algorithm 1, lines 17, 21, and 27"},{"comment":"The experiments set ell = 10*(maxiter+1), which equals at most a few hundred in the reported runs, while the theory in Section 3.2 requires ell ~ m log(m)/eps^2 for Eq. (14) to hold with high probability; for the tested image and tomography problems, m is orders of magnitude larger. The paper acknowledges that the guarantee cannot always be ensured in practice, but every figure shows a single run with no error bars or repeated trials, and the random pivoting sample size is not systematically studied. Please report the distribution of residual norms over repeated sketches and pivot samples, or otherwise provide empirical justification for the small sketch dimension.","section":"Section 4 and Eq. (14)"}],"minor_comments":[{"comment":"There are several typos and grammatical slips, including \"mulitplications\" (Section 1), \"are are\" (Section 4.1), and \"perforamcne\" (Section 5). A careful proofread is needed.","section":"Throughout"},{"comment":"References [15] and [23] are the same paper (Sarlos, FOCS 2006) and should be consolidated.","section":"References"},{"comment":"The two terms in Eq. (17) are missing the superscript 2 and the subscript 2: the expression should read ||S2(ALky - b)||_2^2 + lambda^2 ||S1(Lky)||_2^2. The same omission appears in Algorithm 2, line 32.","section":"Section 3.3, Eq. (17)"},{"comment":"The caption states that sCMRH uses a sample size of 5 for the random pivot search, but Section 4.2 describes a sample size of 25 and the text never defines how the sample size for sCMRH was chosen or whether the results are sensitive to it.","section":"Figure 2 caption and Section 4.1"},{"comment":"Several residual-norm panels appear to lack curve labels or legends, making it difficult to verify which curve corresponds to sLSLU, LSLU, and LSQR; please add legends or otherwise identify each curve.","section":"Figures 4, 6, 8, and 11"}],"recommendation":"major_revision","confidential_remarks":"The central idea is plausible and the theory in Section 3.2 is standard, but the pseudocode errors are load-bearing: Algorithm 1 as printed does not implement the sketched projected problem, so the experimental section may describe a different method. The sketch-dimension gap is also a concern, but it could be addressed with variance reporting and empirical justification. I recommend major revision rather than rejection because the issues appear fixable: the authors need to provide corrected, executable algorithms and rerun or re-report the experiments with clear construction of the sketched quantities."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The new algorithmic family in this paper is legitimate: take the inner-product-free generalized Hessenberg basis construction from CMRH/LSLU and add a randomized sketch-and-solve step for the projected least-squares problem. Section 3.2 is mostly standard and correct: the unbiasedness argument follows from textbook randomized NLA, and Eq. (14) is the usual subspace embedding bound applied to residuals. The numerical results on deblurring, neutron tomography, and two real x-ray datasets suggest the sketched variants track GMRES/LSQR much more closely than CMRH/LSLU, which is what you would hope for if the method works.\n\nBut there is a load-bearing problem in the pseudocode. Algorithm 1 (sLSLU) computes z_k = S2 * (A^T d_k) in line 11 and never uses it, then line 31 asks for the minimizer of ||S2 r0 - Z y|| with Z undefined. To implement Eq. (13) via the generalized Hessenberg relationship A L_k = D_{k+1} H_{k+1,k}, you would need to sketch the D columns (or maintain S2 D_{k+1}) and multiply by H. As printed, the algorithm is non-executable, so the Section 4 results could well come from a different implementation. This is more fundamental than the sketch-size gap.\n\nThe sketch-size gap itself is also worth flagging: the experiments use ell = 10*(maxiter+1), far below the theory's ell ~ m log m / eps^2, and the paper honestly admits the guarantee cannot always be met in practice. Without error bars or multiple trials, it is unclear whether the close match to GMRES/LSQR is robust or partly lucky. Minor issues: a few typos in the loops (e.g., line 27 uses u instead of q) and a duplicated Sarlos reference.\n\nWho is this for? Researchers working on communication-avoiding or low-precision Krylov methods for inverse problems. The idea deserves referee time, but the current manuscript is not reproducible. I would send it to peer review with a strong request for a corrected algorithm and code, not desk-reject it.","headline":"The core idea is sound and worth pursuing, but Algorithm 1 as printed cannot implement the claimed method, so the experimental results are not independently verifiable.","tokens_in":15242,"tokens_out":3765,"would_cite":false,"duration_ms":33922,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F10","65F22","65F20","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Two new inner-product-free Krylov methods track the residual norms of GMRES and LSQR without computing inner products.","keywords":["Krylov subspace methods","inner-product-free algorithms","randomized sketching","sketch-and-solve","inverse problems","least squares","Tikhonov regularization","Hessenberg method"],"falsifier":"Recompute the deblurring example with the paper's sketch size and plot per-iteration residual norms of sCMRH against GMRES and CMRH; the central claim fails if the sCMRH curve rises above CMRH, or if its gap above GMRES ever exceeds the sketch condition number $\\kappa_2(SQ_{[A b]})$ that the paper identifies with $(1+\\epsilon)/(1-\\epsilon)$.","tokens_in":14286,"feed_emoji":"🧮","tokens_out":15128,"duration_ms":115769,"temperature":0.7,"pith_summary":"This paper introduces two Krylov subspace methods, sCMRH and sLSLU, for large-scale linear inverse problems that never compute inner products. Existing inner-product-free Krylov methods such as CMRH and LSLU only minimize a quasi-residual, and the gap between the quasi-norm and the true residual norm is uncontrolled; for inverse problems this gap matters because the residual norm is the fit-to-data part of the likelihood. The new methods build a nonorthogonal basis with the Hessenberg method and solve the projected least-squares problem with a randomized sketch, which the paper shows to be unbiased and close to the minimal-residual solution. Numerical experiments indicate that the sketched methods track the residual-norm curves of GMRES and LSQR while producing smaller residual norms than CMRH and LSLU.","feed_headline":"Sketching lets inner-product-free solvers match GMRES and LSQR","feed_subtitle":"New Krylov methods track GMRES and LSQR residual norms with no inner products.","key_machinery":"The load-bearing object is the sketched projected least-squares problem $\\min_y \\|S(AL_k y - b)\\|$, in which $L_k$ is the nonorthogonal Krylov basis produced by the (generalized) Hessenberg method with partial pivoting and $S$ is a Gaussian sketching matrix. The Hessenberg construction removes inner products, and the sketch turns the tall-skinny projected problem into a small least-squares problem. The bound in Eq. (14) is the engine: it converts the subspace embedding property into multiplicative control of the residual norm, showing that the sketched solution stays within a factor $(1+\\epsilon)/(1-\\epsilon)$ of the minimal-residual solution in that subspace.","core_discovery":"At iteration $k$, the proposed methods generate a nonorthogonal basis $L_k$ for a Krylov subspace using the Hessenberg method (for sCMRH) or the generalized Hessenberg method (for sLSLU), with no inner products. Instead of the quasi-minimal-residual reduction used by CMRH and LSLU, they solve the sketched projected least-squares problem $\\min_{y} \\|S(AL_k y - b)\\|$, where $S$ is a Gaussian sketch. By the subspace embedding property, the resulting residual norm satisfies $\\|Ax_{\\mathrm{LS}}-b\\| \\le \\|Ax_k^{(S)}-b\\| \\le \\frac{1+\\epsilon}{1-\\epsilon}\\|Ax_{\\mathrm{LS}}-b\\|$, where $x_{\\mathrm{LS}}$ is the true minimal-residual solution in the same Krylov subspace; and the sketch-and-solve estimate is unbiased, with expected squared residual norm inflated only by a factor $1 + k/(\\ell-k-1)$. The paper's numerical experiments show sCMRH residual norms tracking GMRES and sLSLU tracking LSQR, while CMRH and LSLU residual norms drift larger.","pith_inferences":["Extending the paper's idea, a natural test is to vary the sketch dimension $\\ell$ with the iteration count or problem size: the fixed choice $\\ell = 10(\\text{maxiter}+1)$ used everywhere is far smaller than the theory requires, so residual tracking might eventually break as the problem grows.","The same sketched-projected-problem idea could be applied to other nonorthogonal Krylov bases, such as truncated Arnoldi or incomplete Golub-Kahan, replacing a reorthogonalization-depth hyperparameter with a sketch.","Because the sketch-and-solve solution is unbiased, averaging several independent sLSLU runs could reduce the variance of the residual-norm estimates; the paper does not explore this averaging.","One further consequence the authors do not draw is that, for hybrid approaches that estimate a regularization parameter from the projected problem, the closer residual norm should make parameter-selection heuristics more reliable than with CMRH and LSLU."],"forward_implications":["If the central claim holds, sCMRH and sLSLU can stand in for GMRES and LSQR in inverse-problem solves where inner products are the bottleneck, because their residual norms follow the same curves.","Inner-product-free operation removes a common source of breakdown in low-precision arithmetic, since no orthogonal projection is computed.","The same sketch-and-solve reduction applies to the Tikhonov-regularized problem with two sketches, giving residual-norm behavior close to LSQR for a fixed regularization parameter.","On the tested problems, the sketched methods achieve smaller residual norms than their non-sketched inner-product-free predecessors CMRH and LSLU."],"supporting_citations":[{"why":"Introduces the CMRH method and the Hessenberg reduction that sCMRH uses as its basis construction.","marker":"[6]"},{"why":"Introduces LSLU and the generalized Hessenberg process, and supplies the residual-norm bounds used as comparison baselines.","marker":"[9]"},{"why":"Provides the theory of sketching and subspace embeddings on which the paper's Eq. (14) rests.","marker":"[14]"},{"why":"Proposes the sketch-and-solve approach for least-squares problems that the new methods apply to the projected problem.","marker":"[15]"},{"why":"Supplies the expected squared residual factor for sketched least-squares solutions used to justify accuracy.","marker":"[24]"},{"why":"Provides the approximation analysis for faster least-squares solvers that supports the unbiasedness and error claims.","marker":"[25]"},{"why":"Supplies the deblurring and neutron-tomography test problems used in the numerical experiments.","marker":"[26]"},{"why":"Supplies one of the open-access tomographic X-ray datasets used for the real-data experiments.","marker":"[27]"},{"why":"Supplies the other open-access tomographic X-ray dataset used for the real-data experiments.","marker":"[28]"}],"fun_headline_variants":["Sketch-based Krylov matches GMRES and LSQR residuals without inner products","Inner-product-free Krylov with sketching tracks minimal residual solvers","Sketching makes inner-product-free Krylov hit near-minimal residual norms","New Krylov method sketches to match GMRES and LSQR residual norms"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method's practical success rests on the assumption that a small random projection of dimension ten times the iteration count preserves residual norms well enough, but the paper's own theoretical guarantee needs a much larger projection that the experiments do not use.","fun_headline_variants_meta":{"raw":{"variants":["Sketch-based Krylov matches GMRES and LSQR residuals without inner products","Inner-product-free Krylov with sketching tracks minimal residual solvers","Sketching makes inner-product-free Krylov hit near-minimal residual norms","New Krylov method sketches to match GMRES and LSQR residual norms"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001042,"raw_usage":{"total_tokens":4410,"prompt_tokens":1001,"completion_tokens":3409,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":617,"completion_tokens_details":{"reasoning_tokens":3328}},"tokens_in":617,"tokens_out":3409,"duration_ms":23239,"temperature":1.0,"reasoning_tokens":3328,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T11:21:20.735826+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Recompute the deblurring example with the paper's sketch size and plot per-iteration residual norms of sCMRH against GMRES and CMRH; the central claim fails if the sCMRH curve rises above CMRH, or if its gap above GMRES ever exceeds the sketch condition number $\\kappa_2(SQ_{[A b]})$ that the paper identifies with $(1+\\epsilon)/(1-\\epsilon)$.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the CMRH method and the Hessenberg reduction that sCMRH uses as its basis construction."},{"cited_title":"Inner Product Free Krylov Methods for Large-Scale Inverse Problems","cited_arxiv_id":"2409.05239","evidence_quote":"Introduces LSLU and the generalized Hessenberg process, and supplies the residual-norm bounds used as comparison baselines."},{"cited_title":"Acta Numerica 29, 403–572 (2020) https://doi.org/10","cited_arxiv_id":null,"evidence_quote":"Provides the theory of sketching and subspace embeddings on which the paper's Eq. (14) rests."},{"cited_title":"In: Proceedin gs of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Minin g, pp","cited_arxiv_id":null,"evidence_quote":"Supplies the expected squared residual factor for sketched least-squares solutions used to justify accuracy."},{"cited_title":"Numerische mathematik 117(2), 219–249 (2011)","cited_arxiv_id":null,"evidence_quote":"Provides the approximation analysis for faster least-squares solvers that supports the unbiasedness and error claims."},{"cited_title":"Tomographic X-ray data of carved cheese","cited_arxiv_id":"1705.05732","evidence_quote":"Supplies one of the open-access tomographic X-ray datasets used for the real-data experiments."},{"cited_title":"arXiv preprint arXiv:1502.04 064 (2015)","cited_arxiv_id":null,"evidence_quote":"Supplies the other open-access tomographic X-ray dataset used for the real-data experiments."}],"review_version":1}