pith. sign in

arxiv: 2605.22281 · v1 · pith:JRZRMR4Vnew · submitted 2026-05-21 · 🧮 math.NA · cs.NA

Randomized Flexible LSQR and LSMR with applications to inverse problems

Alberto Bucci , Silvia Gazzola , Leonardo Robol This is my paper

Pith reviewed 2026-05-22 03:54 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords randomized iterative methodsflexible LSQRLSMRinverse problemssketchingGolub-Kahan bidiagonalizationshort recurrenceslarge-scale least squares
0
0 comments X

The pith

Sketched flexible LSQR and LSMR recover short recurrences via randomization for large-scale inverse problems.

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

The paper develops sketched variants called sFLSQR and sFLSMR of the flexible LSQR and LSMR solvers. These variants embed randomization inside the flexible Golub-Kahan factorization so that the iteration recurrences remain short even when the solution subspace is modified or matrix-vector products are inexact. The goal is to reduce the cost of enforcing prior information in large least-squares problems while keeping the quality of the reconstructed solution. A reader would care because standard flexible methods can incur growing storage and work from long recurrences, and the randomized versions aim to remove that penalty for practical inverse problems.

Core claim

The authors claim that randomization inside the flexible Golub-Kahan factorization recovers short recurrences for the solution approximation, thereby producing efficient sketched solvers sFLSQR and sFLSMR that still allow subspace modifications and inexact products; theoretical analysis and numerical tests on inverse problems show that these solvers alleviate computational cost while preserving reconstruction accuracy.

What carries the argument

The randomized flexible Golub-Kahan factorization, which incorporates sketching to restore short recurrences while supporting flexible modifications to the approximation subspace.

If this is right

  • The new solvers can enforce prior information through subspace modifications at lower storage and arithmetic cost than the original flexible methods.
  • Inexact matrix-vector products can be used inside the iteration without destroying the short-recurrence property.
  • Large-scale inverse problems become tractable because the computational bottleneck of long recurrences is removed while reconstruction quality stays comparable.
  • Theoretical bounds on the behavior of the sketched factorization support the observed numerical stability.

Where Pith is reading between the lines

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

  • The same randomization device could be tested on other bidiagonalization-based solvers beyond LSQR and LSMR to shorten their recurrences.
  • For inverse problems whose coefficient matrices have special structure, the sketching distribution might be chosen to exploit that structure rather than using generic random matrices.
  • The approach suggests a general template for turning flexible but expensive iterations into sketched short-recurrence versions in other areas of numerical linear algebra.

Load-bearing premise

Randomization inside the flexible Golub-Kahan process reliably produces short recurrences without harming convergence rate or final accuracy on the target inverse problems.

What would settle it

Numerical runs on a standard large-scale inverse problem in which the randomized sFLSQR or sFLSMR versions require more iterations or produce visibly worse reconstructions than the non-randomized flexible versions.

Figures

Figures reproduced from arXiv: 2605.22281 by Alberto Bucci, Leonardo Robol, Silvia Gazzola.

