
-
Previous Article
Stability estimates in tensor tomography
- IPI Home
- This Issue
-
Next Article
Retinex based on exponent-type total variation scheme
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 |
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.
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. |
[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
Other articles
by authors
[Back to Top]