A dual split Bregman method for fast ℓ¹ minimization

Yang, Yi; Möller, Michael; Osher, Stanley

doi:10.1090/S0025-5718-2013-02700-7

A dual split Bregman method for fast $\ell ^1$ minimization
HTML articles powered by AMS MathViewer

by Yi Yang, Michael Möller and Stanley Osher PDF

Math. Comp. 82 (2013), 2061-2085 Request permission

Abstract:

In this paper we propose a new algorithm for fast $\ell ^1$ minimization as frequently arising in compressed sensing. Our method is based on a split Bregman algorithm applied to the dual of the problem of minimizing $\|u\|_1 + \frac {1}{2 \alpha } \|u\|^2$ such that $u$ solves the under-determined linear system $Au=f$, which was recently investigated in the context of linearized Bregman methods.

Furthermore, we provide a convergence analysis for split Bregman methods in general and show with our compressed sensing example that a split Bregman approach to the primal energy can lead to a different type of convergence than split Bregman applied to the dual, thus making the analysis of different ways to minimize the same energy interesting for a wide variety of optimization problems.

References

Amir Beck and Marc Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci. 2 (2009), no. 1, 183–202. MR 2486527, DOI 10.1137/080716542
Martin Burger, Guy Gilboa, Stanley Osher, and Jinjun Xu, Nonlinear inverse scale space methods, Commun. Math. Sci. 4 (2006), no. 1, 179–212. MR 2204083
Martin Burger, Michael Möller, Martin Benning, and Stanley Osher, An adaptive inverse scale space method for compressed sensing, Math. Comp. 82 (2013), no. 281, 269–299. MR 2983025, DOI 10.1090/S0025-5718-2012-02599-3
M. Burger, E. Resmerita, and L. He, Error estimation for Bregman iterations and inverse scale space methods in image restoration, Computing 81 (2007), no. 2-3, 109–135. MR 2354192, DOI 10.1007/s00607-007-0245-z
Jian-Feng Cai, Stanley Osher, and Zuowei Shen, Linearized Bregman iterations for compressed sensing, Math. Comp. 78 (2009), no. 267, 1515–1536. MR 2501061, DOI 10.1090/S0025-5718-08-02189-3
Jian-Feng Cai, Stanley Osher, and Zuowei Shen, Convergence of the linearized Bregman iteration for $\ell _1$-norm minimization, Math. Comp. 78 (2009), no. 268, 2127–2136. MR 2521281, DOI 10.1090/S0025-5718-09-02242-X
Jian-Feng Cai, Stanley Osher, and Zuowei Shen, Split Bregman methods and frame based image restoration, Multiscale Model. Simul. 8 (2009/10), no. 2, 337–369. MR 2581025, DOI 10.1137/090753504
Emmanuel J. Candes and Terence Tao, Decoding by linear programming, IEEE Trans. Inform. Theory 51 (2005), no. 12, 4203–4215. MR 2243152, DOI 10.1109/TIT.2005.858979
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, DOI 10.1109/TIT.2006.885507
David L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), no. 4, 1289–1306. MR 2241189, DOI 10.1109/TIT.2006.871582
David L. Donoho and Michael Elad, Optimally sparse representation in general (nonorthogonal) dictionaries via $l^1$ minimization, Proc. Natl. Acad. Sci. USA 100 (2003), no. 5, 2197–2202. MR 1963681, DOI 10.1073/pnas.0437847100
Ivar Ekeland and Roger Témam, Convex analysis and variational problems, Corrected reprint of the 1976 English edition, Classics in Applied Mathematics, vol. 28, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. Translated from the French. MR 1727362, DOI 10.1137/1.9781611971088
E. Esser, Primal dual algorithms for convex models and applications to image restoration, registration and nonlocal inpainting, Ph.D. thesis, UCLA CAM (10-31), June 2010.
Tom Goldstein and Stanley Osher, The split Bregman method for $L1$-regularized problems, SIAM J. Imaging Sci. 2 (2009), no. 2, 323–343. MR 2496060, DOI 10.1137/080725891
E. T. Hale, W. Yin, and Y. Zhang, A fixed-point continuation method for $\ell ^1$-regularized minimization with applications to compressed sensing, Rice CAM Report TR07-07, July 2007.
B. S. He and X. M. Yuan, On convergence rate of the Douglas-Rachford operator splitting method, Mathematical Programming, under revision.
—, On the $O(1/n)$ convergence rate of Douglas-Rachford alternating direction method, SIAM J. Numer. Anal. 50 (2012), 700-709.
Bo Huang, Shiqian Ma, and Donald Goldfarb, Accelerated linearized Bregman method, J. Sci. Comput. 54 (2013), no. 2-3, 428–453. MR 3011366, DOI 10.1007/s10915-012-9592-9
M.J. Lai and W. Yin, Augmented $\ell ^1$ and nuclear-norm models with a globally linearly convergent algorithm, Submitted, 2012.
Michael Möller, Todd Wittman, Andrea L. Bertozzi, and Martin Burger, A variational approach for sharpening high dimensional images, SIAM J. Imaging Sci. 5 (2012), no. 1, 150–178. MR 2902660, DOI 10.1137/100810356
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, DOI 10.1137/040605412
Stanley Osher, Yu Mao, Bin Dong, and Wotao Yin, Fast linearized Bregman iteration for compressive sensing and sparse denoising, Commun. Math. Sci. 8 (2010), no. 1, 93–111. MR 2655902
S. Setzer, Split Bregman algorithm, Douglas-Rachford splitting and frame shrinkage, Proceedings of the Second International Conference on Scale Space and Variational Methods in Computer Vision, SSVM ’09, Springer-Verlag, 2009, pp. 464–476.
Wotao Yin, Analysis and generalizations of the linearized Bregman model, SIAM J. Imaging Sci. 3 (2010), no. 4, 856–877. MR 2735964, DOI 10.1137/090760350
Wotao Yin, Stanley Osher, Donald Goldfarb, and Jerome Darbon, Bregman iterative algorithms for $l_1$-minimization with applications to compressed sensing, SIAM J. Imaging Sci. 1 (2008), no. 1, 143–168. MR 2475828, DOI 10.1137/070703983