{"id":"91d2d777-8ed3-490b-b0d0-3b9e647ed9f4","arxiv_id":"2509.04386","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Randomized two-sided Gram-Schmidt builds bases Q and P with (ΩQ)^T ΩP = I, at about half the cost and often with better conditioning than the deterministic version.","lead":"This paper proposes a cheaper way to build two bases that are 'sketch-biorthogonal', meaning their random sketches are orthogonal. The method often produces better-conditioned bases than the classical two-sided Gram-Schmidt, which could improve nonsymmetric eigenvalue solvers.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 4.1 bounds fixed pairs, but Algorithm 3.1 normalizes vectors that depend on the same Ω; the anti-concentration 'basis' for better conditioning needs an adaptive argument.","rationale":"The paper develops a clean randomized two-sided Gram-Schmidt process with correct exact-arithmetic identities, a sound cost analysis, and informative experiments. The reader's verdict is largely justified: the algorithm is novel and the numerical comparison is convincing. However, the reader's weakest_assumption concerns Gaussian versus sparse-sign sketching, but a more central gap is that even the Gaussian Proposition 4.1 is not sufficient as stated to explain the behavior of Algorithm 3.1, because the vectors whose sketched inner product is normalized are adaptively selected by the same Ω. This does not invalidate the algorithm or the experiments, but it weakens the 'theoretical analysis' that is offered as the basis for the improved conditioning claim. The proposed computational check would show whether the adaptive variables empirically satisfy the same anti-concentration behavior, thereby settling whether the concern is purely formal or also practical. I would therefore keep the acceptance but make it conditional on either adding a rigorous pivot-ratio argument or tempering the claim that Proposition 4.1 explains the improved stability of Algorithm 3.1.","tokens_in":24859,"tokens_out":16605,"duration_ms":165642,"concrete_test":"Run Algorithm 3.1 with Gaussian Ω on the Section 6.1 test matrices for, say, 200 independent Ω realizations, and separately with the sparse-sign Ω used in the experiments. For each iteration i compute the normalized pivot ratio r_i=|(Ωp_i)^TΩq_i|/(∥Ωp_i∥∥Ωq_i∥), and compare the empirical tail P(r_i≤δ) with the Proposition 4.1 bound 202sδ (and with the sparse-sign behavior in Figure 4.1) for δ=10^-4, 10^-6, 10^-8. If the observed tail is grossly above the bound, the fixed-pair theorem does not transfer to the adaptive sequence; if it is at or below, the practical explanation survives and only a formal adaptive proof is missing.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The conditioning argument in Section 4 rests on Proposition 4.1, but that proposition is stated for a fixed pair of unit vectors x,y: for Gaussian Ω, P(|⟨Ωx,Ωy⟩|≤δ) ≤ 202sδ. In Algorithm 3.1, the quantity that sets the normalization is d_i=(Ωp_i)^TΩq_i, where q_i and p_i are the residuals of the previous randomized steps and hence deterministic functions of the same Ω. A probability bound for fixed (x,y) does not automatically transfer to such adaptive pairs; an algorithm could in principle choose vectors that are almost sketch-orthogonal with probability 1. For Algorithm 3.1 the normalization factor d_i is the Schur-complement/pivot ratio det((ΩX_i)^TΩY_i)/det((ΩX_{i-1})^TΩY_{i-1}) (up to the sign convention in lines 8–9), so a rigorous Gaussian analysis would need an anti-concentration statement for these pivot ratios, not merely for a single inner product. The paper does not provide that, and the text speaks as if Proposition 4.1 applies directly to the vectors generated by the algorithm ('the sketched inner product of any two normalized vectors q and p only has probability O(δ) of being smaller than δ'). Thus the probabilistic explanation of the central better-conditioning advantage is currently a heuristic for the actual adaptive process. This is a gap, not a contradiction: the algorithmic construction and the numerical evidence are unaffected, but the claimed theoretical support is weaker than stated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a randomized two-sided Gram-Schmidt process for biorthogonalizing two matrices X, Y in R^{n x m}. Instead of computing P^T Q = I, it constructs Q and P with range(Q)=range(X), range(P)=range(Y), and (ΩQ)^T ΩP = I for a sketching matrix Ω. Section 3 derives the algorithm from sketched oblique projectors and presents three implementations (rCGS, rMGS, rCGS_O). Section 4 gives Proposition 4.1, an anti-concentration bound for Gaussian sketches of fixed vectors, and uses it to argue that the randomized bases are unlikely to become ill-conditioned. Section 5 applies the process to the nonsymmetric Lanczos algorithm for eigenvalue/eigenvector approximation, including an optimality result for the characteristic polynomial of the sketched Hessenberg matrix. Section 6 reports experiments on ill- and well-conditioned inputs and on a nonsymmetric eigenvalue problem, showing lower cost, lower biorthogonality loss, and often smaller condition numbers than deterministic variants; mixed-precision implementations are considered in Appendix B.","tokens_in":25168,"tokens_out":12355,"duration_ms":117174,"significance":"If the claims hold, this is a useful and timely contribution: it extends randomized sketching from one-sided to two-sided Gram-Schmidt, gives a clean projector-based derivation, and demonstrates practical gains in the nonsymmetric Lanczos setting. The cost analysis and the exact-arithmetic sketch-biorthogonality construction are convincing, and the numerical study is broad and well organized. Credit is due for the careful comparison of several implementations and for the explicit algorithmic recipes. However, the theoretical explanation of improved conditioning is not yet rigorous as stated for the actual adaptive process, and there are two concrete algebraic/algorithmic issues, detailed below, that need correction before the paper is fully reliable.","major_comments":[{"comment":"The inference from Proposition 4.1 to Algorithm 3.1 is not justified. Proposition 4.1 bounds the sketched inner product of a fixed pair of unit vectors, but in Algorithm 3.1 the vectors q_i and p_i are deterministic functions of the same Ω, and d_i = (Ωp_i)^T Ωq_i is effectively an adaptive pivot/determinant ratio of the sketch Gram matrix. A fixed-pair anti-concentration bound does not transfer automatically to such adaptive pairs. A rigorous statement would require anti-concentration for the pivot ratios or independent sketching at each step. In addition, Proposition 4.1 is for Gaussian Ω, whereas the sparse sign matrix recommended in Section 2.4.1 and used in the experiments is supported only numerically (Figure 4.1). The text's statement that 'it is extremely unlikely that Algorithm 3.1 constructs sketch-biorthogonal vectors with very large norms' is therefore stronger than what is p","section":"Section 4, discussion after Prop. 4.1"},{"comment":"The normalization step is algebraically incorrect for negative d_i. The algorithms set q_i = q_i / sqrt(d_i) and p_i = p_i / (sqrt(d_i) * sign(d_i)). If d_i < 0, sqrt(d_i) is not real, and even interpreting the formula in complex arithmetic gives (Ωq_i)^T(Ωp_i) = sign(d_i) = -1, not +1 as required by the stated output condition. The paper only excludes d_i=0, not d_i<0. The standard fix is to use the absolute value, e.g. q_i = q_i / sqrt(|d_i|) and p_i = sign(d_i) p_i / sqrt(|d_i|). As written, the algorithm does not always produce (ΩQ)^T ΩP = I, so this is a load-bearing issue in the central construction.","section":"Algorithms 2.1 and 3.1, lines 8-9"},{"comment":"The formula for the sketched oblique projector is stated with the inverse in the wrong order: the text gives /C9_Ω = Q((ΩQ)^T ΩP)^{-1}(ΩP)^T Ω. The correct expression is Q((ΩP)^T ΩQ)^{-1}(ΩP)^T Ω. Indeed, the proof's verification that the residual is sketch-orthogonal to P uses the latter form, and the displayed equality (Q((ΩQ)^T ΩP)^{-1}(ΩP)^T Ω) Q = Q is false in general because ((ΩQ)^T ΩP)^{-1}(ΩP)^T ΩQ = A^{-1} A^T ≠ I. The later implementations in Section 3.2.3 use the correct inverse, so this appears to be a local but important error in the general proposition that should be corrected.","section":"Proposition 3.1(iv)"}],"minor_comments":[{"comment":"Typographical issues: 'Lancozs' in the abstract; 'sketch-orthgonally' in Section 3.2; 'asympototic' in Appendix A. The notation in Algorithm 2.1, line 9, 'pi = pi/√di · sign(di)' is ambiguous; parenthesize the denominator or rewrite using abs/sign.","section":"Throughout"},{"comment":"For the nonsymmetric Lanczos experiments, the sketching parameters (sketch size s and sparsity ζ) are not stated. Since the theoretical support for the sparse sign sketch is only numerical, reporting these parameters would improve reproducibility.","section":"Section 6.2"},{"comment":"The figure shows averaged and minimum sketched inner products over 100 trials. It would be useful to also report the maximum, since the anti-concentration concern is about the smallest values; however, the minimum already conveys the main point.","section":"Figure 4.1"}],"recommendation":"major_revision","confidential_remarks":"The paper is on the right track and the algorithmic/numerical core appears sound, but the revision must address: (i) the normalization bug for negative d_i, (ii) the transposition error in Proposition 3.1(iv), and (iii) the gap between Proposition 4.1 and the adaptive conditioning claim. These are all fixable within the manuscript's scope, so I do not recommend rejection. The conditioning claim should either be rigorously proved for the adaptive pivots or carefully downgraded to a heuristic, with the numerical evidence stated as such."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a genuine extension of the randomized Gram-Schmidt idea to two-sided biorthogonalization, and it deserves a serious referee. The algorithm is well derived, the cost analysis is correct, and the experiments are careful and honest. The main soft spot is a real gap between the theory and the claim it is used to support.\n\nWhat is new: Algorithm 3.1, the sketched oblique projector formalism, and the variants (rCGS, rMGS, rCGS_O) are a clean and useful extension of Balabanov and Grigori's one-sided randomized Gram-Schmidt. The cost reduction of roughly half per iteration is real, and the move to explicit oblique projection (rCGS_O2) is a nice practical contribution. Proposition 4.1 is a correct and interesting fixed-pair anti-concentration bound for Gaussian sketches, and the proof, while not optimized, checks out.\n\nThe stress-test note lands. Proposition 4.1 says that for fixed unit vectors x and y, the sketched inner product is unlikely to be tiny. But in Algorithm 3.1 the vectors q_i and p_i are functions of the same Ω used in the sketches, and the normalization factor d_i is a pivot ratio. The text nonetheless says \"the sketched inner product of any two normalized vectors q and p only has probability O(δ) of being smaller than δ,\" which reads as applying to the generated vectors. That is an adaptive statement and it is not proved. So the theoretical explanation of the improved conditioning is currently a heuristic for the actual process. This is a gap, not a contradiction: the algorithm, the cost analysis, and the numerical evidence are unaffected, and the experiments do show the conditioning improvement convincingly.\n\nOther soft spots are smaller. The sparse sign matrix is used in the experiments but the anti-concentration result is only for Gaussian; the paper acknowledges this and provides numerical evidence, so it is a limitation, not a hidden flaw. The Lanczos application loses the short-term recurrence and H_m and T_m are not similar; the authors say this plainly and show that residuals are competitive anyway. Missing code is a minor reproducibility annoyance; the experimental setup is described in enough detail to reimplement.\n\nWho this is for: anyone working on randomized Gram-Schmidt, sketched Krylov methods, or nonsymmetric Lanczos. It is a within-subfield contribution, not a paradigm shift, but a useful one.\n\nMy recommendation: send it to peer review. The sort of referee who knows randomized NLA ought to look at it, and the adaptive anti-concentration point is the thing to push on. It may need a revision to scope the theoretical claims honestly, but the core is sound.","headline":"A solid, reviewable paper that extends randomized Gram-Schmidt to biorthogonalization; the conditioning story is partly heuristic because the anti-concentration bound is proved for fixed vectors, not the adaptive ones the algorithm actually builds.","tokens_in":25674,"tokens_out":2318,"would_cite":true,"duration_ms":23746,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F25","65F15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Randomizing two-sided Gram-Schmidt by enforcing biorthogonality after sketching cuts the cost roughly in half and, in the paper's numerical experiments, yields better-conditioned bases.","keywords":["randomized biorthogonalization","two-sided Gram-Schmidt","sketched oblique projectors","subspace embeddings","anti-concentration","condition number","nonsymmetric Lanczos"],"falsifier":"Take the paper's sparse sign sketch with zeta = min(s,8) and two fixed unit vectors x != y with <x,y> = 0; estimate P(|<Omega x, Omega y>| <= delta) over many draws for delta = 10^-2 and 10^-3 and compare with the Gaussian bound O(s delta). More decisively, run Algorithm 3.1 on matrices whose deterministic two-sided Gram-Schmidt produces near-breakdowns, such as the ill-conditioned example of Section 6.1.1, with many independent sparse sign sketches; if the condition numbers of Q and P grow at the same rate as deterministic CGS or MGS, or if tiny sketched inner products occur with probability","tokens_in":24741,"feed_emoji":"🧮","tokens_out":8671,"duration_ms":77772,"temperature":0.7,"pith_summary":"This paper proposes a randomized variant of the two-sided Gram-Schmidt process, the algorithm that takes two matrices X and Y and produces bases Q and P with the same column spaces and Q^T P = I. The variant replaces the exact biorthogonality condition with a much cheaper sketched condition: for a random sketching matrix that approximately preserves inner products, it asks that (Omega Q)^T (Omega P) = I. Because the sketched vectors are shorter, each orthogonalization step costs roughly half as much; because sketched inner products of two distinct unit vectors are, with high probability, not close to zero, the algorithm rarely encounters the near-breakdowns that make deterministic bases ill-conditioned. The paper proves this anti-concentration fact for Gaussian sketches, shows numerically it holds for sparse sign and other sketches, reports experiments where randomized bases have substantially smaller condition numbers, and demonstrates a nonsymmetric Lanczos variant with comparable eigenvalue residual convergence.","feed_headline":"Sketching makes biorthogonal bases cheaper, often better conditioned","feed_subtitle":"Enforcing biorthogonality on sketched vectors makes the bases better conditioned at about half the cost.","key_machinery":"The load-bearing object is the sketched oblique projector, which projects onto range(Q) while making the residual sketch-orthogonal to range(P); when the bases are sketch-biorthogonal it simplifies to Q (Omega P)^T Omega. Algorithm 3.1 subtracts this projector from each new column, mirroring deterministic two-sided Gram-Schmidt but with sketched inner products. The second mechanism is the anti-concentration estimate of Proposition 4.1, which shows that for Gaussian sketches two distinct unit vectors have sketched inner product near zero with probability O(s delta), so the normalization step d_i = <Omega q_i, Omega p_i> is unlikely to be tiny. This pair of ingredients converts a worst-case in","core_discovery":"On the paper's own terms, the central discovery is that sketch-biorthogonality is a viable substitute for exact biorthogonality. Algorithm 3.1 computes Q and P with range(Q)=range(X), range(P)=range(Y), and (Omega Q)^T (Omega P)=I, where Omega is an epsilon-subspace embedding; when the sketch is cheap to apply, this halves the per-iteration arithmetic cost because inner products are evaluated in s dimensions instead of n. The sharper point is Proposition 4.1: for a Gaussian Omega and unit vectors x != y, the probability that |<Omega x, Omega y>| <= delta is at most 202 s delta. Thus two distinct sketched vectors are very unlikely to be almost orthogonal, even if x and y themselves are orthog","pith_inferences":["The paper proves anti-concentration only for Gaussian sketches, yet the experiments use sparse sign matrices; if a proof for sparse sign, or a counterexample, were found, the practical claim about conditioning would be placed on the same footing as the algorithmic claim. This is the most direct testable extension.","Sketching may act as a regularizer rather than only a speed-up: the paper's Figure 4.1 indicates that even orthogonal vectors become non-orthogonal after sketching, so any basis pair headed for near-breakdown might be made safer by working in sketch coordinates.","In the randomized Lanczos method, the two Hessenberg matrices are no longer transposes and their eigenvalue sets can differ; the paper's experiments show comparable residual convergence for leading eigenvalues, leaving open how to reconcile or select between the two Ritz spectra when they disagree.","The characteristic-polynomial optimality result hints that the randomized method's convergence could be analyzed by minimal-residual polynomial arguments in the sketched norm, though the paper does not develop such a theory."],"forward_implications":["With a sparse sign sketch costing O(zeta n) per application, each iteration of the randomized classical or modified Gram-Schmidt variant costs about 2 n i + 2 s i + zeta n instead of 4 n i, so about half the deterministic cost for the same n; the saved budget can buy a second pass with better stability.","Because |<Omega x, Omega y>| is unlikely to be below delta for Gaussian Omega, the normalization constants in Algorithm 3.1 are unlikely to be tiny, and consequently the condition numbers of the computed bases do not explode; the paper's ill-conditioned experiment shows cond(Q) falling from roughly 10^9 to 10^17 down to about 10^5 for the stabilized randomized variants.","The best practical variant is the randomized classical Gram-Schmidt with explicit oblique projection run twice, which matched the most accurate methods and was faster; a mixed-precision version of it is fastest but loses about nine orders of magnitude in the decomposition error on the ill-conditioned test.","In the nonsymmetric Lanczos setting, full randomized sketch-biorthogonalization of the Krylov bases removes the short-term recurrence, but since deterministic Lanczos needs full re-biorthogonalization anyway, the randomized method is competitive; its Hessenberg matrix satisfies a characteristic-polynomial optimality condition with respect to the sketched norm, and the experiments show residuals co"],"supporting_citations":[{"why":"Supplies the randomized single-sided Gram-Schmidt method and the ill-conditioned test matrices that the two-sided algorithm extends.","marker":"[4]"},{"why":"Establishes that the sparse sign matrix is an oblivious epsilon-subspace embedding, justifying its use as the recommended sketch.","marker":"[9]"},{"why":"Gives the density of the product of correlated Gaussian variables used in the proof of Proposition 4.1.","marker":"[25]"},{"why":"Provides the nonsymmetric Lanczos theory and the polynomial optimality argument reused in Proposition 5.1.","marker":"[33]"},{"why":"Recommends the sparsity parameter zeta = min(s,8) for the sparse sign sketch used in the experiments.","marker":"[34]"},{"why":"Supplies the subspace-embedding singular-value bounds used to monitor the condition number of sketched bases.","marker":"[35]"}],"fun_headline_variants":["Sketch-based biorthogonalization: half cost, better conditioning","Randomized two-sided Gram-Schmidt: cheaper, stabler bases","Sketched biorthogonality: cost halved, conditioning improved","Biorthogonalize via sketches: cheaper, often better","Sketching replaces exact biorthogonality: half cost, better conditioning"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The practical advantage in conditioning rests on the unlikelihood of near-orthogonal sketched vectors, which Proposition 4.1 proves only for Gaussian sketches; the sparse sign matrix recommended and used in the experiments is supported only numerically, so the paper's better-conditioned claim is a heuristic for the sketch actually deployed.","fun_headline_variants_meta":{"raw":{"variants":["Sketch-based biorthogonalization: half cost, better conditioning","Randomized two-sided Gram-Schmidt: cheaper, stabler bases","Sketched biorthogonality: cost halved, conditioning improved","Biorthogonalize via sketches: cheaper, often better","Sketching replaces exact biorthogonality: half cost, better conditioning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000543,"raw_usage":{"total_tokens":2451,"prompt_tokens":775,"completion_tokens":1676,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":519,"completion_tokens_details":{"reasoning_tokens":1580}},"tokens_in":519,"tokens_out":1676,"duration_ms":11921,"temperature":1.0,"reasoning_tokens":1580,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T10:13:01.878577+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the paper's sparse sign sketch with zeta = min(s,8) and two fixed unit vectors x != y with <x,y> = 0; estimate P(|<Omega x, Omega y>| <= delta) over many draws for delta = 10^-2 and 10^-3 and compare with the Gaussian bound O(s delta). More decisively, run Algorithm 3.1 on matrices whose deterministic two-sided Gram-Schmidt produces near-breakdowns, such as the ill-conditioned example of Section 6.1.1, with many independent sparse sign sketches; if the condition numbers of Q and P grow at the same rate as deterministic CGS or MGS, or if tiny sketched inner products occur with probability","supporting_citations":[{"cited_title":"Balabanov and L","cited_arxiv_id":null,"evidence_quote":"Supplies the randomized single-sided Gram-Schmidt method and the ill-conditioned test matrices that the two-sided algorithm extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes that the sparse sign matrix is an oblivious epsilon-subspace embedding, justifying its use as the recommended sketch."},{"cited_title":"Nadarajah and T","cited_arxiv_id":null,"evidence_quote":"Gives the density of the product of correlated Gaussian variables used in the proof of Proposition 4.1."},{"cited_title":"Saad , Numerical Methods for Large Eigenvalue Problems , Society for Industrial and Applied Mathematics,","cited_arxiv_id":null,"evidence_quote":"Provides the nonsymmetric Lanczos theory and the polynomial optimality argument reused in Proposition 5.1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Recommends the sparsity parameter zeta = min(s,8) for the sparse sign sketch used in the experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the subspace-embedding singular-value bounds used to monitor the condition number of sketched bases."}],"review_version":1}