Projections onto convex sets: Difference between revisions

Revision as of 14:20, 12 April 2014

Revision as of 09:27, 12 June 2015

Line 1:

In mathematics, '''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 set|closed]] [[convex set|convex]] sets. It is a very simple algorithm and has been rediscovered many times.<ref name="SIAMreview"/> 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(2) (1949) 401–485 (a reprint of lecture notes first distributed in 1933) http://dx.doi.org/10.2307/1969463.</ref>

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

Line 6:

== Algorithm ==

[[File:Projections onto convex sets circles.svg|350px|thumb|right350px|Example on two circles.]]

The POCS algorithm solves the following problem:

Line 24:

== Related algorithms ==

[[File:Projections onto convex avg sets circles.svg|350px|thumb|right350px|Example of '''averaged projections''' variant.]]

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

Line 57:

<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. http://dx.doi.org/10.1137/S0036144593251710</ref>

<references/references>

<references/>

[[Category:Convex geometry]]