Characterizing arbitrarily slow convergence in the method of alternating projections

Introduction

For the notation and basic Hilbert space results necessary to read this paper, the book is a good source, especially chapter 9.

Let $H$ be a (real or complex) Hilbert space with inner product $\langle x,y\rangle$ and norm $\|x\|=\sqrt{\langle x,x\rangle}$. If $M$ is any closed (linear) subspace of $H$, let $P_{M}$ denote the orthogonal projection onto $M$. That is, $P_{M}:H\to M$ is defined by

Let $M_{1}$ and $M_{2}$ be closed subspaces in $H$ and $M:=M_{1}\cap M_{2}$. It is well-known that $P_{M_{1}}P_{M_{2}}=P_{M}$ if and only if $P_{M_{1}}$ and $P_{M_{2}}$ commute: $P_{M_{1}}P_{M_{2}}=P_{M_{2}}P_{M_{1}}$. Von Neumann established the following result which yields an interesting analogue in the non-commuting case.

(von Neumann ) For each $x\in H$, there holds

The method of constructing the sequence $(P_{M_{2}}P_{M_{1}})^{n}(x)$ by alternately projecting onto one subspace and then the other is called the method of alternating projections. While Von Neumann’s theorem shows that the sequence of iterates $(P_{M_{2}}P_{M_{1}})^{n}(x)$, always converges to $P_{M}(x)$ for every $x$, it does not say anything about the speed or rate of convergence. To say something about this, we will use the notion of angle between subpaces. Recall that the (Friedrichs) angle between the subspaces $M_{1}$ and $M_{2}$ is defined to be the angle in $[0,\pi/2]$ whose cosine is given by

where $B_{H}:=\{x\in H\mid\|x\|\leq 1\}$ is the unit ball in $H$. It is easy to see that $0\leq c(M_{1},M_{2})\leq 1$.

(Aronszajn ) For each $x\in H$ and $n\geq 1$, we have

Kayalar and Weinert showed that the constant in Aronszajn’s theorem is smallest possible independent of $x$. More precisely, they proved that

The usefulness of the bound in (1.2) depends on knowing when the cosine of the angle between $M_{1}$ and $M_{2}$ is less than one, i.e., when the angle is positive. A useful characterization of when this happens is the following.

$c(M_{1},M_{2})<1$ if and only if $M_{1}+M_{2}$ is closed.

This lemma is a consequence of results of Deutsch and Simonic, whose result appeared in [2, Lemma 4.10] (see also [6, Theorem 9.35, p. 222]).

Recall that a sequence $(x_{n})$ is said to converge to $x$ linearly provided there exists an $\alpha<1$ and a constant $c$ such that

In this case, we say that the rate of convergence is $\alpha$.

Using Lemma 1.3 and Theorem 1.2, we see that there is linear convergence for the method of alternating projections whenever the sum of the subspaces is closed. What can be said when the sum is not closed?

Franchetti and Light gave the first example of a Hilbert space and two closed subspaces whose sum was not closed such that: given any sequence of reals decreasing to zero, there exists a point in the space with the property that the convergence in the von Neumann theorem was at least as slow as this sequence of reals. But this still left open the question of whether such a construction could be made in any Hilbert space whenever $M_{1}$ and $M_{2}$ were any closed subspaces whose sum was not closed.

In their study of the method of alternating projections, Bauschke, Borwein, and Lewis stated the following dichotomy. (Actually, they stated their result as a trichotomy since they were considering the more general setting of closed affine sets, i.e., translates of subspaces, rather than subspaces. In this situation, unlike the subspace case, one must also consider the possibility that the intersection of the affine sets is empty. However, when the intersection is nonempty, the affine sets case easily reduces to the subspace case by a simple translation.) Roughly speaking, it states that in the method of alternating projections, either there is linear convergence for each starting point, or there exists a point which converges arbitrarily slowly.

