16
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Helge
    Sep 12, 2010 at 17:52
  • $\begingroup$ Yes, this is indeed the form of the bound I would need. $\endgroup$ Sep 13, 2010 at 12:14

3 Answers 3

6
$\begingroup$

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

$\endgroup$
0
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ The link is broke. It is better to write out the title and authors of the paper as well as the link so that in the case that the latter is broke, the reader can still search for the paper by the former. $\endgroup$
    – Hans
    Jan 26, 2020 at 6:26
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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