The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle

JOURNAL OF APPROXIMATION THEORY

卷:185

Article

Bauschke, Heinz H.¹  Cruz, J. Y. Bello²  Nghia, Tran T. A.¹  Phan, Hung M.¹  Wang, Xianfu¹ 

[1] Univ British Columbia, Kelowna, BC V1V 1V7, Canada

[2] Univ Fed Goias, IME, BR-74001970 Goiania, Go, Brazil

关键词: Douglas-Rachford splitting method;    Firmly nonexpansive;    Friedrichs angle;    Linear convergence;    Method of alternating projections;    Normal cone operator;    Subspaces;    Projection operator;   

DOI  :  10.1016/j.jat.2014.06.002

来源: Elsevier

【 摘 要 】

The Douglas-Rachford splitting algorithm is a classical optimization method that has found many applications. When specialized to two normal cone operators, it yields an algorithm for finding a point in the intersection of two convex sets. This method for solving feasibility problems has attracted a lot of attention due to its good performance even in nonconvex settings. In this paper, we consider the Douglas-Rachford algorithm for finding a point in the intersection of two subspaces. We prove that the method converges strongly to the projection of the starting point onto the intersection. Moreover, if the sum of the two subspaces is closed, then the convergence is linear with the rate being the cosine of the Friedrichs angle between the subspaces. Our results improve upon existing results in three ways: First, we identify the location of the limit and thus reveal the method as a best approximation algorithm; second, we quantify the rate of convergence, and third, we carry out our analysis in general (possibly infinite-dimensional) Hilbert space. We also provide various examples as well as a comparison with the classical method of alternating projections. (C) 2014 Elsevier Inc. All rights reserved.

【 授权许可】

Free