Capped $\ell_p$ approximations for the composite $\ell_0$ regularization problem

Qia Li; Na Zhang

doi:10.3934/ipi.2018051

Article Contents

2018, Volume 12, Issue 5: 1219-1243. Doi: 10.3934/ipi.2018051

This issue Previous Article Retinex based on exponent-type total variation scheme Next Article Stability estimates in tensor tomography

Capped $\ell_p$ approximations for the composite $\ell_0$ regularization problem

Qia Li^1, and
Na Zhang^2, ,

1.
School of Data and Computer Sciences, Sun Yat-sen University, Guangdong Province Key Laboratory of Computational Science, Guangzhou 510275, China
2.
Department of Applied Mathematics, College of Mathematics and Informatics, South China Agricultural University, Guangzhou 510642, China

* Corresponding author: Na Zhang
* Corresponding author: Na Zhang

Received: July 31, 2017

Revised: January 31, 2018

Published: September 2018

The research is supported by the Natural Science Foundation of China under grants 11501584, 11626103 and 11701189, by the Natural Science Foundation of Guangdong Province under grants 2014A030310332 and 2014A030310414, and by the Fundamental Research Funds for the Central Universities of China.

Abstract Full Text(HTML) Figure(1) Related Papers Cited by

Abstract

The composite $\ell_0$ function serves as a sparse regularizer in many applications. The algorithmic difficulty caused by the composite $\ell_0$ regularization (the $\ell_0$ norm composed with a linear mapping) is usually bypassed through approximating the $\ell_0$ norm. We consider in this paper capped $\ell_p$ approximations with $p>0$ for the composite $\ell_0$ regularization problem. The capped $\ell_p$ function converges to the $\ell_0$ norm pointwisely as the approximation parameter tends to infinity. We first establish the existence of optimal solutions to the composite $\ell_0$ regularization problem and its capped $\ell_p$ approximation problem under conditions that the data fitting function is asymptotically level stable and bounded below. Asymptotically level stable functions cover a rich class of data fitting functions encountered in practice. We then prove that the capped $\ell_p$ problem asymptotically approximates the composite $\ell_0$ problem if the data fitting function is a level bounded function composed with a linear mapping. We further show that if the data fitting function is the indicator function on an asymptotically linear set or the $\ell_0$ norm composed with an affine mapping, then the composite $\ell_0$ problem and its capped $\ell_p$ approximation problem share the same optimal solution set provided that the approximation parameter is large enough.

Keywords:

Mathematics Subject Classification: Primary: 90C26, 49K40; Secondary: 49M30.

Citation:

Full Text(HTML)

