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. Google Scholar

[2]

A. Auslender and M. Teboulle, Asymptotic Cones and Functions in Optimization and Variational Inequalities, Springer, 2003. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[10]

G. DavisS. Mallat and M. Avellaneda, Adaptive greedy approximations, Constructive Approximation, 13 (1997), 57-98. doi: 10.1007/BF02678430. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[19]

B. K. Natarajan, Sparse approximate solutions to linear systems, SIAM Journal on Computing, 24 (1995), 227-234. doi: 10.1137/S0097539792240406. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[23]

R. T. Rockafellar and R. J. B. Wets, Variational Analysis, Springer, 2004. doi: 10.1007/978-3-642-02431-3. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[31]

C.-H. Zhang, Nearly unbiased variable selection under minimax concave penalty, Annals of Statistics, 38 (2010), 894-942. doi: 10.1214/09-AOS729. Google Scholar

[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. Google Scholar

[33]

T. Zhang, Analysis of multi-stage convex relaxation for sparse regularization, Journal of Machine Learning Research, 11 (2010), 1081-1107. Google Scholar

[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. Google Scholar

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. Google Scholar

[2]

A. Auslender and M. Teboulle, Asymptotic Cones and Functions in Optimization and Variational Inequalities, Springer, 2003. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[10]

G. DavisS. Mallat and M. Avellaneda, Adaptive greedy approximations, Constructive Approximation, 13 (1997), 57-98. doi: 10.1007/BF02678430. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[19]

B. K. Natarajan, Sparse approximate solutions to linear systems, SIAM Journal on Computing, 24 (1995), 227-234. doi: 10.1137/S0097539792240406. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[23]

R. T. Rockafellar and R. J. B. Wets, Variational Analysis, Springer, 2004. doi: 10.1007/978-3-642-02431-3. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[31]

C.-H. Zhang, Nearly unbiased variable selection under minimax concave penalty, Annals of Statistics, 38 (2010), 894-942. doi: 10.1214/09-AOS729. Google Scholar

[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. Google Scholar

[33]

T. Zhang, Analysis of multi-stage convex relaxation for sparse regularization, Journal of Machine Learning Research, 11 (2010), 1081-1107. Google Scholar

[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. Google Scholar

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]

Jun Wang, Xing Tao Wang. Sparse signal reconstruction via the approximations of $ \ell_{0} $ quasinorm. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2019035

[4]

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

[5]

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

[6]

Victor Churchill, Rick Archibald, Anne Gelb. Edge-adaptive $ \ell_2 $ regularization image reconstruction from non-uniform Fourier data. Inverse Problems & Imaging, 2019, 13 (5) : 931-958. doi: 10.3934/ipi.2019042

[7]

Razvan C. Fetecau, Mitchell Kovacic, Ihsan Topaloglu. Swarming in domains with boundaries: Approximation and regularization by nonlinear diffusion. Discrete & Continuous Dynamical Systems - B, 2019, 24 (4) : 1815-1842. doi: 10.3934/dcdsb.2018238

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

Thierry Paul, Mario Pulvirenti. Asymptotic expansion of the mean-field approximation. Discrete & Continuous Dynamical Systems - A, 2019, 39 (4) : 1891-1921. doi: 10.3934/dcds.2019080

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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, 2019, 24 (8) : 3667-3687. doi: 10.3934/dcdsb.2018310

[19]

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

[20]

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

2018 Impact Factor: 1.469

Metrics

  • PDF downloads (39)
  • HTML views (114)
  • Cited by (0)

Other articles
by authors

[Back to Top]