Article Contents
Article Contents

# An efficient algorithm for non-convex sparse optimization

• * Corresponding author: Wanquan Liu
• 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.

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

 Citation:

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

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

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

•  [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 l1_ls. Available from: http://www.standord.edu/boyd/l1_ls. [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.

Figures(3)