American Institute of Mathematical Sciences

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

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

Daniel Gerth 1,, , Andreas Hofinger 2, and  Ronny Ramlau 3,

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.

Keywords: Ill-posed problem, stochastic inverse problem, Tikhonov regularization, Bayesian approach, convergence rates.
Mathematics Subject Classification: Primary: 60H35, 65R32; Secondary: 47J06.
Citation: Daniel Gerth, Andreas Hofinger, Ronny Ramlau. On the lifting of deterministic convergence rates for inverse problems with stochastic noise. Inverse Problems & 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.  Google Scholar

[2]

S. Birkholz, G. Steinmeyer, S. Koke, D. Gerth, S. 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.  Google Scholar

[3]

N. Bissantz, T. 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.  Google Scholar

[4]

N. Bissantz, T. Hohage, A. 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.  Google Scholar

[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.  Google Scholar

[6]

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

[7]

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

[8]

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

[9]

I. Daubechies, M. 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.  Google Scholar

[10]

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

[11]

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

[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.  Google Scholar

[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.  Google Scholar

[14]

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

[15]

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

[16]

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

[17]

D. Gerth, B. Hofmann, S. Birkholz, S. 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.  Google Scholar

[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.  Google Scholar

[19]

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

[20]

M. Hanke, A. 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.  Google Scholar

[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.  Google Scholar

[22]

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

[23]

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

[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  Google Scholar

[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.  Google Scholar

[26]

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

[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.  Google Scholar

[28]

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

[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.  Google Scholar

[30]

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

[31]

M. Lassas, E. 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.  Google Scholar

[32]

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

[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.  Google Scholar

[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.  Google Scholar

[35]

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

[36]

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

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.  Google Scholar

[2]

S. Birkholz, G. Steinmeyer, S. Koke, D. Gerth, S. 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.  Google Scholar

[3]

N. Bissantz, T. 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.  Google Scholar

[4]

N. Bissantz, T. Hohage, A. 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.  Google Scholar

[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.  Google Scholar

[6]

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

[7]

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

[8]

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

[9]

I. Daubechies, M. 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.  Google Scholar

[10]

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

[11]

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

[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.  Google Scholar

[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.  Google Scholar

[14]

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

[15]

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

[16]

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

[17]

D. Gerth, B. Hofmann, S. Birkholz, S. 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.  Google Scholar

[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.  Google Scholar

[19]

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

[20]

M. Hanke, A. 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.  Google Scholar

[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.  Google Scholar

[22]

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

[23]

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

[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  Google Scholar

[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.  Google Scholar

[26]

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

[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.  Google Scholar

[28]

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

[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.  Google Scholar

[30]

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

[31]

M. Lassas, E. 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.  Google Scholar

[32]

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

[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.  Google Scholar

[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.  Google Scholar

[35]

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

[36]

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

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
Figure Options

Download full-size image

Download as PowerPoint slide

[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 & 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 & Continuous Dynamical Systems - A, 2010, 26 (2) : 609-623. doi: 10.3934/dcds.2010.26.609
[3]

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

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
[5]

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

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

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 & Continuous Dynamical Systems - B, 2019, 24 (3) : 1273-1295. doi: 10.3934/dcdsb.2019016
[8]

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 & Imaging, 2018, 12 (5) : 1121-1155. doi: 10.3934/ipi.2018047
[9]

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
[10]

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

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

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

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
[14]

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

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

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

Youri V. Egorov, Evariste Sanchez-Palencia. Remarks on certain singular perturbations with ill-posed limit in shell theory and elasticity. Discrete & Continuous Dynamical Systems - A, 2011, 31 (4) : 1293-1305. doi: 10.3934/dcds.2011.31.1293
[18]

Johann Baumeister, Barbara Kaltenbacher, Antonio Leitão. On Levenberg-Marquardt-Kaczmarz iterative methods for solving systems of nonlinear ill-posed equations. Inverse Problems & Imaging, 2010, 4 (3) : 335-350. doi: 10.3934/ipi.2010.4.335
[19]

Olha P. Kupenko, Rosanna Manzo. On optimal controls in coefficients for ill-posed non-Linear elliptic Dirichlet boundary value problems. Discrete & Continuous Dynamical Systems - B, 2018, 23 (4) : 1363-1393. doi: 10.3934/dcdsb.2018155
[20]

Faker Ben Belgacem. Uniqueness for an ill-posed reaction-dispersion model. Application to organic pollution in stream-waters. Inverse Problems & Imaging, 2012, 6 (2) : 163-181. doi: 10.3934/ipi.2012.6.163

2018 Impact Factor: 1.469

Tools

Metrics

  • PDF downloads (21)
  • HTML views (20)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences