An efficient algorithm for non-convex sparse optimization

Yong Wang; Wanquan Liu; Guanglu Zhou

doi:10.3934/jimo.2018134

Article Contents

2019, Volume 15, Issue 4: 2009-2021. Doi: 10.3934/jimo.2018134

This issue Previous Article Extreme values problem of uncertain heat equation Next Article Double projection algorithms for solving the split feasibility problems

An efficient algorithm for non-convex sparse optimization

1.
School of Mathematics, Tianjin University, Tianjin 300072, China
2.
Department of Computing, Curtin University, WA, 6102, Australia
3.
Department of Mathematics and Statistics, Curtin University, WA, 6102, Australia

* Corresponding author: Wanquan Liu
* Corresponding author: Wanquan Liu

Received: February 28, 2017

Revised: March 31, 2018

Early access: September 2018

Published: July 2019

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

Abstract

It is a popular research topic in computer vision community to find a solution for the zero norm minimization problem via solving its non-convex relaxation problem. In fact, there are already many existing algorithms to solve the non-convex relaxation problem. However, most of them are computationally expensive due to the non-Lipschitz property of this problem and thus these existing algorithms are not suitable for many engineering problems with large dimensions.

In this paper, we first develop an efficient algorithm to solve the non-convex relaxation problem via solving a sequence of non-convex sub-problems based on our recent work. To this end, we reformulate the minimization problem into another non-convex one but with non-negative constraint. Then we can transform the non-Lipschitz continuous non-convex problem with the non-negative constraint into a Lipschitz continuous problem, which allows us to use some efficient existing algorithms for its solution. Based on the proposed algorithm, an important relation between the solutions of relaxation problem and the original zero norm minimization problem is established from a different point of view. The results in this paper reveal two important issues: ⅰ) The solution of non-convex relaxation minimization problem converges to the solution of the original problem; ⅱ) The general non-convex relaxation problem can be solved efficiently with another reformulated high dimension problem with nonnegative constraint. Finally, some numerical results are used to demonstrate effectiveness of the proposed algorithm.

Keywords:

Non-Lipschitz optimization,
SMM method,
non-convex problem with non-negative constraint,
sparse optimization,
compressing sensing.

Mathematics Subject Classification: Primary: 65L09, 90C30, 65H10, 68W25, 68W01.

Citation:

Full Text(HTML)

Figure 1. The original signal and the reconstructed signals with $p = 0.8,0.6,0.4,0.2$, respectively

Download: Full-size image PowerPoint slide

Figure 2. The original and recovered images with different values of $p$, where SNR denotes the signal-to-noise ratio

Download: Full-size image PowerPoint slide

