Accelerated projected gradient method for linear inverse problems with sparsity constraints. (English) Zbl 1175.65062

Daubechies, Ingrid; Fornasier, Massimo; Loris, Ignace

J. Fourier Anal. Appl. 14, No. 5-6, 764-792 (2008).

Summary: Regularization of ill-posed linear inverse problems via \(\ell _{1}\) penalization has been proposed for cases where the solution is known to be (almost) sparse. One way to obtain the minimizer of such an \(\ell _{1}\) penalized functional is via an iterative soft-thresholding algorithm. We propose an alternative implementation to \(\ell _{1}\)-constraints, using a gradient method, with projection on \(\ell _{1}\)-balls. The corresponding algorithm uses again iterative soft-thresholding, now with a variable thresholding parameter. We also propose accelerated versions of this iterative method, using ingredients of the (linear) steepest descent method. We prove convergence in norm for one of these projected gradient methods, without and with acceleration.

MSC:

65J10	Numerical solutions to equations with linear operators
65J20	Numerical solutions of ill-posed problems in abstract spaces; regularization
65J22	Numerical solution to inverse problems in abstract spaces
47A52	Linear operators and ill-posed problems, regularization
15A29	Inverse problems in linear algebra
49M30	Other numerical methods in calculus of variations (MSC2010)
65F22	Ill-posedness and regularization problems in numerical linear algebra
65K10	Numerical optimization and variational techniques
90C25	Convex programming
52A41	Convex functions and convex programs in convex geometry

Keywords:

numerical examples; ill-posed linear inverse problems; gradient method; algorithm; iterative method; steepest descent method; convergence

Software:

Mathematica

References:

[1]	Alber, Y.I., Iusem, A.N., Solodov, M.V.: On the projected subgradient method for nonsmooth convex optimization in a Hilbert space. Math. Program. Ser. A 81(1), 23–35 (1998) · Zbl 0919.90122
[2]	Anthoine, S.: Different Wavelet-based Approaches for the Separation of Noisy and Blurred Mixtures of Components. Application to Astrophysical Data. Ph.D. Thesis, Princeton University, 2005
[3]	Brègman, L.M.: Finding the common point of convex sets by the method of successive projection. Dokl. Akad. Nauk SSSR 162, 487–490 (1965)
[4]	Candès, E.J., Donoho, D.L.: New tight frames of curvelets and optimal representations of objects with piecewise C 2 singularities. Commun. Pure Appl. Math. 57(2), 219–266 (2004) · Zbl 1038.94502 · doi:10.1002/cpa.10116
[5]	Candès, E.J., Romberg, J.: Practical signal recovery from random projections. In: Wavelet Applications in Signal and Image Processing XI. Proc. SPIE Conf., vol. 5914 (2004)
[6]	Candès, E.J., Tao, T.: Near-optimal signal recovery from random projections: universal encoding strategies? IEEE Trans. Inf. Theory 52(12), 5406–5425 (2006) · Zbl 1309.94033 · doi:10.1109/TIT.2006.885507
[7]	Candès, E., Romberg, J., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59(8), 1207–1223 (2006) · Zbl 1098.94009 · doi:10.1002/cpa.20124
[8]	Candès, E.J., Romberg, J., Tao, T.: Exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52(2), 489–509 (2006) · Zbl 1231.94017 · doi:10.1109/TIT.2005.862083
[9]	Canuto, C., Urban, K.: Adaptive optimization of convex functionals in Banach spaces. SIAM J. Numer. Anal. 42(5), 2043–2075 (2004) · Zbl 1081.65053 · doi:10.1137/S0036142903429730
[10]	Chambolle, A., DeVore, R.A., Lee, N.-Y., Lucier, B.J.: Nonlinear wavelet image processing: variational problems, compression, and noise removal through wavelet shrinkage. IEEE Trans. Image Process. 7(3), 319–335 (1998) · Zbl 0993.94507 · doi:10.1109/83.661182
[11]	Christensen, O.: An Introduction to Frames and Riesz Bases. Birkhäuser, Boston (2003) · Zbl 1017.42022
[12]	Cohen, A.: Numerical Analysis of Wavelet Methods. Studies in Mathematics and Its Applications, vol. 32. North-Holland, Amsterdam (2003) · Zbl 1038.65151
[13]	Cohen, A., Dahmen, W., DeVore, R.: Adaptive wavelet methods for elliptic operator equations–Convergence rates. Math. Comput. 70, 27–75 (2001) · Zbl 0980.65130
[14]	Cohen, A., Dahmen, W., DeVore, R.: Adaptive wavelet methods II: Beyond the elliptic case. Found. Comput. Math. 2(3), 203–245 (2002) · Zbl 1025.65056 · doi:10.1007/s102080010027
[15]	Cohen, A., Hoffmann, M., Reiss, M.: Adaptive wavelet Galerkin methods for linear inverse problems. SIAM J. Numer. Anal. 42(4), 1479–1501 (2004) · Zbl 1077.65054 · doi:10.1137/S0036142902411793
[16]	Combettes, P.L., Wajs, V.R.: Signal recovery by proximal forward-backward splitting. Multiscale Model. Simul. 4(4), 1168–1200 (2005) · Zbl 1179.94031 · doi:10.1137/050626090
[17]	Dahlke, S., Maass, P.: An outline of adaptive wavelet Galerkin methods for Tikhonov regularization of inverse parabolic problems. In: Hon, J.-C., et al. (eds.) Recent Development in Theories and Numerics. Proceedings of the International Conference on Inverse Problems, Hong Kong, China, January 9–12 2002, pp. 56–66. World Scientific, Singapore (2003) · Zbl 1037.65055
[18]	Dahlke, S., Fornasier, M., Raasch, T.: Adaptive frame methods for elliptic operator equations. Adv. Comput. Math. 27(1), 27–63 (2007) · Zbl 1122.65103 · doi:10.1007/s10444-005-7501-6
[19]	Dahlke, S., Fornasier, M., Raasch, T., Stevenson, R., Werner, M.: Adaptive frame methods for elliptic operator equations: The steepest descent approach. IMA J. Numer. Anal. 27, 717–740 (2007) · Zbl 1153.65050 · doi:10.1093/imanum/drl035
[20]	Daubechies, I.: Ten Lectures on Wavelets. SIAM, Philadelphia (1992) · Zbl 0776.42018
[21]	Daubechies, I., Teschke, G.: Variational image restoration by means of wavelets: Simultaneous decomposition, deblurring, and denoising. Appl. Comput. Harmon. Anal. 19(1), 1–16 (2005) · Zbl 1079.68104 · doi:10.1016/j.acha.2004.12.004
[22]	Daubechies, I., Defrise, M., DeMol, C.: An iterative thresholding algorithm for linear inverse problems. Commun. Pure Appl. Math. 57(11), 1413–1457 (2004) · Zbl 1077.65055 · doi:10.1002/cpa.20042
[23]	Donoho, D.L.: Superresolution via sparsity constraints. SIAM J. Math. Anal. 23(5), 1309–1331 (1992) · Zbl 0769.42007 · doi:10.1137/0523074
[24]	Donoho, D.L.: De-noising by soft-thresholding. IEEE Trans. Inf. Theory 41(3), 613–627 (1995) · Zbl 0820.62002 · doi:10.1109/18.382009
[25]	Donoho, D.L.: Nonlinear solution of linear inverse problems by wavelet-vaguelette decomposition. Appl. Comput. Harmon. Anal. 2(2), 101–126 (1995) · Zbl 0826.65117 · doi:10.1006/acha.1995.1008
[26]	Donoho, D.L.: Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289–1306 (2006) · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582
[27]	Donoho, D.L., Logan, B.F.: Signal recovery and the large sieve. SIAM J. Appl. Math. 52, 577–591 (1992) · Zbl 0768.42001 · doi:10.1137/0152031
[28]	Donoho, D.L., Starck, P.: Uncertainty principles and signal recovery. SIAM J. Appl. Math. 49, 906–931 (1989) · Zbl 0689.42001 · doi:10.1137/0149053
[29]	Efron, B., Hastie, T., Johnstone, I., Tibshirani, R.: Least angle regression. Ann. Stat. 32(2), 407–499 (2004) · Zbl 1091.62054 · doi:10.1214/009053604000000067
[30]	Engl, H.W., Hanke, M., Neubauer, A.: Regularization of Inverse Problems. Mathematics and Its Applications, vol. 375. Kluwer Academic, Dordrecht (1996) · Zbl 0859.65054
[31]	Figueiredo, M.A.T., Nowak, R.D.: An EM algorithm for wavelet-based image restoration. IEEE Trans. Image Proc. 12(8), 906–916 (2003) · Zbl 1279.94015 · doi:10.1109/TIP.2003.814255
[32]	Figueiredo, M.A.T., Nowak, R.D., Wright, S.J.: Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems. IEEE J. Sel. Top. Signal Process. 1(4), 586–597 (2007) · doi:10.1109/JSTSP.2007.910281
[33]	Fornasier, M.: Domain decomposition methods for linear inverse problems with sparsity constraints. Inverse Probl. 23, 2505–2526 (2007) · Zbl 1131.65042 · doi:10.1088/0266-5611/23/6/014
[34]	Fornasier, M., Pitolli, F.: Adaptive iterative thresholding algorithms for magnetoenceophalography (MEG). J. Comput. Appl. Math. (2008, to appear). doi: 10.1016/j.cam.2007.10.048 · Zbl 1146.92022
[35]	Fornasier, M., Rauhut, H.: Iterative thrsholding algorithms. Appl. Comput. Harmon. Anal. 25(2), 187–208 (2008) · Zbl 1149.65038 · doi:10.1016/j.acha.2007.10.005
[36]	Fornasier, M., Rauhut, H.: Recovery algorithms for vector valued data with joint sparsity constraints. SIAM J. Numer. Anal. 46(2), 577–613 (2008) · Zbl 1211.65066 · doi:10.1137/0606668909
[37]	Logan, B.F.: Properties of High-Pass Signals. Ph.D. Thesis, Columbia University, 1965
[38]	Loris, I., Nolet, G., Daubechies, I., Dahlen, F.A.: Tomographic inversion using 1-norm regularization of wavelet coefficients. Geophys. J. Int. 170(1), 359–370 (2007) · doi:10.1111/j.1365-246X.2007.03409.x
[39]	Mallat, S.: A Wavelet Tour of Signal Processing, 2nd edn. Academic Press, San Diego (1999) · Zbl 0998.94510
[40]	Ramlau, R., Teschke, G.: Tikhonov replacement functionals for iteratively solving nonlinear operator equations. Inverse Probl. 21(5), 1571–1592 (2005) · Zbl 1078.47030 · doi:10.1088/0266-5611/21/5/005
[41]	Rauhut, H.: Random sampling of sparse trigonometric polynomials. Appl. Comput. Harmon. Anal. 22(1), 16–42 (2007) · Zbl 1123.94004 · doi:10.1016/j.acha.2006.05.002
[42]	Starck, J.-L., Candès, E.J., Donoho, D.L.: Astronomical image representation by curvelet transform. Astron. Astrophys. 298, 785–800 (2003) · Zbl 1288.94013 · doi:10.1051/0004-6361:20021571
[43]	Starck, J.-L., Nguyen, M.K., Murtagh, F.: Wavelets and curvelets for image deconvolution: a combined approach. Signal Process. 83, 2279–2283 (2003) · Zbl 1145.94329 · doi:10.1016/S0165-1684(03)00150-6
[44]	Teschke, G.: Multi-frame representations in linear inverse problems with mixed multi-constraints. Appl. Comput. Harmon. Anal. 22(1), 43–60 (2007) · Zbl 1144.94002 · doi:10.1016/j.acha.2006.05.003
[45]	van den Berg, E., Friedlander, M.P.: In pursuit of a root. Preprint (2007)
[46]	Wolfram, S.: The Mathematica Book, 5th edn. Wolfram Media/Cambridge University Press, Cambridge (2003)