Questions concerning convergence rate of Iterated Projections

Question

Assume for simplicity $C_1,C_2,...,C_n\subset \mathbb{R}^m$ to be closed and convex subsets with $\underset{i=1}{\overset{n}{\bigcap{}}}C_i\neq\emptyset$.

Let $x^0\in\mathbb{R}^n$ and define the following iterative method: $$x^{k+1}=P_{C_{i_k}}(x^k)$$ Where $P_{C_{i_k}}$ is the projection onto the set $C_{i_k}$ and $i_k:\mathbb{N}\cup\{0\}\rightarrow\{1,...,n\}$ is the control sequence.

I would like to ask the following two questions:

Q1: The special case of $n=2$ is fairly well understood and an exact rate of convergence is known, see for example this paper. Is a similar result known for more than two subsets, perhaps with additional assumptions?

Q2: Some control sequences can be demonstrated numerically to be faster than others in terms of iterations, for example, the cyclic control: $$i_k=(k\mod n)+1$$ can be shown to be slower than the remotest set control: $$i_k=\underset{i\in\{1..n\}}{argmax}\:d(x^k,C_i)$$ Are there papers that capture this behavior theoretically?

Answer 1

A lot of things are known for the convergence of alternating projections for these convex feasibility problems. I suggest to start with

H.H. Bauschke and J.M. Borwein: On projection algorithms for solving convex feasibility problems, SIAM Review 38(3), 1996

which can be obtained via the website of Heinz Bauschke. It's almost 20 years old, but even then a lot was known.

You may also check the book

Parallel Optimization: Theory, Algorithms, and Applications,Oxford University Press, 1997, Yair Censor, ‎Stavros Andrea Zenios.

For some newer results: There is something known for non-convex sets, also with a convergence rate, see e.g.

``Local Linear Convergence of Approximate Projections onto Regularized Sets '', D. R. Luke, Nonlinear Analysis, 75(2012):1531--1546. DOI: 10.1016/j.na.2011.08.027.

There are truly randomized versions, see e.g.

T. Strohmer, R. Vershynin: A randomized Kaczmarz algorithm with exponential convergence, J. Fourier Anal. Appl. 15(1), 262–278, 2009

for the Kaczmarz-method (i.e. the sets $C_i$ are hyperplanes).

Regarding the "remotest set control" I don't know results about convergence speed. From a practical point of view, it seems to me that this rule is not that use useful since in many cases computing the distance $d(x_k,C_i)$ is as expensive as computing the projection $P_{C_i}(x_k)$. In these cases one step with remotest set control is as costly as a whole sweep over all sets and there is no advantage in speed anymore…

Answer 2

If by chance the $C_k$'s are manifolds, then the following refs are relevant:

• Bauschke et al., "Optimal rates of convergence of matrices with applications" http://arxiv.org/pdf/1407.0671v1.pdf
• Liang et al., "Activity Identification and Local Linear Convergence of Douglas-Rachford/ADMM under Partial Smoothness" http://arxiv.org/abs/1412.6858