Sparse signal recovery via minimax-concave penalty and -norm loss function
- Author(s): Yuli Sun 1 ; Hao Chen 1 ; Jinxu Tao 1
-
-
View affiliations
-
Affiliations:
1:
Department of Electronic Engineering and Information Science , University of Science and Technology of China , Hefei , People's Republic of China
-
Affiliations:
1:
Department of Electronic Engineering and Information Science , University of Science and Technology of China , Hefei , People's Republic of China
- Source:
Volume 12, Issue 9,
December
2018,
p.
1091 – 1098
DOI: 10.1049/iet-spr.2018.5130 , Print ISSN 1751-9675, Online ISSN 1751-9683
In sparse signal recovery, to overcome the -norm sparse regularisation's disadvantages tendency of uniformly penalise the signal amplitude and underestimate the high-amplitude components, a new algorithm based on a non-convex minimax-concave penalty is proposed, which can approximate the -norm more accurately. Moreover, the authors employ the -norm loss function instead of the -norm for the residual error, as the -loss is less sensitive to the outliers in the measurements. To rise to the challenges introduced by the non-convex non-smooth problem, they first employ a smoothed strategy to approximate the -norm loss function, and then use the difference-of-convex algorithm framework to solve the non-convex problem. They also show that any cluster point of the sequence generated by the proposed algorithm converges to a stationary point. The simulation result demonstrates the authors’ conclusions and indicates that the algorithm proposed in this study can obviously improve the reconstruction quality.
Inspec keywords: concave programming; approximation theory; minimax techniques; signal reconstruction
Other keywords: cluster point; difference-of-convex algorithm framework; sparse signal recovery; high-amplitude components; nonconvex problem; ℓ1-norm sparse regularisation; ℓ1-norm loss function; nonconvex nonsmooth problem; signal amplitude; nonconvex minimax-concave penalty; reconstruction quality
Subjects: Optimisation techniques; Signal processing and detection; Signal processing theory; Interpolation and function approximation (numerical analysis); Optimisation techniques; Interpolation and function approximation (numerical analysis)
References
-
-
1)
-
21. Zhou, Y.Y., Ye, Z.F., Huang, J.J.: ‘Improved decision-based detail-preserving variational method for removal of random-valued impulse noise’, IET Image Process., 2012, 6, (7), pp. 976–985.
-
-
2)
-
17. Gong, P., Ye, J., Zhang, C.: ‘Robust multi-task feature learning’. Proc. Int. Conf. Knowledge Discovery and Data mining, 2012, Beijing, China, pp. 895–903.
-
-
3)
-
30. Le, T., Dinh, T., Van, N.: ‘Exact penalty and error bounds in DC programming’, J. Glob. Optim., 2012, 52, (3), pp. 509–535.
-
-
4)
-
14. Pant, J., Lu, W., Antoniou, A.: ‘New improved algorithms for compressive sensing based on LP norm’, IEEE Trans. Circuits Syst. II, Express Briefs, 2014, 61, (3), pp. 198–202.
-
-
5)
-
16. Zhang, T.: ‘Multi-stage convex relaxation for feature selection’, Bernoulli. (Andover), 2013, 19, (5B), pp. 2277–2293.
-
-
6)
-
32. Yin, P., Lou, Y., He, Q., et al: ‘Minimization of L1-2 for compressed sensing’, SIAM J. Sci. Comput., 2015, 37, (1), pp. 536–563.
-
-
7)
-
33. Tono, K., Takeda, A., Gotoh, J.: ‘Efficient DC algorithm for constrained sparse optimization’, arXiv preprint, 2017, arXiv:1701.08498.
-
-
8)
-
34. Wen, B., Chen, X., Pong, T.: ‘A proximal difference-of-convex algorithm with extrapolation’, Computational optimization and applications2018, 69, (2), pp. 297–324.
-
-
9)
-
26. Wen, F., Liu, P., Liu, Y., et al: ‘Robust sparse recovery in impulsive noise via LP-L1 optimization’, IEEE Trans. Signal Process., 2017, 65, (1), pp. 105–118.
-
-
10)
-
1. Candès, E.J., Romberg, J., Tao, T.: ‘Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information’, IEEE Trans. Inf. Theory, 2006, 52, (2), pp. 489–509.
-
-
11)
-
25. Wen, F., Liu, P., Liu, Y., et al: ‘Robust sparse recovery for compressive sensing in impulsive noise using ℓp-norm model fitting’. Int. Conf. on Acoustics, Speech and Signal Processing (ICASSP), 2016, pp. 4643–4647.
-
-
12)
-
19. Lou, Y., Yin, P., He, Q., et al: ‘Computing sparse representation in a highly coherent dictionary based on difference of L1 and L2’, J. Sci. Comput., 2015, 64, (1), pp. 178–196.
-
-
13)
-
11. Candes, E.J., Wakin, M.B., Boyd, S.P.: ‘Enhancing sparsity by reweighted L1 minimization’, J. Fourier Anal. Appl., 2008, 14, (5–6), pp. 877–905.
-
-
14)
-
37. Nesterov, Y.: ‘Gradient methods for minimizing composite functions’, Math. Program., 2013, 140, (1), pp. 125–161.
-
-
15)
-
38. Gong, P., Zhang, C., Lu, Z., et al: ‘A general iterative shrinkage and thresholding algorithm for non-convex regularized optimization problems’. Proc. Int. Conf. Machine Learning, Atlanta, Georgia, 2013, pp. 37–45.
-
-
16)
-
22. Bar, L., Brook, A., Sochen, N., et al: ‘Deblurring of color images corrupted by impulsive noise’, IEEE Trans. Image Process., 2007, 16, (4), pp. 1101–1111.
-
-
17)
-
7. Yang, J., Zhang, Y.: ‘Alternating direction algorithms for L1-problemsincompressivesensing’, SIAM J. Sci. Comput., 2011, 33, (1), pp. 250–278.
-
-
18)
-
9. Jaggi, M.: ‘Revisiting Frank-Wolfe: projection-free sparse convex optimization’. Proc. Int. Conf. Machine Learning, Atlanta, Georgia, 2013, pp. 427–435.
-
-
19)
-
15. Zhang, T.: ‘Analysis of multi-stage convex relaxation for sparse regularization’, J. Mach. Learn. Res., 2010, 11, pp. 1081–1107.
-
-
20)
-
35. Selesnick, I., Farshchian, M.: ‘Sparse signal approximation via non-separable regularization’, IEEE Trans. Signal Process., 2017, 65, (10), pp. 2561–2575.
-
-
21)
-
3. Patel, V., Easley, G., Healy, J., et al: ‘Compressed synthetic aperture radar’, IEEE. J. Sel. Top. Signal Process., 2010, 4, (2), pp. 244–254.
-
-
22)
-
20. Lou, Y., Yan, M.: ‘Fast L1–L2 minimization via a proximal operator’, J. Sci. Comput., 2017, 74, (2), pp. 1–19.
-
-
23)
-
12. Xu, Z., Chang, X., Xu, F., et al: ‘L1/2 regularization: a thresholding representation theory and a fast solver’, IEEE Trans. Neural Netw. Learn. Syst., 2012, 23, (7), pp. 1013–1027.
-
-
24)
-
4. Sun, Y., Tao, J.: ‘Few views image reconstruction using alternating direction method via 0norm minimization’, Int. J. Imaging Syst. Technol., 2014, 24, (3), pp. 215–223.
-
-
25)
-
36. Selesnick, I.: ‘Sparse regularization via convex analysis’, IEEE Trans. Signal Process., 2017, 65, (17), pp. 4481–4494.
-
-
26)
-
28. Thi, L., Dinh, T., Le, H., et al: ‘DC approximation approaches for sparse optimization’, Eur. J. Oper. Res., 2015, 244, (1), pp. 26–46.
-
-
27)
-
6. Chen, H., Tao, J., Sun, Y., et al: ‘MR imaging reconstruction using a modified descent-type alternating direction method’, Int. J. Imaging Syst. Technol., 2016, 26, (1), pp. 43–54.
-
-
28)
-
29. Tao, P.: ‘The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems’, Ann. Oper. Res., 2005, 133, (1-4), pp. 23–46.
-
-
29)
-
10. Beck, A., Teboulle, M.: ‘A fast iterative shrinkage-thresholding algorithm for linear inverse problems’, SIAM J. Imaging Sci., 2009, 2, (1), pp. 183–202.
-
-
30)
-
18. Zhang, S., Qian, H., Chen, W., et al: ‘A concave conjugate approach for nonconvex penalized regression with the MCP penalty’. AAAI Conf. on Artificial Intelligence, Bellevue, Washington, 2013, pp. 1027–1033.
-
-
31)
-
27. Huber, P.J.: ‘Robust statistics’ (Wiley, New York, 1981).
-
-
32)
-
23. Pham, D., Venkatesh, S.: ‘Improved image recovery from compressed data contaminated with impulsive noise’, IEEE Trans. Image Process., 2012, 21, (1), pp. 397–405.
-
-
33)
-
24. Pham, D., Venkatesh, S.: ‘Efficient algorithms for robust recovery of images from compressed data’, IEEE Trans. Image Process., 2013, 22, (12), pp. 4724–4737.
-
-
34)
-
8. Goldstein, T., Osher, S.: ‘The split Bregman method for L1-regularized problems’, SIAM J. Imaging Sci., 2009, 2, (2), pp. 323–343.
-
-
35)
-
2. Wen, F., Pei, L., Yang, Y., et al: ‘Efficient and robust recovery of sparse signal and image using generalized nonconvex regularization’, IEEE Trans. Comput. Imaging, 2017, 3, (4), pp. 566–579.
-
-
36)
-
31. Lou, Y., Zeng, T., Osher, S., et al: ‘A weighted difference of anisotropic and isotropic total variation model for image processing’, SIAM J. Imaging Sci., 2015, 8, (3), pp. 1798–1823.
-
-
37)
-
13. Lai, M., Xu, Y., Yin, W.: ‘Improved iteratively reweighted least squares for unconstrained smoothed Lq minimization’, SIAM J. Numer. Anal., 2013, 51, (2), pp. 927–957.
-
-
38)
-
5. Sun, Y., Tao, J.: ‘Image reconstruction from few views by ℓ0-norm optimization’, Chin. Phys. B, 2014, 23, (7), p. 078703.
-
-
1)