Random products of projections: bounds on convergence rate? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T16:58:14Z http://mathoverflow.net/feeds/question/37161 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/37161/random-products-of-projections-bounds-on-convergence-rate Random products of projections: bounds on convergence rate? Martin Schwarz 2010-08-30T14:05:57Z 2012-09-11T13:54:07Z <p>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]. </p> <p>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.</p> <p>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.</p> <p>[vN] J. von Neumann, Functional operators, Annals of Mathematics Studies No. 22, Princeton University Press (1950)</p> <p>[H] I. Halperin, The product of projection operators, Acta. Sci. Math. (Szeged) 23 (1962), 96-99.</p> <p>[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).</p> <p>[AA] I. Amemiya and T. Ando, Convergence of random products of contractions in Hilbert space, Acta. Sci. Math. (Szeged) 26 (1965), 239-244.</p> http://mathoverflow.net/questions/37161/random-products-of-projections-bounds-on-convergence-rate/38995#38995 Answer by S. Sra for Random products of projections: bounds on convergence rate? S. Sra 2010-09-16T16:58:48Z 2010-09-16T16:58:48Z <p>This is not an answer, merely a comment, but somehow MO does not allow me to leave comments.</p> <p>Does the following paper help: <a href="http://www-personal.umich.edu/~romanv/papers/linear-system-solver-journal.pdf" rel="nofollow">http://www-personal.umich.edu/~romanv/papers/linear-system-solver-journal.pdf</a></p> <p>That paper analyzes rate of convergence of <em>randomized</em> 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$)</p> http://mathoverflow.net/questions/37161/random-products-of-projections-bounds-on-convergence-rate/39189#39189 Answer by Tracy Hall for Random products of projections: bounds on convergence rate? Tracy Hall 2010-09-18T02:01:53Z 2010-09-18T02:01:53Z <p>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$.</p> <p>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$. </p> http://mathoverflow.net/questions/37161/random-products-of-projections-bounds-on-convergence-rate/106913#106913 Answer by zouzias for Random products of projections: bounds on convergence rate? zouzias 2012-09-11T13:54:07Z 2012-09-11T13:54:07Z <p>Following Suvrit's post, you can also take a look at <a href="http://arxiv.org/abs/1205.5770" rel="nofollow">http://arxiv.org/abs/1205.5770</a> (Algorithm 3). It handles the case where the set of projectors have co-dimension one.</p> <p>By the way, thanks for the links Martin.</p>