pith. sign in

arxiv: 2606.18073 · v1 · pith:5FDMOA35new · submitted 2026-06-16 · 🧮 math.NA · cs.NA

A Sketched Generalized Krylov Subspace Method for Large-Scale Regularization

Davide Palitta , Mirjeta Pasha This is my paper

Pith reviewed 2026-06-26 23:50 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords sketched Krylov methodsgeneralized Krylov subspaceTikhonov regularizationlarge-scale inverse problemsiterative regularizationsketchingQR factorizationreorthogonalization
0
0 comments X

The pith

The sketched generalized Krylov subspace method produces the same iterates as standard GKS while replacing full QR factorizations with compressed rank-one updates and skipping reorthogonalization.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper develops sGKS as a sketched variant of the generalized Krylov subspace method for large-scale Tikhonov regularization with a general regularization matrix. It establishes that the QR factorizations can be performed on compressed matrices updated incrementally and that explicit reorthogonalization can be omitted entirely because the method steps do not depend on basis orthogonality. A sympathetic reader would care because these modifications reduce the two main per-iteration costs in expanding the subspace, while the paper proves that the resulting iterates remain identical to those of the original method when sketching is not used in the solve and that residual norms stay quasi-optimal when it is.

Core claim

The central claim is that sGKS preserves the approximation quality of GKS: in the absence of sketching in the projected solve the iterates are identical, the sketched projected solve yields quasi-optimal residual norms controlled by the embedding quality, and a small number of iterative refinement steps recovers the full accuracy of the unsketched method for more challenging problems. The algorithm is independent of the choice of sketching operator.

What carries the argument

Incremental rank-one updates to compressed QR factorizations of the projected forward and regularization operators, combined with an optional sketched projected solve that replaces full reorthogonalization.

If this is right

  • When sketching is omitted from the projected solve, sGKS generates exactly the same sequence of iterates as standard GKS.
  • The sketched projected solve produces residual norms that remain quasi-optimal and are controlled by the quality of the embedding.
  • A small number of iterative refinement steps in the projected solve restores the spectral properties of the basis and recovers the accuracy of the unsketched method.
  • The overall algorithm remains independent of the particular sketching operator that is chosen.
  • On image deblurring, X-ray CT, seismic tomography and dynamic CT problems the method matches the reconstruction quality of GKS at substantially lower per-iteration cost.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same sketching-plus-skipped-reorthogonalization pattern may apply directly to other projection methods whose steps do not require an orthogonal basis.
  • When the embedding is of sufficiently high quality the refinement step can be omitted, opening the method to even larger problem sizes.
  • Because the approach does not depend on a specific sketching distribution it can be combined with any existing random-projection library without further theoretical adjustment.

Load-bearing premise

No step of the generalized Krylov subspace method relies intrinsically on the orthogonality of the basis vectors.

What would settle it

A concrete numerical counter-example in which, with no sketching applied to the projected solve, the sequence of sGKS iterates differs from the sequence produced by standard GKS on the same starting data.

read the original abstract

The generalized Krylov subspace (GKS) method is an effective projection technique for large-scale Tikhonov regularization with a general regularization matrix. As the subspace expands, however, two computational bottlenecks limit scalability: the thin QR factorizations of the tall projected matrices formed by the forward operator and the regularization matrix applied to the basis, and the full reorthogonalization of each new basis vector against all previous columns. We propose a sketched variant, named sGKS, that addresses both bottlenecks. The QR factorizations are performed on compressed matrices of much smaller row dimension, maintained incrementally via rank-one updates. Moreover, we observe that explicit reorthogonalization can be skipped entirely without compromising the quality of the approximation subspace, since no step of GKS relies intrinsically on the orthogonality of the basis. The resulting algorithm is independent of the choice of sketching operator and preserves the approximation quality of the original method: we show that, in the absence of sketching in the projected solve, sGKS produces iterates identical to those of standard GKS, and that the sketched projected solve delivers quasi-optimal residual norms controlled by the embedding quality. For more challenging problems where the loss of basis orthogonality becomes significant, we show that incorporating a small number of iterative refinement steps in the projected solve restores the spectral properties of the basis and recovers the full accuracy of the unsketched method. Numerical experiments on image deblurring, X-ray computerized tomography, seismic travel-time tomography, and dynamic computerized tomography demonstrate that sGKS matches the reconstruction quality of standard GKS while significantly reducing per-iteration costs and overall wall-clock time.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper introduces sGKS, a sketched variant of the generalized Krylov subspace method for large-scale Tikhonov regularization with a general regularization matrix L. It compresses the tall projected matrices via sketching for incremental QR updates and skips explicit reorthogonalization of basis vectors, claiming that (i) without sketching in the projected solve sGKS produces iterates identical to standard GKS, (ii) the sketched solve yields quasi-optimal residual norms controlled solely by embedding quality, and (iii) a few iterative refinement steps recover full accuracy when orthogonality loss becomes significant. These claims are supported by theoretical arguments and numerical results on four tomography-style test problems.