Figure 1. Capped $\ell_p$ function $\varphi_\gamma$ with $\gamma = 1$ for $p = 0.5, 1, 2$

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	H. Attouch, J. Bolte and B. F. 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), 91-129. doi: 10.1007/s10107-011-0484-9.
[2]	A. Auslender and M. Teboulle, Asymptotic Cones and Functions in Optimization and Variational Inequalities, Springer, 2003.
[3]	T. Blumensath and M. E. Davies, Iterative hard thresholding for compressive sensing, Applied and Computational Harmonic Analysis, 27 (2009), 265-274. doi: 10.1016/j.acha.2009.04.002.
[4]	J. Bolte, S. Sabach and M. Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Mathematical Programming, 146 (2014), 459-494. doi: 10.1007/s10107-013-0701-9.
[5]	E. J. Candes, The restricted isometry property and its implications for compressed sensing, Comptes Rendus Mathematique, 346 (2008), 589-592. doi: 10.1016/j.crma.2008.03.014.
[6]	E. J. Candes, M. B. Wakin and S. P. Boyd, Enhancing sparsity by reweighted $\ell_1$ minimization, Journal of Fourier Analysis and Applications, 14 (2008), 877-905. doi: 10.1007/s00041-008-9045-x.
[7]	R. Chartrand and V. Staneva, Restricted isometry properties and nonconvex compressive sensing, Inverse Problems, 24 (2008), 035020, 14 pp. doi: 10.1088/0266-5611/24/3/035020.
[8]	E. Chouzenoux, A. Jezierska, J.-C. Pesquet and H. Talbot, A majorize-minimize subspace approach for l(2)-l(0) image regularization, SIAM Journal on Imaging Sciences, 6 (2013), 563-591. doi: 10.1137/11085997X.
[9]	D.-Q. Dai, L. Shen, Y. Xu and N. Zhang, Noisy 1-bit compressive sensing: Models and algorithms, Applied and Computational Harmonic Analysis, 40 (2016), 1-32. doi: 10.1016/j.acha.2014.12.001.
[10]	G. Davis, S. Mallat and M. Avellaneda, Adaptive greedy approximations, Constructive Approximation, 13 (1997), 57-98. doi: 10.1007/BF02678430.
[11]	B. Dong, H. Ji, J. Li, Z. Shen and Y. Xu, Wavelet frame based blind image inpainting, Applied and Computational Harmonic Analysis, 32 (2012), 268-279. doi: 10.1016/j.acha.2011.06.001.
[12]	B. Dong and Y. Zhang, An efficient algorithm for $\ell_0$ minimization in wavelet frame based image restoration, Journal of Scientific Computing, 54 (2013), 350-368. doi: 10.1007/s10915-012-9597-4.
[13]	M. Elad, P. Milanfar and R. Rubinstein, Analysis versus synthesis in signal priors, Inverse Problems, 23 (2007), 947-968. doi: 10.1088/0266-5611/23/3/007.
[14]	M. Elad, J.-L. Starck, P. Querre and D. L. Donoho, Simultaneous cartoon and texture image inpainting using morphological component analysis ({MCA}), Applied and Computational Harmonic Analysis, 19 (2005), 340-358. doi: 10.1016/j.acha.2005.03.005.
[15]	J. Fan and R. Li, Variable selection via nonconcave penalized likelihood and its oracle properties, Journal of the American Statistical Association, 96 (2001), 1348-1360. doi: 10.1198/016214501753382273.
[16]	M. Fornasier and R. Ward, terative thresholding meets free-discontinuity problems, Foundations of Computational Mathematics, 10 (2010), 527-567. doi: 10.1007/s10208-010-9071-3.
[17]	S. Foucart and M. J. Lai, Sparsest solutions of underdetermined linear systems via $\ell_q$-minimization for 0 < q ≤ 1, Applied and Computational Harmonic Analysis, 26 (2009), 395-407. doi: 10.1016/j.acha.2008.09.001.
[18]	Z. Lu, Iterative reweighted minimization methods for regularized unconstrained nonlinear programming, Mathematical Programming, 147 (2014), 277-307. doi: 10.1007/s10107-013-0722-4.
[19]	B. K. Natarajan, Sparse approximate solutions to linear systems, SIAM Journal on Computing, 24 (1995), 227-234. doi: 10.1137/S0097539792240406.
[20]	D. Needell and J. A. Tropp, Cosamp: Iterative signal recovery from incomplete and inaccurate samples, Applied and Computational Harmonic Analysis, 26 (2009), 301-321. doi: 10.1016/j.acha.2008.07.002.
[21]	M. Nikolova, M. K. Ng and C.-P. Tam, Fast nonconvex nonsmooth minimization methods for image restoration and reconstruction, IEEE Transactions on Image Processing, 19 (2010), 3073-3088. doi: 10.1109/TIP.2010.2052275.
[22]	J. Portilla, Image restoration through l0 analysis-based sparse optimization in tight frames, in IEEE International Conference on Image Processing, 2009, 3909–3912. doi: 10.1109/ICIP.2009.5413975.
[23]	R. T. Rockafellar and R. J. B. Wets, Variational Analysis, Springer, 2004. doi: 10.1007/978-3-642-02431-3.
[24]	L. Shen, Y. Xu and X. Zeng, Wavelet inpainting with the $\ell_0$ sparse regularization, Applied and Computational Harmonic Analysis, 41 (2016), 26-53. doi: 10.1016/j.acha.2015.03.001.
[25]	Y. Shen and S. Li, Sparse signals recovery from noisy measurements by orthogonal matching pursuit, Inverse Problems and Imaging, 9 (2015), 231-238. doi: 10.3934/ipi.2015.9.231.
[26]	J. A. Tropp, Just relax: Convex programming methods for identifying sparse signals in noise, IEEE Transactions on Information Theory, 52 (2006), 1030-1051. doi: 10.1109/TIT.2005.864420.
[27]	J. A. Tropp and A. C. Gilbert, Signal recovery from random measurements via orthogonal matching pursuit, IEEE Transactions on Information Theory, 53 (2007), 4655-4666. doi: 10.1109/TIT.2007.909108.
[28]	J. Trzasko and A. Manduca, Highly undersampled magnetic resonance image reconstruction via homotopic l(0) -minimization, IEEE Transactions on Medical Imaging, 28 (2009), 106-121. doi: 10.1109/TMI.2008.927346.
[29]	C. Wang and L. Zeng, Error bounds and stability in the $\ell_0$ regularized for ct reconstruction from small projections, Inverse Problems and Imaging, 10 (2016), 829-853. doi: 10.3934/ipi.2016023.
[30]	M. Yan, Restoration of images corrupted by impulse noise and mixed gaussian impulse noise using blind inpainting, SIAM Journal on Imaging Sciences, 6 (2013), 1227-1245. doi: 10.1137/12087178X.
[31]	C.-H. Zhang, Nearly unbiased variable selection under minimax concave penalty, Annals of Statistics, 38 (2010), 894-942. doi: 10.1214/09-AOS729.
[32]	N. Zhang and Q. Li, On optimal solutions of the constrained $\ell_0$ minimization and its penalty problem, Inverse Problems, 33 (2017), 025010, 28pp. doi: 10.1088/1361-6420/33/2/025010.
[33]	T. Zhang, Analysis of multi-stage convex relaxation for sparse regularization, Journal of Machine Learning Research, 11 (2010), 1081-1107.
[34]	Y. Zhang, B. Dong and Z. Lu, $\ell_0$ minimization for wavelet frame based image restoration, Mathematics of Computation, 82 (2013), 995-1015. doi: 10.1090/S0025-5718-2012-02631-7.