(dichotomy) Let $M_{1}$ and $M_{2}$ be closed subspaces in a Hilbert space $H$ and $M=M_{1}\cap M_{2}$. Then exactly one of the following alternatives holds.

$M_{1}+M_{2}$ is closed. Then for each $x\in H$, the sequence $(P_{M_{2}}P_{M_{1}})^{n}(x)$ converges linearly to $P_{M}(x)$ with a rate $[c(M_{1},M_{2})]^{2}$.

$M_{1}+M_{2}$ is not closed. Then for each $x\in H$, the sequence $(P_{M_{2}}P_{M_{1}})^{n}(x)$ converges to $P_{M}(x)$. But convergence is “arbitrarily slow” in the following sense: for each sequence $(\lambda_{n})$ of positive real numbers with $1>\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}\to 0$, there exists a point $x_{\lambda}\in H$ such that

Remark Clearly, the first statement of Theorem 1.4 is an immediate consequence of Theorem 1.2 and Lemma 1.3. Thus we need only verify the second statement. We will do this in Section 3 below.

Multiplicative form of the spectral theorem

The main fact that we will use in the proof of Theorem 1.4 is the multiplicative form of the spectral theorem (see Halmos or Reed-Simon [14, Corollary on p. 227]). Recall that a bounded linear operator $U:H_{1}\to H_{2}$ between Hilbert spaces $H_{1}$ and $H_{2}$ is called unitary if $U$ is invertible and $U^{*}=U^{-1}$. It follows that a unitary operator is isometric: $\|Ux\|=\|x\|$ for each $x\in H$. Since the inverse of a unitary operator is unitary, it too is isometric. (We will use these facts in a few places below without explicit mention.)

(Spectral Theorem; multiplicative form) Let $H$ be a (real or complex) Hilbert space, and let $T$ be a self-adjoint bounded linear operator on $H$. Then there exists a finite measure space $(\Omega,\mu)$, a bounded real-valued function $F$ on $\Omega$, and a unitary map $U:H\to L_{2}(\Omega,\mu)$ such that

Defining $D:L_{2}(\Omega,\mu)\to L_{2}(\Omega,\mu)$ to be the operator “multiplication by $F$”, $(Df)(t):=F(t)f(t)$, this can be expressed in operator notation as

Actually, in both and , the theorem is stated for a complex Hilbert space only, and even assumes separability. However, it is easy to check that each of the tools used in the proof in , for example, has a corresponding real space analogue.

Acknowledgements We are greatly indebted to Joel Anderson, Nigel Higson, and Barry Simon for personally transmitting some very useful comments to us related to the multiplicative form of the spectral theorem.

A self-adjoint operator $T$ on $H$ is called positive if $\langle Tx,x\rangle\geq 0$ for each $x\in H$. A simple, but important, example of a positive operator is the orthogonal projection $P_{S}$ onto any closed subspace $S\subset H$ (see, e.g., [6, p. 79]).

Assume the hypothesis of Theorem 2.1. If $T$ is also positive, then the bounded real-valued function $F$ of Theorem 2.1 is also nonnegative a.e.$(\mu)$.

Proof. Let $f\in L_{2}(\Omega,\mu)$ be arbitrary and $y=U^{-1}f$. Since $T$ is positive, we have that

Briefly, $\int_{\Omega}F|f|^{2}d\mu\geq 0$ for each $f\in L_{2}(\Omega,\mu)$. We readily deduce that $F\geq 0$ a.e.($\mu$). $\blacksquare$

Proof of Theorem 1.4

In this section we will prove the second statement of Theorem 1.4. Our proof is along the same general lines as in in that we proceed by a series of small steps that are each easily digested. However, there are subtle errors in steps 2 and 3 of (see Section 4 for the details). We will avoid these errors by using Theorem 2.1 and following a somewhat different path.

