Projections onto convex sets: Difference between revisions

Revision as of 13:02, 9 October 2012

Revision as of 06:52, 15 October 2012

Line 3:

<ref>L.G. Gubin, B.T. Polyak, and E.V. Raik. The method of projections for finding the common point of convex sets. U.S.S.R. Computational Mathematics and Mathematical Physics, 7:1–24, 1967.</ref>

<ref>H.H. Bauschke and J.M. Borwein. On the convergence of von Neumann's alternating projection algorithm for two sets. Set-Valued Analysis, 1:185–212, 1993.</ref>

There are now extensions that consider cases when there are more than one set, or when the sets are not [[convex set|convex]],<ref>{{cite DOI| 10.1287/moor.1070.0291}}</ref>, or that give faster convergence rates. 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_(linear_algebra)#Orthogonal_projections|projection]] of the original point. These questions are largely known for simple cases, but a topic of active research for the extensions. There are also variants of the algorithm, such as [[Dykstra's projection algorithm]]. See the references in the [[#Further_reading|further reading]] section for an overview of the variants, extensions and applications of the POCS method; a good historical background can be found in section III of .<ref name="PLC">P. L. Combettes, "The foundations of set theoretic estimation," Proceedings of the IEEE, vol. 81, no. 2, pp. 182-208, February 1993. [http://www.ann.jussieu.fr/~plc/proc.pdf PDF]</ref>.

== Algorithm ==

Line 10:

<math> \text{find} \; x \in \mathcal{R}^n \quad\text{such that}\; x \in C \cap D </math>

where ''C'' and ''D'' are [[closed set|closed]] [[convex set|convex sets]]s.

To use the POCS algorithm, one must know how to project onto the sets ''C'' and ''D'' separately.

Line 26:

<math> x_{k+1} = \frac{1}{2}( \mathcal{P}_C(x_k) + \mathcal{P}_D(x_k) ) </math>

It has long been known to converge globally.<ref> A. Auslender. Methodes Numeriques pour la Resolution des Problems

d’Optimisation avec Constraintes. PhD thesis, Faculte des Sciences, Grenoble, 1969</ref> Furthermore, the method is easy to generalize to more than two sets; some convergence results for this case are in .<ref>Local convergence for alternating and averaged nonconvex projections. A Lewis, R Luke, J Malick, 2007. [http://arxiv.org/abs/0709.0109 arXiv]</ref>.

The ''averaged'' projections method can be reformulated as ''alternating'' projections method using a standard trick. Consider the set

Line 47:

== Further reading ==

* Book from 2011: [http://www.ec-securehost.com/SIAM/FA08.html Alternating Projection Methods] by René Escalante and Marcos Raydan (2011), published by SIAM.

* The review article from 1996: <ref name="SIAMreview"/>

== References ==

<references>

<ref name="SIAMreview"> H.H. Bauschke and J.M. Borwein. On projection algorithms for solving convex feasibility problems. SIAM Review, 38(3):367–426, 1996.</ref>

<references/>

{{Uncategorized|date={{subst:CURRENTMONTHNAME}} {{subst:CURRENTYEAR}}}}