Linearized Bregman iterations for compressed sensing

Cai, Jian-Feng; Osher, Stanley; Shen, Zuowei

doi:10.1090/S0025-5718-08-02189-3

Linearized Bregman iterations for compressed sensing

Authors: Jian-Feng Cai, Stanley Osher and Zuowei Shen
Journal: Math. Comp. 78 (2009), 1515-1536
MSC (2000): Primary 65K05, 65F22; Secondary 65T99
DOI: https://doi.org/10.1090/S0025-5718-08-02189-3
Published electronically: October 22, 2008
MathSciNet review: 2501061
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Finding a solution of a linear equation with various minimization properties arises from many applications. One such application is compressed sensing, where an efficient and robust-to-noise algorithm to find a minimal $\ell_1$ norm solution is needed. This means that the algorithm should be tailored for large scale and completely dense matrices , while and can be computed by fast transforms and the solution we seek is sparse. Recently, a simple and fast algorithm based on linearized Bregman iteration was proposed in [28, 32] for this purpose. This paper is to analyze the convergence of linearized Bregman iterations and the minimization properties of their limit. Based on our analysis here, we derive also a new algorithm that is proven to be convergent with a rate. Furthermore, the new algorithm is simple and fast in approximating a minimal $\ell_1$ norm solution of as shown by numerical simulations. Hence, it can be used as another choice of an efficient tool in compressed sensing.

