Alternating algorithm

An algorithm first proposed by J. von Neumann in 1933 [a6]. It gives a method for calculating the orthogonal projection $P _ { U \cap V }$ onto the intersection of two closed subspaces $U$ and $V$ in a Hilbert space $H$ in terms of the orthogonal projections $P : H \rightarrow U$ and $Q : H \rightarrow V$ (cf. also Orthogonal projector). The result is that

\begin{equation*} \operatorname { lim } _ { n \rightarrow \infty } ( P Q ) ^ { n } f = P _ { U \bigcap V }\, f \text { for all } f \in H . \end{equation*}

It can be equivalently formulated as

\begin{equation} \tag{a1} \operatorname { lim } _ { n \rightarrow \infty } ( ( 1 - Q ) ( I - P ) ) ^ { n } f = ( I - P _ { \overline{U + V} } ) f \end{equation}

for all $f \in H$. Here, $P _ {\overline{U+V}}$ is the orthogonal projection of $H$ onto the subspace $U + V$. Since it was first proposed, this algorithm has undergone many generalizations, mainly concerning the kind of spaces in which the algorithm can be located. It occurs in a large number of practical applications, such as domain decomposition methods for solving linear systems of equations, and certain multi-grid schemes used for solving elliptic partial differential equations. For a survey account of a wide collection of applications, see [a2].

The algorithm easily admits a generalization to a finite number of subspaces of $H$. Let $f$ be a member of the Hilbert space $H$, and let $U_i$, $i = 1 , \dots , n$, be closed subspaces of $H$. Let $U = \cap _ { i = 1 } ^ { n } U _ { i }$, and let $P$ be the orthogonal projection of $H$ onto $U$. Let $P _ { i } : H \rightarrow U _ { i }$ be the orthogonal projection onto $U_i$, $i = 1 , \dots , n$. Given $f \in H$, define $\{ f _ { \text{l} } \} _ { \text{l} = 1 } ^ { \infty }$ by $f _ { l } = ( P _ { n } \ldots P _ { 1 } ) ^ { \text{l} } f$, for $\operatorname{l} = 1,2 , \ldots$. The elements $f _ { \operatorname{l} }$ are the iterates in the alternating algorithm and the analogous convergence result is that $\| f _ { \text{l} } - P f \| \rightarrow 0$ as $1 \rightarrow \infty$. Quite a while later, other authors became interested in the rate of convergence of this algorithm. It was verified by N. Aronszain [a1] in the case of only two subspaces that the rate of convergence is usually linear. That is, there is a constant $c < 1$ such that $\| f _ { \operatorname{l} } - P _ { U \cap V } f \| \leq c ^ { 2 \operatorname{l} - 1 } \| f \|$ for all $f$ in $H$. The number $c$ depends on the notion of an angle between two subspaces of a Hilbert space. The angle $\alpha$ between $U$ and $V$ is given by

\begin{equation*} \operatorname { cos } \alpha = \operatorname { sup } \left\{ \begin{array} { r l } {} &{ u \in U \bigcap V ^ { \perp }, } \\ { \langle u , v \rangle : } & { v \in V \cap U ^ { \perp }, } \\{} & { \| u \| , \| v \| \leq 1 } \end{array} \right\}. \end{equation*}

In the present context, $c = \operatorname { cos } \alpha$. In [a7], K.T. Smith, D.C. Solman and S.L. Wagner gave the analogous result for more than two subspaces. The convergence constant $c$ remains a function of the angles between the subspaces, but is only a little more complicated than the case of two subspaces. Because of the importance of the rate of convergence, later authors have given improved rates. To get a very good expression for the rate of convergence, one needs to be very much more careful over the angles specified in the Smith–Solman–Wagner result. The best result know today (2000) is given in [a5].

The Lorch theorem states that the angle between two subspaces $U$ and $V$ of a Hilbert space $H$ is strictly positive if and only if $U + V$ is a closed subspace of $H$. So if the sum is not closed, the result of Aronszain does not provide linear convergence, and it is of interest to enquire what takes place in this situation. A result of C. Franchetti and W.A. Light [a4] shows that if $U + V$ is not closed, then the rate of convergence of the alternating algorithm may be arbitrarily slow.

Interesting questions arise when the algorithm is considered not as an algorithm in a Hilbert space, but in a Banach space with some fairly strong assumptions on the norm. The operators $P_ i$ and $P$ are then of course the operators of best approximation, so one needs at least to guarantee that such operators exist. For example, the ambient space $X$ can be a strictly convex and reflexive Banach space (cf. also Reflexive space; Smooth space). In fact, W.J. Stiles proved [a8] that if the dimension of such a space is at least $3$, the convergence of the algorithm for all $f$ in $X$ and for all pairs $U$ and $V$ of closed subspaces suffices to guarantee that $X$ is a Hilbert space.

Stiles also proved that in a finite-dimensional, smooth and strictly convex space, the alternating algorithm as given in (a1) is always effective. Several authors have given improvements to this results (see [a2]). The results of Franchetti and Light [a3] show that the convergence of the algorithm can still be linear in this case, with an appropriate modification to the definition of the angle between subspaces.

Finally, there are a number of interesting extensions where the projections are not uniquely defined. Instead, one may work in a space $X$ with subspaces $U$ and $V$ which do not guarantee unique best approximations. An example of this is the Diliberto–Straus algorithm, where $X = C ( S \times T )$, $U = C ( S )$ and $V = C ( T )$. In this algorithm, which is a realization of (a1), a selection must be employed to define the mappings $P$ and $Q$.

References

[a1]	N. Aronszajn, "Theory of reproducing kernels" Trans. Amer. Math. Soc. , 68 (1950) pp. 337–404
[a2]	F. Deutsch, "The method of alternating projections" S.P. Singh (ed.) , Approximation Theory, Spline Functions and Applications , Kluwer Acad. Publ. (1992) pp. 105–121
[a3]	C. Franchetti, W.A. Light, "The alternating algorithm in uniformly convex spaces" J. London Math. Soc. , 29 : 2 (1984) pp. 454–555
[a4]	C. Franchetti, W.A. Light, "On the von Neumann alternating algorithm in Hilbert Space" J. Math. Anal. Appl. , 114 (1986) pp. 305–314
[a5]	S. Kaylar, H.L. Weinert, "Error bounds for the method of alternating projections" Math. Control Signals Syst. , 1 (1988) pp. 43–59
[a6]	J. von Neumann, "Functional operators II. The geometry of orthogonal spaces" , Ann. of Math. Stud. , 22 , Princeton Univ. Press (1950)
[a7]	K.T. Smith, D.C. Solman, S.L. Wagner, "Practical and mathematical aspects of the problem of reconstructing objects from radiographs" Bull. Amer. Math. Soc. , 83 (1977) pp. 1227–1270
[a8]	W.J. Stiles, "Closest point maps and their products" Nieuw Archief voor Wiskunde , 13 : 3 (1965) pp. 19–29