October 2018, 12(5): 1219-1243. doi: 10.3934/ipi.2018051

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

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

Received  August 2017 Revised  February 2018 Published  July 2018

Fund Project: 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

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.

Citation: Qia Li, Na Zhang. Capped $\ell_p$ approximations for the composite $\ell_0$ regularization problem. Inverse Problems & Imaging, 2018, 12 (5) : 1219-1243. doi: 10.3934/ipi.2018051
References:
[1]

H. AttouchJ. 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. BolteS. 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. CandesM. 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. ChouzenouxA. JezierskaJ.-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. DaiL. ShenY. 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. DavisS. Mallat and M. Avellaneda, Adaptive greedy approximations, Constructive Approximation, 13 (1997), 57-98. doi: 10.1007/BF02678430.

[11]

B. DongH. JiJ. LiZ. 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. EladP. 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. EladJ.-L. StarckP. 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. NikolovaM. 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. ShenY. 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. ZhangB. 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.

show all references

References:
[1]

H. AttouchJ. 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. BolteS. 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. CandesM. 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. ChouzenouxA. JezierskaJ.-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. DaiL. ShenY. 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. DavisS. Mallat and M. Avellaneda, Adaptive greedy approximations, Constructive Approximation, 13 (1997), 57-98. doi: 10.1007/BF02678430.

[11]

B. DongH. JiJ. LiZ. 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. EladP. 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. EladJ.-L. StarckP. 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. NikolovaM. 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. ShenY. 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. ZhangB. 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.

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

Lianjun Zhang, Lingchen Kong, Yan Li, Shenglong Zhou. A smoothing iterative method for quantile regression with nonconvex $ \ell_p $ penalty. Journal of Industrial & Management Optimization, 2017, 13 (1) : 93-112. doi: 10.3934/jimo.2016006

[2]

Z.Y. Wu, H.W.J. Lee, F.S. Bai, L.S. Zhang. Quadratic smoothing approximation to $l_1$ exact penalty function in global optimization. Journal of Industrial & Management Optimization, 2005, 1 (4) : 533-547. doi: 10.3934/jimo.2005.1.533

[3]

Chengxiang Wang, Li Zeng, Wei Yu, Liwei Xu. Existence and convergence analysis of $\ell_{0}$ and $\ell_{2}$ regularizations for limited-angle CT reconstruction. Inverse Problems & Imaging, 2018, 12 (3) : 545-572. doi: 10.3934/ipi.2018024

[4]

Hui Huang, Eldad Haber, Lior Horesh. Optimal estimation of $\ell_1$-regularization prior from a regularized empirical Bayesian risk standpoint. Inverse Problems & Imaging, 2012, 6 (3) : 447-464. doi: 10.3934/ipi.2012.6.447

[5]

Razvan C. Fetecau, Mitchell Kovacic, Ihsan Topaloglu. Swarming in domains with boundaries: Approximation and regularization by nonlinear diffusion. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 1-28. doi: 10.3934/dcdsb.2018238

[6]

Christopher Bose, Rua Murray. The exact rate of approximation in Ulam's method. Discrete & Continuous Dynamical Systems - A, 2001, 7 (1) : 219-235. doi: 10.3934/dcds.2001.7.219

[7]

Ahmet Sahiner, Gulden Kapusuz, Nurullah Yilmaz. A new smoothing approach to exact penalty functions for inequality constrained optimization problems. Numerical Algebra, Control & Optimization, 2016, 6 (2) : 161-173. doi: 10.3934/naco.2016006

[8]

Martin Hanke, William Rundell. On rational approximation methods for inverse source problems. Inverse Problems & Imaging, 2011, 5 (1) : 185-202. doi: 10.3934/ipi.2011.5.185

[9]

Jing Zhou, Dejun Chen, Zhenbo Wang, Wenxun Xing. A conic approximation method for the 0-1 quadratic knapsack problem. Journal of Industrial & Management Optimization, 2013, 9 (3) : 531-547. doi: 10.3934/jimo.2013.9.531

[10]

Huining Qiu, Xiaoming Chen, Wanquan Liu, Guanglu Zhou, Yiju Wang, Jianhuang Lai. A fast $\ell_1$-solver and its applications to robust face recognition. Journal of Industrial & Management Optimization, 2012, 8 (1) : 163-178. doi: 10.3934/jimo.2012.8.163

[11]

Martha Garlick, James Powell, David Eyre, Thomas Robbins. Mathematically modeling PCR: An asymptotic approximation with potential for optimization. Mathematical Biosciences & Engineering, 2010, 7 (2) : 363-384. doi: 10.3934/mbe.2010.7.363

[12]

Li-Xia Liu, Sanyang Liu, Chun-Feng Wang. Smoothing Newton methods for symmetric cone linear complementarity problem with the Cartesian $P$/$P_0$-property. Journal of Industrial & Management Optimization, 2011, 7 (1) : 53-66. doi: 10.3934/jimo.2011.7.53

[13]

S. Kanagawa, K. Inoue, A. Arimoto, Y. Saisho. Mean square approximation of multi dimensional reflecting fractional Brownian motion via penalty method. Conference Publications, 2005, 2005 (Special) : 463-475. doi: 10.3934/proc.2005.2005.463

[14]

Jake Bouvrie, Boumediene Hamzi. Kernel methods for the approximation of some key quantities of nonlinear systems. Journal of Computational Dynamics, 2017, 4 (1&2) : 1-19. doi: 10.3934/jcd.2017001

[15]

Caojin Zhang, George Yin, Qing Zhang, Le Yi Wang. Pollution control for switching diffusion models: Approximation methods and numerical results. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 1-21. doi: 10.3934/dcdsb.2018310

[16]

Xuemei Li, Rafael de la Llave. Convergence of differentiable functions on closed sets and remarks on the proofs of the "Converse Approximation Lemmas''. Discrete & Continuous Dynamical Systems - S, 2010, 3 (4) : 623-641. doi: 10.3934/dcdss.2010.3.623

[17]

Liuyang Yuan, Zhongping Wan, Qiuhua Tang. A criterion for an approximation global optimal solution based on the filled functions. Journal of Industrial & Management Optimization, 2016, 12 (1) : 375-387. doi: 10.3934/jimo.2016.12.375

[18]

Mei Ju Luo, Yi Zeng Chen. Smoothing and sample average approximation methods for solving stochastic generalized Nash equilibrium problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 1-15. doi: 10.3934/jimo.2016.12.1

[19]

Stefan Klus, Christof Schütte. Towards tensor-based methods for the numerical approximation of the Perron--Frobenius and Koopman operator. Journal of Computational Dynamics, 2016, 3 (2) : 139-161. doi: 10.3934/jcd.2016007

[20]

Julian Koellermeier, Roman Pascal Schaerer, Manuel Torrilhon. A framework for hyperbolic approximation of kinetic equations using quadrature-based projection methods. Kinetic & Related Models, 2014, 7 (3) : 531-549. doi: 10.3934/krm.2014.7.531

2017 Impact Factor: 1.465

Metrics

  • PDF downloads (37)
  • HTML views (111)
  • Cited by (0)

Other articles
by authors

[Back to Top]