By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Imaging Sciences

Previous Article
Segmentation under Occlusions Using Selective Shape Prior
In this work, we address the problem of segmenting multiple objects, under possible occlusions, in a level set framework. A variational energy that incorporates a piecewise constant representation of...

You are logged in to this journal.

Bregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing

SIAM J. Img. Sci. Volume 1, Issue 1, pp. 143-168 (2008)

Published March 20, 2008
FULL TEXT OPTIONS   (FREE)
Download PDF (362 kB) View Cart

We propose simple and extremely efficient methods for solving the basis pursuit problem $\min\{\|u\|_1 : Au = f, u\in\mathbb{R}^n\},$ which is used in compressed sensing. Our methods are based on Bregman iterative regularization, and they give a very accurate solution after solving only a very small number of instances of the unconstrained problem $\min_{u\in\mathbb{R}^n} \mu\|u\|_1+\frac{1}{2}\|Au-f^k\|_2^2$ for given matrix $A$ and vector $f^k$. We show analytically that this iterative approach yields exact solutions in a finite number of steps and present numerical results that demonstrate that as few as two to six iterations are sufficient in most cases. Our approach is especially useful for many compressed sensing applications where matrix-vector operations involving $A$ and $A^\top$ can be computed by fast transforms. Utilizing a fast fixed-point continuation solver that is based solely on such operations for solving the above unconstrained subproblem, we were able to quickly solve huge instances of compressed sensing problems on a standard PC.

©2008 Society for Industrial and Applied Mathematics
History: Received September 28, 2007; accepted January 29, 2008; published March 20, 2008
Permalink: http://dx.doi.org/10.1137/070703983

KEYWORDS and AMS

Keywords
AMS Subject Classifications
49, 90, 65

PUBLICATION DATA

ISSN:
1936-4954 (online)
Publisher:
AIP is a member of CrossRef SIAM

