Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Primal and dual alternating direction algorithms for ℓ 1-ℓ 1-norm minimization problems in compressive sensing

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

In this paper, we propose, analyze and test primal and dual versions of the alternating direction algorithm for the sparse signal reconstruction from its major noise contained observation data. The algorithm minimizes a convex non-smooth function consisting of the sum of ℓ 1-norm regularization term and ℓ 1-norm data fidelity term. We minimize the corresponding augmented Lagrangian function alternatively from either primal or dual forms. Both of the resulting subproblems admit explicit solutions either by using a one-dimensional shrinkage or by an efficient Euclidean projection. The algorithm is easily implementable and it requires only two matrix-vector multiplications per-iteration. The global convergence of the proposed algorithm is established under some technical conditions. The extensions to the non-negative signal recovery problem and the weighted regularization minimization problem are also discussed and tested. Numerical results illustrate that the proposed algorithm performs better than the state-of-the-art algorithm YALL1.

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
Fig. 4

Similar content being viewed by others

Notes

  1. In the case of β=0.2, both algorithm fail to recovery the original solution in a pre-fixed time. Hence, in the following experiments, we test the combination (α,β) with β=0.1.

References

  1. 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 

  2. Becker, S., Bobin, J., Candès, E.: NESTA: A fast and accurate first-order method for sparse recovery. SIAM J. Imaging Sci. 4, 1–39 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  3. Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)

    MATH  Google Scholar 

  4. van den Berg, E., Friedlander, M.P.: Probing the Pareto frontier for basis pursuit solutions. SIAM J. Sci. Comput. 31, 890–912 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bertsekas, D.P., Tsitsiklis, J.N.: Parallel and Distributed Computation: Numerical Methods. Prentice Hall, Englewood Cliffs (1989)

    MATH  Google Scholar 

  6. Bioucas-Dias, J.M., Figueiredo, M.: A new TwIST: Two-step iterative shrinkage/thresholding algorithms for image restoration. IEEE Trans. Image Process. 16, 2992–3004 (2007)

    Article  MathSciNet  Google Scholar 

  7. Candès, E., Romberg, J.: Quantitative robust uncertainty principles and optimally sparse decompositions. Found. Comput. Math. 6, 227–254 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  8. Candès, E., Romberg, J., Tao, T.: Stable signal recovery from incomplete and inaccurate information. Commun. Pure Appl. Math. 59, 1207–1233 (2005)

    Article  Google Scholar 

  9. Candès, E., Romberg, J., Tao, T.: Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequence information. IEEE Trans. Inf. Theory 52, 489–509 (2006)

    Article  MATH  Google Scholar 

  10. Candès, E., Tao, T.: Near optimal signal recovery from random projections: universal encoding strategies. IEEE Trans. Inf. Theory 52, 5406–5425 (2004)

    Article  Google Scholar 

  11. Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40, 120–145 (2010)

    Article  MathSciNet  Google Scholar 

  12. Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM Rev. 43, 129–159 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  13. Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  15. Donoho, D.L.: For most large underdetemind systems of linear equations, the minimal ℓ 1-norm solution is also the sparsest solution. Commun. Pure Appl. Math. 59, 907–934 (2006)

    Article  MathSciNet  Google Scholar 

  16. Esser, E.: Applications of Lagrangian-based alternating direction methods and connections to split Bregman. TR. 09-31, CAM, UCLA (2009). Available at ftp://ftp.math.ucla.edu/pub/camreport/cam09-31.pdf

  17. Figueiredo, M., Nowak, R., Wright, S.J.: Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems. In: IEEE J. Selected Topics in Signal Process., pp. 586–597. IEEE Press, Piscataway (2007)

    Google Scholar 

  18. Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite-element approximations. Comput. Math. Appl. 2, 17–40 (1976)

    Article  MATH  Google Scholar 

  19. Glowinski, R., Marrocco, A.: Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de Dirichlet nonlinéaires, Revue Francaise d’automatique, informatique, recherche opéretionnelle. Anal. Numér. 2, 41–76 (1975)

    MathSciNet  Google Scholar 

  20. Goldstein, T., Osher, S.: The split Bregman method for ℓ 1-regularized problems. SIAM J. Imaging Sci. 2, 323–343 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  21. Hale, E.T., Yin, W., Zhang, Y.: Fixed-point continuation for ℓ 1-minimization: Methodology and convergence. SIAM J. Optim. 19, 1107–1130 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  22. He, B.S., Liao, L.Z., Han, D., Yang, H.: A new inexact alternating directions method for monotone variational inequalities. Math. Program. 92, 103–118 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  23. He, B.S., Yang, H.: Some convergence properties of a method of multipliers for linearly constrained monotone variational inequalities. Oper. Res. Lett. 23, 151–161 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  24. He, B.S., Yang, H., Wang, S.L.: Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities. J. Optim. Theory Appl. 106, 337–356 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  25. Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, Berlin (1999)

    Book  MATH  Google Scholar 

  26. Setzer, S.: Operator splitting, Bregman methods and frame shrinkage in image processing. Int. J. Comput. Vis. 92, 265–280 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  27. Shen, Y., Wen, Z., Zhang, Y.: Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization. TR11-02, Rice University (2011). Available at http://www.caam.rice.edu/~zhang/reports/tr1102.pdf

  28. Steidl, G., Teuber, T.: Removing multiplicative noise by Douglas-Rachford splitting methods. J. Math. Imaging Vis. 36, 168–184 (2010)

    Article  MathSciNet  Google Scholar 

  29. Tao, M., Yuan, X.M.: Recovering low-rank and sparse components of matrices from incomplete and noisy observations. SIAM J. Optim. 21, 57–81 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  30. Wright, J., Ma, Y.: Dense error correction via ℓ 1-minimization. Available online at http://www.dsp.ece.rice.edu/cs/

  31. Wright, S.J., Nowak, R., Figueiredo, M.: Sparse reconstruction by separable approximation. IEEE Trans. Signal Process. 57, 2479–2493 (2009)

    Article  MathSciNet  Google Scholar 

  32. Xiao, Y., Jin, Z.: An alternating direction method for linear-constrained matrix nuclear norm minimization. Numer. Linear Algebra Appl. (2011). doi:10.1002/nla.783

    Google Scholar 

  33. Yang, J., Zhang, Y.: Alternating direction algorithms for ℓ 1-problems in compressive sensing. SIAM J. Sci. Comput. 33, 250–278 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  34. Ye, C.H., Yuan, X.M.: A descent method for structured monotone variational inequalities. Optim. Methods Softw. 22, 329–338 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  35. Yun, S., Toh, K.C.: A coordinate gradient descent method for ℓ 1-regularized convex minimization. Comput. Optim. Appl. 48, 273–307 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  36. Zhang, X., Burger, M., Osher, S.: A unified primal-dual framework based on Bregman iteration. J. Sci. Comput. 46, 20–46 (2011)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We would like to thank two anonymous referees for their useful comments and suggestions which improved this paper greatly. The work of Yunhai Xiao is supported in part by the Natural Science Foundation of China grant NSFC-11001075.

Author information

Authors and Affiliations

  1. Institute of Applied Mathematics, College of Mathematics and Information Science, Henan University, Kaifeng, 475000, China

    Yunhai Xiao & Hong Zhu

  2. National Center for Theoretical Sciences (South), National Cheng Kung University, Tainan, 700, Taiwan

    Soon-Yi Wu

Authors
  1. Yunhai Xiao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hong Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Soon-Yi Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yunhai Xiao.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Xiao, Y., Zhu, H. & Wu, SY. Primal and dual alternating direction algorithms for ℓ 1-ℓ 1-norm minimization problems in compressive sensing. Comput Optim Appl 54, 441–459 (2013). https://doi.org/10.1007/s10589-012-9475-x

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-012-9475-x

Keywords

Search

Navigation