Figure 1
Figure 1. Figure 1: Deblurring and inpainting for the house test image, contaminated with 5% Gaussian noise. From the left, we have: the original image, the blurred and subsam￾pled image, the recovery with 31 iterations of LSQR (which yields the minimum error result among the first 50 iterations), the recovery with 50 iterations of FLSQR with low-rank truncation at rank 30 at each step. 0 10 20 30 40 50 0.06 0.08 0.1 0.12 Ite… view at source ↗
Figure 2
Figure 2. Figure 2: Deblurring and inpainting for the house test image. 2-norm residual and error plot, using LSQR and FLSQR (with low-rank-truncation as in [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Artificial test problem described in Section 2.4, with noise levels 1% and 10%. [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Artificial test problem described in Section 2.4, with noise levels 1% and 10%. [PITH_FULL_IMAGE:figures/full_fig_p014_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Artificial test problem described in Section 2.4, with singular values decay [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Class of artificial test problems obtained from the one described in Section 2.4, [PITH_FULL_IMAGE:figures/full_fig_p018_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Image deblurring and inpainting test problem. Timings for running 50 it [PITH_FULL_IMAGE:figures/full_fig_p019_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Image deblurring and inpainting test problem. Images recovered, with FLSQR [PITH_FULL_IMAGE:figures/full_fig_p019_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Image deblurring and inpainting test problem. Convergence history for residu [PITH_FULL_IMAGE:figures/full_fig_p020_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: 2D CT test problem. Original phantom; reconstructed phantoms at the 15th [PITH_FULL_IMAGE:figures/full_fig_p022_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: 2D CT test problem. Residual and error plots versus iteration count. [PITH_FULL_IMAGE:figures/full_fig_p022_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: 3D CT test problem. 3 slices (with index 64, 96, and 128, out of 256) [PITH_FULL_IMAGE:figures/full_fig_p023_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: 3D CT test problem. Residual and error plots versus iteration count. [PITH_FULL_IMAGE:figures/full_fig_p023_13.png] view at source ↗
read the original abstract

LSQR and LSMR are iterative methods, based on the Golub-Kahan bidiagonalization algorithm, widely used for large-scale linear least squares problems. FLSQR and FLSMR are flexible variants of LSQR and LSMR, respectively, based on a flexible Golub-Kahan (Arnoldi-like) factorization algorithm, which naturally allow modifications of the solution approximation subspace and/or handling inexact matrix-vector multiplications with the (transpose of the) coefficient matrix, thereby enabling to enforce prior information into the computed solution. The goal of this paper is to introduce sFLSQR and sFLSMR, i.e., sketched variants of FLSQR and FLSMR, respectively, where randomization becomes particularly effective, as it allows to recover short recurrences for the solution approximation. In particular, this paper explores applications to large-scale inverse problems, showing the ability of the new randomized solvers to alleviate computational bottlenecks while preserving reconstruction quality. A theoretical analysis of sFLSQR and sFLSMR is provided, and their performance is validated through numerical experiments.

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

2 major / 2 minor

Summary. The manuscript introduces sFLSQR and sFLSMR, sketched randomized variants of the flexible LSQR and LSMR solvers. These methods embed randomization into the flexible Golub-Kahan bidiagonalization process to recover short recurrences while accommodating subspace modifications for prior information and inexact matrix-vector products. The central claims are that the new solvers alleviate computational costs in large-scale inverse problems without degrading reconstruction quality, supported by theoretical analysis of the sketched factorization and numerical validation on inverse-problem test cases.

Significance. If the error-control arguments extend rigorously to the flexible and inexact setting, the work would supply a practical route to scaling flexible iterative solvers for inverse problems. The combination of sketching with flexible updates could reduce per-iteration costs while retaining the ability to enforce priors, offering a concrete advance over both standard LSQR/LSMR and their non-sketched flexible counterparts.

major comments (2)
  1. [§3.2] §3.2, Theorem 3.3 (or the main concentration result): the deviation bound between the sketched flexible bidiagonalization and the exact flexible factorization is stated under fixed subspaces and exact arithmetic. The proof does not quantify the accumulation of perturbations when the subspace is updated at every flexible step or when matvecs are inexact; this directly affects whether short recurrences are recovered while preserving the approximation power claimed for inverse problems.
  2. [§5] §5, Table 2 (inverse-problem experiments): the reported reconstruction errors for sFLSQR/sFLSMR are comparable to FLSQR/FLSMR only for the chosen sketch dimension; no systematic study of how the error grows as the sketch size decreases relative to the flexible update frequency is provided, leaving open whether the observed quality preservation is general or problem-specific.
minor comments (2)
  1. [Abstract] The abstract states that 'theoretical analysis is provided' without naming the key assumptions (exact vs. inexact arithmetic, fixed vs. adaptive subspaces). Adding one sentence on the scope of the guarantees would improve readability.
  2. [§2.2] Notation for the flexible correction vectors in §2.2 could be aligned more clearly with the standard Golub-Kahan notation to help readers track the differences introduced by flexibility.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below and indicate the revisions we will make to strengthen the presentation and analysis.

read point-by-point responses

  1. Referee: [§3.2] §3.2, Theorem 3.3 (or the main concentration result): the deviation bound between the sketched flexible bidiagonalization and the exact flexible factorization is stated under fixed subspaces and exact arithmetic. The proof does not quantify the accumulation of perturbations when the subspace is updated at every flexible step or when matvecs are inexact; this directly affects whether short recurrences are recovered while preserving the approximation power claimed for inverse problems.

    Authors: We agree that Theorem 3.3 establishes the concentration bound under the simplifying assumptions of fixed subspaces and exact arithmetic. This serves as the foundational result for the sketched factorization. We will revise Section 3.2 to include an additional remark that discusses the effect of subspace updates and inexact matvecs on perturbation accumulation, explaining why the short-recurrence property is retained in the flexible setting for the inverse-problem applications considered. revision: yes

  2. Referee: [§5] §5, Table 2 (inverse-problem experiments): the reported reconstruction errors for sFLSQR/sFLSMR are comparable to FLSQR/FLSMR only for the chosen sketch dimension; no systematic study of how the error grows as the sketch size decreases relative to the flexible update frequency is provided, leaving open whether the observed quality preservation is general or problem-specific.

    Authors: The experiments in Table 2 were designed to show that practical sketch sizes preserve reconstruction quality while lowering per-iteration cost. We acknowledge that a fuller parametric study relating sketch dimension to update frequency would make the generality clearer. In the revised manuscript we will add a short discussion together with one additional plot (for a representative test case) that illustrates the sensitivity of reconstruction error to sketch size. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation extends established flexible Golub-Kahan methods with standard sketching

full rationale

The paper defines sFLSQR and sFLSMR as sketched variants of prior FLSQR/FLSMR algorithms that already incorporate flexible updates and inexact matvecs. The central step—recovering short recurrences via randomization—is presented as a direct consequence of applying sketching to the flexible factorization, with a separate theoretical analysis and numerical validation on inverse problems. No equation or claim reduces a derived quantity to a fitted parameter, self-citation chain, or renamed input by construction; the work relies on external concentration bounds and prior flexible variants without load-bearing self-reference. The derivation chain remains self-contained against standard benchmarks.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The central claim depends on standard properties of Golub-Kahan bidiagonalization being preserved under sketching and flexibility; no new entities are introduced.

free parameters (1)
  • sketch dimension
    Random sketch size chosen to trade accuracy for speed in the flexible factorization.
axioms (1)
  • domain assumption Random sketching preserves the essential short-recurrence property of the flexible Golub-Kahan process for the problems considered.
    This is the key step that enables computational savings while retaining flexibility.

pith-pipeline@v0.9.0 · 5718 in / 1123 out tokens · 42083 ms · 2026-05-22T03:54:21.457440+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

30 extracted references · 30 canonical work pages

  1. [1]

    TRUNCATED LSQR FOR MATRIX LEAST SQUARES PROBLEMS AND APPLICATION TO DICTIONARY LEARNING , author=

    work page

  2. [2]

    , title =

    Gazzola, Silvia and Meng, Chang and Nagy, James G. , title =. SIAM Journal on Matrix Analysis and Applications , volume =. 2020 , doi =

    work page 2020

  3. [3]

    D. C. L. Fong and M. Saunders , title =. SIAM J. Scientific Computing , volume =

    work page

  4. [4]

    Palenstijn, Willem Jan and Batenburg, K Joost and Sijbers, Jan , booktitle=. The

    work page

  5. [5]

    Acta Numerica , volume=

    Randomized numerical linear algebra: Foundations and algorithms , author=. Acta Numerica , volume=. 2020 , publisher=

    work page 2020

  6. [6]

    Inner-Product Free

    Brown, Ariana N and Chung, Julianne and Nagy, James G and Sabat. Inner-Product Free. SIAM Journal on Scientific Computing , number=. 2025 , publisher=

    work page 2025

  7. [7]

    Randomized and inner-product free

    Sabat. Randomized and inner-product free. Numerical Algorithms , pages=. 2025 , publisher=

    work page 2025

  8. [8]

    Randomized

    Chung, Julianne and Gazzola, Silvia , journal=. Randomized

    work page

  9. [9]

    , title =

    Saad, Y. , title =. SIAM J. Sci. Comput. , volume =. 1993 , doi =

    work page 1993

  10. [10]

    Randomized flexible

    Sabat. Randomized flexible. arXiv preprint arXiv:2302.13616 , year=

    work page arXiv

  11. [11]

    and Gazzola, S

    Chung, J. and Gazzola, S. , journal=sisc, volume=. Flexible. 2019 , publisher=

    work page 2019

  12. [12]

    2022 , author =

    Journal of Computational and Applied Mathematics , volume =. 2022 , author =

    work page 2022

  13. [13]

    Matrix Anal

    SIAM J. Matrix Anal. Appl. , volume =. 2010 , author =

    work page 2010

  14. [14]

    Dong and P

    Y. Dong and P. C. Hansen and M. E. Hochstenbach and N. A. Brogaard Riis , title =. SIAM Journal on Scientific Computing , volume =

    work page

  15. [15]

    1982 , publisher=

    Paige, Christopher C and Saunders, Michael A , journal=. 1982 , publisher=

    work page 1982

  16. [16]

    Hn e tynkov \'a and M

    I. Hn e tynkov \'a and M. Ple s inger and Z. Strakos. The regularizing effect of the G olub- K ahan iterative bidiagonalization and revealing the noise level in the data. BIT

    work page

  17. [17]

    2016 , title =

    BIT Numerical Mathematics , pages =. 2016 , title =

    work page 2016

  18. [18]

    SIAM Review53(2), 217–288 (2011)

    Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions , volume=. SIAM Rev. , author=. 2011 , pages=. doi:10.1137/090771806 , number=

    work page doi:10.1137/090771806 2011

  19. [19]

    SIAM Journal on Matrix Analysis and Applications , volume=

    Fast and accurate randomized algorithms for linear systems and eigenvalue problems , author=. SIAM Journal on Matrix Analysis and Applications , volume=. 2024 , publisher=

    work page 2024

  20. [20]

    Foundations and Trends

    Randomized algorithms for matrices and data , author=. Foundations and Trends. 2011 , publisher=

    work page 2011

  21. [21]

    Foundations and Trends

    Sketching as a tool for numerical linear algebra , author=. Foundations and Trends. 2014 , publisher=

    work page 2014

  22. [22]

    Randomized

    Balabanov, Oleg and Grigori, Laura , journal=. Randomized. 2022 , publisher=

    work page 2022

  23. [23]

    1999 , publisher=

    Sadok, Hassane , journal=. 1999 , publisher=

    work page 1999

  24. [24]

    SIAM Journal on Matrix Analysis and Applications , volume=

    Brown, Ariana N and Sabat. SIAM Journal on Matrix Analysis and Applications , volume=. 2025 , publisher=

    work page 2025

  25. [25]

    2010 , publisher=

    Discrete Inverse Problems: Insight and Algorithms , author=. 2010 , publisher=

    work page 2010

  26. [26]

    SIAM Journal on Scientific Computing , volume =

    Julianne Chung and Katrina Palmer , title =. SIAM Journal on Scientific Computing , volume =. 2015 , doi =

    work page 2015

  27. [27]

    2024 , title =

    SIAM Review , pages =. 2024 , title =

    work page 2024

  28. [28]

    Van Aarle, Wim and Palenstijn, Willem Jan and De Beenhouwer, Jan and Altantzis, Thomas and Bals, Sara and Batenburg, K Joost and Sijbers, Jan , journal=. The. 2015 , publisher=

    work page 2015

  29. [29]

    Journal of structural biology , volume=

    Performance improvements for iterative electron tomography reconstruction using graphics processing units (GPUs) , author=. Journal of structural biology , volume=. 2011 , publisher=

    work page 2011

  30. [30]

    Gazzola and P

    S. Gazzola and P. Novati and M. R. Russo. O n K rylov projection methods and T ikhonov regularization. Electron. Trans. Numer. Anal

    work page