Eventual linear convergence of the Douglas-Rachford iteration for basis pursuit
HTML articles powered by AMS MathViewer
- by Laurent Demanet and Xiangxiong Zhang PDF
- Math. Comp. 85 (2016), 209-238 Request permission
Abstract:
We provide a simple analysis of the Douglas-Rachford splitting algorithm in the context of $\ell ^1$ minimization with linear constraints, and quantify the asymptotic linear convergence rate in terms of principal angles between relevant vector spaces. In the compressed sensing setting, we show how to bound this rate in terms of the restricted isometry constant. More general iterative schemes obtained by $\ell ^2$-regularization and over-relaxation including the dual split Bregman method are also treated, which answers the question of how to choose the relaxation and soft-thresholding parameters to accelerate the asymptotic convergence rate. We make no attempt at characterizing the transient regime preceding the onset of linear convergence.References
- F. J. Aragón Artacho and J. M. Borwein, Global convergence of a non-convex Douglas-Rachford iteration, Journal of Global Optimization, pages 1–17, 2012.
- Heinz H. Bauschke, Patrick L. Combettes, and D. Russell Luke, Phase retrieval, error reduction algorithm, and Fienup variants: a view from convex optimization, J. Opt. Soc. Amer. A 19 (2002), no. 7, 1334–1345. MR 1914365, DOI 10.1364/JOSAA.19.001334
- Ȧke Björck and Gene H. Golub, Numerical methods for computing angles between linear subspaces, Math. Comp. 27 (1973), 579–594. MR 348991, DOI 10.1090/S0025-5718-1973-0348991-3
- Emmanuel Candès, Laurent Demanet, David Donoho, and Lexing Ying, Fast discrete curvelet transforms, Multiscale Model. Simul. 5 (2006), no. 3, 861–899. MR 2257238, DOI 10.1137/05064182X
- 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
- Antonin Chambolle and Thomas Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision 40 (2011), no. 1, 120–145. MR 2782122, DOI 10.1007/s10851-010-0251-1
- Scott Shaobing Chen, David L. Donoho, and Michael A. Saunders, Atomic decomposition by basis pursuit, SIAM J. Sci. Comput. 20 (1998), no. 1, 33–61. MR 1639094, DOI 10.1137/S1064827596304010
- Patrick L. Combettes, Solving monotone inclusions via compositions of nonexpansive averaged operators, Optimization 53 (2004), no. 5-6, 475–504. MR 2115266, DOI 10.1080/02331930412331327157
- Patrick L. Combettes, Iterative construction of the resolvent of a sum of maximal monotone operators, J. Convex Anal. 16 (2009), no. 3-4, 727–748. MR 2583892
- Jonathan Eckstein and Dimitri P. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Programming 55 (1992), no. 3, Ser. A, 293–318. MR 1168183, DOI 10.1007/BF01581204
- E. Esser, Applications of Lagrangian based alternating direction methods and connections to split Bregman, CAM Report 09-31, UCLA, 2009.
- Jean-Jacques Fuchs, On sparse representations in arbitrary redundant bases, IEEE Trans. Inform. Theory 50 (2004), no. 6, 1341–1344. MR 2094894, DOI 10.1109/TIT.2004.828141
- D. Gabay, Applications of the method of multipliers to variational inequalities, Augmented Lagrangian Methods: Applications to the Solution of Boundary-Value Problems, edited by M. Fortin and R. Glowinski, 1983.
- D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl. 2 (1976), no. 1, 17–40.
- R. Glowinski and A. Marrocco, 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 non linéaires, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge Anal. Numér. 9 (1975), no. R-2, 41–76 (French, with English summary). MR 388811
- 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
- Elaine T. Hale, Wotao Yin, and Yin Zhang, Fixed-point continuation for $l_1$-minimization: methodology and convergence, SIAM J. Optim. 19 (2008), no. 3, 1107–1130. MR 2460734, DOI 10.1137/070698920
- D. Han and X. Yuan, Convergence analysis of the peaceman-rachford splitting method for nonsmooth convex optimization, 2012.
- Bingsheng He and Xiaoming Yuan, On the $O(1/n)$ convergence rate of the Douglas-Rachford alternating direction method, SIAM J. Numer. Anal. 50 (2012), no. 2, 700–709. MR 2914282, DOI 10.1137/110836936
- F. J. Herrmann and G. Hennenfent, Non-parametric seismic data recovery with curvelet frames, Geophysical Journal International 173 (2008), no. 1, 233–248.
- Robert Hesse and D. Russell Luke, Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems, SIAM J. Optim. 23 (2013), no. 4, 2397–2419. MR 3134441, DOI 10.1137/120902653
- Ming-Jun Lai and Wotao Yin, Augmented $\ell _1$ and nuclear-norm models with a globally linearly convergent algorithm, SIAM J. Imaging Sci. 6 (2013), no. 2, 1059–1091. MR 3062582, DOI 10.1137/120863290
- A. S. Lewis, Active sets, nonsmoothness, and sensitivity, SIAM J. Optim. 13 (2002), no. 3, 702–725 (2003). MR 1972212, DOI 10.1137/S1052623401387623
- P.-L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal. 16 (1979), no. 6, 964–979. MR 551319, DOI 10.1137/0716071
- S. Setzer, Split Bregman algorithm, Douglas-Rachford splitting and frame shrinkage, In Proceedings of the Second International Conference on Scale Space and Variational Methods in Computer Vision, SSVM ’09, (2009), 464–476, Springer-Verlag, Berlin, Heidelberg.
- Yi Yang, Michael Möller, and Stanley Osher, A dual split Bregman method for fast $\ell ^1$ minimization, Math. Comp. 82 (2013), no. 284, 2061–2085. MR 3073192, DOI 10.1090/S0025-5718-2013-02700-7
- 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 and Stanley Osher, Error forgetting of Bregman iteration, J. Sci. Comput. 54 (2013), no. 2-3, 684–695. MR 3011377, DOI 10.1007/s10915-012-9616-5
- H. Zhang, W. Yin, and L. Cheng, Necessary and sufficient conditions of solution uniqueness in $\ell 1$ minimization, Technical report, Rice University CAAM, 2012.
Additional Information
- Laurent Demanet
- Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
- Email: laurent@math.mit.edu
- Xiangxiong Zhang
- Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
- Address at time of publication: Department of Mathematics, Purdue University, 150 N. University Street, West Lafayette, Indiana 47907
- Email: zhan1966@purdue.edu
- Received by editor(s): January 24, 2013
- Received by editor(s) in revised form: April 27, 2013, June 11, 2013, and May 5, 2014
- Published electronically: May 15, 2015
- © Copyright 2015 American Mathematical Society
- Journal: Math. Comp. 85 (2016), 209-238
- MSC (2010): Primary 49M29, 65K10, 90C25
- DOI: https://doi.org/10.1090/mcom/2965
- MathSciNet review: 3404448