August  2017, 11(4): 663-687. doi: 10.3934/ipi.2017031

On the lifting of deterministic convergence rates for inverse problems with stochastic noise

1. 

Technische Universität Chemnitz, Fakultät für Mathematik, D-09107 Chemnitz, Germany

2. 

Radon Institute for Computational and Applied Mathematics (RICAM), Altenbergerstraße 69, A-4040 Linz, Austria

3. 

Radon Institute for Computational and Applied Mathematics (RICAM), (also Industrial Mathematics Institute, Johannes Kepler University Linz), Altenbergerstraße 69, A-4040 Linz, Austria

* Corresponding author: Daniel Gerth

Received  April 2016 Revised  April 2017 Published  June 2017

Fund Project: The first author was supported in part by the Austrian Science Fund (FWF): W1214-N15 and by the German Research Foundation (DFG) under grants HO1454/8-2 and HO1454/10-1.

Both for the theoretical and practical treatment of Inverse Problems, the modeling of the noise is crucial. One either models the measurement via a deterministic worst-case error assumption or assumes a certain stochastic behavior of the noise. Although some connections between both models are known, the communities develop rather independently. In this paper we seek to bridge the gap between the deterministic and the stochastic approach and show convergence and convergence rates for Inverse Problems with stochastic noise by lifting the theory established in the deterministic setting into the stochastic one. This opens the wide field of deterministic regularization methods for stochastic problems without having to do an individual stochastic analysis for each problem.

Citation: Daniel Gerth, Andreas Hofinger, Ronny Ramlau. On the lifting of deterministic convergence rates for inverse problems with stochastic noise. Inverse Problems and Imaging, 2017, 11 (4) : 663-687. doi: 10.3934/ipi.2017031
References:
[1]

S. W. Anzengruber and R. Ramlau, Morozov's discrepancy principle for Tikhonov-type functionals with nonlinear operators Inverse Problems, 26 (2010), 025001, 17pp. doi: 10.1088/0266-5611/26/2/025001.

[2]

S. BirkholzG. SteinmeyerS. KokeD. GerthS. Bürger and B. Hofmann, Phase retrieval via regularization in self-diffraction-based spectral interferometry, JOSA B, 32 (2015), 983-992.  doi: 10.1364/JOSAB.32.000983.

[3]

N. BissantzT. Hohage and A. Munk, Consistency and rates of convergence of nonlinear {T}ikhonov regularization with random noise, Inverse Problems, 20 (2004), 1773-1789.  doi: 10.1088/0266-5611/20/6/005.

[4]

N. BissantzT. HohageA. Munk and F. Ruymgaart, Convergence rates of general regularization methods for statistical inverse problems and applications, SIAM J. Numer. Anal., 45 (2007), 2610-2636.  doi: 10.1137/060651884.

[5]

G. Blanchard and P. Mathé, Discrepancy principle for statistical inverse problems with application to conjugate gradient iteration, Inverse Problems, 28 (2012), 115011, 23pp. doi: 10.1088/0266-5611/28/11/115011.

[6]

V. I. Bogachev, Gaussian Measures, AMS, Providence RI, 1998. doi: 10.1090/surv/062.

[7]

D. Calvetti and E. Somersalo, An introduction to Bayesian Scientific Computing Ten Lectures on Subjective Computing, Springer, New York, 2007.

[8]

R. M. CorlessG. H. GonnetD. E. G. HareD. J. Jeffrey and D. E. Knuth, On the Lambert $W$ function, Adv. Comput. Math., 5 (1996), 329-359.  doi: 10.1007/BF02124750.

[9]

I. DaubechiesM. Defrise and C. De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Comm. Pure Appl. Math., 57 (2004), 1413-1457.  doi: 10.1002/cpa.20042.

[10]

R. M. Dudley, Real Analysis and Probability Wadsworth & Brooks/Cole Advanced Books & Software, Pacific Grove, CA, 1989.

[11]

D. Th. Egoroff, Sur les suites de fonctions mesurables, CR Acad. Sci. Paris, 152 (1911), 244-246. 

[12]

H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems, Kluwer Academic Publishers Group, Dordrecht, 1996. doi: 10.1007/978-94-009-1740-8.

[13]

S. N. Evans and P. B. Stark, Inverse problems as statistics, Inverse Problems, 18 (2002), R55-R97.  doi: 10.1088/0266-5611/18/4/201.

[14]

K. Fan, Entfernung zweier zufälligen Grössen und die Konvergenz nach Wahrscheinlichkeit, Mathematische Zeitschrift, 49 (1944), 681-683.  doi: 10.1007/BF01174225.

