Pith. sign in

REVIEW 2 major objections 3 minor 34 references

A conjugate-gradient-type rational Krylov subspace method for ill-posed problems

T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Rational Krylov method SINE is order-optimal for all smoothness exponents

desk verdict A genuinely new rational-Krylov iterative regularizer with a mostly careful analysis, but the order-optimality proof stops at a deferred 'literal' transfer from CGNE that the author needs to write out. read the letter →

arxiv 1908.03011 v1 pith:5EAUTBK4 submitted 2019-08-08 math.NA cs.NA

Volker Grimm This is my paper · ORCID
classification math.NAcs.NA MSC 65J2065F1047A52
keywords ill-posedproblemsregularisationrationalKrylovsubspaceshift-and-invertconjugategradientnormalequationdiscrepancyprincipleorder-optimalinverse
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper proposes a new iterative regularisation method for ill-posed linear inverse problems: minimise the residual $\|y^\delta - Tx\|$ over the shift-and-invert rational Krylov subspace $Q_m = \operatorname{span}\{T^*y^\delta, (I+T^*T/\gamma)^{-1}T^*y^\delta, \dots\}$, then stop by Morozov's discrepancy principle. The central claim is that this method, called SINE, is order-optimal for every smoothness exponent $\mu>0$: if the exact solution lies in the source set $X_{\mu,\rho}$, the error is bounded by $c\,\rho^{1/(2\mu+1)}\delta^{2\mu/(2\mu+1)}$. The paper also proves that the SINE residual at each step is no larger than the CGNE residual, so SINE never needs more iterations than CGNE to meet the discrepancy principle. A sympathetic reader would care because rational Krylov subspaces can accelerate convergence; if the claim is right, users can gain that speed while keeping the best worst-case accuracy known for CGNE.

What carries the argument

SINE is defined by $x^\delta_m=\arg\min_{x\in Q_m}\|y^\delta-Tx\|$ with $Q_m=\operatorname{span}\{T^*y^\delta,(I+T^*T/\gamma)^{-1}T^*y^\delta,\ldots,(I+T^*T/\gamma)^{-(m-1)}T^*y^\delta\}$. The argument is carried by the rational residual function $r_m(\lambda)=p_m(\lambda)/(1+\lambda/\gamma)^{m-1}$, whose zeros are the interlacing positive Ritz values of the subspace; all estimates reduce to bounds on $|r'_m(0)|=\sum_j 1/\lambda_{j,m}+(m-1)/\gamma$. Orthogonality is measured in the weighted inner product $[\phi,\psi]=\int_0^{\|T\|^2}\phi(\lambda)\psi(\lambda)\lambda\,d\|F_\lambda y^\delta\|^2$. The proof of the main theorem reaches identity (27), $[u_m,u_m]=(\pi_m-1/\gamma)([r_{m-1},r_{m-1}/\lambda]-[r_m,r_m/\lambda])$ with $u_m=(r_{m-1}-r_m)/\lambda$ and $\pi_m=r'_{m-1}(0)-r'_m(0)>1/\gamma$, and then claims the rest follows literally from the corresponding CGNE proof.

What would settle it

Set $T$ to the multiplication operator $Tf(t)=tf(t)$ on $L^2(0,1)$ and run SINE with small $\gamma$ and known exact solutions $t$ and $t^3$ over noise levels $\delta=10^{-2},\dots,10^{-6}$; the measured error exponents must approach $1/2$ and $3/4$ if Theorem 4.3 holds. More directly, write out the omitted continuation of the CGNE proof: if the rational denominator $(1+\lambda/\gamma)^{m-1}$ breaks any of the inequalities involving $\pi_m>1/\gamma$ and the decay of $[u_m,u_m]$, the claimed bound is not established.

Watch

Extended reading notes

Core claim

The central result, Theorem 4.3, states: if $y\in R(T)$, the noisy data satisfy $\|y^\delta-y\|\le\delta$, SINE is stopped by the discrepancy principle with fixed $\tau>1$, and $T^+y\in X_{\mu,\rho}$, then $\|T^+y - x^\delta_{m(\delta,y^\delta)}\| \le c\,\rho^{1/(2\mu+1)}\delta^{2\mu/(2\mu+1)}$ for a constant $c$ independent of $\delta$ and $\rho$. This is exactly the definition of an order-optimal regularisation scheme for all $\mu>0$. Theorem 5.1 adds a comparison with CGNE: for every iteration $m$, $\min_{x\in Q_m}\|y^\delta-Tx\| \le \min_{x\in K_m}\|y^\delta-Tx\|$, so the discrepancy-principle stopping index for SINE is at most that of CGNE. The paper also shows convergence of the iterates for exact data and, as corollaries, transfers CGNE's iteration-count bounds to SINE.

