Inverse problems in spaces of measures

Kristian Bredies; Hanna Katriina Pikkarainen

ESAIM: Control, Optimisation and Calculus of Variations (2013)

  • Volume: 19, Issue: 1, page 190-218
  • ISSN: 1292-8119

Abstract

top
The ill-posed problem of solving linear equations in the space of vector-valued finite Radon measures with Hilbert space data is considered. Approximate solutions are obtained by minimizing the Tikhonov functional with a total variation penalty. The well-posedness of this regularization method and further regularization properties are mentioned. Furthermore, a flexible numerical minimization algorithm is proposed which converges subsequentially in the weak* sense and with rate 𝒪(n-1) in terms of the functional values. Finally, numerical results for sparse deconvolution demonstrate the applicability for a finite-dimensional discrete data space and infinite-dimensional solution space.

How to cite

top

Bredies, Kristian, and Pikkarainen, Hanna Katriina. "Inverse problems in spaces of measures." ESAIM: Control, Optimisation and Calculus of Variations 19.1 (2013): 190-218. <http://eudml.org/doc/272801>.

@article{Bredies2013,
abstract = {The ill-posed problem of solving linear equations in the space of vector-valued finite Radon measures with Hilbert space data is considered. Approximate solutions are obtained by minimizing the Tikhonov functional with a total variation penalty. The well-posedness of this regularization method and further regularization properties are mentioned. Furthermore, a flexible numerical minimization algorithm is proposed which converges subsequentially in the weak* sense and with rate &#x1d4aa;(n-1) in terms of the functional values. Finally, numerical results for sparse deconvolution demonstrate the applicability for a finite-dimensional discrete data space and infinite-dimensional solution space.},
author = {Bredies, Kristian, Pikkarainen, Hanna Katriina},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
keywords = {inverse problems; vector-valued finite Radon measures; Tikhonov regularization; delta-peak solutions; generalized conditional gradient method; iterative soft-thresholding; sparse deconvolution; ill-posed problem; linear equation; Hilbert space; numerical results},
language = {eng},
number = {1},
pages = {190-218},
publisher = {EDP-Sciences},
title = {Inverse problems in spaces of measures},
url = {http://eudml.org/doc/272801},
volume = {19},
year = {2013},
}

TY - JOUR
AU - Bredies, Kristian
AU - Pikkarainen, Hanna Katriina
TI - Inverse problems in spaces of measures
JO - ESAIM: Control, Optimisation and Calculus of Variations
PY - 2013
PB - EDP-Sciences
VL - 19
IS - 1
SP - 190
EP - 218
AB - The ill-posed problem of solving linear equations in the space of vector-valued finite Radon measures with Hilbert space data is considered. Approximate solutions are obtained by minimizing the Tikhonov functional with a total variation penalty. The well-posedness of this regularization method and further regularization properties are mentioned. Furthermore, a flexible numerical minimization algorithm is proposed which converges subsequentially in the weak* sense and with rate &#x1d4aa;(n-1) in terms of the functional values. Finally, numerical results for sparse deconvolution demonstrate the applicability for a finite-dimensional discrete data space and infinite-dimensional solution space.
LA - eng
KW - inverse problems; vector-valued finite Radon measures; Tikhonov regularization; delta-peak solutions; generalized conditional gradient method; iterative soft-thresholding; sparse deconvolution; ill-posed problem; linear equation; Hilbert space; numerical results
UR - http://eudml.org/doc/272801
ER -

References

top
  1. [1] R.A. Adams and J.J.F. Fournier, Sobolev spaces. Academic Press (2003). Zbl1098.46001MR2424078
  2. [2] L. Ambrosio, N. Fusco and D. Pallara, Functions of Bounded Variation and Free Discontinuity Problems. Oxford University Press (2000). Zbl0957.49001MR1857292
  3. [3] A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci.2 (2009) 183–202. Zbl1175.94009MR2486527
  4. [4] T. Bonesky, K.S. Kazimierski, P. Maass, F. Schöpfer and T. Schuster, Minimization of Tikhonov functionals in Banach spaces. Abstr. Appl. Anal. (2008) 192679. Zbl05313168MR2393115
  5. [5] K. Bredies and D.A. Lorenz, Iterated hard shrinkage for minimization problems with sparsity constraints. SIAM J. Sci. Comput.30 (2008) 657–683. Zbl1170.46067MR2385880
  6. [6] K. Bredies and D.A. Lorenz, Linear convergence of iterative soft-thresholding. J. Fourier Anal. Appl.14 (2008) 813–837. Zbl1175.65061MR2461608
  7. [7] K. Bredies, D.A. Lorenz and P. Maass, A generalized conditional gradient method and its connection to an iterative shrinkage method. Comput. Optim. Appl.42 (2009) 173–193. Zbl1179.90326MR2471395
  8. [8] K. Bredies, T. Alexandrov, J. Decker, D.A. Lorenz and H. Thiele, Sparse deconvolution for peak picking and ion charge estimation in mass spectrometry, in Progress in Industrial Mathematics at ECMI 2008, edited by H.-G. Bock et al., Springer (2010) 287–292. Zbl1220.78067
  9. [9] M. Burger and S. Osher, Convergence rates of convex variational regularization. Inverse Prob.20 (2004) 1411–1421. Zbl1068.65085MR2109126
  10. [10] E.J. Candès, J.K. Romberg and T. Tao, Stable signal recovery from incomplete and inaccurate measurements. Comm. Pure Appl. Math.59 (2006) 1207–1223. Zbl1098.94009MR2230846
  11. [11] C. Clason and K. Kunisch, A duality-based approach to elliptic control problems in non-reflexive Banach spaces. ESAIM : COCV 17 (2011) 243–266. Zbl1213.49041MR2775195
  12. [12] P.L. Combettes and V.R. Wajs, Signal recovery by proximal forward-backward splitting. Multiscale Model. Simul.4 (2005) 1168–1200. Zbl1179.94031MR2203849
  13. [13] J.B. Conway, A course in functional analysis. Springer (1990). Zbl0706.46003MR1070713
  14. [14] 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. Zbl1077.65055MR2077704
  15. [15] D.L. Donoho, Compressed sensing. IEEE Trans. Inf. Theory52 (2006) 1289–1306. Zbl1288.94016MR2241189
  16. [16] D.L. Donoho, M. Elad and V.N. Temlyakov, Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Trans. Inf. Theory52 (2006) 6–18. Zbl1288.94017MR2237332
  17. [17] C. Dossal and S. Mallat, Sparse spike deconvolution with minimum scale, in Proc. of SPARS’05 (2005). 
  18. [18] N. Dunford and J.T. Schwartz, Linear Operators. I. General Theory. Interscience Publishers (1958). Zbl0084.10402MR117523
  19. [19] B. Efron, T. Hastie, I. Johnstone and R. Tibshirani, Least angle regression. Ann. Statist.32 (2004) 407–499. Zbl1091.62054MR2060166
  20. [20] I. Ekeland and R. Temam, Convex analysis and variational problems. North-Holland (1976). Zbl0322.90046MR463994
  21. [21] H.W. Engl and G. Landl, Convergence rates for maximum entropy regularization. SIAM J. Numer. Anal.30 (1993) 1509–1536. Zbl0790.65110MR1239834
  22. [22] H.W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems. Kluwer Academic Publishers (1996). Zbl0859.65054MR1408680
  23. [23] M.A.T. Figueiredo, R.D. Nowak and S.J. Wright, Gradient projection for sparse reconstruction : Application to compressed sensing and other inverse problems. IEEE J. Sel. Top. Signal Process.1 (2007) 586–597. 
  24. [24] I. Fonseca and G. Leoni, Modern methods in the calculus of variations : Lp spaces. Springer (2007). Zbl1153.49001MR2341508
  25. [25] M. Fornasier and H. Rauhut, Recovery algorithms for vector valued data with joint sparsity constraints. SIAM J. Numer. Anal.46 (2008) 577–613. Zbl1211.65066MR2383204
  26. [26] J.-J. Fuchs, On sparse representations in arbitrary redundant bases. IEEE Trans. Inf. Theory.50 (2004) 1341–1344. Zbl1284.94018MR2094894
  27. [27] A.L. Gibbs and F.E. Su, On choosing and bounding probability metrics. Int. Stat. Rev.70 (2002) 419–435. Zbl1217.62014
  28. [28] M. Grasmair, M. Haltmeier and O. Scherzer, Sparse regularization with ℓq penalty term. Inverse Prob. 24 (2008) 055020. Zbl1157.65033MR2438955
  29. [29] R. Griesse and D.A. Lorenz, A semismooth Newton method for Tikhonov functionals with sparsity constraints. Inverse Prob. 24 (2008) 035007. Zbl1152.49030MR2421961
  30. [30] P. Grisvard, Elliptic Problems in Nonsmooth Domains. Pitman Publishing Limited (1985). Zbl0695.35060MR775683
  31. [31] T. Hein, Tikhonov regularization in Banach spaces – improved convergence rates results. Inverse Prob. 25 (2009) 035002. Zbl1170.65033MR2480172
  32. [32] B. Hofmann, B. Kaltenbacher, C. Pöschl and O. Scherzer, A convergence rates result for Tikhonov regularization in Banach spaces with non-smooth operators. Inverse Prob.23 (2007) 987–1010. Zbl1131.65046MR2329928
  33. [33] L. Hörmander, The Analysis of Linear Partial Differential Operators I. Springer-Verlag (1990). Zbl0712.35001MR1065993
  34. [34] V.K. Ivanov, V.V. Vasin and V.P. Tanana, Theory of linear ill-posed problems and its applications, 2nd edition. Inverse and Ill-posed Problems Series, VSP, Utrecht (2002). Zbl1037.65056MR2010817
  35. [35] H. Lee, A. Battle, R. Raina and A.Y. Ng, Efficient sparse coding algorithms, in Advances in Neural Information Processing Systems, edited by B. Schölkopf, J. Platt and T. Hoffman. MIT Press 19 (2007) 801–808. 
  36. [36] J. Lindenstrauss and L. Tzafriri, Classical Banach Spaces II. Function Spaces. Springer (1979). Zbl0852.46015MR540367
  37. [37] D.A. Lorenz, Convergence rates and source conditions for Tikhonov regularization with sparsity constraints. J. Inverse Ill-Posed Probl.16 (2008) 463–478. Zbl1161.65041MR2442066
  38. [38] D.A. Lorenz and D. Trede, Optimal convergence rates for Tikhonov regularization in Besov scales. Inverse Prob. 24 (2008) 055010. Zbl1147.49030MR2438945
  39. [39] D.A. Lorenz and D. Trede, Greedy deconvolution of point-like objects, in Proc. of SPARS’09 (2009). 
  40. [40] Y. Mao, B. Dong and S. Osher, A nonlinear PDE-based method for sparse deconvolution. Multiscale Model. Simul.8 (2010) 965–976. Zbl1201.35025MR2644319
  41. [41] L.M. Mugnier, T. Fusco and J.-M. Conan, MISTRAL : a myopic edge-preserving image restoration method, with application to astronomical adaptive-optics-corrected long-exposure images. J. Opt. Soc. Am. A21 (2004) 1841–1854. MR2164634
  42. [42] Y.E. Nesterov, A method of solving a convex programming problem with convergence rate O(1/k2). Soviet Math. Dokl.27 (1983) 372–376. Zbl0535.90071
  43. [43] A. Neubauer, On enhanced convergence rates for Tikhonov regularization of nonlinear ill-posed problems in Banach spaces. Inverse Prob. 25 (2009) 065009. Zbl1176.65071MR2506854
  44. [44] E. Resmerita and O. Scherzer, Error estimates for non-quadratic regularization and the relation to enhancement. Inverse Prob.22 (2006) 801–814. Zbl1103.65062MR2235638
  45. [45] O. Scherzer and B. Walch, Sparsity regularization for Radon measures, in Scale Space and Variational Methods in Computer Vision, edited by X.-C. Tai, K. Morken, M. Lysaker and K.-A. Lie. Springer-Verlag (2009) 452–463. 
  46. [46] G. Stadler, Elliptic optimal control problems with L1-control cost and applications for the placement of control devices. Comput. Optim. Appl.44 (2009) 159–181. Zbl1185.49031MR2556849
  47. [47] G. Stampacchia, Le problème de Dirichlet pour les équations elliptiques du second ordre à coefficients discontinus. Ann. Inst. Fourier (Grenoble) 15 (1965) 189–258. Zbl0151.15401MR192177
  48. [48] A.S. Stern, D.L. Donoho and J.C. Hoch, NMR data processing using iterative thresholding and minimum l1-norm reconstruction. J. Magn. Reson.188 (2007) 295–300. 
  49. [49] A.N. Tikhonov, A.S. Leonov and A.G. Yagola, Nonlinear ill-posed problems 1. Chapman & Hall (1998). Zbl0920.65038MR1630660
  50. [50] Z.B. Xu and G.F. Roach, Characteristic inequalities of uniformly convex and uniformly smooth Banach spaces. J. Math. Anal. Appl.157 (1991) 189–210. Zbl0757.46034MR1109451
  51. [51] C. Zălinescu, Convex analysis in general vector spaces. World Scientific (2002). Zbl1023.46003
  52. [52] E. Zeidler, Nonlinear Functional Analysis and its Applications III. Springer-Verlag (1985). Zbl0583.47051MR768749

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.