MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The von Neumann-Halperin [vN,H] theorem shows that iterating a fixed product of projection operators converges to the projector onto the intersection subspace of the individual projectors. A good bound on the rate of convergence using the concept of the Friedrichs number has recently been shown [BGM].

A generalization of this result due to Amemiya and Ando [AA] to the product of random sequences of projection operators drawn from a fixed set also shows convergence to the projector onto the intersection subspace.

My question is: are there any known bounds on the convergence rate for the latter problem analogous to the earlier one? In my application I'm only interested in the case of finite-dimensional Hilbert spaces.

[vN] J. von Neumann, Functional operators, Annals of Mathematics Studies No. 22, Princeton University Press (1950)

[H] I. Halperin, The product of projection operators, Acta. Sci. Math. (Szeged) 23 (1962), 96-99.

[BGM] C. Badea, S. Grivaux, and V. M¨uller. A generalization of the Friedrichs angle and the method of alternating projections. Comptes Rendus Mathematique, 348(1–2):53–56, (2010).

[AA] I. Amemiya and T. Ando, Convergence of random products of contractions in Hilbert space, Acta. Sci. Math. (Szeged) 26 (1965), 239-244.

share|cite|improve this question
Is the statement you desire that: dist(Product of n projections, Projection on Intersection) < exp(- c n) with probability 1 - exp(- c n) for some c > 0. Or would something weaker be enough? – Helge Sep 12 '10 at 17:52
Yes, this is indeed the form of the bound I would need. – Martin Schwarz Sep 13 '10 at 12:14
up vote 5 down vote accepted

If you only care about the bound having the correct form, and don't mind obtaining constants that are much worse than the actual asymptotic convergence, then all you have to do is apply [BGM] to a subsequence. Specifically, let $k$ be the number of projections from which you sample, and let $p_0, p_1, \ldots, p_{k-1}, p_k = p_0$ be a particular circular ordering of them. Given a random sequence $X_i$ of projections, consider the initial segment $S(n)$ of $n$ projections, and define $L(n)$ such that $L(n) \ge 1$ if and only if $(p_0, p_1)$ occurs consecutively in $S(n)$, such that $L(n) \ge 2$ if and only if the consecutive pair $(p_1,p_2)$ occurs somewhere after $(p_0, p_1)$ in $S(n)$, such that $L(n) \ge 3$ if and only if that is somewhere followed by $(p_2, p_3)$, and so forth. For large values of $n$, the random variable $L(n)$ is tightly concentrated around a value close to $n/k^2$, and the convergence of, say, the segment $S(2k^2n)$ will, with high probability, be at least as good as the fixed cyclic ordering of length $n$.

The one technical lemma to prove is that you cannot lose by replacing each $p_i$ in the fixed sequence by a product of projections that both starts and ends with $p_i$.

share|cite|improve this answer
Thanks! This seems to work! – Martin Schwarz Sep 18 '10 at 14:13

This is not an answer, merely a comment, but somehow MO does not allow me to leave comments.

Does the following paper help:

That paper analyzes rate of convergence of randomized Kaczmarz's method for solving the linear system $Ax=b$ for an $m \times n$ matrix $A$ with $m \ge n$ (the method proceeds by iteratively projecting the current iterate onto a randomly chosen hyperplane $a_i^Tx=b_i$)

share|cite|improve this answer
Thanks for the link! This is already quite useful! – Martin Schwarz Sep 16 '10 at 18:27

Following Suvrit's post, you can also take a look at (Algorithm 3). It handles the case where the set of projectors have co-dimension one.

By the way, thanks for the links Martin.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.