Dykstra's alternating projection algorithm for two sets (Q1340505): Difference between revisions

The paper presents a detailed analysis of the Dykstra and von Neumann alternating projection algorithms for two closed convex subsets of a Hilbert space; it is readable and thorough, though it refers for further information to an associated Technical Report [CORR 92-15, Faculty of Mathematics, University of Waterloo (1992)]\ by the same authors and with the same title. The author's results for the Dykstra algorithm are summarised in Theorem 3.8: Let \(X\) be a Hilbert space, \(A\), \(B\) two closed convex subsets, and \(x\) a point in \(X\). Define the terms of the Dykstra sequences for every integer \(n\geq 1\) by \[ \begin{alignedat}{2} p_0 &:= q_0 :=0, &b_0 &:= x,\\ a_n &:= P_A (b_{n-1}+ p_{n-1}), \qquad &p_n &:= b_{n-1}+ p_{n-1} -a_n\\ b_n &:= P_B (a_n+ q_{n-1}), &q_n &:= a_n+ q_{n-1} -b_n \end{alignedat} \] [where \(P_A\) is the metric projection of \(X\) onto \(A\) etc.]. Then \[ b_n- a_n, b_n- a_{n+1}\to \nu, \] where \(\nu:= P_{\overline {B-A}} (0)\) and \(|\nu|= d(A, B)\) \([:= \inf\{ |a-b |\): \(a\in A\), \(b\in B\}]\). In particular, \(|b_n- a_n |, |b_n- a_{n+1} |\to d(A, B)\) and \(a_n/n, b_n/n\to 0\), \(p_n/ n\to\nu\), \(q_n/ n\to -\nu\). Furthermore, \[ \begin{aligned} &\text{if } d(A, B) \text{ is not attained then } |a_n |,|b_n|\to\infty;\\ &\text{if } d(A, B) \text{ is attained then }a_n\to P_E x,\;b_n\to P_F x, \end{aligned} \] where \(E:= \{a\in A\): \(d(a, B)= d(A, B)\}\), \(F= \{b\in B\): \(d(b, A)= d(A, B)\}\) are non-empty closed convex sets with \(E+ \nu= F\). The theorem contains earlier results of Boyle and Dykstra (the case \(A\cap B\neq \emptyset\)) and of Iusem and De Pierro \((\dim X< \infty\), \(d(A, B)\) attained). Section 4 discusses the von Neumann algorithm. In the case of two closed affine subsets the algorithms are equivalent and Theorem 3.8 applies. An analysis of the general case similar to that of the Dykstra algorithm yields a corresponding Theorem 4.8 for the von Neumann sequences, defined by \[ b_0: =x, \qquad a_{n+1}:= P_A b_n, \qquad b_{n+1}:= P_B a_{n+1}, \] for \(n\geq 0\), except that if \(d(A, B)\) is attained the conclusion is that the sequences \((a_n)\) and \((b_n)\) are weakly convergent to some \(e^*\in E\) and \(f^*= e^*+ \nu\in F\). Section 5 considers conditions which ensure that \(d(A, B)\) is attained and some examples. Section 6 considers closed convex subsets \(C_1, C_2, \dots, C_N\), \(N\geq 2\), of the Hilbert space \(X\), and uses an approach due to Pierra which allows Theorems 3.8 and 4.8 to be applied.