[15]

M. Gardner, White and brown music, fractal curves and one-over-f fluctuations, Scientific American, 238 (1978), 16-32. 

[16]

D. Gerth, Problem-adapted Regularization for Inverse Problems in the Deterministic and Stochastic Setting, Ph. D thesis, Johannes Kepler University Linz, 2015.

[17]

D. GerthB. HofmannS. BirkholzS. Koke and G. Steinmeyer, Regularization of an autoconvolution problem in ultrashort laser pulse characterization, Inverse Probl. Sci. Eng, 22 (2014), 245-266.  doi: 10.1080/17415977.2013.769535.

[18]

D. Gerth and R. Ramlau, A stochastic convergence analysis for Tikhonov regularization with sparsity constraints Inverse Problems, 30 (2014), 055009, 24pp. doi: 10.1088/0266-5611/30/5/055009.

[19]

R. Gorenflo and B. Hofmann, On autoconvolution and regularization, Inverse Problems, 10 (1994), 353-373.  doi: 10.1088/0266-5611/10/2/011.

[20]

M. HankeA. Neubauer and O. Scherzer, A convergence analysis of the Landweber iteration for nonlinear ill-posed problems, Numer. Math., 72 (1995), 21-37.  doi: 10.1007/s002110050158.

[21]

T. Helin and M. Burger, Maximum a posteriori probability estimates in infinite-dimensional Bayesian inverse problems Inverse Problems, 31 (2015), 085009, 22pp. doi: 10.1088/0266-5611/31/8/085009.

[22]

A. Hofinger, Ill-posed problems: Extending the Deterministic Theory to a Stochastic Setup, Ph. D thesis, Johannes Kepler University Linz, 2006.

[23]

A. Hofinger, Ill-posed problems: Extending the Deterministic Theory to a Stochastic Setup, Trauner-Verlag, Linz, 2006.

[24]

A. Hofinger, The metrics of prokhorov and ky fan for assessing uncertainty in inverse problems, FWF Sitzungsber. Abt. Ⅱ, 215 (2006), 107–125, Available online http://www.planet-austria.at/0xc1aa500d_0x00239061.pdf

[25]

A. Hofinger and H. K. Pikkarainen, Convergence rate for the Bayesian approach to linear inverse problems, Inverse Problems, 23 (2007), 2469-2484.  doi: 10.1088/0266-5611/23/6/012.

[26]

B. Hofmann, Regularization for Applied Inverse and Ill-posed Problems, Teubner Verlagsgesellschaft, Leipzig, 1986. doi: 10.1007/978-3-322-93034-7.

[27]

T. Hohage and F. Werner, Convergence rates in expectation for Tikhonov-type regularization of inverse problems with Poisson data Inverse Problems, 28 (2012), 104004, 15pp. doi: 10.1088/0266-5611/28/10/104004.

[28]

J. Kaipio and E. Somersalo, Statistical and Computational Inverse Problems, Springer, New York, 2005.

[29]

H. Kekkonen, M. Lassas and S. Siltanen, Analysis of regularized inversion of data corrupted by white Gaussian noise Inverse Problems, 30 (2014), 045009, 18pp. doi: 10.1088/0266-5611/30/4/045009.

[30]

S. Kogan, Electronic Noise and Fluctuations in Solids, Cambridge University Press, Cambridge, 1996. doi: 10.1017/CBO9780511551666.

[31]

M. LassasE. Saksman and S. Siltanen, Discretization-invariant Bayesian inversion and Besov space priors, Inverse Probl. Imaging, 3 (2009), 87-122.  doi: 10.3934/ipi.2009.3.87.

[32]

A. K. Louis, Inverse und Schlecht Gestellte Probleme, B. G. Teubner, Stuttgart, 1989. doi: 10.1007/978-3-322-84808-6.

[33]

K. Mosegaard and M. Sambridge, Monte Carlo analysis of inverse problems, Inverse Problems, 18 (2002), R29-R54.  doi: 10.1088/0266-5611/18/3/201.

[34]

A. Neubauer and H. K. Pikkarainen, Convergence results for the Bayesian inversion theory, J. Inverse Ill-Posed Probl., 16 (2008), 601-613.  doi: 10.1515/JIIP.2008.032.

[35]

A. M. Stuart, Inverse Problems: A Bayesian perspective, Acta Numerica, 19 (2010), 451-559.  doi: 10.1017/S0962492910000061.

[36]

