Eventual linear convergence of the Douglas-Rachford iteration for basis pursuit

Demanet, Laurent; Zhang, Xiangxiong

doi:10.1090/mcom/2965

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.