Optimal Rates of Linear Convergence of Relaxed Alternating Projections and Generalized Douglas-Rachford Methods for Two Subspaces

详细信息    查看全文

• 作者：Heinz H. Bauschke ; J. Y. Bello Cruz ; Tran T. A. Nghia ; Hung M. Pha…
• 刊名：Numerical Algorithms
• 出版年：2016
• 出版时间：September 2016
• 年：2016
• 卷：73
• 期：1
• 页码：33-76
• 全文大小：929 KB
• 刊物类别：Computer Science
• 刊物主题：Numeric Computing
  Algorithms
  Mathematics
  Algebra
  Theory of Computation
  
• 出版者：Springer U.S.
• ISSN：1572-9265
• 卷排序：73

文摘

We systematically study the optimal linear convergence rates for several relaxed alternating projection methods and the generalized Douglas-Rachford splitting methods for finding the projection on the intersection of two subspaces. Our analysis is based on a study on the linear convergence rates of the powers of matrices. We show that the optimal linear convergence rate of powers of matrices is attained if and only if all subdominant eigenvalues of the matrix are semisimple. For the convenience of computation, a nonlinear approach to the partially relaxed alternating projection method with at least the same optimal convergence rate is also provided. Numerical experiments validate our convergence analysisKeywordsConvergent and semi-convergent matrixFriedrichs angleGeneralized Douglas-Rachford methodLinear convergencePrincipal angleRelaxed alternating projection method