Load-bearing premise

The load-bearing premise is that, after identity (27), the remainder of the classical CGNE order-optimality proof can be copied verbatim to the rational residual functions $r_m(\lambda)=p_m(\lambda)/(1+\lambda/\gamma)^{m-1}$; the paper states this without writing the continuation, so the main theorem stands or falls on that unshown transfer.

Editorial extensions

If this is right

  • SINE is a fully order-optimal regularisation method with the discrepancy principle, matching CGNE's worst-case rate $\delta^{2\mu/(2\mu+1)}$ for every source smoothness $\mu>0$.
  • For every iterate, SINE's residual is at most CGNE's residual, so its stopping index $m_\gamma(\delta,y^\delta)$ is never larger than $m_\infty(\delta,y^\delta)$; all known iteration-count bounds for CGNE apply to SINE.
  • SINE is the fastest method among all regularisation schemes restricted to the shift-and-invert Krylov subspace $Q_m$: by construction it minimises the residual there, so no other method in that subspace can satisfy the discrepancy principle earlier.
  • Because $\gamma\to\infty$ makes the rational Krylov subspace collapse to the polynomial Krylov subspace, SINE contains CGNE as a limit case and the two are governed by the same optimality framework.
  • The sharp bound $m_\gamma(\delta,y^\delta)\le c(\rho/\delta)^{1/(2\mu+1)}$ carries over from CGNE, so the iteration count, not just the error, is order-optimal.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A direct extension, only sketched in the paper, is that any rational Krylov subspace with negative real poles, chosen deterministically or randomly, should have residuals no larger than CGNE's; testing random pole choices on severely ill-posed problems would quantify how much early stopping improves.
  • The proof structure suggests the order-optimality result should transfer to other residual-minimising rational methods, such as nonstationary iterated Tikhonov with varying step sizes, although the missing CGNE transfer in Section 4 would have to be filled in first.
  • In finite-dimensional discretisations the worst-case rates are minimax, so SINE's practical payoff is likely lower iteration counts at the same worst-case accuracy; the paper's 2-versus-19 iteration example on a multiplication operator is a clean setting to test this on larger problems.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The manuscript introduces SINE, a regularisation method for linear ill-posed operator equations, defined by minimizing the residual over shift-and-invert rational Krylov subspaces Q_m and stopping by Morozov's discrepancy principle. It presents the algorithm, proves orthogonality and rational residual representation, establishes convergence for exact data, claims order-optimal rates in Theorem 4.3, and shows in Theorem 5.1 that SINE's residual at each iteration is no larger than CGNE's, so SINE stops no later than CGNE. A simple multiplication-operator experiment illustrates the rates and the faster stopping behaviour.

Significance. If Theorem 4.3 is fully established, this is a worthwhile contribution: it extends order-optimal regularisation results from polynomial Krylov methods to shift-and-invert rational Krylov subspaces, with a fixed parameter gamma that is not fitted to the data. Theorem 5.1 gives a clean, falsifiable comparison with CGNE, and the algebraic lemmas in Section 2 are useful and coherent. The value of the paper is conditional on completing the rational-function continuation of the CGNE proof that is deferred in the central argument.

major comments (2)
  1. [Section 4, proof of Theorem 4.3 after Eq. (27)] The order-optimality proof is not complete as written. The text states 'From here, the proof continues literally as the proof of Theorem 7.12 in [6],' but the deferred continuation is load-bearing. In the CGNE case, the remaining proof uses polynomial residual functions to obtain the bound |r'_m(0)| <= C(rho/delta)^(2/(2mu+1)) via the decay of [u_m,u_m] and the identity replacing Eq. (27). Here r_m is rational and Eq. (27) contains the shifted factor (pi_m - 1/gamma) instead of the polynomial-case pi_m, so the transfer is not verbatim; the sign and smallness of pi_m - 1/gamma, and the corresponding control of |r'_m(0)| from Eq. (22), must be verified explicitly. Without this, Theorem 4.3 is not established by the text alone.
  2. [Section 4, Lemma 4.2, final paragraph] Lemma 4.2 similarly rests on a 'literal copy of the proof of Lemma 7.11 in [6]'. That proof relies on estimates for lambda^mu r_m(lambda) and lambda^(1/2) g_m(lambda) on [0,epsilon] and on a final noise-term bound involving |r'_m(0)|. For rational r_m = p_m(lambda)/(1+lambda/gamma)^(m-1), these estimates are not identical to the polynomial case, and the text does not spell out why the same inequalities and constants hold. Since Lemma 4.2 feeds directly into Theorem 4.3, this deferral must be filled in before the central claim can be accepted.