A. Tarantola, Inverse Problem Theory and Methods for Model Parameter Estimation, SIAM, Philadelphia, 2005. doi: 10.1137/1.9780898717921.

show all references

References:
[1]

S. W. Anzengruber and R. Ramlau, Morozov's discrepancy principle for Tikhonov-type functionals with nonlinear operators Inverse Problems, 26 (2010), 025001, 17pp. doi: 10.1088/0266-5611/26/2/025001.

[2]

S. BirkholzG. SteinmeyerS. KokeD. GerthS. Bürger and B. Hofmann, Phase retrieval via regularization in self-diffraction-based spectral interferometry, JOSA B, 32 (2015), 983-992.  doi: 10.1364/JOSAB.32.000983.

[3]

N. BissantzT. Hohage and A. Munk, Consistency and rates of convergence of nonlinear {T}ikhonov regularization with random noise, Inverse Problems, 20 (2004), 1773-1789.  doi: 10.1088/0266-5611/20/6/005.

[4]

N. BissantzT. HohageA. Munk and F. Ruymgaart, Convergence rates of general regularization methods for statistical inverse problems and applications, SIAM J. Numer. Anal., 45 (2007), 2610-2636.  doi: 10.1137/060651884.

[5]

G. Blanchard and P. Mathé, Discrepancy principle for statistical inverse problems with application to conjugate gradient iteration, Inverse Problems, 28 (2012), 115011, 23pp. doi: 10.1088/0266-5611/28/11/115011.

[6]

V. I. Bogachev, Gaussian Measures, AMS, Providence RI, 1998. doi: 10.1090/surv/062.

[7]

D. Calvetti and E. Somersalo, An introduction to Bayesian Scientific Computing Ten Lectures on Subjective Computing, Springer, New York, 2007.

[8]

R. M. CorlessG. H. GonnetD. E. G. HareD. J. Jeffrey and D. E. Knuth, On the Lambert $W$ function, Adv. Comput. Math., 5 (1996), 329-359.  doi: 10.1007/BF02124750.

[9]

I. DaubechiesM. Defrise and C. De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Comm. Pure Appl. Math., 57 (2004), 1413-1457.  doi: 10.1002/cpa.20042.

[10]

R. M. Dudley, Real Analysis and Probability Wadsworth & Brooks/Cole Advanced Books & Software, Pacific Grove, CA, 1989.

[11]

D. Th. Egoroff, Sur les suites de fonctions mesurables, CR Acad. Sci. Paris, 152 (1911), 244-246. 

[12]

H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems, Kluwer Academic Publishers Group, Dordrecht, 1996. doi: 10.1007/978-94-009-1740-8.

[13]

S. N. Evans and P. B. Stark, Inverse problems as statistics, Inverse Problems, 18 (2002), R55-R97.  doi: 10.1088/0266-5611/18/4/201.

[14]

K. Fan, Entfernung zweier zufälligen Grössen und die Konvergenz nach Wahrscheinlichkeit, Mathematische Zeitschrift, 49 (1944), 681-683.  doi: 10.1007/BF01174225.

[15]

M. Gardner, White and brown music, fractal curves and one-over-f fluctuations, Scientific American, 238 (1978), 16-32. 

[16]

D. Gerth, Problem-adapted Regularization for Inverse Problems in the Deterministic and Stochastic Setting, Ph. D thesis, Johannes Kepler University Linz, 2015.

[17]

D. GerthB. HofmannS. BirkholzS. Koke and G. Steinmeyer, Regularization of an autoconvolution problem in ultrashort laser pulse characterization, Inverse Probl. Sci. Eng, 22 (2014), 245-266.  doi: 10.1080/17415977.2013.769535.

[18]

D. Gerth and R. Ramlau, A stochastic convergence analysis for Tikhonov regularization with sparsity constraints Inverse Problems, 30 (2014), 055009, 24pp. doi: 10.1088/0266-5611/30/5/055009.

[19]

R. Gorenflo and B. Hofmann, On autoconvolution and regularization, Inverse Problems, 10 (1994), 353-373.  doi: 10.1088/0266-5611/10/2/011.

[20]

M. HankeA. Neubauer and O. Scherzer, A convergence analysis of the Landweber iteration for nonlinear ill-posed problems, Numer. Math., 72 (1995), 21-37.  doi: 10.1007/s002110050158.

[21]

T. Helin and M. Burger, Maximum a posteriori probability estimates in infinite-dimensional Bayesian inverse problems Inverse Problems, 31 (2015), 085009, 22pp. doi: 10.1088/0266-5611/31/8/085009.

[22]