1. L. M. Brègman, A relaxation method of finding a common point of convex sets and its application to the solution of problems in convex programming, Ž. Vyčisl. Mat i Mat. Fiz. 7 (1967), 620–631 (Russian). MR 215617
2. A. M. Bruckstein, D. L. Donoho, and M. Elad, From sparse solutions of systems of equations to sparse modeling of signals and images, 2008, to appear in SIAM Review.
3. J.-F. Cai, R. H. Chan, L. Shen, and Z. Shen, Restoration of chopped and nodded images by framelets, SIAM J. Sci. Comput. 30 (2008), no. 3, 1205-1227.
4. -, Simultaneously inpainting in image and transformed domains, 2008, preprint.
5. Jian-Feng Cai, Raymond H. Chan, and Zuowei Shen, A framelet-based image inpainting algorithm, Appl. Comput. Harmon. Anal. 24 (2008), no. 2, 131–149. MR 2393979, https://doi.org/10.1016/j.acha.2007.10.002
6. -, Simultaneous cartoon and texture inpainting, 2008, preprint.
7. J.-F. Cai and Z. Shen, Deconvolution: A wavelet frame approach, II, 2008, preprint.
8. Emmanuel Candès and Justin Romberg, Sparsity and incoherence in compressive sampling, Inverse Problems 23 (2007), no. 3, 969–985. MR 2329927, https://doi.org/10.1088/0266-5611/23/3/008
9. Emmanuel J. Candès, Compressive sampling, International Congress of Mathematicians. Vol. III, Eur. Math. Soc., Zürich, 2006, pp. 1433–1452. MR 2275736
10. Emmanuel J. Candès and Justin Romberg, Quantitative robust uncertainty principles and optimally sparse decompositions, Found. Comput. Math. 6 (2006), no. 2, 227–254. MR 2228740, https://doi.org/10.1007/s10208-004-0162-x
11. Emmanuel J. Candès, Justin Romberg, and Terence Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory 52 (2006), no. 2, 489–509. MR 2236170, https://doi.org/10.1109/TIT.2005.862083
12. Emmanuel J. Candes and Terence Tao, Near-optimal signal recovery from random projections: universal encoding strategies?, IEEE Trans. Inform. Theory 52 (2006), no. 12, 5406–5425. MR 2300700, https://doi.org/10.1109/TIT.2006.885507
13. Anwei Chai and Zuowei Shen, Deconvolution: a wavelet frame approach, Numer. Math. 106 (2007), no. 4, 529–587. MR 2317925, https://doi.org/10.1007/s00211-007-0075-0
14. Patrick L. Combettes and Jean-Christophe Pesquet, Proximal thresholding algorithm for minimization over orthonormal bases, SIAM J. Optim. 18 (2007), no. 4, 1351–1376. MR 2373305, https://doi.org/10.1137/060669498
15. Patrick L. Combettes and Valérie R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul. 4 (2005), no. 4, 1168–1200. MR 2203849, https://doi.org/10.1137/050626090
16. J. Darbon and S. Osher, Fast discrete optimization for sparse approximations and deconvolutions, 2007, preprint.
17. Ingrid Daubechies, Michel Defrise, and Christine De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Comm. Pure Appl. Math. 57 (2004), no. 11, 1413–1457. MR 2077704, https://doi.org/10.1002/cpa.20042
18. Ingrid Daubechies, Gerd Teschke, and Luminita Vese, Iteratively solving linear inverse problems under general convex constraints, Inverse Probl. Imaging 1 (2007), no. 1, 29–46. MR 2262744, https://doi.org/10.3934/ipi.2007.1.29
19. Ronald A. DeVore, Deterministic constructions of compressed sensing matrices, J. Complexity 23 (2007), no. 4-6, 918–925. MR 2371999, https://doi.org/10.1016/j.jco.2007.04.002
20. David L. Donoho, De-noising by soft-thresholding, IEEE Trans. Inform. Theory 41 (1995), no. 3, 613–627. MR 1331258, https://doi.org/10.1109/18.382009
21. David L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), no. 4, 1289–1306. MR 2241189, https://doi.org/10.1109/TIT.2006.871582
22. David L. Donoho and Jared Tanner, Neighborliness of randomly projected simplices in high dimensions, Proc. Natl. Acad. Sci. USA 102 (2005), no. 27, 9452–9457. MR 2168716, https://doi.org/10.1073/pnas.0502258102
23. Michael Elad and Alfred M. Bruckstein, A generalized uncertainty principle and sparse representation in pairs of bases, IEEE Trans. Inform. Theory 48 (2002), no. 9, 2558–2567. MR 1929464, https://doi.org/10.1109/TIT.2002.801410
24. Arie Feuer and Arkadi Nemirovski, On sparse representation in pairs of bases, IEEE Trans. Inform. Theory 49 (2003), no. 6, 1579–1581. MR 1984950, https://doi.org/10.1109/TIT.2003.811926
25. Jean-Baptiste Hiriart-Urruty and Claude Lemaréchal, Convex analysis and minimization algorithms. I, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 305, Springer-Verlag, Berlin, 1993. Fundamentals. MR 1261420
26. Peter J. Huber, Robust regression: asymptotics, conjectures and Monte Carlo, Ann. Statist. 1 (1973), 799–821. MR 0356373
27. Stanley Osher, Martin Burger, Donald Goldfarb, Jinjun Xu, and Wotao Yin, An iterative regularization method for total variation-based image restoration, Multiscale Model. Simul. 4 (2005), no. 2, 460–489. MR 2162864, https://doi.org/10.1137/040605412
28. S. Osher, Y. Mao, B. Dong, and W. Yin, Fast linearized Bregman iteration for compressed sensing and sparse denoising, 2008, UCLA CAM Reports (08-37).
29. Mark Rudelson and Roman Vershynin, Geometric approach to error-correcting codes and reconstruction of signals, Int. Math. Res. Not. 64 (2005), 4019–4041. MR 2206919, https://doi.org/10.1155/IMRN.2005.4019
30. Joel A. Tropp, Just relax: convex programming methods for identifying sparse signals in noise, IEEE Trans. Inform. Theory 52 (2006), no. 3, 1030–1051. MR 2238069, https://doi.org/10.1109/TIT.2005.864420
31. Y. Tsaig and D. L. Donono, Extensions of compressed sensing, Signal Processing 86 (2005), 533-548.
32. W. Yin, S. Osher, D. Goldfarb, and J. Darbon, Bregman iterative algorithms for $\ell_1$ -minimization with applications to compressed sensing, SIAM J. Imaging Sci. 1 (2008), no. 1, 143-168.
33. Y. Zhang, A simple proof for recoverability of $\ell_1$ -minimization: Go over or under?, 2005, Rice University CAAM Technical Report TR05-09.
34. -, When is missing data recoverable?, 2006, Rice University CAAM Technical Report TR06-15.
35. Hui Zou and Trevor Hastie, Regularization and variable selection via the elastic net, J. R. Stat. Soc. Ser. B Stat. Methodol. 67 (2005), no. 2, 301–320. MR 2137327, https://doi.org/10.1111/j.1467-9868.2005.00503.x