Sparse non-negative signal reconstruction using fraction function penalty

Angang Cui; Jigen Peng; Haiyang Li; Meng Wen

Sparse non-negative signal reconstruction using fraction function penalty

View Fulltext

Author(s): Angang Cui¹ ; Jigen Peng² ; Haiyang Li² ; Meng Wen³
- Affiliations: 1: School of Mathematics and Statistics , Xi'an Jiaotong University , Xi'an 710049 , People's Republic of China ;
  2: School of Mathematics and Information Science , Guangzhou University , Guangzhou 510006 , People's Republic of China ;
  3: School of Science , Xi'an Polytechnic University , Xi'an 710048 , People's Republic of China
Source: Volume 13, Issue 2, April 2019, p. 125 – 132
DOI: 10.1049/iet-spr.2018.5056 , Print ISSN 1751-9675, Online ISSN 1751-9683

« Previous Article
Table of contents
Next Article »

Received 31/03/2018, Accepted 07/08/2018, Revised 19/07/2018, Published 29/08/2018

Many practical problems in the real world can be formulated as the non-negative $ℓ 0$ -minimisation problems, which seek the sparsest non-negative signals to underdetermined linear equations. They have been widely applied in signal and image processing, machine learning, pattern recognition and computer vision. Unfortunately, this non-negative $ℓ 0$ -minimisation problem is non-deterministic polynomial hard (NP-hard) because of the discrete and discontinuous nature of the $ℓ 0$ -norm. Inspired by the good performances of the fraction function in the authors’ former work, in this paper, the authors replace the $ℓ 0$ -norm with the non-convex fraction function and study the minimisation problem of the fraction function in recovering the sparse non-negative signal from an underdetermined linear equation. They discuss the equivalence between non-negative $ℓ 0$ -minimisation problem and non-negative fraction function minimisation problem, and the equivalence between non-negative fraction function minimisation problem and regularised non-negative fraction function minimisation problem. It is proved that the optimal solution to the non-negative $ℓ 0$ -minimisation problem could be approximately obtained by solving their regularised non-negative fraction function minimisation problem if some specific conditions are satisfied. Then, they propose a non-negative iterative thresholding algorithm to solve their regularised non-negative fraction function minimisation problem. At last, numerical experiments on some sparse non-negative signal recovery problems are reported.

References

1. 1)
  - 4. Donoho, D.L., Tanner, J.: ‘Counting the faces of randomly projected hypercubes and orthants with applications’, Discrete Comput. Geom., 2010, 43, (3), pp. 522–541.
2. 2)
  - 13. Mangasarian, O.L.: ‘Minimum-support solutions of polyhedral concave programs’, Optimization, 1999, 45, (1–4), pp. 149–162.
3. 3)
  - 5. Khajehnejad, M.A., Dimakis, A.G., Xu, W.Y., et al: ‘Sparse recovery of non-negative signals with minima expansion’, IEEE Trans. Signal Process., 2011, 59, (1), pp. 196–208.
4. 4)
  - 7. Vo, N., Moran, B., Challa, S.: ‘Non-negative-least-square classifier for face recognition’. Proc. Sixth Int. Symp. Neural Networks: Advances Neural Networks, China, 2009, vol. 5553, pp. 449–456.
5. 5)
  - 22. Li, H.Y., Zhang, Q., Cui, A.G., et al: ‘Minimization of fraction function penalty in compressed sensing’. Available at URL https://arxiv.org/pdf/1705.06048, accessed 2017.
6. 6)
  - 18. Zhao, Y.B.: ‘Equivalence and strong equivalence between the sparsest and least l1-norm non-negative solutions of linear systems and their applications’, J. Oper. Res. Soc. China, 2014, 2, (2), pp. 171–193.
7. 7)
  - 2. Bardsley, J.M., Nagy, J.G.: ‘Covariance-preconditioned iterative methods for non-negativity constrained astronomical imaging’, SIAM J. Matrix Anal. Appl., 2006, 27, (4), pp. 1184–1197.
8. 8)
  - 27. Foucart, S., Rauhut, H.: ‘A mathematical introduction to compressive sensing’ (Springer, New York, 2013).
9. 9)
  - 6. ÓGrady, P.D., Rickard, S.T.: ‘Recovery of non-negative signals from compressively samples observations via non-negative quadratic programming’. Available at URL https://www.researchgate.net/publication/252320106, accessed 2009.
