Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC (2010): 49M29, 65K10, 90C25
  • Retrieve articles in all journals with MSC (2010): 49M29, 65K10, 90C25
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