Content deleted Content added
Willywheel (talk | contribs) →References: on wheels Tag: categories removed |
Tags: Mobile edit Mobile web edit Advanced mobile edit |
||
| (29 intermediate revisions by 19 users not shown) | |||
Line 1:
{{confusing|date=April 2018}}
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
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
| last1=Lewis | first1=Adrian S.
| 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
▲
== Algorithm ==
[[File:Projections onto convex sets circles.svg
The POCS algorithm solves the following problem:
: <math> \text{find} \; x \in \
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>.▼
▲To use the POCS algorithm, one must know how to project onto the sets ''C'' and ''D'' separately.
The algorithm starts with an arbitrary value for <math>x_0</math> and then generates the sequence
Line 24 ⟶ 32:
== Related algorithms ==
[[File:Projections onto convex avg sets circles.svg
The method of '''averaged projections''' is quite similar. For the case of two closed convex sets ''C'' and ''D'', it proceeds by
Line 31 ⟶ 39:
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>
| | | | 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
Line 37 ⟶ 56:
: <math> E = \{ (x,y) : x \in C, \; y \in D \}</math>
which is defined in the [[Tensor product|product space]] <math> \
Then define another set, also in the product space:
: <math> F = \{ (x,y) : x \in \
Thus finding <math> C \cap D </math> is equivalent to finding <math> E \cap F</math>.
Line 49 ⟶ 68:
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>.
== References ==
{{reflist}}
== Further reading ==
* Book from 2011: [
[[Category:Convex geometry]]
| |||