minor comments (3)
  1. [Section 6, discussion of Figure 1] The text says the convergence for x2+ = t^3 is 'at least delta^(1/2) or delta^(3/2), respectively'; the theorem predicts delta^(2mu/(2mu+1)), which for mu = 3/2 is delta^(3/4), not delta^(3/2).
  2. [Corollary 5.2] The upper bound m_gamma(delta,y^delta) <= c(rho/delta)^(1/(2mu+1)) follows from Theorem 5.1 and Theorem 7.13 of [6], but the asserted sharpness of the exponent does not transfer automatically from CGNE to SINE. Since SINE may stop strictly earlier than CGNE, a separate lower-bound argument is needed; as written, the sharpness assertion is unsupported.
  3. [Section 3, proof of Theorem 3.1] Several typographical corruptions obscure the computation, for example 'Since 0 nu phi_m^2(0)' and 'By inserting in(...)'; these should be corrected to the intended formulas involving the derivative of phi_m and the maximum of lambda^nu phi_m^2(lambda).

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: SINE's main claims derive from the discrepancy principle, source conditions, and external CGNE proofs; the deferred proof transfer at Eq. (27) is an incompleteness risk, not a circular reduction.

full rationale

The paper does not fit any parameter to the target error and then rename the fit as a prediction. The shift parameter γ is fixed and arbitrary; Theorem 5.1 compares SINE residuals with CGNE residuals via the elementary inequality 1/(1+λ/γ)^(m−1) ≤ 1, so the claimed faster stopping is a direct consequence of the definition of the subspace minimizer, not of data fitted by the method. Theorem 4.3 obtains its rate from the discrepancy principle (19), the source condition x+ ∈ X_{μ,ρ}, and bounds on |r'_m(0)|; the parameter-free derivation follows the standard Engl–Hanke–Neubauer template. The only load-bearing reference to prior work is the sentence after Eq. (27), where the proof 'continues literally as the proof of Theorem 7.12 in [6]'; this is an external CGNE proof, not a self-citation, and the rational-function transfer is asserted rather than exhibited. That is a verification gap for the correctness pass, but it is not circularity: no equation in the paper is equivalent by construction to its own input, and the author's own rational-Krylov papers [9,11,12] are cited only as background on rational Krylov subspaces, not as the source of the order-optimality claim. Accordingly, no circular step can be quoted, and the circularity score is 0.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The method's central result rests on standard spectral calculus, the discrepancy principle, and source conditions, plus one paper-specific transfer assumption: the final part of the CGNE optimality proof is asserted to carry over verbatim to the rational setting. The user parameters γ and τ are not fitted to data.

free parameters (2)
  • gamma = user-chosen; no fitted value required; experiment uses γ=1/1000
    Shift parameter in (I+T*T/γ)^{-1}. The order-optimality theorem holds for every γ>0, so it is not fitted to data, but it controls the rational subspace and practical iteration count.
  • tau = user-chosen; experiment uses τ=1001/1000
    Discrepancy principle parameter in stopping rule (3). Any τ>1 is allowed; the constant in the error bound may depend on τ but the order-optimality does not.
assumptions (5)
  • domain assumption T is a bounded linear operator between Hilbert spaces X and Y with non-closed range and yδ satisfies ||yδ-y|| ≤ δ.
    Stated in Section 1 as the setup of the ill-posed problem; all subsequent analysis assumes this.
  • standard math Functional calculus for bounded self-adjoint operators T*T and TT* (spectral theorem).
    Invoked throughout Sections 2-5 through reference to Section 2.3 of [6], especially for representing iterates by rational functions.
  • standard math The Morozov discrepancy principle with τ>1 yields a convergent regularization scheme.
    Used as the stopping rule (3) and cited to [6] for convergence; Theorem 4.3 relies on the stopping index inequalities.
  • domain assumption Source condition x+=(T*T)^μ w with ||w||≤ρ and y∈R(T) for the rate statements.
    Defines the source set X_{μ,ρ} in Section 1 and is used in Lemmas 4.1 and 4.2 and Theorem 4.3.
  • ad hoc to paper The final part of the proof of Theorem 7.12 in [6] transfers literally to the rational residual functions r_m.
    After Eq. (27), the paper does not spell out the completion of Theorem 4.3; this transfer is the load-bearing unverified step.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A conjugate-gradient-type rational Krylov subspace method for ill-posed problems." pith.science (2026). https://pith.science/paper/5EAUTBK4