A. Hofinger, Ill-posed problems: Extending the Deterministic Theory to a Stochastic Setup, Ph. D thesis, Johannes Kepler University Linz, 2006.

[23]

A. Hofinger, Ill-posed problems: Extending the Deterministic Theory to a Stochastic Setup, Trauner-Verlag, Linz, 2006.

[24]

A. Hofinger, The metrics of prokhorov and ky fan for assessing uncertainty in inverse problems, FWF Sitzungsber. Abt. Ⅱ, 215 (2006), 107–125, Available online http://www.planet-austria.at/0xc1aa500d_0x00239061.pdf

[25]

A. Hofinger and H. K. Pikkarainen, Convergence rate for the Bayesian approach to linear inverse problems, Inverse Problems, 23 (2007), 2469-2484.  doi: 10.1088/0266-5611/23/6/012.

[26]

B. Hofmann, Regularization for Applied Inverse and Ill-posed Problems, Teubner Verlagsgesellschaft, Leipzig, 1986. doi: 10.1007/978-3-322-93034-7.

[27]

T. Hohage and F. Werner, Convergence rates in expectation for Tikhonov-type regularization of inverse problems with Poisson data Inverse Problems, 28 (2012), 104004, 15pp. doi: 10.1088/0266-5611/28/10/104004.

[28]

J. Kaipio and E. Somersalo, Statistical and Computational Inverse Problems, Springer, New York, 2005.

[29]

H. Kekkonen, M. Lassas and S. Siltanen, Analysis of regularized inversion of data corrupted by white Gaussian noise Inverse Problems, 30 (2014), 045009, 18pp. doi: 10.1088/0266-5611/30/4/045009.

[30]

S. Kogan, Electronic Noise and Fluctuations in Solids, Cambridge University Press, Cambridge, 1996. doi: 10.1017/CBO9780511551666.

[31]

M. LassasE. Saksman and S. Siltanen, Discretization-invariant Bayesian inversion and Besov space priors, Inverse Probl. Imaging, 3 (2009), 87-122.  doi: 10.3934/ipi.2009.3.87.

[32]

A. K. Louis, Inverse und Schlecht Gestellte Probleme, B. G. Teubner, Stuttgart, 1989. doi: 10.1007/978-3-322-84808-6.

[33]

K. Mosegaard and M. Sambridge, Monte Carlo analysis of inverse problems, Inverse Problems, 18 (2002), R29-R54.  doi: 10.1088/0266-5611/18/3/201.

[34]

A. Neubauer and H. K. Pikkarainen, Convergence results for the Bayesian inversion theory, J. Inverse Ill-Posed Probl., 16 (2008), 601-613.  doi: 10.1515/JIIP.2008.032.

[35]

A. M. Stuart, Inverse Problems: A Bayesian perspective, Acta Numerica, 19 (2010), 451-559.  doi: 10.1017/S0962492910000061.

[36]

A. Tarantola, Inverse Problem Theory and Methods for Model Parameter Estimation, SIAM, Philadelphia, 2005. doi: 10.1137/1.9780898717921.

Figure 1.  $\mathbb{E}(||\epsilon||)^2/ \alpha$ (dashed) and regularization parameter $\alpha$ (solid) versus variance $\eta$. Left: A constant value of $\tau$ in the discrepancy principle with the expectation of the noise leads to the regularization parameter decreasing too fast, thus the deterministic condition $\delta^2/\alpha\rightarrow0$ is violated (dashed line) Right: increasing $\tau$ appropriately with decreasing variance resolves this issue
[1]

Guozhi Dong, Bert Jüttler, Otmar Scherzer, Thomas Takacs. Convergence of Tikhonov regularization for solving ill-posed operator equations with solutions defined on surfaces. Inverse Problems and Imaging, 2017, 11 (2) : 221-246. doi: 10.3934/ipi.2017011

[2]

Misha Perepelitsa. An ill-posed problem for the Navier-Stokes equations for compressible flows. Discrete and Continuous Dynamical Systems, 2010, 26 (2) : 609-623. doi: 10.3934/dcds.2010.26.609

[3]

Ye Zhang, Bernd Hofmann. Two new non-negativity preserving iterative regularization methods for ill-posed inverse problems. Inverse Problems and Imaging, 2021, 15 (2) : 229-256. doi: 10.3934/ipi.2020062

[4]

Stefan Kindermann. Convergence of the gradient method for ill-posed problems. Inverse Problems and Imaging, 2017, 11 (4) : 703-720. doi: 10.3934/ipi.2017033

[5]

