Projections onto convex sets: Difference between revisions

Revision as of 06:40, 28 May 2017

Revision as of 21:40, 8 September 2017

Line 5:

<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 | url = | journal = U.S.S.R. Computational Mathematics and Mathematical Physics | volume = 7 | issue = | 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 | url = | journal = Set-Valued Analysis | volume = 1 | issue = | pages = 185–212 | doi=10.1007/bf01027691}}</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 journal | last1 = Lewis | first1 = A. S. | last2 = Malick | first2 = J. | doi = 10.1287/moor.1070.0291 | title = Alternating Projections on Manifolds | journal = Mathematics of Operations Research | volume = 33 | pages = 216–234 | year = 2008 | pmid = | pmc = }}</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_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. | year = 1993 | title = The foundations of set theoretic estimation | url = http://www.ann.jussieu.fr/~plc/proc.pdf | format = PDF | journal = Proceedings of the IEEE | volume = 81 | issue = 2| pages = 182–208 | doi=10.1109/5.214546}}</ref>

== Algorithm ==

Line 51:

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

<references>

Line 61 ⟶ 56:

</references>

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

[[Category:Convex geometry]]