@misc{pith2026190803011,
  author       = {Pith},
  title        = {Pith review of: A conjugate-gradient-type rational Krylov subspace method for ill-posed problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5EAUTBK4}},
  note         = {Machine review of arXiv:1908.03011}
}
read the original abstract

Conjugated gradients on the normal equation (CGNE) is a popular method to regularise linear inverse problems. The idea of the method can be summarised as minimising the residuum over a suitable Krylov subspace. It is shown that using the same idea for the shift-and-invert rational Krylov subspace yields an order-optimal regularisation scheme.

Figures

Figures reproduced from arXiv: 1908.03011 by the authors.

Figure 1
Figure 1. L2-error versus inverse noise δ −1 computing regularisations in the shift-and-invert Krylov subspace Qm. That is, where these methods have been used successfully, SINE should also be a very good choice. That SINE might also be useful with respect to regularisation schemes that do not use the shift-and-invert Krylov subspace Qm, will be illustrated by another simple experiment, where we compare SINE and CGNE. For γ =… view at source ↗
Figure 2
Figure 2. Left-hand side SINE-regularisation attained in 2nd step, right-hand side CGNE-regularisation attained in 19th step Krylov subspace, rational Krylov subspaces inspire a wide range of methods that might be adapted to the needs at hand. As a possible application, rational Krylov subspaces have been successfully used to accelerate computations related to seismic imaging (e.g. [4, 19, 33, 34]), which is known to be an il… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 33 canonical work pages

  1. [6]

    H.W. Engl, M. Hanke, and A. Neubauer. Regularization of inverse problems , volume 375 of Mathematics and its Applications . Kluwer Academic Publishers Group, Dordrecht, 1996

    work page 1996

  2. [1]

    M. A. Botchev and L. A. Knizhnerman. ART: Adaptive residual-tim e restarting for Krylov subspace matrix exponential evaluations. J. Comput. Appl. Math. , 364, 2020

    work page 2020

  3. [2]

    Brezinski, P

    C. Brezinski, P. Novati, and M. Redivo-Zaglia. A rational Arnoldi a pproach for ill-conditioned linear systems. J. Comput. Appl. Math. , 236(8):2063–2077, 2012

    work page 2012

  4. [3]

    Buccini, M

    A. Buccini, M. Donatelli, and L. Reichel. Iterated Tikhonov regular ization with a general penalty term. Numer. Linear Algebra Appl. , 24(4):e2089, 12, 2017

    work page 2017

  5. [4]

    Druskin, R

    V. Druskin, R. F. Remis, M. Zaslavsky, and J. T. Zimmerling. Compr essing large-scale wave propagation models via phase-preconditioned rational Krylov subs paces. Multiscale Model. Simul., 16(4):1486–1518, 2018

    work page 2018

  6. [5]

    Eicke, A

    B. Eicke, A. K. Louis, and R. Plato. The instability of some gradient methods for ill-posed problems. Numer. Math. , 58(1):129–134, 1990

    work page 1990

  7. [7]

    A. G. Fakeev. A class of iteration processes for solution of dege nerate systems of linear algebraic equations. U.S.S.R. Comput. Math. and Math. Phys. , 21(3):545–552, 809, 1981

    work page 1981

  8. [8]

    G¨ ockler

    T. G¨ ockler. Rational Krylov subspace methods for ϕ -functions in exponential integrators . PhD thesis, Karlsruhe Institute of Technology (KIT), Germany, 2014

    work page 2014