REFERENCES (102)
View in Separate Window/Tab
  1. T. Adeyemi and M. Davies, Sparse representations of images using overcomplete complex wavelets, in 2005 IEEE/SP 13th Workshop on Statistical Signal Processing, 2005, pp. 865–870.
  2. M. Bachmayr, Iterative Total Variation Methods for Nonlinear Inverse Problems, Master's thesis, Johannes Kepler Universität, Linz, Austria, 2007.
  3. W. Bajwa, J. Haupt, A. Sayeed, and R. Nowak, Compressive wireless sensing, in Proceedings of the Fifth International Conference on Information Processing in Sensor Networks (IPSN), Nashville, TN, ACM, New York, 2006, pp. 134–142.
  4. D. Baron, M. Wakin, M. Duarte, S. Sarvotham, and R. Baraniuk, Distributed Compressed Sensing, preprint, 2005.
  5. J. Bect, L. Blanc-Féraud, G. Aubert, and A. Chambolle, A $\ell_1$-unified variational framework for image restoration, in Proceedings of the 8th European Conference on Computer Vision, Prague, Lecture Notes in Comput. Sci. 3024, Springer-Verlag, Berlin, 2004, pp. 1–13.
  6. J. Bioucas-Dias, Bayesian wavelet-based image deconvolution: A GEM algorithm exploiting a class of heavy-tailed priors, IEEE Trans. Image Process., 15 (2006), pp. 937–951. [MEDLINE]
  7. J. Bioucas-Dias and M. Figueiredo, Two-step algorithms for linear inverse problems with non-quadratic regularization, in Proceedings of the IEEE International Conference on Image Processing (ICIP 2007), San Antonio, TX, 2007.
  8. T. Blumensath and M. Davies, Iterative thresholding for sparse approximations, J. Fourier Anal. Appl., to appear.
  9. L. Bregman, The relaxation method of finding the common points of convex sets and its application to the solution of problems in convex programming, Comput. Math. Math. Phys., 7 (1967), pp. 200–217. [MathRev]
  10. M. Burger, G. Gilboa, S. Osher, and J. Xu, Nonlinear inverse scale space methods, Commun. Math. Sci., 4 (2006), pp. 179–212. [ZentralblattMath] [MathRev]
  11. M. Burger, S. Osher, J. Xu, and G. Gilboa, Nonlinear inverse scale space methods for image restoration, in Variational Geometric and Level Set Methods in Computer Vision, Lecture Notes in Comput. Sci. 3752, Springer-Verlag, Berlin, 2005, pp. 25–36.
  12. E. Candès and J. Romberg, Quantitative robust uncertainty principles and optimally sparse decompositions, Found. Comput. Math., 6 (2006), pp. 227–254.
  13. E. Candès and J. Romberg, Sparsity and incoherence in compressive sampling, Inverse Problems, 23 (2007), pp. 969–985.
  14. E. Candès, J. Romberg, and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory, 52 (2006), pp. 489–509. [Inspec]
  15. E. Candès and T. Tao, Decoding by linear programming, IEEE Trans. Inform. Theory, 51 (2005), pp. 4203–4215.
  16. E. Candès and T. Tao, Near optimal signal recovery from random projections: Universal encoding strategies, IEEE Trans. Inform. Theory, 52 (2006), pp. 5406–5425.
  17. A. Chambolle, An algorithm for total variation minimization and applications, J. Math. Imaging Vision, 20 (2004), pp. 89–97. [MathRev]
  18. A. Chambolle, Total Variation Minimization and a Class of Binary MRF models, Technical report UMR CNRS 7641, Ecole Polytechnique, Palaiseau, France, 2005.
  19. A. Chambolle, R. A. DeVore, N.-Y. Lee, and B. J. Lucier, Nonlinear wavelet image processing: Variational problems, compression, and noise removal through wavelet shrinkage, IEEE Trans. Image Process., 7 (1998), pp. 319–335. [Inspec] [ISI] [MEDLINE] [MathRev]
  20. R. Chartrand, Exact reconstructions of sparse signals via nonconvex minimization, IEEE Signal Process. Lett., 14 (2007), pp. 707–710. [Inspec]
  21. R. Chartrand, Nonconvex compressed sensing and error correction, in Proceedings of the 32nd International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2007, pp. 889–892.
  22. R. Chartrand and W. Yin, Iteratively reweighted algorithms for compressive sensing, Proceedings of ICASSP'08, submitted.
  23. S. S. Chen, D. L. Donoho, and M. A. Saunders, Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., 20 (1998), pp. 33–61. [ISI]
  24. T. Chen, T. Huang, W. Yin, and X. S. Zhou, A new coarse-to-fine framework for $3$D brain MR image registration, in Computer Vision for Biomedical Image Applications, Lecture Notes in Comput. Sci. 3765, Springer-Verlag, Berlin, 2005, pp. 114–124.
  25. T. Chen, W. Yin, X. S. Zhou, D. Comaniciu, and T. Huang, Total variation models for variable lighting face recognition, IEEE Trans. Pattern Anal. Mach. Intell. (PAMI), 28 (2006), pp. 1519–1524.
  26. P. L. Combettes and J.-C. Pesquet, Proximal thresholding algorithm for minimization over orthonormal bases, SIAM J. Optim., 18 (2007), pp. 1351–1376.
  27. J. Darbon and S. Osher, Fast Discrete Optimization for Sparse Approximations and Deconvolutions, preprint, 2007.
  28. J. Darbon and M. Sigelle, Image restoration with discrete constrained total variation, Part I: Fast and exact optimization, J. Math. Imaging Vision, 26 (2006), pp. 261–276. [Inspec]
  29. I. Daubechies, M. Defrise, and C. De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Comm. Pure Appl. Math., 57 (2004), pp. 1413–1457.
  30. I. Daubechies, M. Fornasier, and I. Loris, Accelerated Projected Gradient Method for Linear Inverse Problems with Sparsity Constraints, http://arxiv.org/abs/0706.4297 (2007).
  31. C. De Mol and M. Defrise, A note on wavelet-based inversion algorithms, Contemp. Math., 313 (2002), pp. 85–96. [ZentralblattMath] [MathRev]
  32. R. A. DeVore, Deterministic constructions of compressed sensing matrices, J. Complexity, 23 (2007), pp. 918–925. [Inspec] [MathRev]
  33. R. A. DeVore and B. J. Lucier, Wavelets, in Acta Numerica 1992, Acta Numer., Cambridge University Press, Cambridge, UK, 1992, pp. 54–81.
  34. B. Dong, Y. Mao, S. Osher, and W. Yin, Fast Linearized Bregman Iteration for Compressed Sensing and Related Problems, working paper, 2007.
  35. D. Donoho, Compressed sensing, IEEE Trans. Inform. Theory, 52 (2006), pp. 1289–1306. [Inspec]
  36. D. Donoho and J. Tanner, Neighborliness of randomly projected simplices in high dimensions, Proc. Natl. Acad. Sci. USA, 102 (2005), pp. 9452–9457. [MEDLINE] [MathRev]
  37. D. Donoho, Y. Tsaig, I. Drori, and J.-C. Starck, Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit, IEEE Trans. Inform. Theory, submitted.
  38. M. Elad, Why simple shrinkage is still relevant for redundant representations?, IEEE Trans. Inform. Theory, 52 (2006), pp. 5559–5569.
  39. M. Elad and A. Bruckstein, A generalized uncertainty principle and sparse representations in pairs of bases, IEEE Trans. Inform. Theory, 48 (2002), pp. 2558–2567.
  40. M. Elad, B. Matalon, J. Shtok, and M. Zibulevsky, A wide-angle view at iterated shrinkage algorithms, in Proceedings of the SPIE (Wavelet XII), San Diego, CA, 2007.
  41. M. Elad, B. Matalon, and M. Zibulevsky, Coordinate and subspace optimization methods for linear least squares with non-quadratic regularization, Appl. Comput. Harmon. Anal., 23 (2007), pp. 346–367. [MathRev]
  42. M. Elad, J.-C. Starck, P. Querre, and D. Donoho, Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA), Appl. Comput. Harmon. Anal., 19 (2005), pp. 340–358. [Inspec]
  43. M. J. Fadili and J. L. Starck, Sparse representation-based image deconvolution by iterative thresholding, in Proceedings of Astronomical Data Analysis (ADA'06), Marseille, France, 2006.
  44. A. Feuer and A. Nemirovski, On sparse representation in pairs of bases, IEEE Trans. Inform. Theory, 49 (2003), pp. 1579–1581. [Inspec] [MathRev]
  45. M. Figueiredo, J. Bioucas-Dias, and R. Nowak, Majorization-minimization algorithms for wavelet-based image restoration, IEEE Trans. Image Process., 16 (2007), pp. 2980–2991. [Inspec] [MEDLINE]
  46. M. Figueiredo and R. Nowak, An EM algorithm for wavelet-based image restoration, IEEE Trans. Image Process., 12 (2003), pp. 906–916. [MEDLINE] [MathRev]
  47. M. Figueiredo and R. Nowak, A bound optimization approach to wavelet-based image deconvolution, in Proceedings of the IEEE International Conference on Image Processing (ICIP), 2005.
  48. M. Figueiredo, R. Nowak, and S. J. Wright, GPSR: Gradient projection for sparse reconstruction, IEEE J. Selected Topics Image Process., to appear.
  49. M. Figueiredo, R. Nowak, and S. J. Wright, Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems, IEEE J. Selected Topics in Signal Processing, to appear.
  50. M. Fornasier and H. Rauhut, Recovery Algorithms for Vector Valued Data with Joint Sparsity Constraints, preprint, 2006; available online at http://arxiv.org/abs/math/0608124.
  51. L. Gan, Block compressed sensing of natural images, in Proceedings of the International Conference on Digital Signal Processing (DSP), Cardiff, UK, 2007.
  52. H.-Y. Gao and A. G. Bruce, WaveShrink with firm shrinkage, Statist. Sinica, 7 (1997), pp. 855–874. [ZentralblattMath] [MathRev]
  53. D. Goldfarb and W. Yin, Parametric Maximum Flow Algorithms for Fast Total Variation Minimization, CAAM Technical report TR07-09, Rice University, Houston, TX, 2007.
  54. R. Gribonval, H. Rauhut, K. Schnass, and P. Vandergheynst, Atoms of All Channels, Unite! Average Case Analysis of Multi-channel Sparse Recovery Using Greedy Algorithms, http://hal.inria.fr/inria-00146660 http://hal.inria.fr/inria-00146660 (2007).
  55. E. Hale, W. Yin, and Y. Zhang, A Fixed-Point Continuation Method for $\ell_1$-Regularization with Application to Compressed Sensing, CAAM Technical report TR07-07, Rice University, Houston, TX, 2007.
  56. E. Hale, W. Yin, and Y. Zhang, FPC: A Fixed-Point Continuation Method for $\ell_1$-Regularization, http://www.caam.rice.edu/ optimization/L1 (2007).
  57. E. Hale, W. Yin, and Y. Zhang, A numerical study of fixed-point continuation applied to compressed sensing, IEEE Trans. Inform. Theory, submitted.
  58. E. T. Hale, W. Yin, and Y. Zhang, Fixed-point continuation for $\ell_1$-minimization: Methodology and convergence, SIAM J. Optim., submitted.
  59. L. He, T.-C. Chang, S. Osher, T. Fang, and P. Speier, MR Image Reconstruction by Using the Iterative Refinement Method and Nonlinear Inverse Scale Space Methods, UCLA CAM Report 06-35, University of California, Los Angeles, 2006.
  60. M. R. Hestenes, Multiplier and gradient methods, J. Optim. Theory Appl., 4 (1969), pp. 303–320. [ZentralblattMath] [MathRev]
  61. H. Jung, J. Ye, and E. Kim, Improved k-t BLAST and k-t SENSE using FOCUSS, Phys. Med. Biol., 52 (2007), pp. 3201–3226. [Inspec] [MEDLINE]
  62. S.-J. Kim, K. Koh, M. Lustig, S. Boyd, and D. Gorinevsky, A Method for Large-Scale $\ell_1$-Regularized Least Squares Problems with Applications in Signal Processing and Statistics, http://www.stanford.edu/ boyd/l1ls.html http://www.stanford.edu/$\sim$boyd/l1_ls.html (2007).
  63. S. Kirolos, J. Laska, M. Wakin, M. Duarte, D. Baron, T. Ragheb, Y. Massoud, and R. Baraniuk, Analog-to-information conversion via random demodulation, in Proceedings of the IEEE Dallas Circuits and Systems Workshop (DCAS), Dallas, TX, 2006.
  64. K. Koh, S.-J. Kim, and S. Boyd, $\ell_1\_\ell_s$: A Simple MATLAB Solver for $\ell_1$-Regularized Least Squares Problems, http://www.stanford.edu/ boyd/l1ls/ (2007).
  65. J. Laska, S. Kirolos, M. Duarte, T. Ragheb, R. Baraniuk, and Y. Massoud, Theory and implementation of an analog-to-information converter using random demodulation, in Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS), New Orleans, LA, 2007.
  66. J. Laska, S. Kirolos, Y. Massoud, R. Baraniuk, A. Gilbert, M. Iwen, and M. Strauss, Random sampling for analog-to-information conversion of wideband signals, in Proceedings of the IEEE Dallas Circuits and Systems Workshop, Dallas, TX, 2006.
  67. Z.-Q. Luo and P. Tseng, On the linear convergence of descent methods for convex essentially smooth minimization, SIAM J. Control Optim., 30 (1992), pp. 408–425. [ZentralblattMath] [MathRev]
  68. M. Lustig, D. Donoho, and J. M. Pauly, Sparse MRI: The application of compressed sensing for rapid MR imaging, Magnetic Resonance in Medicine, 58 (2007), pp. 1182–1195. [MEDLINE]
  69. M. Lustig, J. Santos, D. Donoho, and J. Pauly, k-t SPARSE: High frame rate dynamic MRI exploiting spatio-temporal sparsity, in Proceedings of the 14th Annual Meeting of the International Society for Magnetic Resonance in Medicine, Seattle, WA, 2006.
  70. M. Lustig, J. Santos, J.-H. Lee, D. Donoho, and J. Pauly, Application of Compressed Sensing for Rapid MR Imaging, preprint, Stanford University, Stanford, CA, 2007.
  71. Y. Nesterov, Gradient Methods for Minimizing Composite Objective Function, CORE Discussion Paper 2007/76, http://www.optimization-online.org (2007).
  72. R. Nowak and M. Figueiredo, Fast wavelet-based image deconvolution using the EM algorithm, in Proceedings of the 35th Asilomar Conference on Signals, Systems, and Computers, Monterey, CA, 2001.
  73. S. Osher, M. Burger, D. Goldfarb, J. Xu, and W. Yin, An iterated regularization method for total variation-based image restoration, Multiscale Model. Simul., 4 (2005), pp. 460–489.
  74. J.-S. Pang, A posteriori error bounds for the linearly-constrained variational inequality problem, Math. Oper. Res., 12 (1987), pp. 474–484. [ISI]
  75. M. J. D. Powell, A method for nonlinear constraints in minimization problems, in Optimization, R. Fletcher, ed., Academic Press, New York, 1972, pp. 283–298.
  76. M. Rabbat, J. Haupt, A. Singh, and R. Nowak, Decentralized compression and predistribution via randomized gossiping, in Proceedings of the International Conference on Information Processing in Sensor Networks (IPSN), Nashville, TN, 2006.
  77. T. Ragheb, S. Kirolos, J. Laska, A. Gilbert, M. Strauss, R. Baraniuk, and Y. Massoud, Implementation models for analog-to-information conversion via random sampling, in Proceedings of the Midwest Symposium on Circuits and Systems (MWSCAS), 2007.
  78. T. H. Reeves and N. G. Kingsbury, Overcomplete image coding using iterative projection-based noise shaping, in Proceedings of the 2002 International Conference on Image Processing, Vol. 3, 2002, pp. 24–28.
  79. R. T. Rockafellar, A dual approach to solving nonlinear programming problems by unconstrained optimization, Math. Programming, 5 (1973), pp. 354–373. [ZentralblattMath] [MathRev]
  80. M. Rudelson and R. Vershynin, Geometric approach to error correcting codes and reconstruction of signals, Int. Math. Res. Not., 64 (2005), pp. 4019–4041.
  81. L. Rudin, S. Osher, and E. Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D, 60 (1992), pp. 259–268. [Inspec] [ISI] [ZentralblattMath]
  82. I. Selesnick, R. Van Slyke, and O. Guleryuz, Pixel recovery via $\ell_1$ minimization in the wavelet domain, in Proceedings of the 2004 International Conference on Image Processing, Vol. 3, 2004, pp. 1819–1822.
  83. M. Sheikh, O. Milenkovic, and R. Baraniuk, Compressed Sensing DNA Microarrays, Rice ECE Department Technical report TREE 0706, Rice University, Houston, TX, 2007.
  84. D. Takhar, J. Laska, M. Wakin, M. Duarte, D. Baron, S. Sarvotham, K. Kelly, and R. Baraniuk, A new compressive imaging camera architecture using optical-domain compression, in Proceedings of Computational Imaging IV at the SPIE Symposium on Electronic Imaging, San Jose, CA, 2006.
  85. R. Tibshirani, Regression shrinkage and selection via the lasso, J. Roy. Statist. Soc. Ser. B, 58 (1996), pp. 267–288.
  86. J. Tropp, Just relax: Convex programming methods for identifying sparse signals, IEEE Trans. Inform. Theory, 51 (2006), pp. 1030–1051. [MathRev]
  87. J. Tropp, M. Wakin, M. Duarte, D. Baron, and R. Baraniuk, Random filters for compressive sampling and reconstruction, in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Toulouse, France, 2006.
  88. Y. Tsaig and D. L. Donoho, Extensions of compressed sensing, Signal Processing, 86 (2006), pp. 549–571. [Inspec]
  89. E. Van den Berg and M. P. Friedlander, In Pursuit of a Root, UBC Computer Science Technical report TR-2007-16, University of British Columbia, Vancouver, 2007.
  90. E. Van den Berg and M. P. Friedlander, SPGL1: A solver for sparse reconstruction, http://www.cs.ubc.ca/labs/scl/spgl1 http://www.cs.ubc.ca/labs/scl/spgl1 (2007).
  91. M. Wakin, J. Laska, M. Duarte, D. Baron, S. Sarvotham, D. Takhar, K. Kelly, and R. Baraniuk, An architecture for compressive imaging, in Proceedings of the IEEE International Conference on Image Processing (ICIP), Atlanta, GA, 2006.
  92. M. Wakin, J. Laska, M. Duarte, D. Baron, S. Sarvotham, D. Takhar, K. Kelly, and R. Baraniuk, Compressive imaging for video representation and coding, in Proceedings of the Picture Coding Symposium (PCS), Beijing, China, 2006.
  93. W. Wang, M. Garofalakis, and K. Ramchandran, Distributed sparse random projections for refinable approximation, in Proceedings of the International Conference on Information Processing in Sensor Networks (IPSN), Nashville, TN, 2007.
  94. Y. Wang, W. Yin, and Y. Zhang, A Fast Fixed-Point Algorithm for Convex Total Variation Regularization, working paper, Rice University, Houston, TX, 2007.
  95. J. Xu and S. Osher, Iterative regularization and nonlinear inverse scale space applied to wavelet-based denoising, IEEE Trans. Image Process., 16 (2006), pp. 534–544. [Inspec] [MEDLINE]
  96. J. Ye, Compressed sensing shape estimation of star-shaped objects in Fourier imaging, IEEE Signal Process. Lett., 14 (2007), pp. 750–753. [Inspec]
  97. W. Yin, T. Chen, X. S. Zhou, and A. Chakraborty, Background correction for cDNA microarray image using the $TV+L^1$ model, Bioinformatics, 21 (2005), pp. 2410–2416. [MEDLINE]
  98. W. Yin, D. Goldfarb, and S. Osher, A comparison of three total variation-based texture extraction models, J. Visual Commun. Image Representation, 18 (2007), pp. 240–252. [Inspec]
  99. W. Yin, D. Goldfarb, and S. Osher, The total variation regularized $L^1$ model for multiscale decomposition, Multiscale Model. Simul., 6 (2007), pp. 190–211.
  100. Y. Zhang, A Simple Proof for Recoverability of $\ell_1$-Minimization: Go Over or Under?, CAAM Technical report TR05-09, Rice University, Houston, TX, 2005.
  101. Y. Zhang, When Is Missing Data Recoverable?, CAAM Technical report TR06-15, Rice University, Houston, TX, 2006.
  102. W. P. Ziemer, Weakly Differentiable Functions: Sobolev Spaces and Functions of Bounded Variation, Grad. Texts in Math., Springer-Verlag, New York, 1989.