Significance. If the central claims hold, sGKS would provide a practical, lower-cost alternative to GKS for large-scale inverse problems while preserving reconstruction quality and being independent of the specific sketching operator. The incremental rank-one update strategy and the refinement recovery mechanism are potentially useful algorithmic contributions for scalable regularization.

major comments (3)
  1. [Abstract] Abstract and the paragraph beginning 'We observe that explicit reorthogonalization...': The load-bearing claim that 'no step of GKS relies intrinsically on the orthogonality of the basis' is stated as an observation rather than derived from the Arnoldi-like relation or the thin-QR construction on the stacked blocks (A V_k, L V_k). In the generalized setting the basis is generated by repeated applications of A and L (or inverses), so loss of orthogonality can change the numerical range of the projected blocks and the spectrum of the reduced Tikhonov problem; without an explicit invariance proof or counter-example analysis the exact equivalence asserted for the unsketched case is not established.
  2. [Abstract] The quasi-optimality paragraph: The statement that 'the sketched projected solve delivers quasi-optimal residual norms controlled by the embedding quality' is asserted without a concrete bound relating the embedding distortion to the residual norm or to the choice of sketching dimension; this makes it impossible to verify a priori when the sketched solve remains quasi-optimal for a given problem.
  3. [Numerical experiments] Numerical experiments section (tomography examples): The reported wall-clock savings and matching reconstruction quality are shown, but no quantitative metric (e.g., loss of orthogonality measured by ||V_k^T V_k - I|| or deviation of the projected operator spectrum) is given to identify the regime where refinement becomes necessary, weakening the claim that refinement recovers full accuracy for 'more challenging problems'.
