publication . Preprint . 2017

Capped Lp approximations for the composite L0 regularization problem

Li, Qia; Zhang, Na;
Open Access English
  • Published: 24 Jul 2017
The composite L0 function serves as a sparse regularizer in many applications. The algorithmic difficulty caused by the composite L0 regularization (the L0 norm composed with a linear mapping) is usually bypassed through approximating the L0 norm. We consider in this paper capped Lp approximations with $p>0$ for the composite L0 regularization problem. For each $p>0$, the capped Lp function converges to the L0 norm pointwisely as the approximation parameter tends to infinity. We point out that the capped Lp approximation problem is essentially a penalty method with an Lp penalty function for the composite L0 problem from the viewpoint of numerical optimization. ...
free text keywords: Mathematics - Optimization and Control
Download from
17 references, page 1 of 2

[1] Hedy Attouch, Jerome Bolte, Patrick Redont, and Antoine Soubeyran, Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the kurdyka-lojasiewicz inequality, Mathematics of Operations Research, 35 (2010), pp. 438-457.

[2] Hedy Attouch, Jerome Bolte, and Benar Fux Svaiter, Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods, Mathematical Programming, 137 (2013), pp. 91-129.

[3] Alfred Auslender and Marc Teboulle, Asymptotic Cones and Functions in Optimization and Variational Inequalities, springer, 2003.

[4] Thomas Blumensath and Mike E. Davies, Iterative hard thresholding for compressive sensing, Applied and Computational Harmonic Analysis, 27 (2009), pp. 265-274.

[5] Emmanuel J. Candes, The restricted isometry property and its implications for compressed sensing, Comptes Rendus Mathematique, 346 (2008), pp. 589-592.

[6] Emmanuel J. Candes, Michael B. Wakin, and Stephen P. Boyd, Enhancing sparsity by reweighted ℓ1 minimization, Journal of Fourier Analysis and Applications, 14 (2008), pp. 877-905.

[7] Rick Chartrand and Valentina Staneva, Restricted isometry properties and nonconvex compressive sensing, Inverse Problems, 24 (2008), pp. 657-682.

[8] Emilie Chouzenoux, Anna Jezierska, Jean-Christophe Pesquet, and Hugues Talbot, A majorize-minimize subspace approach for l(2)-l(0) image regularization, SIAM Journal on Imaging Sciences, 6 (2013), pp. 563-591.

[9] Geoffrey Davis, Stephane Mallat, and Marco Avellaneda, Adaptive greedy approximations, Constructive Approximation, 13 (1997), pp. 57-98.

[10] Bin Dong, Hui Ji, Jia Li, Zuowei Shen, and Yuhong Xu, Wavelet frame based blind image inpainting, Applied and Computational Harmonic Analysis, 32 (2012), pp. 268-279.

[11] Bin Dong and Yong Zhang, An efficient algorithm for ℓ0 minimization in wavelet frame based image restoration, Journal of Scientific Computing, (2011), pp. 1-19.

[12] Michael Elad, Peyman Milanfar, and Ron Rubinstein, Analysis versus synthesis in signal priors, Inverse Problems, 23 (2007), p. 947.

[13] Michael Elad, Jean-Luc Starck, Philippe Querre, and David L. Donoho, Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA), Applied and Computational Harmonic Analysis, 19 (2005), pp. 340-358.

[14] Jianqing Fan and Runze Li, Variable selection via nonconcave penalized likelihood and its oracle properties, Journal of the American Statistical Association, 96 (2002), pp. 1348-1360.

[15] Massimo Fornasier and Rachel Ward, Iterative thresholding meets free-discontinuity problems, Foundations of Computational Mathematics, 10 (2010), pp. 527-567.

17 references, page 1 of 2
Any information missing or wrong?Report an Issue