Projections onto convex sets: Difference between revisions

Revision as of 12:35, 8 October 2012

Revision as of 12:44, 8 October 2012

Line 1:

'''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 set|convex]] sets. It is a very simple algorithm and has been rediscovered many times.<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> The simplest case, when the sets are [[affine spaces]], was analyzed by [[John von Neumann]].<ref>J. von Neumann, On rings of operators. Reduction theory, Ann. of Math. 50 (1949) 401–485 (a reprint of lecture notes first distributed in 1933).</ref> There are now extensions that consider cases when there are more than one set, or when the sets are not [[convex]]<ref>{{cite DOI| 10.1287/moor.1070.0291}}</ref>. 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]].

<ref>J. von Neumann. Functional Operators, volume II. Princeton University Press, Princeton, NJ, 1950. Reprint of mimeographed lecture notes first distributed in 1933.</ref> The case when the sets are affine spaces is special, since the iterates not only converge to a point in the intersection (assuming the intersection is non-empty) but in fact to the orthogonal projection onto the intersection of the initial iterate. For general closed convex sets, the limit point need not be the projection. Classical work on the case of two closed convex sets shows that the [[rate of convergence]] of the iterates is linear.

<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 Neu- mann’s alternating projection algorithm for two sets. Set-Valued Anal- ysis, 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]]<ref>{{cite DOI| 10.1287/moor.1070.0291}}</ref>. 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. 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]].

== Algorithm ==

Line 23 ⟶ 27:

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

== References ==

{{Reflist}}

== Further reading ==

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