pith. sign in

arxiv: 2605.18259 · v1 · pith:4UZ2QYZNnew · submitted 2026-05-18 · 🧮 math.NA · cs.NA

Stochastic Convergence Analysis for Large-Scale Linear Discrete Ill-posed Problems

Duan-Peng Ling , Wenlong Zhang This is my paper

Pith reviewed 2026-05-20 00:04 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords weighted Tikhonov regularizationstochastic error boundsill-posed problemsparameter choicerandom noisediscrete forward operatorconvergence analysislarge-scale problems
0
0 comments X

The pith

Polynomial upper bound on generalized eigenvalues allows stochastic error bounds for weighted Tikhonov regularization in large-scale ill-posed problems.

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

The paper establishes stochastic convergence results for weighted Tikhonov regularization applied to large linear discrete ill-posed problems with random noise. The key step is assuming that the generalized eigenvalues of the forward operator obey a polynomial upper bound. Under this assumption, expectation bounds are derived for zero-mean bounded-variance noise and high-probability bounds for sub-Gaussian noise. These results support an a priori choice of the regularization parameter and an adaptive strategy that is computationally feasible for large-scale problems. A reader would care because choosing the parameter correctly is essential for accurate solutions in inverse problems where noise is inevitable and problem size prevents expensive tuning methods.

Core claim

Under a polynomial upper-bound assumption on the generalized eigenvalues of the discrete forward operator, stochastic error bounds are derived for weighted Tikhonov regularization. Expectation bounds are obtained for independent zero-mean bounded-variance noise and high-probability bounds for independent sub-Gaussian noise. The analysis provides an a priori parameter-choice rule and an adaptive strategy for large-scale computation.

What carries the argument

Polynomial upper-bound assumption on the generalized eigenvalues of the discrete forward operator, which controls the decay and enables derivation of the explicit stochastic error rates and parameter rules.

If this is right

  • An a priori parameter-choice rule follows directly from the error bounds and achieves the predicted convergence rates.
  • An adaptive strategy is suggested that remains effective for large-scale computation without explicit knowledge of the noise level.
  • The derived bounds apply in expectation to zero-mean bounded-variance noise and with high probability to sub-Gaussian noise.
  • Numerical experiments confirm that the parameter selected by the rule is nearly optimal and that the adaptive method works in practice.

Where Pith is reading between the lines

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

  • For discretizations whose eigenvalues are known to decay polynomially, the a priori rule could replace more expensive parameter-tuning procedures such as cross-validation.
  • The high-probability bounds could support uncertainty quantification by providing explicit probabilistic guarantees on reconstruction accuracy.
  • The same assumption and bounding technique might extend to other regularization schemes or to continuous operator settings if analogous eigenvalue control holds.

Load-bearing premise

The generalized eigenvalues of the discrete forward operator are upper-bounded by a polynomial in their ordering index.

What would settle it

Compute the generalized eigenvalues on a discretization of an ill-posed problem; if they violate the polynomial upper bound yet the observed reconstruction error with the a priori parameter still matches the predicted rate, or if they obey the bound but the error exceeds the bound, the claim is falsified.

Figures

Figures reproduced from arXiv: 2605.18259 by Duan-Peng Ling, Wenlong Zhang.