Proof of the second statement in Theorem 1.4. Suppose $M_{1}+M_{2}$ is not closed, and let $(\lambda_{n})$ be a sequence with $1>\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}>0$, and $\lambda_{n}\to 0$. By Lemma 1.3, $c(M_{1},M_{2})=1$. Let

Note that $A$ and $B$ are closed subspaces with $A\cap B=\{0\}$. Clearly,

and hence, by Lemma 1.3 again, $A+B$ is not closed. Since $c(A,B)=\|P_{B}P_{A}\|$ by (see also [6, Lemma 9.5(7), p. 197]), it follows that $\|P_{B}P_{A}\|=1$.

The operator $T:=P_{A}P_{B}P_{A}$ is a bounded self-adjoint linear operator on $H$ which is positive and $\|T\|=1$. Hence there exists a finite measure space $(\Omega,\mu)$, a nonnegative bounded function $F$ on $\Omega$, and a unitary operator $U:H\to L_{2}:=L_{2}(\Omega,\mu)$ such that

where $D:L_{2}\to L_{2}$ is defined by $Df:=Ff$ for each $f\in L_{2}$.

Proof of Lemma 3.1. By Corollary 2.2, it suffices to verify the first statement of the lemma. Clearly, $T$ is self-adjoint and bounded. Moreover, using [9, Corollary 5.17], $\|T\|=\|P_{A}P_{B}P_{A}\|=\|P_{B}P_{A}\|^{2}=1$. Fix any $x\in H$ and set $y=P_{A}x$. Since $P_{B}$ is positive, we have that

This shows that $T$ is positive on $H$ and completes the proof of Lemma 3.1.

Next let $(t_{n})$ be the strictly increasing sequence of integers with

Note that since $(t_{n})$ is a subsequence of $(n)$, it follows that

It is clear that $k_{0}(n)\to\infty$, $k_{1}(n)\to\infty$, and

To see this, note that by definition, $\lambda_{k_{0}(n)}t_{n}=\lambda_{k_{0}(n)}s_{k_{0}(n)}<1$, and $1\leq\lambda_{k_{0}(n)}(s_{k_{0}(n)}+1)$. But the latter inequality implies that $1-\lambda_{k_{0}(n)}\leq\lambda_{k_{0}(n)}s_{k_{0}(n)}=\lambda_{k_{0}(n)}t_{n}$. Also, $\lambda_{k_{0}(n)}t_{n}<1$ implies that $\alpha_{n}<1$. Since $\lambda_{k_{0}(n)}\to 0$, relation (3.9) implies that $\lambda_{k_{0}(n)}t_{n}\to 1$. This, along with $k_{1}(n)\to\infty$, shows that $\alpha_{n}\to 1$, which completes the proof of Claim 2.

We note that the first two claims follow exactly as in the proof given in . However, at this point our approach will deviate significantly from that of .

To see this, let $S:=F^{-1}[1,\infty)$ and $y=U^{-1}(\chi_{S})$, where $\chi_{S}$ denotes the characteristic function of $S$: $\chi_{S}(t)=1$ if $t\in S$ and $0$ otherwise. We must show that $\mu(S)=0$. Since

it suffices to show that $y=0$. Using (3.11), we have

This shows that $\|Ty\|\geq\|y\|$. But since $T=P_{A}P_{B}P_{A}$ is the product of norm one operators, $\|Ty\|\leq\|y\|$. Thus $\|Ty\|=\|y\|$. We deduce that

Thus we must have equality holding throughout the string of inequalities (3.13). It follows (see, e.g., [6, Theorem 5.8(2), p. 76]) that $y\in A\cap B=\{0\}$ and hence $y=0$. This proves Claim 3.

Claim 4. For each $\varepsilon>0$, $\mu\{F^{-1}((1-\varepsilon,1))\}>0$.

If not, there exists $\varepsilon>0$ such that $\mu\{F^{-1}((1-\varepsilon,1))\}=0$. Choose any $y\in H$ and set $g=Uy$. Then, using Claim 3, we have that

