{"id":"8da8c5b8-a96c-4498-8f7c-d906331d5644","arxiv_id":"2508.05400","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"The randomized Krylov-Schur algorithm computes a few eigenpairs of large nonsymmetric matrices with consistent 2-4x speedups over deterministic eigensolvers and adds a deflation step with backward error bounds.","lead":"A new randomized eigensolver, rKS, finds a few important eigenvalue-vector pairs of huge matrices two to four times faster than standard methods, using cheap randomized orthogonalization. It also locks in already-found solutions to keep computing further ones, and the paper proves the method matches the convergence of prior randomized Arnoldi approaches.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Fixed sparse-sign sketch (d=2m, ζ=8) has no guarantee or runtime check of the ε-embedding hypothesis for the polynomial-filtered subspaces reached during restarts, so Algorithm 2's sketch-orthogonalization, the Eq. (4.9) residual estimates, and Theorem 4.2's bounds can fail silently.","rationale":"I read the paper's central claims as (1) rKS inherits rIRA's polynomial-filtering convergence via the exact-arithmetic equivalence of Theorem 3.1, and (2) deflation has a backward error controlled by Theorem 4.2. I checked the algebra of Theorems 2.2, 3.1, and 4.2 carefully. The equivalence proof is sound in exact arithmetic: the transformation arguments preserve span, the similarity W is orthonormal, and the Schur-vector span argument for the contraction step goes through. I also examined the deflation coupling subtlety: an active-block Ritz pair closed under the deflated operator A_q is not itself an eigenvector of A; however, after Schur reordering it is absorbed into the locked block, and the Ritz vectors of the locked T_qq (which mix the locked vectors) genuinely satisfy the residual bound (4.32) via the coefficient of u_{k+1}. So Theorem 4.2 is internally consistent, provided the ε-embedding hypothesis holds for the relevant subspace. That is the linchpin: every residual bound in Section 4.1 and every norm bound in Theorem 4.2 reduces to the ε-embedding property for the current subspace, and the paper only ever assumes this per cycle (Remark 1) without establishing it for the concrete sketch parameters used in the implementation, across the evolving filtered subspaces. The Section 3.3 whitening step fixes orthogonality drift of S but cannot fix the more fundamental failure where Ω distorts a direction of the current Krylov subspace. The numerical sections also never compare the Eq. (4.9) estimate to true residuals computed exactly, and never exercise the deflation procedure, so both the correctness hypothesis and the headline 'practical deflation' claim are empirically unverified. My concern therefore reinforces the reader's CONDITIONAL verdict; the concrete test monitors sketch distortion and true residuals across restarts and independent draws to settle whether the concern lands in practice.","tokens_in":27118,"tokens_out":51586,"duration_ms":509341,"concrete_test":"Re-run the Section 5.2 experiments (Table 2 matrices) with the same d=2m, ζ=8 sketch, and (i) at every restart compute the exact distortion of Ω on the current Krylov basis U, i.e., the extreme singular values of S=ΩU, checking whether σ_max/σ_min stays within the ε=1/√2 band [√(1−ε), √(1+ε)]; (ii) replace the Eq. (4.9) estimate by the exactly computed residual ‖Ax̃−λ̃x̃‖/‖Ax̃‖ for each claimed converged pair; (iii) repeat over, say, 20 independent draws of Ω. If for any draw and any restart the singular-value band is violated, or the true/estimated residual ratio exceeds √((1+ε)/(1−ε))≈2.4, the central hypothesis fails in the claimed regime. A companion analytic check: instantiate the sharpest available sparse-sign OSE guarantee for subspace dimension m, ε=1/√2, ζ=8, and compare the required d against the used d=2m.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Definition 1.1 and Remark 1 fix a single subspace K_{k+p+1}; every factorization in Section 2 is built under the hypothesis that Ω is an ε-embedding for that subspace. Algorithm 1 reuses one fixed Ω across all restarts, yet each restart produces a new polynomial-filtered subspace ψ(A)K (Section 3.2). The paper never upgrades the per-cycle hypothesis to an oblivious-subspace-embedding guarantee for the actual parameter regime (d=2m, ζ=8, ε≈1/√2, Section 5), nor gives a failure probability for the fixed sketch remaining an ε-embedding for every subspace encountered. The failure mode is concrete. In Algorithm 2 lines 7–8, if the current subspace contains a direction nearly annihilated by Ω, β_{j+1}=‖Ωu~_{j+1}‖ can be tiny while ‖u~_{j+1}‖ is O(1), so the normalized u_{j+1}=u~/β has huge ℓ2 norm, S=ΩU drifts from orthonormal, κ(S) grows, and U becomes ill-conditioned. The convergence test then uses Eq. (4.9), whose intermediate identities (4.7)–(4.8) assume ‖Ωu_{k+1}‖=1 and ‖ΩU_k y‖=‖y‖ exactly; both fail when S loses orthonormality, so estimated residuals no longer bound true residuals. Theorem 4.2 inherits the same failure: Eq. (4.27) uses ‖u_{k+1}‖≤1/√(1−ε), an ε-embedding inequality applied to a vector in a subspace for which the embedding was never verified. The Section 3.3 re-orthogonalization repairs loss of orthogonality of S but not loss of the embedding property, so it cannot detect or fix the failure. The experiments (Figs. 3–7) report residuals only through the Eq. (4.9) estimate and never validate against exactly computed residuals, so no evidence is presented that the hypothesis holds in the claimed operating regime.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a randomized Krylov-Schur eigensolver (rKS) for computing a small number of eigenpairs of large nonsymmetric matrices. It defines sketch-orthonormal Krylov(-Schur) decompositions, proves their equivalence to randomized Arnoldi factorizations, and shows that one rKS cycle is equivalent to the randomized Implicitly Restarted Arnoldi method, so that polynomial-filtering convergence transfers. It then derives residual estimators and a deflation procedure for converged eigenpairs, with backward-error bounds in Theorem 4.2, and reports numerical experiments on synthetic and SuiteSparse matrices showing 2--4x speedups over deterministic IRA/KS.","tokens_in":27646,"tokens_out":11753,"duration_ms":148086,"significance":"If the claims hold, the paper provides a simple, scalable randomized eigensolver with a plausible theoretical justification for convergence and deflation. The algebraic framework is clean and the sketch-orthonormal decomposition viewpoint is a natural extension of Stewart's Krylov-Schur framework. The main positive elements are the explicit factorization equivalences, the use of Schur reordering instead of shifted QR, and the experimental demonstration of consistent speedups on large sparse problems. However, the central guarantees are conditional on an epsilon-embedding hypothesis that the implemented algorithm does not verify, and the deflation backward-error theorem contains a real-diagonalization step that is not valid for real Schur forms with 2-by-2 blocks.","major_comments":[{"comment":"The proof of Theorem 4.2 assumes an eigendecomposition T_qq W = W D with a real diagonal D (equivalently, real eigenvectors forming a basis). But T_qq is a block upper-triangular real Schur form with 1-by-1 and 2-by-2 diagonal blocks. A 2-by-2 block such as [[0,-1],[1,0]] has no real diagonalization, and even a triangular block with repeated real eigenvalues can be defective. Consequently the claimed existence of real unit vectors Z and a real diagonal D satisfying the bound in eq. (4.33) is not established for the general stated setting. This is load-bearing for the subspace-deflation contribution. The theorem should be restated either for Schur vectors (block-diagonal D), over the complex field, or under an explicit diagonalizability assumption.","section":"Section 4.4, Theorem 4.2"},{"comment":"All theoretical results are conditional on Omega being an epsilon-embedding for each Krylov subspace encountered, but the implementation uses one fixed sparse-sign sketch with d=2m, zeta=8 and no verification that the embedding property holds for the polynomial-filtered subspaces produced across restarts. The paper gives no oblivious-subspace-embedding guarantee for this parameter regime and no failure probability for the union of subspaces seen by the algorithm. This is not merely a formal gap: if at some restart the current subspace contains a direction nearly annihilated by Omega, then in Algorithm 2 line 8 beta_{j+1} can be tiny while ||u~_{j+1}|| is O(1), so u_{j+1} has huge norm. The sketched basis S remains orthonormal by construction, but U becomes ill-conditioned, and the residual estimator in eq. (4.9) and the deflation bound in eq. (4.32) can fail silently because they rely on","section":"Definition 1.1 / Remark 1, Section 5, and Theorem 4.2"}],"minor_comments":[{"comment":"The expression 'U_{j+1} = (U_j u_{k+p+1} = ...)' contains an index typo; it should be 'u_{j+1}'.","section":"Algorithm 2, line 9"},{"comment":"The caption says 'The execution times for each method are reported in Fig. 7'; this should refer to Fig. 6.","section":"Figure 7 caption"},{"comment":"The text refers to 'line 4 of Algorithm 2' for deflated sketch-orthogonalization. In Algorithm 2, line 4 is w_j = A u_j, while the projection is performed in line 6. Please update the reference.","section":"Section 4.2"},{"comment":"Equation (4.9) is presented as a bound but uses the approximation ||Omega(A x~)|| ~= |lambda|. This is an estimate rather than a rigorous inequality unless ||A x~|| ~= |lambda| ||x~|| is justified. It would be clearer to state it as a heuristic and to base convergence certificates on the exact bound in eq. (4.10) or on true residuals.","section":"Section 4.1, eq. (4.9)"},{"comment":"The notation ||E|K||_{F,2} is nonstandard and ambiguous. Define the norm of the restriction of E to K explicitly.","section":"Theorem 4.2, eq. (4.34)"},{"comment":"Corollary 1.0.1 should be numbered as Corollary 1.1; the current numbering is unusual.","section":"Section 1.1"}],"recommendation":"major_revision","confidential_remarks":"The conditional theory is mostly coherent, and the numerical results are promising, but the two major issues are both in the scope of the paper's main claims: the real-diagonalization step in Theorem 4.2 is mathematically incorrect for the stated real Schur setting, and the practical algorithm does not verify the epsilon-embedding hypothesis on which the residual and deflation guarantees rest. Both issues appear patchable (restating the theorem via Schur forms, and adding a verification/probabilistic argument or a clear caveat), so I would not reject the manuscript, but a major revision is needed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper does two things well. First, it extends Stewart's deterministic Krylov-Schur to a randomized setting with sketch-orthonormal bases, defining a clean factorization framework and proving that one rKS cycle is equivalent to one rIRA cycle. Second, it gives a backward-error analysis for deflation that is transparent and does not rely on fitted constants. The experiments are also honest: rKS is consistently 2-4x faster than IRA and deterministic KS on synthetic and SuiteSparse matrices, and the iteration counts are reported, not hidden. That is real evidence the method works in practice.\n\nThe soft spots are real but not fatal. The stress-test note is on point: the theory assumes Omega is an epsilon-embedding for each Krylov subspace, but the implementation uses a fixed sparse-sign sketch with d=2m and never checks whether the embedding actually holds for the polynomial-filtered subspaces that appear after restarts. The convergence test and the deflation bounds both rely on estimates from eq. (4.9) and Theorem 4.2, which assume sketch-orthonormality and the embedding property. If the sketch degrades, the residual estimates can be wrong and the algorithm could declare convergence spuriously. The paper does not validate its residual estimator against exactly computed residuals, so we have no evidence about whether this is a real risk or a theoretical one. That is the main thing I would want a referee to push on.\n\nTwo smaller gaps: the deflation procedure, which is a headline contribution, is never exercised in numerical experiments; and no code or data are released, so the timing claims are not reproducible. The citation pattern looks fine; the paper builds on the authors' own rIRA and on randomized Gram-Schmidt, and the self-citation is appropriate.\n\nWho is this for? Researchers in randomized numerical linear algebra and practitioners who need a fast nonsymmetric eigensolver. It is not groundbreaking, but it is a solid algorithmic contribution with a convincing speedup story. I would send it to peer review with the expectation of revision: validate residuals against true residuals, test deflation, and ideally release code. The central argument holds up; the paper deserves a serious referee.","headline":"A genuinely useful randomized Krylov-Schur with sound algebra and real speedups, but the embedding assumption is unchecked and the headline deflation is never tested.","tokens_in":28142,"tokens_out":2211,"would_cite":true,"duration_ms":25675,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F15","65F25","65F50","15B52"],"pacs":[],"model":"deepseek-v4-flash","headline":"Randomized Krylov-Schur eigensolver computes a few eigenpairs of large nonsymmetric matrices 2–4x faster than deterministic restarted methods, with comparable accuracy.","keywords":["eigenvalue problem","randomized Krylov-Schur","sketching","deflation","nonsymmetric matrices","Krylov subspace methods","Schur form","randomized linear algebra"],"falsifier":"Run rKS on a matrix with a clustered spectrum that forces many restarts, using the recommended sparse-sign sketch with d = 2m. If, before convergence, the condition number of the stored sketch S_k grows beyond a fixed factor, or the ratio between the true residual $\\|A\\tilde x - \\tilde\\lambda \\tilde x\\|/\\|A\\tilde x\\|$ and the estimate $|b^T y|/|\\tilde\\lambda|$ exceeds $\\sqrt{(1+\\varepsilon)/(1-\\varepsilon)} \\approx 2.4$, then the ε-embedding assumption is violated for that run.","tokens_in":27019,"feed_emoji":"⚡","tokens_out":8257,"duration_ms":84200,"temperature":0.7,"pith_summary":"This paper introduces randomized Krylov-Schur (rKS), a restarted eigensolver for large sparse nonsymmetric matrices when only a small set of eigenpairs is wanted. The method works by sketching the Krylov basis into a low-dimensional space, performing orthonormalization and Rayleigh-Ritz there, and restarting with stable reordering of a Schur form instead of implicitly shifted QR. The authors prove that after each restart rKS produces the same Krylov spans as randomized Implicitly Restarted Arnoldi, so it inherits that method's polynomial-filtering convergence. They also prove a backward error bound for deflating converged eigenpairs, which lets the solver lock them and continue for the rest of the spectrum. The payoff is a simple implementation that runs 2 to 4 times faster in experiments than deterministic IRA and Krylov-Schur while finding the same eigenvalues.","feed_headline":"Randomized eigensolver finds eigenpairs 2–4x faster","feed_subtitle":"Schur reordering and sketched bases cut restart cost while keeping accuracy on million-row matrices.","key_machinery":"The engine of the method is the randomized $\\varepsilon$-embedding—a matrix $\\Omega\\in\\mathbb{R}^{d\\times n}$ that approximately preserves norms on a $k$-dimensional subspace—used to define sketch-orthonormal bases, for which $(\\Omega U_k)^T(\\Omega U_k)=I_k$. Orthogonalization, Rayleigh-Ritz, residual estimation, and the deflation projector $P^\\Omega_{U_q}=U_q(\\Omega U_q)^\\dagger\\Omega$ all act on the sketch $S=\\Omega U$ or in the small space $\\mathbb{R}^d$, while the full-space vectors are updated by cheap triangular solves. This keeps per-iteration cost low, and the Schur form of the small Rayleigh quotient $T_k$ provides the stable reordering mechanism that replaces shifted QR for restart","core_discovery":"The central object is the sketch-orthonormal Krylov-Schur decomposition\n$$AU_k = U_k T_k + u_{k+1} b_k^T,$$\nwhere $(U_k,u_{k+1})$ is orthonormal after multiplication by a random $\\varepsilon$-embedding $\\Omega$ and $T_k$ is block upper-triangular (Definition 2.4). The paper shows that every Krylov decomposition is equivalent to a randomized Arnoldi factorization in the sense of spanning the same space (Theorem 2.2), and that one cycle of rKS—expand to length $k+p$, reorder the Schur form, truncate—produces the same subspace as one cycle of rIRA with the same shifts (Theorem 3.1). It then shows that a converged eigenpair can be locked by zeroing the corresponding entries of $b$; if those entr","pith_inferences":["The authors leave implicit that the probabilistic guarantee on $\\Omega$ suggests a practical safeguard: monitoring the condition number of the stored sketch $S_k$ during restarts and re-drawing or enlarging the embedding if it degrades.","Since the residual estimate (4.9) approximates $\\|A\\tilde x\\|$ by $|\\tilde\\lambda|\\,\\|\\tilde x\\|$, it is weakest for smallest-modulus targets; the exact bound (4.10) avoids that approximation and would be the safer convergence test for smallest-modulus eigenproblems.","The convergence spikes seen in the residual plots hint that randomization can temporarily disturb the approximate eigenvalues; if confirmed more broadly, it may explain both the sometimes-fewer iterations and the need for a slightly relaxed deflation threshold.","The backward-error bound grows like $\\sqrt{q}\\,\\eta$, so if the number of locked vectors $q$ is large, the threshold $\\eta$ may need to shrink to keep the perturbed problem faithful."],"forward_implications":["rKS inherits the polynomial-filtering convergence of randomized IRA because each restart cycle yields the same Krylov subspace spans (Theorem 3.1).","A converged eigenpair can be locked when its $|b_i|$ entry is below $\\eta$; the remaining computation runs on a perturbed operator whose restriction to the active Krylov space has error bounded by $\\sqrt{q}\\sqrt{(1+\\varepsilon)/(1-\\varepsilon)}\\,\\eta$ (Theorem 4.2).","In numerical experiments on synthetic and real sparse matrices, rKS is 2–4 times faster than deterministic IRA and Krylov-Schur, finds the same eigenvalues, and often needs the fewest restarts.","Because the sketch $S$ is stored and updated, the contraction and expansion steps operate in dimension $d\\ll n$, so the method scales to matrices with millions of rows.","The method is less sensitive to the ratio between Krylov dimension and number of wanted eigenvalues, easing the choice of subspace size."],"supporting_citations":[{"why":"Introduces the deterministic Krylov-Schur algorithm, Krylov decompositions, and the Schur-reordering restart framework that rKS extends.","marker":"[Ste02b]"},{"why":"Defines randomized Implicitly Restarted Arnoldi; Theorem 3.1 proves rKS spans equal rIRA spans, transferring convergence properties.","marker":"[dDG24]"},{"why":"Provides Randomized Gram-Schmidt and the singular-value preservation result used to keep sketch-orthonormal bases well-conditioned.","marker":"[BG22]"},{"why":"Supplies the sketch Rayleigh-Ritz residual bound and whitening strategy behind eq. (4.9) and the re-orthogonalization procedure.","marker":"[NT24a]"},{"why":"Documents the forward instability of implicit shifted QR restarts and the deflation strategies that motivate the Schur-based approach.","marker":"[LS95]"},{"why":"Is the source of the $\\varepsilon$-embedding definition and the oblivious subspace embedding guarantees assumed throughout.","marker":"[Woo14]"},{"why":"Describes sparse sign embeddings and the $d=O(k/\\varepsilon^2)$ trade-off; the implementation uses $d=2m$ and $\\varepsilon\\approx 1/\\sqrt{2}$.","marker":"[MT20]"},{"why":"Supplies the locking/deflation framework and the Schur-vector convergence criterion on which Section 4 builds.","marker":"[Kre05]"}],"fun_headline_variants":["Randomized Krylov-Schur: scalable eigenpairs with deflation","Sketch-orthogonalization makes eigensolver fast and stable","Deflation technique locks converged eigenpairs in rKS","Simple randomized eigensolver for large-scale spectra","Random embeddings speed up Krylov-Schur eigensolving"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"The argument assumes that the fixed random sketching matrix Ω remains an ε-embedding for the Krylov subspace at every restart; in the implementation this is only guaranteed with high probability, and if it fails the sketched basis becomes ill-conditioned, so the residual estimates and deflation error bounds no longer hold.","fun_headline_variants_meta":{"raw":{"variants":["Randomized Krylov-Schur: scalable eigenpairs with deflation","Sketch-orthogonalization makes eigensolver fast and stable","Deflation technique locks converged eigenpairs in rKS","Simple randomized eigensolver for large-scale spectra","Random embeddings speed up Krylov-Schur eigensolving"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000961,"raw_usage":{"total_tokens":3888,"prompt_tokens":658,"completion_tokens":3230,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":402,"completion_tokens_details":{"reasoning_tokens":3145}},"tokens_in":402,"tokens_out":3230,"duration_ms":24858,"temperature":1.0,"reasoning_tokens":3145,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T23:22:29.718638+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run rKS on a matrix with a clustered spectrum that forces many restarts, using the recommended sparse-sign sketch with d = 2m. If, before convergence, the condition number of the stored sketch S_k grows beyond a fixed factor, or the ratio between the true residual $\\|A\\tilde x - \\tilde\\lambda \\tilde x\\|/\\|A\\tilde x\\|$ and the estimate $|b^T y|/|\\tilde\\lambda|$ exceeds $\\sqrt{(1+\\varepsilon)/(1-\\varepsilon)} \\approx 2.4$, then the ε-embedding assumption is violated for that run.","supporting_citations":[],"review_version":1}