Figure 1
Figure 1. Figure 1: Output error √ 1 n ∥Axλ − Ax∗∥ versus the regularization parameter λ on a log–log scale for different discretization levels n, illustrating the near-optimality of the parameter choice rule (3.18). To examine the scaling predicted by the expectation bounds, we performed a Monte Carlo ex￾periment for the discretization levels n ∈ {1000, 2000, 4000, 8000, 16000} and the noise levels δ ∈ {10−1 , 10−2 , 10−3 , … view at source ↗
Figure 2
Figure 2. Figure 2: Log–log plots of λ versus E[n −1/2∥Axλ − Ax∗∥] (left) and E[n −1/2∥B(xλ − x ∗ )∥] (right) with B = (A⊤A) 1/4 for n ∈ {1000, 2000, 4000, 8000, 16000} and δ ∈ {10−1 , 10−2 , 10−3 , 10−4}. The solid lines denote least-squares fits in logarithmic coordinates, with fitted slopes 0.498 and 0.250, while the dashed lines indicate the reference slopes 1/2 and 1/4, respectively. The observed agreement supports the p… view at source ↗
Figure 3
Figure 3. Figure 3: Convergence histories of the iteratively selected regularization parameter [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Reconstruction results at three noise levels, namely [PITH_FULL_IMAGE:figures/full_fig_p017_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Decay of the generalized eigenvalues ρk versus the index k on a double-logarithmic scale for two discretization levels: n = 10000 (left) and n = 32400 (right) [PITH_FULL_IMAGE:figures/full_fig_p018_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Comparison of output errors √ 1 n ∥Axλ − Ax∗∥ versus the regularization parameter λ for two representative settings: δ = 0.01, n = 10000, and δ = 0.001, n = 32400. In both cases, the error first decreases, then attains a minimum in an intermediate parameter range, and finally increases rapidly for larger λ. The predicted parameters λpred, marked by red stars, lie close to the minima of the corresponding er… view at source ↗
Figure 7
Figure 7. Figure 7: Empirical distribution of √ 1 n ∥Axλ − Ax∗∥ over 10000 Monte Carlo samples: histogram (left) and normal QQ plot (right). The results indicate an approximately Gaussian distribution with mild tail deviations. then levels off. For the smaller noise level δ = 0.001 with n = 32400, the iteration selects a substantially smaller parameter, approximately 1.33×10−6 , and achieves a lower final output error. Figure… view at source ↗
read the original abstract

We study weighted Tikhonov regularization for large-scale linear discrete ill-posed problems with random noise. Under a polynomial upper-bound assumption on the generalized eigenvalues of the discrete forward operator, we derive stochastic error bounds for two noise models: expectation bounds for independent zero-mean bounded-variance noise, and high-probability bounds for independent sub-Gaussian noise. The analysis yields an a priori parameter-choice rule and suggests an adaptive strategy suitable for large-scale computation. Numerical experiments support the theory and show that the predicted parameter is nearly optimal and that the adaptive method is effective in practice.

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

1 major / 0 minor

Summary. The manuscript analyzes stochastic error bounds for weighted Tikhonov regularization of large-scale linear discrete ill-posed problems. Under the assumption that the generalized eigenvalues of the discrete forward operator satisfy a polynomial upper bound λ_j ≤ C j^{-α} (α > 0), expectation bounds are derived for independent zero-mean bounded-variance noise and high-probability bounds for independent sub-Gaussian noise. The analysis produces an a priori parameter-choice rule and an adaptive strategy for large-scale settings. Numerical experiments on standard test problems are reported to illustrate the theory and indicate that the predicted parameter is nearly optimal while the adaptive method is effective.

Significance. If the polynomial eigenvalue-decay assumption holds for the operators arising in typical large-scale discretizations, the derived stochastic bounds and the associated a priori/adaptive parameter rules would constitute a useful contribution to regularization theory for random-noise inverse problems. The explicit treatment of both expectation and high-probability settings, together with a computationally feasible adaptive strategy, strengthens the practical relevance. The numerical illustrations provide initial evidence of performance, but the overall significance remains conditional on verification of the modeling hypothesis.

major comments (1)
  1. [Numerical experiments] The central theorems (preceding the main results) and the subsequent a priori parameter rule rest on the polynomial upper-bound assumption λ_j ≤ C j^{-α}. The numerical experiments section reports results on standard discretizations of integral operators yet contains no computation, table, or plot of the observed generalized eigenvalue (or singular-value) decay that would confirm the assumption holds with the stated form for the concrete matrices employed. Without this check, the claim that the predicted parameter is “nearly optimal” and that the experiments support the derived rates rests on an unverified modeling hypothesis rather than on the actual operators tested.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and constructive feedback on our manuscript. We address the major comment point by point below.

read point-by-point responses

  1. Referee: [Numerical experiments] The central theorems (preceding the main results) and the subsequent a priori parameter rule rest on the polynomial upper-bound assumption λ_j ≤ C j^{-α}. The numerical experiments section reports results on standard discretizations of integral operators yet contains no computation, table, or plot of the observed generalized eigenvalue (or singular-value) decay that would confirm the assumption holds with the stated form for the concrete matrices employed. Without this check, the claim that the predicted parameter is “nearly optimal” and that the experiments support the derived rates rests on an unverified modeling hypothesis rather than on the actual operators tested.

    Authors: We agree that including a verification of the polynomial eigenvalue decay assumption for the specific test problems would make the numerical section more convincing and directly link the experiments to the theoretical assumptions. In the revised version of the manuscript, we will add a new figure showing the decay of the generalized eigenvalues for the discretizations used in the experiments (such as those from the Regularization Tools package). This will demonstrate that the assumption λ_j ≤ C j^{-α} holds for suitable α > 0, thereby justifying the application of our derived bounds and parameter-choice rules to these problems. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation proceeds from explicit assumptions to derived bounds

full rationale

The paper explicitly invokes a polynomial upper-bound assumption on the generalized eigenvalues of the discrete forward operator as the foundation for deriving stochastic error bounds (expectation bounds under bounded-variance noise and high-probability bounds under sub-Gaussian noise) and the associated a priori parameter-choice rule. No quoted steps reduce these bounds or rules back to fitted parameters, self-citations, or input data by construction. The analysis is forward from the stated modeling hypothesis and noise models to the convergence results, with numerical experiments presented only as empirical support rather than definitional inputs. This constitutes a standard assumption-based theoretical derivation without load-bearing circular reductions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim depends on one key domain assumption about eigenvalue decay; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Polynomial upper-bound assumption on the generalized eigenvalues of the discrete forward operator
    Invoked to derive the stochastic error bounds and a priori parameter choice rule

pith-pipeline@v0.9.0 · 5614 in / 1200 out tokens · 42919 ms · 2026-05-20T00:04:55.184704+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

26 extracted references · 26 canonical work pages

  1. [1]

    Andrews and B

    H. Andrews and B. Hunt.Digital Image Restoration. Prentice Hall, Englewood Cliffs, NJ, 1977

    work page 1977

  2. [2]

    Bianchi, M

    D. Bianchi, M. Donatelli, D. Furchí, and L. Reichel. Convergence analysis and parameter estima- tion for the iterated arnoldi–tikhonov method.Numerische Mathematik, 157:749–779, 2025

    work page 2025

  3. [3]

    A. F. Boden, D. C. Redding, R. J. Hanisch, and J. Mo. Massively parallel spatially-variant maximum likelihood restoration of hubble space telescope imagery.Journal of the Optical Society of America A, 13:1537–1545, 1996

    work page 1996

  4. [4]

    N. K. Bose and K. J. Boo. High-resolution image reconstruction with multisensors.International Journal of Imaging Systems and Technology, 9:294–304, 1998

    work page 1998

  5. [5]

    Buccini, S

    A. Buccini, S. Gazzola, L. Onisk, M. Pasha, and L. Reichel. Projected iterated tikhonov in general form with adaptive choice of the regularization parameter.Numerical Algorithms, 100:1617–1637, 2025

    work page 2025

  6. [6]

    T. M. Buzug.Computed Tomography. Springer, Berlin, 2008

    work page 2008

  7. [7]

    Z. Chen, R. Tuo, and W. Zhang. Stochastic convergence of a nonconforming finite element method for the thin plate spline smoother for observational data.SIAM Journal on Numerical Analysis, 56:635–659, 2018

    work page 2018

  8. [8]

    Chung, E

    J. Chung, E. Haber, and J. Nagy. Numerical methods for coupled super-resolution.Inverse Problems, 22:1261–1272, 2006

    work page 2006

  9. [9]

    Chung and S

    J. Chung and S. Gazzola. Computational methods for large-scale inverse problems: A survey on hybrid projection methods.SIAM Review, 66(2):205–284, 2024

    work page 2024

  10. [10]

    Chung and K

    J. Chung and K. Palmer. A hybrid LSMR algorithm for large-scale tikhonov regularization.SIAM Journal on Scientific Computing, 37(5):S562–S580, 2015. 19 (a) Convergence history of the adaptive reg- ularization parameterλ k forδ= 0.01and n= 10000. (b) Convergence history of the adaptive reg- ularization parameterλ k forδ= 0.001and n= 32400. (c) The output e...

    work page 2015

  11. [11]

    Chung and A

    J. Chung and A. K. Saibaba. Generalized hybrid iterative methods for large-scale bayesian inverse problems.SIAM Journal on Scientific Computing, 39(5):S24–S46, 2017

    work page 2017

  12. [12]

    C. L. Epstein.Introduction to the Mathematics of Medical Imaging. SIAM, Philadelphia, 2nd edition, 2007

    work page 2007

  13. [13]

    Gazzola, P

    S. Gazzola, P. C.Hansen, and J. G. Nagy. IR Tools: A MATLAB package of iterative regulariza- tion methods and large-scale test problems.Numerical Algorithms, 81:773–811, 2019. Software 20 available athttps://github.com/jnagy1/IRtools

    work page 2019

  14. [14]

    G. H. Golub, M. Heath, and G. Wahba. Generalized cross-validation as a method for choosing a good ridge parameter.Technometrics, 21(2):215–223, 1979

    work page 1979

  15. [15]

    Haber.Computational Methods in Geophysical Electromagnetics

    E. Haber.Computational Methods in Geophysical Electromagnetics. SIAM, Philadelphia, 2014

    work page 2014

  16. [16]

    P. C. Hansen. Analysis of discrete ill-posed problems by means of the L-curve.SIAM Review, 34:561–580, 1992

    work page 1992

  17. [17]

    P. C. Hansen and J. S. Jørgensen. AIR tools II: Algebraic iterative reconstruction meth- ods, improved implementation.Numerical algorithms, 79:107–137, 2018. Software available at https://github.com/jakobsj/AIRToolsII/

    work page 2018

  18. [18]

    P. C. Hansen, J. G. Nagy, and D. P. O’Leary.Deblurring Images: Matrices, Spectra, and Filtering. SIAM, Philadelphia, PA, 2006

    work page 2006

  19. [19]

    P. C. Hansen and D. P. O’Leary. The use of the L-curve in the regularization of discrete ill-posed problems.SIAM Journal on Scientific Computing, 14(6):1487–1503, 1993

    work page 1993

  20. [20]

    Hauptmann, S

    A. Hauptmann, S. Mukherjee, C.-B. Schönlieb, and F. Sherry. Convergent regularization in inverse problems and linear plug-and-play denoisers.Foundations of Computational Mathematics, 25:1087–1120, 2025

    work page 2025

  21. [21]

    Huang, Q

    J. Huang, Q. Jin, X. Lu, and L. Zhang. On early stopping of stochastic mirror descent method for ill-posed inverse problems.Numerische Mathematik, 157:539–571, 2025

    work page 2025

  22. [22]

    S. M. Jefferies, K. J. Schulze, C. L. Matson, K. Stoltenberg, and E. K. Hege. Blind deconvolution in optical diffusion tomography.Optics express, 10:46–53, 2002

    work page 2002

  23. [23]

    Jiang, J

    J. Jiang, J. Chung, and E. de Sturler. Hybrid projection methods with recycling for inverse problems.SIAM Journal on Scientific Computing, 43(5):S146–S172, 2021

    work page 2021

  24. [24]

    S. A. van de Geer.Empirical Processes in M-Estimation. Cambridge University Press, Cambridge, 2000

    work page 2000

  25. [25]

    A. W. van der Vaart and J. A. Wellner.Weak Convergence and Empirical Processes. Springer, New York, 1996

    work page 1996

  26. [26]

    Y. Wang. Regularization for inverse models in remote sensing.Progress in physical geography, 36:38–59, 2012. 21

    work page 2012