Briefly, $\|Ty\|\leq(1-\varepsilon)\|y\|$ for each $y\in H$. It follows that $\|T\|\leq 1-\varepsilon$, which (by Lemma 3.1) contradicts $\|T\|=1$. This proves Claim 4.

Claim 5. For each $\varepsilon>0$, there exists $\varepsilon_{1}\in(0,\varepsilon)$ such that

To verify this, we use Claim 4 and the countable additivity of $\mu$ to obtain

Thus there exists an integer $i$ such that $\mu\left\{F^{-1}\left((1-\frac{\varepsilon}{i},1-\frac{\varepsilon}{i+1}]\right)\right\}>0$. Let $\varepsilon_{1}=\frac{\varepsilon}{i+2}$. Then $\varepsilon_{1}\in(0,\varepsilon)$ and

We prove Claim 6 by induction. For $n=1$, take $\beta_{1}=\alpha_{1}^{2}$. Then $\beta_{1}<1$. Assume next that $\beta_{1},\dots,\beta_{m}$ have been chosen so that $\beta_{1}<\beta_{2}<\cdots<\beta_{m}<1$, $\beta_{k}\geq\alpha_{k}^{2}$ for $k=1,2,\dots,m$, and $\mu\{F^{-1}\left([\beta_{k},\beta_{k+1})\right)>0$ for $k=1,2,\dots,m-1$. Let $\varepsilon:=\min\{1-\alpha^{2}_{m+1},1-\beta_{m}\}$. Then $\varepsilon>0$ and Claim 5 implies the existence of $\varepsilon_{1}\in(0,\varepsilon)$ such that $\mu\{F^{-1}\left((1-\varepsilon,1-\varepsilon_{1})\right)\}>0$. Let $\beta_{m+1}:=1-\varepsilon_{1}$. Then $\beta_{m+1}>1-\varepsilon\geq\beta_{m}$. Also, $\beta_{m+1}>1-\varepsilon\geq\alpha^{2}_{m+1}$. Finally, $\mu\{F^{-1}\left([\beta_{m},\beta_{m+1})\right)\}\geq\mu\{F^{-1}\left([1-\varepsilon,1-\varepsilon_{1})\right)\}>0$. This completes the induction step and hence the proof.

It is convenient to list next a few basic and easily verified facts concerning powers of $T$ and $D$.

$D^{k}f=F^{k}f$ for all $f\in L_{2}(\Omega,\mu)$.

The last inequality follows from Claim 6. Next observe that

Also, by the definition of $S_{n}$ (in Definition 3.2), it is clear that

Taking square roots completes the proof of Claim 10.

Now we can define the element which will converge slower than the sequence $(\lambda_{n})$.

Since $\sum_{1}^{\infty}1/t^{2}_{n}\leq\sum_{1}^{\infty}1/n^{2}<\infty$ and $\|e_{n}\|=1$, it follows that $x_{\lambda}$ is a well-defined element of $H$.

Thus $\|T^{k}x_{\lambda}\|\geq{\alpha_{n}^{2k}}/{t_{n}}$ as claimed.

Using the facts that $M=M_{1}\cap M_{2}$, $P_{M^{\perp}}=I-P_{M}$, and $P_{M^{\perp}}$ is idempotent and commutes with both $P_{M_{1}}$ and $P_{M_{2}}$ (see, e.g., [6, p. 194]), we get that $P_{M_{i}}P_{M^{\perp}}=P_{M_{i}\cap M^{\perp}}$ for $i=1,2$ and

Combining Claims 12 and 13, we immediately obtain

This completes the proof of the second statement of Theorem 1.4.

Two errors in [4]

In this section, we point out two errors in . We shall use the notation of . (Note that this is the same as the notation of the present paper except that here we have used $M_{1},M_{2}$ instead of $C_{1},C_{2}$.)

First error. The proof of the Claim in Step 2 of the proof of Theorem 5.7.16 in has a mistake. The Claim itself is correct, only the proof of this claim is incorrect.

Specifically, we inductively construct $(e_{n}^{\prime})$ and $(f_{n}^{\prime})$ in $A$ and $B$, respectively. Let $E$ and $F$ be the finite-dimensional spaces as in the proof. Let $(a_{n})$ in $A$ and $(b_{n})$ in $B$ as in the proof:

and $a_{n}\to 0$ weakly and $b_{n}\to 0$ weakly. Because $E+F$ is finite-dimensional, the sum $A^{\bot}+(E+F)$ is closed. Hence $\{A^{\bot},E+F\}$ is regular (by [3, Proposition 5.16]) and so is $\{A^{\bot\bot},(E+F)^{\bot}\}=\{A,E^{\bot}\cap F^{\bot}\}$ (again by [3, Proposition 5.16]). This means the following by definition of regularity.

Observation. If $(z_{n})$ is a bounded sequence with $\max\big\{d(z_{n},A),d(z_{n},E^{\bot}\cap F^{\bot})\big\}\to 0$, then $d(z_{n},A\cap E^{\bot}\cap F^{\bot})\to 0$. (And analogously when $A$ is replaced by $B$.)

Now back to the proof of the Claim. This time, $P_{E+F}$ is a compact operator. (In , $P_{E}$ and $P_{F}$ were considered, which is not sufficient.) Since $a_{n}\to 0$ weakly and $b_{n}\to 0$ weakly, we deduce that

Since $(E+F)^{\bot}=E^{\bot}\cap F^{\bot}$, this implies

The above Observation now implies $d(a_{n},A\cap E^{\bot}\cap F^{\bot})\to 0$ and $d(b_{n},B\cap E^{\bot}\cap F^{\bot})\to 0$; equivalently,

Thus, for all $n$ sufficiently large, we have $\|P_{A\cap E^{\bot}\cap F^{\bot}}a_{n}\|\leq 1$, $\|P_{B\cap E^{\bot}\cap F^{\bot}}b_{n}\|\leq 1$, $P_{A\cap E^{\bot}\cap F^{\bot}}a_{n}\in A\cap E^{\bot}\cap F^{\bot}$, $P_{B\cap E^{\bot}\cap F^{\bot}}b_{n}\in B\cap E^{\bot}\cap F^{\bot}$, and $\langle P_{A\cap E^{\bot}\cap F^{\bot}}a_{n},P_{B\cap E^{\bot}\cap F^{\bot}}b_{n}\rangle$ is as close to $1$ (from below) as we like. Then for $n$ sufficiently large, we can take $e_{m+1}^{\prime}=P_{A\cap E^{\perp}\cap F^{\perp}}a_{n}$ and $f_{m+1}^{\prime}=P_{B\cap E^{\perp}\cap F^{\perp}}b_{n}$.

Second error. The second error is on the third line on page 32 of , where it is claimed that

is true. This invalidates the rest of the proof in .

(Sketch: the spanning vectors are orthogonal. Normalize and use Fourier expansions. Equate coefficients, compare odd and even ones. Deduce that they are all equal; thus they must be equal to $0$.) Hence $A=C_{1}$ and $B=C_{2}$. Set

where $\rho_{n}:=(1+\tfrac{1}{4n^{2}})^{-1/2}$. Since $\langle{e_{n}^{\prime}},{f_{n}^{\prime}}\rangle=(1+\tfrac{1}{4n^{2}})^{-1}$, the sequences $(e_{n}^{\prime})$ and $(f_{n}^{\prime})$ are as in the Claim of Step 2, and the sequences $(e_{n})$ and $(f_{n})$ are as in Step 3. Set

This would imply that $x$ belongs entirely to $A\cap E^{\bot}\cap F^{\bot}$. While it is true that $x\in A\cap E^{\bot}$, it is not true that $x$ belongs to $E^{\bot}\cap F^{\bot}$. This can be verified using relation (4.12).

References