Random products of projections: bounds on convergence rate? - MathOverflow

Random products of projections: bounds on convergence rate?

2010-08-30T14:05:57Z

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.

Answer by S. Sra for Random products of projections: bounds on convergence rate?

2010-09-16T16:58:48Z

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$)

Answer by Tracy Hall for Random products of projections: bounds on convergence rate?

2010-09-18T02:01:53Z

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$.

Answer by zouzias for Random products of projections: bounds on convergence rate?

2012-09-11T13:54:07Z

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.