minor comments (2)
  1. Notation for the sketching operator and the compressed matrices should be introduced once with a clear definition of dimensions before the algorithmic description.
  2. The abstract mentions four test problems; the corresponding figure captions or table should explicitly list the regularization matrix L used in each case.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We appreciate the referee's detailed review and valuable suggestions for improving the manuscript. We address each of the major comments below and plan to incorporate revisions accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract and the paragraph beginning 'We observe that explicit reorthogonalization...': The load-bearing claim that 'no step of GKS relies intrinsically on the orthogonality of the basis' is stated as an observation rather than derived from the Arnoldi-like relation or the thin-QR construction on the stacked blocks (A V_k, L V_k). In the generalized setting the basis is generated by repeated applications of A and L (or inverses), so loss of orthogonality can change the numerical range of the projected blocks and the spectrum of the reduced Tikhonov problem; without an explicit invariance proof or counter-example analysis the exact equivalence asserted for the unsketched case is not established.

    Authors: We thank the referee for pointing this out. While the manuscript asserts that sGKS produces identical iterates to GKS without sketching in the projected solve, we agree that a more rigorous derivation is needed. In the revised version, we will add a subsection deriving the invariance from the structure of the GKS method, showing that the projected Tikhonov problem depends only on the column space of the basis matrix V_k rather than its specific orthogonalization, using the properties of the thin QR factorization on the stacked matrices. This will establish the equivalence explicitly. revision: yes

  2. Referee: [Abstract] The quasi-optimality paragraph: The statement that 'the sketched projected solve delivers quasi-optimal residual norms controlled by the embedding quality' is asserted without a concrete bound relating the embedding distortion to the residual norm or to the choice of sketching dimension; this makes it impossible to verify a priori when the sketched solve remains quasi-optimal for a given problem.

    Authors: We acknowledge the need for a more precise statement. The quasi-optimality follows from standard results in randomized linear algebra for sketched least-squares problems, where if the sketching matrix satisfies the (1+ε)-subspace embedding property, the residual norm is bounded by a factor of (1+ε) times the optimal residual. In the revision, we will include an explicit reference to the relevant theorem (e.g., from Woodruff's survey or Drineas et al.) and specify how the sketching dimension m relates to ε via the Johnson-Lindenstrauss lemma or matrix concentration bounds, allowing a priori verification. revision: yes

  3. Referee: [Numerical experiments] Numerical experiments section (tomography examples): The reported wall-clock savings and matching reconstruction quality are shown, but no quantitative metric (e.g., loss of orthogonality measured by ||V_k^T V_k - I|| or deviation of the projected operator spectrum) is given to identify the regime where refinement becomes necessary, weakening the claim that refinement recovers full accuracy for 'more challenging problems'.

    Authors: We agree that providing quantitative metrics would better support the claims about when refinement is needed. In the revised manuscript, we will add figures or tables reporting the loss of orthogonality ||V_k^T V_k - I||_F as a function of iteration count for the test problems, and indicate the iterations where iterative refinement was applied. This will help identify the regime where orthogonality loss becomes significant and demonstrate the recovery of accuracy. revision: yes

Circularity Check

0 steps flagged

No circularity: algorithmic claims rest on method structure, not self-definition or fitted inputs

full rationale

The paper proposes an algorithmic variant (sGKS) of the generalized Krylov subspace method, with the central claims (exact equivalence without sketching, quasi-optimality controlled by embedding quality, and skip of reorthogonalization) presented as direct consequences of the algorithm's construction and standard sketching properties. The statement that 'no step of GKS relies intrinsically on the orthogonality of the basis' is an observation about the existing method rather than a reduction to a fitted quantity or a self-citation chain. No equations reduce by construction to inputs, no uniqueness theorems are imported from the authors' prior work, and no ansatz is smuggled via citation. The derivation is self-contained against the method's own projected solves and numerical validation.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard mathematical properties of sketching operators (embedding quality controlling residual norms) and the structural observation that GKS steps do not require basis orthogonality; no free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption Sketching operators satisfy embedding properties that control the quality of the projected residual norms
    Invoked to guarantee quasi-optimality of the sketched projected solve
  • domain assumption No algorithmic step in GKS intrinsically requires orthogonality of the basis vectors
    Used to justify skipping explicit reorthogonalization without loss of subspace quality

pith-pipeline@v0.9.1-grok · 5821 in / 1508 out tokens · 30622 ms · 2026-06-26T23:50:02.249665+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

49 extracted references · 14 canonical work pages

  1. [1]

    Arridge, P

    S. Arridge, P. Maass, O. Öktem, and C.-B. Schönlieb. Solving inverse prob- lems using data-driven models.Acta Numerica, 28:1–174, 2019.doi:10.1017/ S0962492919000059

    2019

  2. [2]

    Avron, P

    H. Avron, P. Maymounkov, and S. Toledo. Blendenpik: Supercharging LAPACK’s Preprint. 2026-06-17 D. Palitta and M. Pasha: Sketching for GKS24 0 100 200 300 400 100 10−4 10−8 10−12 10−16 σj(Wk) sGKS (no IR) sGKS (IR, q=0) sGKS (IR, q=1) (a) (b) Figure 15: Experiment 4 (Dynamic CT). (a) Singular valuesσj(Wk)of the sGKS basis afterk= 400iterations: without it...

    work page doi:10.1137/090767911 2026

  3. [3]

    Balabanov and L

    O. Balabanov and L. Grigori. Randomized Gram–Schmidt Process with Application to GMRES.SIAM Journal on Scientific Computing, 44(3):A1450–A1474, 2022.doi: 10.1137/20M138870X

    work page doi:10.1137/20m138870x 2022

  4. [4]

    Bucci, D

    A. Bucci, D. Palitta, and L. Robol. Randomized sketched tt-gmres for linear systems with tensor structure.SIAM Journal on Scientific Computing, 47(5):A2801–A2827, 2025.doi:10.1137/24M1694999

    work page doi:10.1137/24m1694999 2025

  5. [5]

    Buccini and L

    A. Buccini and L. Reichel. Generalized cross validation forℓ p–ℓq minimiza- tion.Numerical Algorithms, 88(4):1595–1616, 2021.doi:doi.org/10.1007/ s11075-021-01087-9

    2021

  6. [6]

    Buccini, L

    A. Buccini, L. Reichel, et al. Software for limited memory restartedℓ p −ℓ q min- imization methods using generalized krylov subspaces.Electronic Transactions on Numerical Analysis, 61:66–91, 2024.doi:doi:10.1553/etna_vol61s66

    work page doi:10.1553/etna_vol61s66 2024

  7. [7]

    Calvetti, B

    D. Calvetti, B. Lewis, and L. Reichel. GMRES, L-curves, and discrete ill-posed prob- lems.BIT Numerical Mathematics, 42(1):44–65, 2002

    2002

  8. [8]

    Calvetti and L

    D. Calvetti and L. Reichel. Tikhonov regularization of large linear problems.BIT Numerical Mathematics, 43:263–283, 2003

    2003

  9. [9]

    Chung, M

    J. Chung, M. Chung, S. Gazzola, and M. Pasha. Efficient learning methods for large- scale optimal inversion design.arXiv preprint arXiv:2110.02720, 2021

    arXiv 2021

  10. [10]

    Chung and S

    J. Chung and S. Gazzola.Computational Methods for Large-Scale Inverse Problems and Quantification of Uncertainty. SIAM, Philadelphia, 2024. Preprint. 2026-06-17 D. Palitta and M. Pasha: Sketching for GKS25

    2024

  11. [11]

    Chung and S

    J. Chung and S. Gazzola. Randomized Krylov methods for inverse problems.arXiv preprint arXiv:2508.20269, 2025

    arXiv 2025

  12. [12]

    Chung, J

    J. Chung, J. G. Nagy, and D. P. O’Leary. A weighted GCV method for Lanczos-hybrid regularization.Electronic Transactions on Numerical Analysis, 28:149–167, 2008

    2008

  13. [13]

    L. Eldén. A weighted pseudoinverse, generalized singular values, and constrained least squares problems.BIT Numerical Mathematics, 22:487–502, 1982

    1982

  14. [14]

    H. W. Engl, M. Hanke, and A. Neubauer.Regularization of inverse problems, volume

  15. [15]

    Springer Science & Business Media, 1996

    1996

  16. [16]

    E. N. Epperly, M. Meier, and Y. Nakatsukasa. Fast randomized least-squares solvers can be just as accurate and stable as classical direct solvers.Communications on Pure and Applied Mathematics, 79(2):293–339, 2026.doi:10.1002/cpa.70013

    work page doi:10.1002/cpa.70013 2026

  17. [17]

    Gazzola, P

    S. Gazzola, P. C. Hansen, and J. G. Nagy. IR Tools: A MATLAB package of iterative regularization methods and large-scale test problems.Numerical Algorithms, 81:773– 811, 2019

    2019

  18. [18]

    Gazzola, P

    S. Gazzola, P. Novati, and M. R. Russo. On Krylov projection methods for large-scale Tikhonov regularization.Electronic Transactions on Numerical Analysis, 44:83–114, 2015

    2015

  19. [19]

    Giraud, J

    L. Giraud, J. Langou, and M. Rozložník. The loss of orthogonality in the Gram– Schmidt orthogonalization process.Computers & Mathematics with Applications, 50(7):1069–1075, 2005.doi:10.1016/j.camwa.2005.08.009

    work page doi:10.1016/j.camwa.2005.08.009 2005

  20. [20]

    C. W. Groetsch.The Theory of Tikhonov Regularization for Fredholm Equations of the First Kind, volume 105 ofResearch Notes in Mathematics. Pitman, Boston, 1984

    1984

  21. [21]

    Güttel and M

    S. Güttel and M. Schweitzer. Randomized sketching for Krylov approximations of large-scale matrix functions.SIAM Journal on Matrix Analysis and Applications, 44(3):1073–1095, 2023

    2023

  22. [22]

    Halko, P

    N. Halko, P.-G. Martinsson, and J. A. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions.SIAM Review, 53(2):217–288, 2011.doi:10.1137/090771806

    work page doi:10.1137/090771806 2011

  23. [23]

    P. C. Hansen. The truncated SVD as a method for regularization.BIT Numerical Mathematics, 27(4):534–553, 1987

    1987

  24. [24]

    P. C. Hansen.Rank-Deficient and Discrete Ill-Posed Problems: Numerical Aspects of Linear Inversion. Monographs on Mathematical Modeling and Computation. SIAM, Philadelphia, 1998

    1998

  25. [25]

    P. C. Hansen.Discrete Inverse Problems: Insight and Algorithms. Fundamentals of Algorithms. SIAM, Philadelphia, 2010

    2010

  26. [26]

    P. C. Hansen and J. S. Jørgensen. Air tools ii: algebraic iterative reconstruction methods, improved implementation.Numerical Algorithms, 79(1):107–137, 2018

    2018

  27. [27]

    Huang, A

    G. Huang, A. Lanza, S. Morigi, L. Reichel, and F. Sgallari. Majorization–minimization generalized Krylov subspace methods forℓp–ℓq optimization applied to image restora- tion.BIT Numerical Mathematics, 57(2):351–378, 2017. Preprint. 2026-06-17 D. Palitta and M. Pasha: Sketching for GKS26

    2017

  28. [28]

    Kirsch.An Introduction to the Mathematical Theory of Inverse Problems, volume 120 ofApplied Mathematical Sciences

    A. Kirsch.An Introduction to the Mathematical Theory of Inverse Problems, volume 120 ofApplied Mathematical Sciences. Springer, New York, 2nd edition, 2011

    2011

  29. [29]

    Lampe, L

    J. Lampe, L. Reichel, and H. Voss. Large-scale Tikhonov regularization via reduction byorthogonalprojection.Linear Algebra and its Applications, 436(7):2845–2865, 2012

    2012

  30. [30]

    S. Lan, M. Pasha, S. Li, and W. Shen. Spatiotemporal besov priors for bayesian inverse problems.Journal of the American Statistical Association, pages 1–15, 2025

    2025

  31. [31]

    AgeneralizedKrylovsubspacemethod forℓ p–ℓq minimization.SIAM Journal on Scientific Computing, 37(5):S30–S50, 2015

    A.Lanza, S.Morigi, L.Reichel, andF.Sgallari. AgeneralizedKrylovsubspacemethod forℓ p–ℓq minimization.SIAM Journal on Scientific Computing, 37(5):S30–S50, 2015

    2015

  32. [32]

    Nakatsukasa and J

    Y. Nakatsukasa and J. A. Tropp. Fast and Accurate Randomized Algorithms for Linear Systems and Eigenvalue Problems.SIAM Journal on Matrix Analysis and Applications, 45(2):1183–1214, 2024.doi:10.1137/23M1565413

    work page doi:10.1137/23m1565413 2024

  33. [33]

    Natterer.The Mathematics of Computerized Tomography

    F. Natterer.The Mathematics of Computerized Tomography. Classics in Applied Mathematics. SIAM, Philadelphia, 2001

    2001

  34. [34]

    Mono- graphs on Mathematical Modeling and Computation

    F.NattererandF.Wübbeling.Mathematical Methods in Image Reconstruction. Mono- graphs on Mathematical Modeling and Computation. SIAM, Philadelphia, 2001

    2001

  35. [35]

    Okunola, M

    T. Okunola, M. Pasha, M. Kilmer, and M. Freitag. Efficient dynamic image recon- struction with motion estimation.arXiv preprint arXiv:2501.12497, 2025

    arXiv 2025

  36. [36]

    C. C. Paige and M. A. Saunders. LSQR: An algorithm for sparse linear equations and sparse least squares.ACM Transactions on Mathematical Software, 8(1):43–71, 1982

    1982

  37. [37]

    Palitta, M

    D. Palitta, M. Schweitzer, and V. Simoncini. Sketched and Truncated Polynomial Krylov Methods: Evaluation of Matrix Functions.Numerical Linear Algebra with Applications, 32(1):e2596, 2025.doi:10.1002/nla.2596

    work page doi:10.1002/nla.2596 2025

  38. [38]

    Palitta, M

    D. Palitta, M. Schweitzer, and V. Simoncini. Sketched and truncated polynomial Krylov subspace methods: Matrix Sylvester equations .Math. Comp., 94:1761–1792, 2025.doi:10.1090/mcom/4002

    work page doi:10.1090/mcom/4002 2025

  39. [39]

    Pasha, S

    M. Pasha, S. Gazzola, C. Sanderford, and U. O Ugwu. Trips-py: Techniques for regularization of inverse problems in python.Numerical Algorithms, 99(1):285–322, 2025

    2025

  40. [40]

    Pasha, A

    M. Pasha, A. K. Saibaba, S. Gazzola, M. I. Espanol, and E. de Sturler. A com- putational framework for edge-preserving regularization in dynamic inverse prob- lems.Electronic Transactions on Numerical Analysis, 58:486–516, 2023.doi: 10.1553/etna_vol58s416

    work page doi:10.1553/etna_vol58s416 2023

  41. [41]

    Shyshkov

    L Reichel and A. Shyshkov. A new zero-finder for Tikhonov regularization.BIT Numerical Mathematics, 48:627–643, 2008

    2008

  42. [42]

    L. I. Rudin, S. Osher, and E. Fatemi. Nonlinear total variation based noise removal algorithms.Physica D: Nonlinear Phenomena, 60(1–4):259–268, 1992

    1992

  43. [43]

    Saad.Iterative methods for sparse linear systems

    Y. Saad.Iterative methods for sparse linear systems. SIAM, Society for Industrial and Applied Mathematics, 2nd edition, 2003. Preprint. 2026-06-17 D. Palitta and M. Pasha: Sketching for GKS27

    2003

  44. [44]

    T. Sarlós. Improved approximation algorithms for large matrices via random projec- tions. In47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 143–152, 2006.doi:10.1109/FOCS.2006.37

    work page doi:10.1109/focs.2006.37 2006

  45. [45]

    Simoncini and D

    V. Simoncini and D. Szyld. The effect of non-optimal bases on the convergence of Krylov subspace methods.Numer. Math., 100:711–733, 2005.doi:10.1007/ s00211-005-0603-8

    2005

  46. [46]

    A. N. Tikhonov. Solution of incorrectly formulated problems and the regularization method.Soviet Mathematics Doklady, 4:1035–1038, 1963

    1963

  47. [47]

    J. A. Tropp. Improved analysis of the subsampled randomized Hadamard transform. Advances in Adaptive Data Analysis, 3(1–2):115–126, 2011

    2011

  48. [48]

    D. P. Woodruff.Sketching as a Tool for Numerical Linear Algebra, volume 10. 2014. doi:10.1561/0400000060

    work page doi:10.1561/0400000060 2014

  49. [49]

    Woolfe, E

    F. Woolfe, E. Liberty, V. Rokhlin, and M. Tygert. A fast randomized algorithm for the approximation of matrices.Applied and Computational Harmonic Analysis, 25(3):335–366, 2008.doi:10.1016/j.acha.2007.12.002. Preprint. 2026-06-17

    work page doi:10.1016/j.acha.2007.12.002 2008