Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
add comment

3 Answers 3

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|improve this answer
    
Thanks! This seems to work! –  Martin Schwarz Sep 18 '10 at 14:13
add comment

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

Does the following paper help: http://www-personal.umich.edu/~romanv/papers/linear-system-solver-journal.pdf

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|improve this answer
    
Thanks for the link! This is already quite useful! –  Martin Schwarz Sep 16 '10 at 18:27
add comment

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

By the way, thanks for the links Martin.

share|improve this answer
add comment

Your Answer

 
discard

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.