American Institute of Mathematical Sciences

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

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

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.

Keywords: Capped $\ell_p$ functions, composite $\ell_0$ regularization, asymptotic approximation, exact approximation, penalty methods.
Mathematics Subject Classification: Primary: 90C26, 49K40; Secondary: 49M30.
Citation: Qia Li, Na Zhang. Capped $\ell_p$ approximations for the composite $\ell_0$ regularization problem. Inverse Problems and Imaging, 2018, 12 (5) : 1219-1243. doi: 10.3934/ipi.2018051
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.

show all references

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.

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

Download full-size image

Download as PowerPoint slide

[1]

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

Peili Li, Xiliang Lu, Yunhai Xiao. Smoothing Newton method for $ \ell^0 $-$ \ell^2 $ regularized linear inverse problem. Inverse Problems and Imaging, 2022, 16 (1) : 153-177. doi: 10.3934/ipi.2021044
[3]

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 and Management Optimization, 2005, 1 (4) : 533-547. doi: 10.3934/jimo.2005.1.533
[4]

Jun Wang, Xing Tao Wang. Sparse signal reconstruction via the approximations of $ \ell_{0} $ quasinorm. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1907-1925. doi: 10.3934/jimo.2019035
[5]

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 and Imaging, 2018, 12 (3) : 545-572. doi: 10.3934/ipi.2018024
[6]

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

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

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

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

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

Yarui Duan, Pengcheng Wu, Yuying Zhou. Penalty approximation method for a double obstacle quasilinear parabolic variational inequality problem. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022017
[12]

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

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

Peter Giesl, Boumediene Hamzi, Martin Rasmussen, Kevin Webster. Approximation of Lyapunov functions from noisy data. Journal of Computational Dynamics, 2020, 7 (1) : 57-81. doi: 10.3934/jcd.2020003
[15]

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
[16]

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

Yan Liu, Minjia Shi, Hai Q. Dinh, Songsak Sriboonchitta. Repeated-root constacyclic codes of length $ 3\ell^mp^s $. Advances in Mathematics of Communications, 2020, 14 (2) : 359-378. doi: 10.3934/amc.2020025
[18]

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 and Management Optimization, 2012, 8 (1) : 163-178. doi: 10.3934/jimo.2012.8.163
[19]

Jiahui Tang, Yifan Xu, Wei Wang. An approach to solve local and global optimization problems based on exact objective filled penalty functions. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022084
[20]

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 and Management Optimization, 2011, 7 (1) : 53-66. doi: 10.3934/jimo.2011.7.53

2020 Impact Factor: 1.639

Tools

Metrics

  • PDF downloads (195)
  • HTML views (169)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy