Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

The Non-convex Sparse Problem with Nonnegative Constraint for Signal Reconstruction

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

The problem of finding a sparse solution for linear equations has been investigated extensively in recent years. This is an NP-hard combinatorial problem, and one popular method is to relax such combinatorial requirement into an approximated convex problem, which can avoid the computational complexity. Recently, it is shown that a sparser solution than the approximated convex solution can be obtained by solving its non-convex relaxation rather than by solving its convex relaxation. However, solving the non-convex relaxation is usually very costive due to the non-convexity and non-Lipschitz continuity of the original problem. This difficulty limits its applications and possible extensions. In this paper, we will consider the non-convex relaxation problem with the nonnegative constraint, which has many applications in signal processing with such reasonable requirement. First, this optimization problem is formulated and equivalently transformed into a Lipschitz continuous problem, which can be solved by many existing optimization methods. This reduces the computational complexity of the original problem significantly. Second, we solve the transformed problem by using an efficient and classical limited-memory Broyden–Fletcher–Goldfarb–Shanno algorithm. Finally, some numerical results show that the proposed method can effectively find a nonnegative sparse solution for the given linear equations with very low computational cost.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

References

  1. Beck, A., Eldar, Y.C.: Sparsity constrained nonlinear optimization: optimality conditions and algorithms. SIAM J. Optim. 23, 1480–1509 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  2. Lu, Z., Zhang, Y.: Sparse approximation via penalty decomposition methods. SIAM J. Optim. 23, 2448–2478 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  3. Blumensath, T., Davies, M.E.: Iterative thresholding for sparse approximations. J. Fourier Anal. Appl. 14, 629–654 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  4. Elad, M.: Optimized projections for compressed sensing. IEEE Trans. Signal Process. 55, 5695–5702 (2007)

    Article  MathSciNet  Google Scholar 

  5. Hyder, M., Mahata, K.: An improved smoothed \(l^0\) approximation algorithm for sparse representation. IEEE Trans. Signal Process. 58, 2194–2205 (2010)

    Article  MathSciNet  Google Scholar 

  6. Wang, J., Shim, B.: On the recovery limit of sparse signals using orthogonal matching pursuit. IEEE Trans. Signal Process. 60, 4973–4976 (2012)

    Article  MathSciNet  Google Scholar 

  7. Mohimani, H., Babaie-Zadeh, M., Jutten, C.: A fast approach for overcomplete sparse decomposition based on smoothed \(l^0\) norm. IEEE Trans. Signal Process. 57, 289–301 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  8. Natraajan, B.K.: Sparse approximation to linear systems. SIAM J. Comput. 24, 227–234 (1995)

    Article  MathSciNet  Google Scholar 

  9. Hyder, M., Mahata, K.: An approximate \(l_0\) norm minimization algorithm for compressed sensing. In: IEEE International Conference on Acoustics, Speech and Signal Precessing (ICASSP), pp. 3365–3368 (2009)

  10. Cohen, A., Dahmen, W., DeVore, R.: Compressed sensing and best \(k\)-term approximation. J. Am. Math. Soc. 22, 211–231 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  11. Donoho, D.L.: Compressed sensing. IEEE Trans. Inf. Theory 52, 1289–1306 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  12. Candès, E.J., Tao, T.: Decoding by linear programming. IEEE Trans. Inf. Theory 51, 4203–4215 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  13. Candès, E.J., Romberg, J., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59, 1207–1223 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  14. Candès, E.J., Recht, B.: Exact matrix completion via convex optimization. Found. Comput. Math. 9, 717–772 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  15. Candès, E.J., Tao, T.: The power of convex relaxation: near-optimal matrix completion. IEEE Trans. Inf. Theory 56, 2053–2080 (2010)

    Article  MathSciNet  Google Scholar 

  16. Wright, J., Yang, A., Ganesh, A., Sastry, S., Ma, Y.: Robust face recognition via sparse representation. IEEE Trans. Pattern Recogn. Anal. Mach. Intell. 31, 210–227 (2009)

    Article  Google Scholar 

  17. Koh, K., Kim, S.-J., Boyd, S.: The code package \(l_1\_l_s\): http://stanford.edu/~boyd/l1_ls/

  18. Candès, E.J., Romberg, J.: The code package \(l_1\)-magic: http://statweb.stanford.edu/~candes/l1magic/

  19. Figueiredo, M.A.T., Nowak, R.D., Wright, S.J.: Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems. IEEE J. Select. Top. Signal Process. 1, 585–597 (2007)

    Article  Google Scholar 

  20. Hale, E.T., Yin, W., Zhang, Y.: 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)

  21. Wang, Y.J., Zhou, G.L., Caccetta, L., Liu, W.Q.: An alternating direction algorithm for \(l_1\) problems in compressive sensing. IEEE Trans. Signal Process. 59, 1895–1901 (2011)

    Article  Google Scholar 

  22. Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3, 1–122 (2010)

    Article  MATH  Google Scholar 

  23. Saab, R., Chartrand, R., Yilmaz, O.: Stable sparse approximations via nonconvex optimization. In: IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 3885–3888 (2008)

  24. Chartrand, R.: Nonconvex compressed sensing and error correction. In: IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 889–892 (2007)

  25. She, Y.: Thresholding-based iterative selection procedures for model selection and shrinkage. Electron. J. Stat. 3, 384–415 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  26. She, Y.: An iterative algorithm for fitting nonconvex penalized generalized linear models with grouped predictors. Comput. Statist. Data Anal. 9, 2976–2990 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  27. Lyu, Q., Lin, Z., She, Y., Zhang, C.: A comparison of typical \(l_p\) minimization algorithms. Neurocomputing 119, 413–424 (2013)

    Article  Google Scholar 

  28. Foucart, S., Lai, M.: Sparsest solutions of underdetermined linear systems via \(l_q\) minimization for \(0 < {q} < 1\). Appl. Comput. Harmon. Anal. 26, 395–407 (2009)

  29. Gasso, G., Rakotomamonjy, A., Canu, S.: Recovering sparse signals with a certain family of nonconvex penalties and DC programming. IEEE Trans. Signal Process. 57, 4686–4698 (2009)

    Article  MathSciNet  Google Scholar 

  30. Ochs, P., Dosovitskiy, A., Brox, T., Pock, T.: An iterated \(l_1\) algorithm for non-smooth non-convex optimization in computer vision. In: Computer Vision and Pattern Recognition (CVPR), IEEE Conference, pp. 1759–1766 (2013)

  31. Chen, X., Zhou, W.: Convergence of reweighted \(l_1\) minimization algorithms and unique solution of truncated \(l_p\) minimization. Technical report, Hong Kong Polytechnic University (2010)

  32. Chartrand, R., Yin, W.: Iteratively reweighted algorithms for compressive sensing. In: IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 3869–3872 (2008)

  33. Lai, M., Wang, J.: An unconstrained \(l_q\) minimization with \(0 < {q} < 1\) for sparse solution of under-determined linear systems. SIAM J. Optim. 21, 82–101 (2011)

  34. Chartrand, R., Staneva, V.: Restricted isometry properties and nonconvex compressive sensing. Inverse Probl. 24, 1–14 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  35. Pant, J.K., Lu, W.S., Antoniou, A.: New improved algorithms for compressive sensing based on \(l_p\) norm. IEEE Trans. Circuits Syst. II: Express Briefs 61, 198–202 (2014)

    Article  Google Scholar 

  36. Krishnan, D., Fergus, R.: Fast image deconvolution using hyper-Laplacian priors. In: Advances in Neural Information Processing Systems, pp. 1033–1041 (2009)

  37. Xu, Z., Chang, X., Xu, F., Zhang, H.: \(L_{1/2}\) regularization: a thresholding representation theory and a fast solver. IEEE Trans. Neural Netw. Learn. Syst. 23, 1013–1027 (2012)

    Article  Google Scholar 

  38. Zeng, J., Lin, S., Wang, Y., Xu, Z.: \(L_{1/2}\) regularization: convergence of iterative half thresholding algorithm. IEEE Trans. Signal Process. 62, 2317–2328 (2014)

    Article  MathSciNet  Google Scholar 

  39. Chen, X., Ng, Michael K., Zhang, C.: Non-Lipschitz-regularization and box constrained model for image restoration. IEEE Trans. Image Process. 21, 4709–4721 (2012)

    Article  MathSciNet  Google Scholar 

  40. Bayram, I., Selesnick, I.W.: A subband adaptive iterative shrinkage/thresholding algorithm. IEEE Trans. Signal Process. 58, 1131–1143 (2010)

    Article  MathSciNet  Google Scholar 

  41. Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183–202 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  42. Zuo, W., Meng, D., Zhang, L., Feng, X., Zhang, D.: A generalized iterated shrinkage algorithm for non-convex sparse coding. In: IEEE International Conference on Computer Vision (ICCV) (2013)

  43. Pan, L., Xiu, N., Zhou, S.: Gradient Support Projection Algorithm for Affine Feasibility Problem with Sparsity and Nonnegativity. arXiv preprint (2014) arXiv:1406.7178

  44. Bruckstein, A.M., Elad, M., Zibulevsky, M.: On the uniqueness of non-negative sparse solutions to underdetermined systems of equations. IEEE Trans. Inf. Theory 54, 4813–4820 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  45. Zhang, B., Mu, Z., Zeng, H., Luo, S.: Robust ear recognition via nonnegative sparse representation of Gabor orientation information. Sci. World J. 2014, 131605 (2014). doi:10.1155/2014/131605

  46. Donoho, D.L., Tanner, J.: Sparse nonnegative solution of underdetermined linear equations by linear programming. Proc. Natl. Acad. Sci. 102, 9446–9451 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  47. Zou, F., Feng, H., Ling, H., Liu, C., Yan, L., Li, P., Li, D.: Nonnegative sparse coding induced hashing for image copy detection. Neurocomputing 105, 81–89 (2013)

    Article  Google Scholar 

  48. Qin, L., Xiu, N., Kong, L., Li, Y.: Linear program relaxation of sparse nonnegative recovery in compressive sensing microarrays. Comput. Math. Methods Med. 2012, 775–795 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  49. He, R., Zheng, W.S., Hu, B.G., Kong, X.W.: Two-stage nonnegative sparse representation for large-scale face recognition. IEEE Trans. Neural Netw. Learn. Syst. 24, 35–46 (2013)

    Article  Google Scholar 

  50. Ji, Y., Lin, T., Zha, H.: Mahalanobis distance based non-negative sparse representation for face recognition. In: IEEE International Conference on Machine Learning and Applications, 2009 (ICMLA ’09), pp. 41–46 (2009)

  51. Luo, Z., Qin, L., Kong, L., Xiu, N.: The nonnegative zero-norm minimization under generalized z-matrix measurement. J. Optim. Theory Appl. 160, 854–864 (2014)

  52. Chen, Y., Zhang, H., Zuo, Y., Wang, D.: An improved regularized latent semantic indexing with \(L_{1/2}\) regularization and non-negative constraints. 16th International Conference on Computational Science and Engineering, IEEE (2013)

  53. Sun, W., Yuan, Y.-X.: Optimization theory and methods: nonlinear programming. In: Springer Optimization and Its Applications, vol. 1, Springer, New York (2006)

  54. Liu, D.C., Nocedal, J.: On the limited memory method for large scale optimization. Math. Program. B 45, 503–528 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  55. Byrd, R.H., Lu, P., Nocedal, J.: A limited memory algorithm for bound constrained optimization. SIAM J. Sci. Stat. Comput. 16, 1190–1208 (1995)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The constructive comments from the two reviewers and the Editor-in-Chief are highly appreciated. Especially we thank the Edit Assistant of the Editor-in-Chief for his/her tedious effort to polish our paper. Finally, this work was partially supported by the National Natural Science Foundation of China (NSFC 61363066, 11171252, 11431002)

Author information

Authors and Affiliations

  1. Department of Mathematics, School of Science, Tianjin University, Tianjin, 300072, People’s Republic of China

    Yong Wang

  2. Department of Mathematics and Statistics, Curtin University, Perth, WA, Australia

    Guanglu Zhou & Louis Caccetta

  3. Department of Computing, Curtin University, Perth, WA, Australia

    Xin Zhang & Wanquan Liu

Authors
  1. Yong Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Guanglu Zhou
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xin Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Wanquan Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Louis Caccetta
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Wanquan Liu.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Wang, Y., Zhou, G., Zhang, X. et al. The Non-convex Sparse Problem with Nonnegative Constraint for Signal Reconstruction. J Optim Theory Appl 170, 1009–1025 (2016). https://doi.org/10.1007/s10957-016-0869-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-016-0869-2

Keywords

Mathematics Subject Classification