The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle (Q2252928): Difference between revisions

The paper deals with a convex feasibility problem, namely to find a point in the intersection of two subspaces. The authors completely analyze the Douglas-Rachford splitting algorithm proposed in [\textit{J. Douglas jun.} and \textit{H. H. Rachford jun.}, Trans. Am. Math. Soc. 82, 421--439 (1956; Zbl 0070.35401)] and prove that the method converges strongly to the projection of the starting point onto the intersection. The paper complements a basic convergence result proposed in [\textit{R. Hesse} and \textit{D. R. Luke}, SIAM J. Optim. 23, No. 4, 2397--2419 (2013; Zbl 1288.65094)] in three ways. First, the authors identify the location of the shadow sequence limit and reveal the Douglas-Rachford method as a best approximation algorithm. Further, they quantify the sharp rate of linear convergence being the cosine of the Friedrichs angle between the subspaces. Finally, they carry out the analysis in a general (possibly infinite-dimensional) Hilbert space. The reader will find here various properties of the Friedrichs angle, the Douglas-Rachford splitting operator, and the reflector. The authors also present some geometric results concerning the lines in the plane (to illustrate the main results), construct an example to illustrate the case when the Friedrichs angle is zero (then one cannot expect linear convergence of the projected iterates of the Douglas-Rachford splitting operator (lack of convergence)), and compare their method to the method of alternating projections.