An iteratively reweighted least squares algorithm for sparse regularization. (English) Zbl 1392.65074

Voronin, Sergey; Daubechies, Ingrid

Cwikel, Michael (ed.) et al., Functional analysis, harmonic analysis, and image processing: a collection of papers in honor of Björn Jawerth. Providence, RI: American Mathematical Society (AMS) (ISBN 978-1-4704-2836-5/pbk; 978-1-4704-4166-1/ebook). Contemporary Mathematics 693, 391-411 (2017).

Summary: We present a new algorithm and the corresponding convergence analysis for the regularization of linear inverse problems with sparsity constraints, applied to a new generalized sparsity promoting functional. The algorithm is based on the idea of iteratively reweighted least squares, reducing the minimization at every iteration step to that of a functional including only \(\ell _2\)-norms. This amounts to smoothing of the absolute value function that appears in the generalized sparsity promoting penalty we consider, with the smoothing becoming iteratively less pronounced. We demonstrate that the sequence of iterates of our algorithm converges to a limit that minimizes the original functional.
For the entire collection see [Zbl 1378.46003].

MSC:

65F10

Iterative numerical methods for linear systems

References:

[1]	Beck, Amir; Teboulle, Marc, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 1, 183-202 (2009) · Zbl 1175.94009 · doi:10.1137/080716542
[2]	Cai, Jian-Feng; Osher, Stanley; Shen, Zuowei, Linearized Bregman iterations for compressed sensing, Math. Comp., 78, 267, 1515-1536 (2009) · Zbl 1198.65102 · doi:10.1090/S0025-5718-08-02189-3
[3]	Emmanuel J Candes and Michael B Wakin. An introduction to compressive sampling. Signal Processing Magazine, IEEE, 25(2):21-30, 2008.
[4]	Daubechies, Ingrid; Defrise, Michel; De Mol, Christine, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Comm. Pure Appl. Math., 57, 11, 1413-1457 (2004) · Zbl 1077.65055 · doi:10.1002/cpa.20042
[5]	Daubechies, Ingrid; DeVore, Ronald; Fornasier, Massimo; G{\`“u}nt{\'”u}rk, C. Sinan, Iteratively reweighted least squares minimization for sparse recovery, Comm. Pure Appl. Math., 63, 1, 1-38 (2010) · Zbl 1202.65046 · doi:10.1002/cpa.20303
[6]	Figueiredo, M{\'a}rio A. T.; Bioucas-Dias, Jos{\'e} M.; Nowak, Robert D., Majorization-minimization algorithms for wavelet-based image restoration, IEEE Trans. Image Process., 16, 12, 2980-2991 (2007) · doi:10.1109/TIP.2007.909318
[7]	Fornasier, Massimo; Peter, Steffen; Rauhut, Holger; Worm, Stephan, Conjugate gradient acceleration of iteratively re-weighted least squares methods, Comput. Optim. Appl., 65, 1, 205-259 (2016) · Zbl 1353.90115 · doi:10.1007/s10589-016-9839-8
[8]	Jean Jacques Fuchs. Convergence of a sparse representations algorithm applicable to real or complex data. IEEE Journal of Selected Topics in Signal Processing, 1(4):598-605, 2007.
[9]	Per Christian Hansen. The L-curve and its use in the numerical treatment of inverse problems. IMM, Department of Mathematical Modelling, Technical Universityof Denmark, 1999.
[10]	Frederik J Simons, Ignace Loris, Guust Nolet, Ingrid C Daubechies, S Voronin, JS Judd, Ph A Vetter, J Charlety, and C Vonesch. Solving or resolving global tomographic models with spherical wavelets, and the scale and sparsity of seismic heterogeneity. Geophysical journal international, 187(2):969-988, 2011.
[11]	Voronin, Sergey, Regularization of linear systems with sparsity constraints with applications to large scale inverse problems, 228 pp. (2012), ProQuest LLC, Ann Arbor, MI
[12]	S. Voronin and R. Chartrand. A new generalized thresholding algorithm for inverse problems with sparsity constraints. ICASSP, 2013.
[13]	S. Voronin, G. Ozkaya, and D. Yoshida. Convolution based smooth approximations to the absolute value function with application to non-smooth regularization. ArXiv e-prints, August 2014.
[14]	John Wright, Arvind Ganesh, Shankar Rao, Yigang Peng, and Yi Ma. Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization. In Advances in neural information processing systems, pages 2080-2088, 2009.
[15]	Allen Y Yang, S Shankar Sastry, Arvind Ganesh, and Yi Ma. Fast l1-minimization algorithms and an application in robust face recognition: A review. In Image Processing (ICIP), 2010 17th IEEE International Conference on, pages 1849-1852. IEEE, 2010.
[16]	Yang, Junfeng; Zhang, Yin, Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing, SIAM J. Sci. Comput., 33, 1, 250-278 (2011) · Zbl 1256.65060 · doi:10.1137/090777761
[17]	Yin, Wotao; Osher, Stanley; Goldfarb, Donald; Darbon, Jerome, Bregman iterative algorithms for \(l_1\)-minimization with applications to compressed sensing, SIAM J. Imaging Sci., 1, 1, 143-168 (2008) · Zbl 1203.90153 · doi:10.1137/070703983