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

Enhancing Sparsity by Reweighted ℓ 1 Minimization

  • Published:
Journal of Fourier Analysis and Applications Aims and scope Submit manuscript

Abstract

It is now well understood that (1) it is possible to reconstruct sparse signals exactly from what appear to be highly incomplete sets of linear measurements and (2) that this can be done by constrained ℓ 1 minimization. In this paper, we study a novel method for sparse signal recovery that in many situations outperforms ℓ 1 minimization in the sense that substantially fewer measurements are needed for exact recovery. The algorithm consists of solving a sequence of weighted ℓ 1-minimization problems where the weights used for the next iteration are computed from the value of the current solution. We present a series of experiments demonstrating the remarkable performance and broad applicability of this algorithm in the areas of sparse signal recovery, statistical estimation, error correction and image processing. Interestingly, superior gains are also achieved when our method is applied to recover signals with assumed near-sparsity in overcomplete representations—not by reweighting the ℓ 1 norm of the coefficient sequence as is common, but by reweighting the ℓ 1 norm of the transformed object. An immediate consequence is the possibility of highly efficient data acquisition protocols by improving on a technique known as Compressive Sensing.

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

Similar content being viewed by others

References

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

    MATH  Google Scholar 

  2. Taylor, H.L., Banks, S.C., McCoy, J.F.: Deconvolution with the ℓ 1 norm. Geophysics 44(1), 39–52 (1979)

    Article  Google Scholar 

  3. Claerbout, J.F., Muir, F.: Robust modeling with erratic data. Geophysics 38(5), 826–844 (1973)

    Article  Google Scholar 

  4. Santosa, F., Symes, W.W.: Linear inversion of band-limited reflection seismograms. SIAM J. Sci. Stat. Comput. 7(4), 1307–1330 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  5. Donoho, D.L., Stark, P.B.: Uncertainty principles and signal recovery. SIAM J. Appl. Math. 49(3), 906–931 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  6. Donoho, D.L., Logan, B.F.: Signal recovery and the large sieve. SIAM J. Appl. Math. 52(2), 577–591 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  7. Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Stat. Soc. B 58(1), 267–288 (1996)

    MATH  MathSciNet  Google Scholar 

  8. Chen, S., Donoho, D., Saunders, M.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20(1), 33–61 (1998)

    Article  MathSciNet  Google Scholar 

  9. Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60(1–4), 259–268 (1992)

    Article  MATH  Google Scholar 

  10. Blomgren, P., Chan, T.F.: Color TV: total variation methods for restoration of vector-valued images. IEEE Trans. Image Process. 7, 304–309 (1998)

    Article  Google Scholar 

  11. Vandenberghe, L., Boyd, S., El Gamal, A.: Optimal wire and transistor sizing for circuits with non-tree topology. In: Proceedings of the 1997 IEEE/ACM International Conference on Computer Aided Design, pp. 252–259 (1997)

  12. Vandenberghe, L., Boyd, S., El Gamal, A.: Optimizing dominant time constant in RC circuits. IEEE Trans. Comput.-Aided Des. 2(2), 110–125 (1998)

    Article  Google Scholar 

  13. Hassibi, A., How, J., Boyd, S.: Low-authority controller design via convex optimization. AIAA J. Guid. Control Dyn. 22(6), 862–872 (1999)

    Article  Google Scholar 

  14. Dahleh, M., Diaz-Bobillo, I.: Control of Uncertain Systems: A Linear Programming Approach. Prentice-Hall, Englewood Cliffs (1995)

    MATH  Google Scholar 

  15. Lobo, M., Fazel, M., Boyd, S.: Portfolio optimization with linear and fixed transaction costs. Ann. Oper. Res. 152(1), 341–365 (2006)

    Article  MathSciNet  Google Scholar 

  16. Ghosh, A., Boyd, S.: Growing well-connected graphs. In: Proceedings of the 45th IEEE Conference on Decision and Control, December 2006, pp. 6605–6611

  17. Sun, J., Boyd, S., Xiao, L., Diaconis, P.: The fastest mixing Markov process on a graph and a connection to a maximum variance unfolding problem. SIAM Rev. 48(4), 681–699 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  18. Kim, S.-J., Koh, K., Boyd, S., Gorinevsky, D.: ℓ 1 trend filtering. SIAM Rev. (2008, to appear); available at www.stanford.edu/~boyd/l1_trend_filter.html

  19. Donoho, D.L., Huo, X.: Uncertainty principles and ideal atomic decomposition. IEEE Trans. Inf. Theory 47(7), 2845–2862 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  20. Elad, M., Bruckstein, A.M.: A generalized uncertainty principle and sparse representation in pairs of bases. IEEE Trans. Inf. Theory 48(9), 2558–2567 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  21. Gribonval, R., Nielsen, M.: Sparse representations in unions of bases. IEEE Trans. Inf. Theory 49(12), 3320–3325 (2003)

    Article  MathSciNet  Google Scholar 

  22. Tropp, J.A.: Just relax: convex programming methods for identifying sparse signals in noise. IEEE Trans. Inf. Theory 52, 1030–1051 (2006)

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  24. Candès, E.J., Tao, T.: Near optimal signal recovery from random projections: Universal encoding strategies? IEEE Trans. Inf. Theory 52(12), 5406–5425 (2006)

    Article  Google Scholar 

  25. Donoho, D.: Compressed sensing. IEEE Trans. Inf. Theory 52(4) (2006)

  26. Donoho, D.L., Tanner, J.: Counting faces of randomly-projected polytopes when the projection radically lowers dimension. J. Am. Math. Soc. 22, 1–53 (2009)

    Article  MathSciNet  Google Scholar 

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

    Article  MATH  Google Scholar 

  28. Donoho, D., Tsaig, Y.: Extensions of compressed sensing. Signal Process. 86(3), 533–548 (2006)

    Article  Google Scholar 

  29. Takhar, D., Bansal, V., Wakin, M., Duarte, M., Baron, D., Kelly, K.F., Baraniuk, R.G.: A compressed sensing camera: New theory and an implementation using digital micromirrors. In: Proceedings of Comp. Imaging IV at SPIE Electronic Imaging, San Jose, California, January 2006

  30. Lustig, M., Donoho, D., Pauly, J.M.: Sparse MRI: The application of compressed sensing for rapid MR imaging. Preprint (2007)

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

    Article  Google Scholar 

  32. Candès, E.J., Randall, P.A.: Highly robust error correction by convex programming. Available on the ArXiV preprint server (cs/0612124) (2006)

  33. Healy, D.L.: Analog-to-information (A-to-I). DARPA/MTO Broad Agency Announcement BAA 05-35 (July 2005)

  34. Bajwa, W., Haupt, J., Sayeed, A., Nowak, R.: Compressive wireless sensing. In: Proceedings of Fifth Int. Conf. on Information Processing in Sensor Networks, pp. 134–142 (2006)

  35. Baron, D., Wakin, M.B., Duarte, M.F., Sarvotham, S., Baraniuk, R.G.: Distributed compressed sensing. Preprint (2005)

  36. Lange, K.: Optimization, Springer Texts in Statistics. Springer, New York (2004)

    MATH  Google Scholar 

  37. Fazel, M.: Matrix rank minimization with applications. Ph.D. thesis, Electrical Engineering Department, Stanford University (2002)

  38. Lobo, M.S., Fazel, M., Boyd, S.: Portfolio optimization with linear and fixed transaction costs. Ann. Oper. Res. 152(1), 341–365 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  39. Fazel, M., Hindi, H., Boyd, S.: Log-det heuristic for matrix rank minimization with applications to Hankel and Euclidean distance matrices. In: Proceedings of Am. Control Conf., June 2003

  40. Figueiredo, M.A.T., Nowak, R.D.: A bound optimization approach to wavelet-based image deconvolution. In: Proceedings of IEEE Int. Conf. on Image Processing (ICIP), vol. 2 (2005)

  41. Figueiredo, M., Bioucas-Dias, J.M., Nowak, R.D.: Majorization–minimization algorithms for wavelet-based image restoration. IEEE Trans. Image Process. 16(12), 2980–2991 (2007)

    Article  MathSciNet  Google Scholar 

  42. Wipf, D.P., Nagarajan, S.: A new view of automatic relevance determination. In: Proceedings on Neural Information Processing Systems (NIPS), vol. 20 (2008)

  43. Zou, H.: The adaptive Lasso and its oracle properties. J. Am. Stat. Assoc. 101(476), 1418–1429 (2006)

    Article  MATH  Google Scholar 

  44. Zou, H., Li, R.: One-step sparse estimates in nonconcave penalized likelihood models. Ann. Stat. 36(4), 1509–1533 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  45. Schlossmacher, E.J.: An iterative technique for absolute deviations curve fitting. J. Am. Stat. Assoc. 68(344), 857–859 (1973)

    Article  MATH  Google Scholar 

  46. Holland, P., Welsch, R.: Robust regression using iteratively reweighted least-squares. Commun. Stat. Theor. Methods A6, 813–827 (1977)

    Article  Google Scholar 

  47. Huber, P.J.: Robust Statistics. Wiley-Interscience, New York (1981)

    Book  MATH  Google Scholar 

  48. Yarlagadda, R., Bednar, J.B., Watt, T.L.: Fast algorithms for ℓ p deconvolution. IEEE Trans. Acoust. Speech Signal Process. 33(1), 174–182 (1985)

    Article  Google Scholar 

  49. Yin, W., Osher, S., Goldfarb, D., Darbon, J.: Bregman iterative algorithms for ℓ 1-minimization with applications to compressed sensing. SIAM J. Imaging Sci. 1(1), 143–168 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  50. Candès, E.J., Tao, T.: The Dantzig selector: Statistical estimation when p is much larger than n. Ann. Stat. 35(6), 2313–2351 (2007)

    Article  MATH  Google Scholar 

  51. Goldfarb, D., Yin, W.: Second-order cone programming methods for total variation-based image restoration. SIAM J. Sci. Comput. 27(2), 622–645 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  52. Chartrand, R.: Exact reconstruction of sparse signals via nonconvex minimization. Signal Process. Lett. 14(10), 707–710 (2007)

    Article  Google Scholar 

  53. Starck, J.-L., Elad, M., Donoho, D.L.: Redundant multiscale transforms and their application for morphological component analysis. Adv. Imaging Electron. Phys. 132, 288–348 (2004)

    Google Scholar 

  54. Elad, M., Milanfar, P., Rubinstein, R.: Analysis versus synthesis in signal priors. Inverse Probl. 23(3), 947–968 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  55. Gorodnitsky, I.F., Rao, B.D.: Sparse signal reconstruction from limited data using FOCUSS: A re-weighted minimum norm algorithm. IEEE Trans. Signal Process. 45(3), 600–616 (1997)

    Article  Google Scholar 

  56. Chartrand, R., Yin, W.: Iteratively reweighted algorithms for compressive sensing. In: Proceedings of Int. Conf. on Acoustics, Speech, Signal Processing (ICASSP), pp. 3869–3872 (2008)

  57. Wipf, D.P.: Personal communication (January 2008)

  58. Harikumar, G., Bresler, Y.: A new algorithm for computing sparse solutions to linear inverse problems. In: Proceedings of Int. Conf. on Acoustics, Speech, Signal Processing (ICASSP). IEEE, New York (1996)

    Google Scholar 

  59. Delaney, A.H., Bresler, Y.: Globally convergent edge-preserving regularized reconstruction: An application to limited-angle tomography. IEEE Trans. Image Process. 7(2), 204–221 (1998)

    Article  Google Scholar 

  60. Saab, R., Chartrand, R., Yilmaz, O.: Stable sparse approximations via nonconvex optimization. In: 33rd International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2008

  61. Black, M.J., Sapiro, G., Marimont, D.H., Heeger, D.: Robust anisotropic diffusion. IEEE Trans. Image Process. 7(3), 421–432 (1998)

    Article  Google Scholar 

  62. Boyd, S.: Lecture notes for EE364B: convex optimization II. Available at www.stanford.edu/class/ee364b/ (2007)

Download references

Author information

Authors and Affiliations

  1. Applied and Computational Mathematics, Caltech, Pasadena, CA, 91125, USA

    Emmanuel J. Candès

  2. Engineering, Colorado School of Mines, Golden, CO, 80401, USA

    Michael B. Wakin

  3. Department of Electrical Engineering, Stanford University, Stanford, CA, 94305, USA

    Stephen P. Boyd

Authors
  1. Emmanuel J. Candès
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michael B. Wakin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Stephen P. Boyd
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Michael B. Wakin.

Additional information

Communicated by Albert Cohen.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Candès, E.J., Wakin, M.B. & Boyd, S.P. Enhancing Sparsity by Reweighted ℓ 1 Minimization. J Fourier Anal Appl 14, 877–905 (2008). https://doi.org/10.1007/s00041-008-9045-x

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00041-008-9045-x

Keywords

Search

Navigation