Figure 3. Comparison of the performance for ITM and SMM with large-scale problems. The first line: $p = 0.9$; the second line: $p = 0.7$; the final line: $p = 0.5$. The first column: sparsity; the second column: relative error; the final column: cpu time

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	R. H. Byrd, P. Lu and J. Nocedal, A limited memory algorithm for bound constrained optimization, SIAM J. Sci. Stat. Comput., 16 (1995), 1190-1208. doi: 10.1137/0916069.
[2]	S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learning, 3 (2010), 1-122.
[3]	S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004. doi: 10.1017/CBO9780511804441.
[4]	A. Cohen, W. Dahmen and R. DeVore, Compressed sensing and best $k$-term approximation, J. Amer. Math. Soc., 22 (2009), 211-231. doi: 10.1090/S0894-0347-08-00610-3.
[5]	R. Chartrand, Nonconvex compressed sensing and error correction, IEEE International Conference on Acoustics, Speech and Signal Processing, (2007), 889-892.
[6]	A. Charkrabarti and F. Hirakawa, Efective separation of sparse and non-sparse image features for denoising, in Proc. Int. Conf. Acoust., Speech, Signal Process. (ICASSP), (2008), 857-860.
[7]	X. Chen, K. Ng. Michael and C. Zhang, Non-Lipschitz-Regularization and box constrained model for image restoration, IEEE Trans. Image Processing, 21 (2012), 4709-4721. doi: 10.1109/TIP.2012.2214051.
[8]	E. J. Candès and J. Romberg, The code package $l_1$-magic. Available from: http://statweb.stanford.edu/candes/l1magic/.
[9]	E. J. Candès, J. Romberg and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Commun. Pure Appl. Math., 59 (2006), 1207-1223. doi: 10.1002/cpa.20124.
[10]	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.
[11]	E. J. Candès and T. Tao, Decoding by linear programming, IEEE Trans. Inf. Theory, 51 (2005), 4203-4215. doi: 10.1109/TIT.2005.858979.
[12]	X. Chen and S. Xiang, Sparse solutions of linear complementarity problems, Math. Program., 159 (2016), 539-556. doi: 10.1007/s10107-015-0950-x.
[13]	R. Chartrand and W. Yin, Iteratively reweighted algorithms for compressive sensing, IEEE International Conference on Acoustics, Speech and Signal Processing, (2008), 3869-3872.
[14]	X. Chen and W. Zhou, Convergence of Reweighted $l_1$ Minimization Algorithms and Unique Solution of Truncated $l_p$ Minimization, Tech. rep., Hong Kong Polytechnic University, 2010.
[15]	D. L. Donoho, Compressed sensing, IEEE Trans. Inf. Theory, 52 (2006), 1289-1306. doi: 10.1109/TIT.2006.871582.
[16]	D. L. Donoho and X. Huo, Uncertainty principles and ideal atomic decomposition, IEEE Trans. Inf. Theory, 47 (2001), 2845-2862. doi: 10.1109/18.959265.
[17]	M. Elad and A. M. Bruckstein, A generalized uncertainly priciple and sparse representation in pairs of bases, IEEE Trans. Inf. Theory, 48 (2002), 2558-2567. doi: 10.1109/TIT.2002.801410.
[18]	G. Fung and O. Mangasarian, Equivalence of minimal $l_0-$ and $l_p-$norm solutions of linear equalities, inequalities and linear programs for sufficiently small $p$, J. Optim. Theory Appl., 151 (2011), 1-10. doi: 10.1007/s10957-011-9871-x.
[19]	S. Foucart and M. Lai, Sparsest solutions of underdetermined linear systems via $l_q$ minimization for $0 < q < 1$, Applied and Computational Harmonic Analysis, 26 (2009), 395-407. doi: 10.1016/j.acha.2008.09.001.
[20]	M. A. T. Figueiredo, R. D. Nowak and S. J. Wright, Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems, IEEE J. Select. Top. Signal Process., 1 (2007), 585-597.
[21]	G. Gasso, A. Rakotomamonjy and S. Canu, Recovering sparse signals with a certain family of nonconvex penalties and DC programming, IEEE Trans. Signal Process., 57 (2009), 4686-4698. doi: 10.1109/TSP.2009.2026004.
[22]	M. Hyder and K. Mahata, An approximate $l_0$ norm minimization algorithm for compressed sensing, in IEEE International Conference on Acoustics, Speech and Signal Precessing(ICASSP), (2009), 3365-3368.
[23]	E. T. Hale, W. Yin and Y. Zhang, A fixed-point continuation method for $l_1$-regularized minimization with applications to compressed sensing, CAAM Technical Report TR07-07, Rice University, Houston, TX, 2007.
[24]	D. Krishnan and R. Fergus, Fast Image Deconvolution Using Hyper-Laplacian Priors, Neural Information Processing Systems., Cambridge, MA: MIT Press, 2009.
[25]	K. Koh, S.-J. Kim and S. Boyd, The code package l₁_l_s. Available from: http://www.standord.edu/boyd/l₁_l_s.
[26]	Q. Lyu, Z. Lin, Y. She and C. Zhang, A comparison of typical $l_p$ minimization algorithms, Neurocomputing, 119 (2013), 413-424.
[27]	D. C. Liu and J. Nocedal, On the limited memory method for large scale optimization, Mathematical Programming B, 45 (1989), 503-528. doi: 10.1007/BF01589116.
[28]	M. Lai and J. Wang, An unconstrained $l_q$ minimization with $0 < q < 1$ for sparse solution of under-determined linear systems, SIAM J. Optim., 21 (2011), 82-101. doi: 10.1137/090775397.
[29]	B. K. Natraajan, Sparse approximation to linear systems, SIAM J. Comput., 24 (1995), 227-234. doi: 10.1137/S0097539792240406.
[30]	P. Ochs, A. Dosovitskiy, T. Brox and T. Pock, An iterated $l_1$ algorithm for non-smooth non-convex optimization in computer vision, in Computer Vision and Pattern Recognition (CVPR), IEEE Conference, (2013), 1759-1766.
[31]	J. K. Pant, W. S. Lu and A. Antoniou, New improved algorithms for compressive sensing based on $l_p$ norm, IEEE Trans. on Circuits and Systems-Ⅱ: Express Briefs, 61 (2014), 198-202.
[32]	J. Peng, S. Yue and H. Li, NP/CMP equivalence: A phenomenon hidden among sparsity models $l_ {0}$ minimization and $l_ {p}$ minimization for information processing, IEEE Trans. Inf. Theory, 61 (2015), 4028-4033. doi: 10.1109/TIT.2015.2429611.
[33]	R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970.
[34]	Y. She, Thresholding-based iterative selection procedures for model selection and shrinkage, Electron. J. Stat., 3 (2009), 384-415. doi: 10.1214/08-EJS348.
[35]	Y. She, An iterative algorithm for fitting nonconvex penalized generalized linear models with grouped predictors, Comput. Statist. Data Anal., 9 (2012), 2976-2990. doi: 10.1016/j.csda.2011.11.013.
[36]	R. Saab, R. Chartrand and O. Yilmaz, Stable sparse approximations via nonconvex optimization, in IEEE International Confereence on Acoustics, Speech and Signal Processing, (2008), 3885-3888.
[37]	J. Wright, A. Yang, A. Ganesh, S. Sastry and Y. Ma, Robust face recognition via sparse representation, IEEE Trans. Pattern Recogn. Anal. Mach. Intell., 31 (2009), 210-227.
[38]	Y. J. Wang, G. L. Zhou, L. Caccetta and W. Q. Liu, An alternating direction algorithm for $l_1$ problems in compressive sensing, IEEE Trans. Signal Process., 59 (2011), 1895-1901.
[39]	Y. Wang and Q. Ma, A fast subspace method for image deblurring, Appl. Math. Comput., 215 (2009), 2359-2377. doi: 10.1016/j.amc.2009.08.033.
[40]	Y. Wang, G. Zhou, X. Zhang, W. Liu and L. Caccetta, The non-convex sparse problem with nonnegative constraint for signal reconstruction, J. Optim. Theory App., 170 (2016), 1009-1025. doi: 10.1007/s10957-016-0869-2.
[41]	A. Y. Yang, Z. Zhou, A. G. Balasubramanian, S. S. Sastry and Y. Ma, Fast-minimization algorithms for robust face recognition, IEEE Trans. Image Processing, 22 (2013), 3234-3246.
[42]	F. Zou, H. Feng, H. Ling, C. Liu, L. Yan, P. Li and D. Li, Nonnegative sparse coding induced hashing for image copy detection, Neurocomputing, 105 (2013), 81-95.
[43]	J. Zeng, S. Lin, Y. Wang and Z. Xu, $L_{1/2}$ regularization: Convergence of iterative half thresholding algorithm, IEEE Trans. Signal Process., 62 (2014), 2317-2329. doi: 10.1109/TSP.2014.2309076.
[44]	W. Zuo, D. Meng, L. Zhang, X. Feng and D. Zhang, A generalized iterated shrinkage algorithm for non-convex sparse coding, in IEEE International Conference on Computer Vision (ICCV), 2013.