Show all 34 references
  1. [9]

    G¨ ockler and V

    T. G¨ ockler and V. Grimm. Convergence Analysis of an Extended K rylov Subspace Method for the Approximation of Operator Functions in Exponential Integrat ors. SIAM J. Numer. Anal. , 51(4):2189–2213, 2013

    2013

  2. [10]

    G¨ ockler and V

    T. G¨ ockler and V. Grimm. Acceleration of contour integration t echniques by rational Krylov subspace methods. J. Comput. Appl. Math. , 316:133–142, 2017

    2017

  3. [11]

    V. Grimm. Resolvent Krylov subspace approximation to operato r functions. BIT, 52(3):639–659, 2012

    2012

  4. [12]

    Grimm and T

    V. Grimm and T. G¨ ockler. Automatic smoothness detection of t he resolvent Krylov subspace method for the approximation of C0-semigroups. SIAM J. Numer. Anal. , 55(3):1483–1504, 2017

    2017

  5. [13]

    G¨ uttel

    S. G¨ uttel. Rational Krylov approximation of matrix functions: numerical methods and optimal pole selection. GAMM-Mitt., 36(1):8–31, 2013

    2013

  6. [14]

    M. Hanke. Conjugate gradient type methods for ill-posed problems , volume 327 of Pitman Research Notes in Mathematics Series . Longman Scientific & Technical, Harlow, 1995

    1995

  7. [15]

    M. R. Hestenes and E. Stiefel. Methods of conjugate gradient s for solving linear systems. J. Research Nat. Bur. Standards , 49:409–436 (1953), 1952

    1953

  8. [16]

    Jin and L

    Q. Jin and L. Stals. Nonstationary iterated Tikhonov regulariza tion for ill-posed problems in Banach spaces. Inverse Problems , 28(10):104011, 15, 2012

    2012

  9. [17]

    J. T. King and C. Chillingworth. Approximation of generalized inver ses by iterated regularization. Numer. Funct. Anal. Optim. , 1(5):499–513, 1979

    1979

  10. [18]

    A. V. Krjanev. An iterative Method for Solving Incorrectly Pos ed Problems. U.S.S.R. Comput. Math. and Math. Phys. , 14:25–35, 1974

    1974

  11. [19]

    W. Liu, C. G. Farquharson, J. Zhou, and X. Li. A rational Krylov subspace method for 3D modeling of grounded electrical source airborne time-domain electr omagnetic data. J. Geophys. Eng., 16:451–462, 2019

    2019

  12. [20]

    Liu and Ch

    Y. Liu and Ch. Gu. A shift and invert reorthogonalization Arnoldi algorithm for solving the chemical master equation. Appl. Math. Comput. , 349:1–13, 2019

    2019

  13. [21]

    Moret and P

    I. Moret and P. Novati. RD-rational approximations of the mat rix exponential. BIT Numerical Mathematics, 44:595–615, 2004

    2004

  14. [22]

    Moret and P

    I. Moret and P. Novati. Krylov subspace methods for function s of fractional differential operators. Math. Comp. , 88(315):293–312, 2019

    2019

  15. [23]

    V. A. Morozov. On the solution of functional equations by the m ethod of regularization. Soviet Rational Krylov subspace regularisation 21 Math. Dokl. , 7:414–417, 1966

    1966

  16. [24]

    A. S. Nemirovskiy. The regularizing properties of the adjoint gr adient method in ill-posed problems. USSR Comput. Math. and Math. Phys. , 26(2):7–16, 1986

    1986

  17. [25]

    A. S. Nemirovskiy and B. T. Polyak. Iterative methods for solvin g linear ill-posed problems under precise information. I. Engrg. Cybernetics, 22(3):1–11, 1984

    1984

  18. [26]

    A. S. Nemirovskiy and B. T. Polyak. Iterative methods for solvin g linear ill-posed problems under precise information. II. Engrg. Cybernetics, 22(4):50–56, 1984

    1984

  19. [27]

    Ramlau and L

    R. Ramlau and L. Reichel. Error estimates for Arnoldi-Tikhonov r egularization for ill-posed operator equations. Inverse Problems , 35(5):055002, 23, 2019

    2019

  20. [28]

    A. Rieder. Runge-Kutta integrators yield optimal regularizatio n schemes. Inverse Problems , 21(2):453–471, 2005

    2005

  21. [29]

    J. D. Riley. Solving systems of linear equations with a positive defin ite, symmetric, but possibly ill-conditioned matrix. Math. Tables Aids Comput. , 9:96–101, 1955

    1955

  22. [30]

    A. Ruhe. Rational Krylov sequence methods for eigenvalue com putation. Linear Algebra Appl. , 58:391–405, 1984

    1984

  23. [31]

    G. W. Stewart. Afternotes goes to graduate school : lectures on advanced nu merical analysis . SIAM, Philadelphia, 1998

    1998

  24. [32]

    G. W. Stewart. Matrix algorithms. Vol. II . Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2001. Eigensystems

    2001

  25. [33]

    J. Zhou, W. Liu, , X. Li, and Z. Qi. 3D transient electromagnetic m odeling using a shift-and-invert Krylov subspace method. J. Geophys. Eng. , 15:1341–1349, 2018

    2018

  26. [34]

    Zimmerling

    J. Zimmerling. Model reduction of wave equations, theory and applications in forward modeling and imaging . PhD thesis, Delft University of Technology, The Netherlands, 201 8

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.