Matthew A. Fury. Regularization for ill-posed inhomogeneous evolution problems in a Hilbert space. Conference Publications, 2013, 2013 (special) : 259-272. doi: 10.3934/proc.2013.2013.259

[6]

Alfredo Lorenzi, Luca Lorenzi. A strongly ill-posed integrodifferential singular parabolic problem in the unit cube of $\mathbb{R}^n$. Evolution Equations and Control Theory, 2014, 3 (3) : 499-524. doi: 10.3934/eect.2014.3.499

[7]

Adriano De Cezaro, Johann Baumeister, Antonio Leitão. Modified iterated Tikhonov methods for solving systems of nonlinear ill-posed equations. Inverse Problems and Imaging, 2011, 5 (1) : 1-17. doi: 10.3934/ipi.2011.5.1

[8]

Zonghao Li, Caibin Zeng. Center manifolds for ill-posed stochastic evolution equations. Discrete and Continuous Dynamical Systems - B, 2022, 27 (5) : 2483-2499. doi: 10.3934/dcdsb.2021142

[9]

Peter I. Kogut, Olha P. Kupenko. On optimal control problem for an ill-posed strongly nonlinear elliptic equation with $p$-Laplace operator and $L^1$-type of nonlinearity. Discrete and Continuous Dynamical Systems - B, 2019, 24 (3) : 1273-1295. doi: 10.3934/dcdsb.2019016

[10]

Felix Lucka, Katharina Proksch, Christoph Brune, Nicolai Bissantz, Martin Burger, Holger Dette, Frank Wübbeling. Risk estimators for choosing regularization parameters in ill-posed problems - properties and limitations. Inverse Problems and Imaging, 2018, 12 (5) : 1121-1155. doi: 10.3934/ipi.2018047

[11]

Markus Haltmeier, Antonio Leitão, Otmar Scherzer. Kaczmarz methods for regularizing nonlinear ill-posed equations I: convergence analysis. Inverse Problems and Imaging, 2007, 1 (2) : 289-298. doi: 10.3934/ipi.2007.1.289

[12]

Sergiy Zhuk. Inverse problems for linear ill-posed differential-algebraic equations with uncertain parameters. Conference Publications, 2011, 2011 (Special) : 1467-1476. doi: 10.3934/proc.2011.2011.1467

[13]

De-han Chen, Daijun jiang. Convergence rates of Tikhonov regularization for recovering growth rates in a Lotka-Volterra competition model with diffusion. Inverse Problems and Imaging, 2021, 15 (5) : 951-974. doi: 10.3934/ipi.2021023

[14]

Markus Haltmeier, Richard Kowar, Antonio Leitão, Otmar Scherzer. Kaczmarz methods for regularizing nonlinear ill-posed equations II: Applications. Inverse Problems and Imaging, 2007, 1 (3) : 507-523. doi: 10.3934/ipi.2007.1.507

[15]

Matthew A. Fury. Estimates for solutions of nonautonomous semilinear ill-posed problems. Conference Publications, 2015, 2015 (special) : 479-488. doi: 10.3934/proc.2015.0479

[16]

Paola Favati, Grazia Lotti, Ornella Menchi, Francesco Romani. An inner-outer regularizing method for ill-posed problems. Inverse Problems and Imaging, 2014, 8 (2) : 409-420. doi: 10.3934/ipi.2014.8.409

[17]

Jussi Korpela, Matti Lassas, Lauri Oksanen. Discrete regularization and convergence of the inverse problem for 1+1 dimensional wave equation. Inverse Problems and Imaging, 2019, 13 (3) : 575-596. doi: 10.3934/ipi.2019027

[18]

Stefan Kindermann, Andreas Neubauer. On the convergence of the quasioptimality criterion for (iterated) Tikhonov regularization. Inverse Problems and Imaging, 2008, 2 (2) : 291-299. doi: 10.3934/ipi.2008.2.291

[19]

Luca Rondi. On the regularization of the inverse conductivity problem with discontinuous conductivities. Inverse Problems and Imaging, 2008, 2 (3) : 397-409. doi: 10.3934/ipi.2008.2.397

[20]

Jiangfeng Huang, Zhiliang Deng, Liwei Xu. A Bayesian level set method for an inverse medium scattering problem in acoustics. Inverse Problems and Imaging, 2021, 15 (5) : 1077-1097. doi: 10.3934/ipi.2021029

2020 Impact Factor: 1.639

Metrics

  • PDF downloads (141)
  • HTML views (61)
  • Cited by (1)

Other articles
by authors

[Back to Top]