Projections onto convex sets

Projections onto Convex Sets (POCS), sometimes known as the alternating projection method, is a method to find a point in the intersection of two closed convex sets. It is a very simple algorithm and has been rediscovered many times. The simplest case, when the sets are affine spaces, was analyzed by John von Neumann. There are now extensions that consider cases when there are more than one set, or when the sets are not convex. Analysis of POCS and related methods attempt to show that the algorithm converges (and if so, find the rate of convergence), and whether it converges to the projection of the original point. There are also variants of the algorithm, such as Dykstra's projection algorithm.

Algorithm

The POCS algorithm solves the following problem:

${\text{find}}\;x\in {\mathcal {R}}^{n}\quad {\text{such that}}\;x\in C\cap D$

where C and D are closed convex sets.

To use the POCS algorithm, one must know how to project onto the sets C and D separately. The algorithm starts with an arbitrary value for $x_{0}$ and then generate the sequence

$x_{k+1}={\mathcal {P}}_{C}\left({\mathcal {P}}_{D}(x_{k})\right)$.

If the intersection of C and D is non-empty, then the sequence generated by the algorithm will converge to some point in this intersection.

Unlike Dykstra's projection algorithm, the solution need not be a projection onto the intersection C and D.

Related algorithms

The method of averaged projections is quite similar. For the case of two closed convex sets C and D, it proceeds by

$x_{k+1}={\frac {1}{2}}({\mathcal {P}}_{C}(x_{k})+{\mathcal {P}}_{D}(x_{k}))$

It has long been known to converge globally.. Furthermore, the method is easy to generalize to more than two sets; some convergence results for this case are in .