Projections onto convex sets: Difference between revisions

Revision as of 16:50, 4 November 2012

Latest revision as of 12:00, 29 December 2023

(38 intermediate revisions by 24 users not shown)

Line 1:

{{confusing|date=April 2018}}

'''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 (1949) 401–485 (a reprint of lecture notes first distributed in 1933).</ref>

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>{{cite journal | last1 = Bauschke | first1 = H.H. | last2 = Borwein | first2 = J.M. | year = 1996 | title = On projection algorithms for solving convex feasibility problems | doi = 10.1137/S0036144593251710 | journal = SIAM Review | volume = 38 | issue = 3| pages = 367–426 | citeseerx = 10.1.1.49.4940 }}</ref> The simplest case, when the sets are [[affine spaces]], was analyzed by [[John von Neumann]].<ref>J. von Neumann,{{cite journal | year = 1949 | title = On rings of operators. Reduction theory | doi = 10.2307/1969463 | journal = Ann. of Math. | volume = 50 | issue = 2| pages = 401–485 | jstor = 1969463 | last1 = Neumann | first1 = John Von }} (a reprint of lecture notes first distributed in 1933)</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 ontoof the intersectionpoint ofonto the initial iterateintersection. 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>{{cite journal | last1 = Gubin | first1 = L.G. | last2 = Polyak | first2 = B.T. | last3 = Raik | first3 = E.V. | year = 1967 | title = The method of projections for finding the common point of convex sets | journal = U.S.S.R. Computational Mathematics and Mathematical Physics | volume = 7 | issue = 6| pages = 1–24 | doi=10.1016/0041-5553(67)90113-9}}</ref><ref>{{cite journal | last1 = Bauschke | first1 = H.H. | last2 = Borwein | first2 = J.M. | year = 1993 | title = On the convergence of von Neumann's alternating projection algorithm for two sets | journal = Set-Valued Analysis | volume = 1 | issue = 2| pages = 185–212 | doi=10.1007/bf01027691| s2cid = 121602545 }}</ref>

There are now extensions that consider cases when there are more than two sets, or when the sets are not [[convex set|convex]],<ref>{{Cite journal

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

| last1=Lewis | first1=Adrian S.

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

| last2=Malick | first2=Jérôme

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>

| doi=10.1287/moor.1070.0291

| title=Alternating Projections on Manifolds

| journal=[[Mathematics of Operations Research]]

| volume=33

| pages=216–234

| date=2008

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| citeseerx=10.1287/moor1.10701.0291416.6182 }}</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_Projection (linear_algebralinear algebra)#Orthogonal_projectionsOrthogonal 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_readingFurther 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">{{cite journal | last1 = Combettes | first1 = P. L. Combettes,| year = 1993 | title = "The foundations of set theoretic estimation," | url = http://www.ann.jussieu.fr/~plc/proc.pdf | journal = Proceedings of the IEEE, vol.| volume = 81, no.| issue = 2, pp| pages = 182–208 | doi = 10.1109/5.214546 182| access-208,date February= 1993.2012-10-09 [| archive-url = https://web.archive.org/web/20150614002927/http://www.ann.jussieu.fr/~plc/proc.pdf PDF]| archive-date = 2015-06-14 | url-status = dead }}</ref>

== Algorithm ==

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

The POCS algorithm solves the following problem:

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

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

To use the POCS algorithm, one must know how to project onto the sets ''C'' and ''D'' separately, via the projections <math>\mathcal{P}_i</math>.

The algorithm starts with an arbitrary value for <math>x_0</math> and then generate the sequence

The algorithm starts with an arbitrary value for <math>x_0</math> and then generategenerates the sequence

<math>x_{k+1} = \mathcal{P}_C \left( \mathcal{P}_D ( x_k ) \right) </math>.

: <math>x_{k+1} = \mathcal{P}_C \left( \mathcal{P}_D ( x_k ) \right). </math>.

The simplicity of the algorithm explains some of its popularity. If the [[Intersection (set theory)|intersection]] of ''C'' and ''D'' is non-empty, then the [[sequence]] generated by the algorithm will [[Convergent series|converge]] to some point in this intersection.

Line 22 ⟶ 32:

== Related algorithms ==

[[File:Projections onto convex avg sets circles.svg|thumb|350px|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

: <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{{cite convergencejournal
| forlast1=Lewis alternating| andfirst1=A. averagedS.
| nonconvexlast2=Luke | projectionsfirst2=D. A Lewis, R.
| Luke, J last3=Malick, 2007.| [http://arxivfirst3=J.org/abs/0709.0109 arXiv]</ref>

| title=Local convergence for alternating and averaged nonconvex projections

| journal=Foundations of Computational Mathematics

| volume=9

| issue=4

| pages=485–513

| date=2009

| arxiv=0709.0109

| doi=10.1007/s10208-008-9036-y}}</ref>

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

: <math> E = \{ (x,y) : x \in C, \; y \in D \}</math>

which is defined in the [[Tensor product|product space]] <math> \mathcal{R}^n \times \mathcal{R}^n </math>.

Then define another set, also in the product space:

<math>which Fis =defined \{in (x,y)the :[[Tensor xproduct|product \inspace]] <math> \mathcalmathbb{R}^b,\, yn \intimes \mathcalmathbb{R}^n,\; x=y \}.</math>.

Then define another set, also in the product space:

: <math> F = \{ (x,y) : x \in \mathbb{R}^n,\, y \in \mathbb{R}^n,\; x=y \}.</math>

Thus finding <math> C \cap D </math> is equivalent to finding <math> E \cap F</math>.

Line 41 ⟶ 65:

To find a point in <math> E \cap F</math>, use the alternating projection method. The projection of a vector <math>(x,y)</math> onto the set ''F'' is given by <math>(x+y,x+y)/2</math>. Hence

: <math>(x_{k+1},y_{k+1}) = \mathcal{P}_{F}( \mathcal{P}_{E}( (x_{k},y_{k}) ) ) = \mathcal{P}_{F}( (\mathcal{P}_{C}x_{k},\mathcal{P}_{D}y_{k}) ) = \frac{1}{2}( \mathcal{P}_C(x_k) + \mathcal{P}_D(y_k) , (\mathcal{P}_C(x_k) + \mathcal{P}_D(y_k) ). </math>

Since <math> x_{k+1} = y_{k+1} </math> and assuming <math> x_0 = y_0 </math>, then <math>x_j=y_j</math> for all <math> j \ge 0</math>, and hence we can simplify the iteration to <math> x_{k+1} = \frac{1}{2}( \mathcal{P}_C(x_k) + \mathcal{P}_D(x_k) ) </math>.

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

{{reflist}}

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

== Further reading ==

* Book from 2011: [httphttps://wwwdl.ec-securehostacm.comorg/SIAM/FA08citation.htmlcfm?id=2077655 Alternating Projection Methods] by René Escalante and Marcos Raydan (2011), published by SIAM.

[[Category:Convex geometry]]