10. 10)
  - 8. Wang, M., Xu, W.Y., Tang, A.: ‘A unique non-negative solution to an underdetermined system: from vectors to matrices’, IEEE Trans. Signal Process., 2011, 59, (3), pp. 1007–1016.
11. 11)
  - 11. He, R., Zheng, W.S., Hu, B.G., et al: ‘Non-negative sparse coding for discriminative semi-supervised learning’. Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR), USA, 2011, vol. 42, (7), pp. 2849–2856.
12. 12)
  - 26. Schwarz, G.: ‘Estimating the dimension of a model’, Ann. Stat., 1978, 6, (2), pp. 461–464.
13. 13)
  - 3. Bruckstein, A.M., Elad, M., Zibulevsky, M.: ‘On the uniqueness of non-negative sparse solutions to underdetermined systems of equations’, IEEE Trans. Inf. Theory, 2008, 54, (11), pp. 4813–4820.
14. 14)
  - 16. Elad, M.: ‘Sparse and redundant representations: from theory to applications in signal and image processing’ (Springer, New York, 2010).
15. 15)
  - 17. Theodoridis, S., Kopsinis, Y., Slavakis, K.: ‘Sparsity-aware learning and compressed sensing: an overview’. Available at URL https://arxiv.org/pdf/1211.5231, accessed 2012.
16. 16)
  - 9. Bradley, P.S., Mangasarian, O.L., Rosen, J.B.: ‘Parsimonious least norm approximation’, Comput. Optim. Appl., 1998, 11, pp. 5–21.
17. 17)
  - 12. Mangasarian, O.L.: ‘Machine learning via polyhedral concave minimization’, in Fischer, H., Riedmueller, B., Schaeffler, S. (Eds.): Applied Mathematics and Parallel Computing: Festschrift for Klaus Ritter, (Springer, Heidelberg, 1996), pp. 175–188.
18. 18)
  - 21. Strayer, J.K.: ‘Linear programming and its applications’ (Springer, New York, 1989, 1st edn.).
19. 19)
  - 14. Szlam, A., Guo, Z.H., Osher, S.: ‘A split Bregman method for non-negative sparsity penalized least squares with applications to hyperspectral demixing’. Proc. 2010 IEEE 17th Int. Conf. Image Processing, 2010, pp. 1917–1920.
20. 20)
  - 10. Bradley, P.S., Fayyad, U.M., Mangasarian, O.L.: ‘Mathematical programming for data mining: formulations and challenges’, INFORMS J. Comput., 1999, 11, pp. 217–238.
21. 21)
  - 1. Donoho, D.L., Tanner, J.: ‘Sparse nonnegative solution of underdetermined linear equations by linear programming’, Proc. Natl. Acad. Sci. USA, 2005, 102, (27), pp. 9446–9451.
22. 22)
  - 23. Cui, A.G., Peng, J.G., Li, H.Y., et al: ‘Affine matrix rank minimization problem via non-convex fraction function penalty’, J. Comput. Appl. Math., 2018, 336, pp. 353–374.
23. 23)
  - 15. Bruckstein, A.M., Donoho, D.L., Elad, M.: ‘From sparse solutions of systems of equations to sparse modelling of signals and images’, SIAM Rev., 2009, 51, (1), pp. 34–81.
24. 24)
  - 20. Zhao, Y.B.: ‘RSP-based analysis for sparsest and least l1-norm solutions to underdetermined linear systems’, IEEE Trans. Signal Process., 2013, 61, (22), pp. 5777–5788.
25. 25)
  - 24. Geman, D., Reynolds, G.: ‘Constrained restoration and the recovery of discontinuities’, IEEE Trans. Pattern Anal. Mach. Intell., 1992, 14, (3), pp. 367–383.
26. 26)
  - 19. Donoho, D.L., Tanner, J.: ‘Sparse non-negative solutions of underdetermined linear equations by linear programming’, Proc. Natl. Acad. Sci. USA, 2005, 102, (27), pp. 9446–9451.
27. 27)
  - 25. Nikolova, M.: ‘Local strong homogeneity of a regularized estimator’, SIAM J. Appl. Math., 2000, 61, (2), pp. 633–658.

Login

Not registered yet?

Share

Tools

Login to add to favourites

Key

Sparse non-negative signal reconstruction using fraction function penalty

References

Related content