An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. (English) Zbl 1077.65055

Daubechies, Ingrid; Defrise, Michel; De Mol, Christine

Commun. Pure Appl. Math. 57, No. 11, 1413-1457 (2004).

The linear inverse problem corresponding to an equation \(Kf=h\) with a bounded linear operator \(K:H\to L^2(\Omega)\) on a Hilbert space \(H\) consists in finding an estimate of \(f\) from not exactly given \(h\). One of the best known methods of solving such (possibly ill-posed) problems is the Tikhonov regularization method where a regularization functional has to be minimized which is a sum of discrepancy and additional quadratic constraints multiplied by the regularization parameter.
The authors present a new method which is a generalization of the Tikhonov method. Namely, in place of classical quadratic constraints, a weighted \(l^p\)-norm (\(1\leq p\leq2\)) of expansion coefficients of \(f\) with respect to a particular orthogonal basis in \(H\) is taken as a penalization term added to the discrepancy in the regularization functional. The proposed minimization procedure promotes sparsity of the expansion of \(f\) with respect to the basis under consideration. Wavelet bases as well as other orthogonal bases are taken into account.
To compute the corresponding regularized solution, the authors propose an iterative algorithm for solving a system of nonlinear equations related to the minimizing problem for the regularization functional. The detailed and full mathematical analysis of the proposed method is given. The strong convergence of successive iterates to the minimizer of the regularization functional is proved and stability of regularized solution is shown. The presented general regularization theorem establishes the convergence to the exact solution as the noise level tends to zero. Under some additional a priori assumptions error estimates are derived. Moreover, possible generalizations as well as the numerical complexity of the algorithm are discussed. In the Appendix a brief review of basic definitions of wavelets and their connection with Besov spaces is given.

Reviewer: Teresa Regińska (Warszawa)

MSC:

65J10	Numerical solutions to equations with linear operators
65J22	Numerical solution to inverse problems in abstract spaces
65J20	Numerical solutions of ill-posed problems in abstract spaces; regularization
47A52	Linear operators and ill-posed problems, regularization
42C40	Nontrigonometric harmonic analysis involving wavelets and other special systems
65T60	Numerical methods for wavelets

Keywords:

linear inverse problems; regularization; generalization of the Tikhonov method; nonquadratic constraints; sparse extension; wavelets; iterative algorithm; thresholding; ill-posed problem; convergence; stability; Hilbert space

References:

[1]	Abramovich, Biometrika 85 pp 115– (1998)
[2]	Linear inverse and ill-posed problems. Advances in Electronics and Electron Physics, vol. 75, 1-120. ed. Academic, New York, 1989.
[3]	; Introduction to inverse problems in imaging. Institute of Physics, Bristol, 1998. · Zbl 0914.65060 · doi:10.1887/0750304359
[4]	; Super-resolution by data inversion. Progress in Optics, vol. 36, 129-178. ed. Elsevier, Amsterdam, 1996. · doi:10.1016/S0079-6638(08)70314-7
[5]	Beylkin, Comm Pure Appl Math 44 pp 141– (1991)
[6]	Candès, Ann Statist 30 pp 784– (2002)
[7]	Chambolle, IEEE Trans Image Process 7 pp 319– (1998)
[8]	Chen, SIAM Rev 43 pp 129– (2001)
[9]	Wavelet methods in numerical analysis. Handbook of numerical analysis, vol. 7, 417-711. North-Holland, Amsterdam, 2000. · Zbl 0976.65124
[10]	Cohen, SIAM J Numer Anal
[11]	; A note on wavelet-based inversion algorithms. Inverse problems, image analysis, and medical imaging (New Orleans, LA, 2001), 85-96. Contemporary Mathematics, 313. American Mathematical Society, Providence, R.I., 2002. · doi:10.1090/conm/313/05370
[12]	De Pierro, IEEE Trans Med Im 14 pp 132– (1995)
[13]	Nonlinear approximation. Acta numerica, 1998, 51-150. Acta Numerica, 7. Cambridge University, Cambridge, 1998.
[14]	Dicken, J Inverse Ill-Posed Probl 4 pp 203– (1996)
[15]	Donoho, SIAM J Math Anal 23 pp 1309– (1992)
[16]	Donoho, IEEE Trans Inform Theory 41 pp 613– (1995)
[17]	Donoho, Appl Comput Harmon Anal 2 pp 101– (1995)
[18]	Donoho, SIAM J Math Anal 31 pp 1062– (2000)
[19]	Donoho, Biometrika 81 pp 425– (1994)
[20]	Donoho, J Roy Statist Soc Ser B 57 pp 301– (1995)
[21]	Duffin, Trans Amer Math Soc 72 pp 341– (1952)
[22]	Eicke, Numer Funct Anal Optim 13 pp 413– (1992)
[23]	; ; Regularization of inverse problems. Mathematics and Its Applications, 375. Kluwer, Dordrecht, 1996. · doi:10.1007/978-94-009-1740-8
[24]	Figueiredo, IEEE Trans Image Process 12 pp 906– (2003)
[25]	Franklin, Math Comp 28 pp 889– (1974)
[26]	; ; Independent component analysis. Wiley, New York, 2001. · Zbl 1009.62049 · doi:10.1002/0471221317
[27]	Kalifa, IEEE Trans Image Process 12 pp 446– (2003)
[28]	Landweber, Amer J Math 73 pp 615– (1951)
[29]	Lange, J Comput Graph Stat 9 pp 1– (2000)
[30]	Lee, IEEE Trans Image Process 10 pp 79– (2001)
[31]	Li, Phys Med Biol 47 pp 2599– (2002)
[32]	; ; Wavelets: theory and applications. Wiley, Chichester, 1997. · Zbl 0897.42019
[33]	A wavelet tour of signal processing. 2nd ed. Academic, San Diego, 1999. · Zbl 0998.94510
[34]	Wavelets and operators. Cambridge University, Cambridge, 1992.
[35]	; Fast wavelet-based image deconvolution using the EM algorithm. Proceedings of the 35th Asilomar Conference on Signals, Systems, and Computers (Monterey, CA, Nov. 4-7, 2001), vol. 1, 371-375.
[36]	Opial, Bull Amer Math Soc 73 pp 591– (1967)
[37]	Sardy, J Comput Graph Stat 9 pp 361– (2000)
[38]	Starck, Astronomy and Astrophysics 398 pp 785– (2003)
[39]	Starck, Signal Process 83 pp 2279– (2003)
[40]	Tibshirani, J Roy Statist Soc Ser B 58 pp 267– (1996)