Projections onto convex sets

Key takeaways

Projections onto convex sets belongs to mathematics; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Projections onto convex sets to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Projections onto convex sets from memory before moving on to harder problems.

Reference excerpt

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 convex sets. It is a very simple algorithm and has been rediscovered many times. The simplest case, when the sets are affine spaces, was analyzed by John von Neumann. 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 to the orthogonal projection of the point onto the intersection. 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. There are now extensions that consider cases when there are more than two sets, or when the sets are not convex, 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 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 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.

Algorithm

The POCS algorithm solves the following problem:

find x ∈ R n such that x ∈ C ∩ D {\displaystyle {\text{find}}\;x\in \mathbb {R} ^{n}\quad {\text{such that}}\;x\in C\cap D}

where C and D are closed convex sets. To use the POCS algorithm, one must know how to project onto the sets C and D separately, via the projections P i {\displaystyle {\mathcal {P}}_{i}} . The algorithm starts with an arbitrary value for x 0 {\displaystyle x_{0}} and then generates the sequence

x k + 1 = P C ( P D ( x k ) ) . {\displaystyle x_{k+1}={\mathcal {P}}_{C}\left({\mathcal {P}}_{D}(x_{k})\right).}

The simplicity of the algorithm explains some of its popularity. If the intersection of C and D is non-empty, then the sequence generated by the algorithm will converge to some point in this intersection. Unlike Dykstra's projection algorithm, the solution need not be a projection onto the intersection C and D.

Related algorithms

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

x k + 1 = 1 2 ( P C ( x k ) + P D ( x k ) ) {\displaystyle x_{k+1}={\frac {1}{2}}({\mathcal {P}}_{C}(x_{k})+{\mathcal {P}}_{D}(x_{k}))}

It has long been known to converge globally. Furthermore, the method is easy to generalize to more than two sets; some convergence results for this case are in. The averaged projections method can be reformulated as alternating projections method using a standard trick. Consider the set

E = { ( x , y ) : x ∈ C , y ∈ D } {\displaystyle E=\{(x,y):x\in C,\;y\in D\}}

which is defined in the product space R n × R n {\displaystyle \mathbb {R} ^{n}\times \mathbb {R} ^{n}} . Then define another set, also in the product space:

F = { ( x , y ) : x ∈ R n , y ∈ R n , x = y } . {\displaystyle F=\{(x,y):x\in \mathbb {R} ^{n},\,y\in \mathbb {R} ^{n},\;x=y\}.}

Thus finding C ∩ D {\displaystyle C\cap D} is equivalent to finding E ∩ F {\displaystyle E\cap F} . To find a point in E ∩ F {\displaystyle E\cap F} , use the alternating projection method. The projection of a vector ( x , y ) {\displaystyle (x,y)} onto the set F is given by ( x + y , x + y ) / 2 {\displaystyle (x+y,x+y)/2} . Hence

… excerpt ends here. Continue reading the full article.

Illustrations

Worked examples

Example 1 — a first encounter with Projections onto convex sets

Start with the simplest possible case. Write down what Projections onto convex sets claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Projections onto convex sets before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Projections onto convex sets ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Projections onto convex sets

In research: Projections onto convex sets appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Projections onto convex sets in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Projections onto convex sets is common in secondary-school and first-year university syllabi. It links to neighbouring topics Convex geometry, so understanding it makes those chapters shorter.
In everyday life: Look for Projections onto convex sets outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Projections onto convex sets in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Projections onto convex sets means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Projections onto convex sets out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Projections onto convex sets in simple terms?

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 convex sets. It is a very simple algorithm and has been rediscovered many times.

Why does Projections onto convex sets matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Projections onto convex sets?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Projections onto convex sets.