Iterated Projection Methods
An introduction to the algorithms behind these visualizers: what problem they solve, the two simple operations they're built from, and how Alternating Projections, Averaged Projections, Douglas–Rachford and Peaceman–Rachford differ. Every diagram on this page is live. Click or drag to move the starting point.
Finding a point in an intersection
Many problems come down to finding a point that satisfies several constraints at once. If each constraint is described by a set A, B, …, we want a point in their intersection:
The intersection itself is usually hard to describe. Each individual set, though, is often easy to work with: for any point we can quickly compute the nearest point in that set. Iterated projection methods take advantage of this. They never deal with A ∩ B directly. They just keep projecting onto one set at a time and combine the results until they settle on a common point.
The same idea turns up in many places:
- Image reconstruction (CT scans). Each X-ray measurement defines a hyperplane. Kaczmarz's method, which projects onto those hyperplanes one by one, is alternating projections.
- Phase retrieval. Recovering an image from the magnitude of its Fourier transform. One set says “matches the measurements”, the other says “zero outside the object”. Fienup's hybrid input–output algorithm is closely related to Douglas–Rachford.
- Puzzles and combinatorics. Sudoku, n-queens, and graph colouring can be written as intersections of (nonconvex) constraint sets.
- Optimization. ADMM, a workhorse of large-scale optimization, is Douglas–Rachford applied to a dual problem.
Projections and reflections
Projection PC(x)
The point of C closest to x. If x is already in C, it stays put.
Reflection RC(x)
Go to the projection, then keep going the same distance again. Points in C are also fixed by reflection.
Convex vs. nonconvex sets
A set is convex if the straight segment between any two of its points stays inside it, like the disk, the square and the line above. For convex sets the projection is always unique and moves smoothly as x moves, and projections never push two points further apart. That property (being nonexpansive) is what most convergence proofs rest on.
The circle (just the boundary) and the two-point set are nonconvex. Try moving the point across the dashed grey line, or onto the centre of the circle: the projection jumps or stops being unique. That's why nonconvex problems are much harder to analyze. It's also where the methods differ most in practice.
How to read the demos
Each method below gets its own demo. Set A is always the blue horizontal line. Set B is red and changes with the Scenario menu. Use the Iteration slider (or Play) to step through, and the dashed arrows show the projections and reflections that make up the most recent step.
Alternating Projections
AP von Neumann 1933 · Bregman 1965The most natural idea: project onto A, then onto B, and repeat. Each step can only bring the iterate closer to both sets, so for convex sets with a common point it always converges to a point of A ∩ B.
The default scenario shows its main weakness: when two sets meet at a shallow angle, the iterates zig-zag between them in ever-smaller steps. Switch to Line & point set to see the other weakness. With nonconvex sets, AP often gets stuck at a point that isn't a solution.
Advantages
- Very simple: no parameters, easy to implement and explain.
- Guaranteed to converge for closed convex sets with a common point. The rate is linear when the sets cross “transversally”.
- The distance to the other set never increases, so progress is monotone and easy to monitor.
- Every iterate lies in B. If the sets don't intersect, AP still settles on a best-approximation pair (closest points of A and B) under mild conditions.
Disadvantages
- Can be extremely slow when the sets meet at a small angle. For two lines at angle θ the error shrinks only by cos²θ per step.
- For nonconvex sets it often stagnates at a point that isn't in the intersection.
- Finds some point of the intersection, not necessarily the one closest to z0 (Dykstra's variant does that).
- Inherently sequential: the projections can't run in parallel.
Averaged Projections
Avg Cimmino 1938 · simultaneous projectionsInstead of taking turns, project onto every set at the same time from the current point and move to the average. It's equivalent to a gradient-descent step on ½(dist(x,A)² + dist(x,B)²), the average squared distance to the sets. It's also exactly alternating projections carried out in a larger “product space” (Pierra's trick).
Try the Disjoint scenario. When there's no common point, averaged projections still converge, to the point that best compromises between the sets in the least-squares sense.
Advantages
- Embarrassingly parallel: all projections are independent, which suits many sets and distributed hardware.
- Handles any number of sets in the same way, and weights let some constraints count more than others.
- Converges for convex sets. If they don't intersect, it converges to a meaningful least-squares compromise.
- Has a clean optimization interpretation (gradient descent), which makes it easy to analyze and accelerate.
Disadvantages
- Usually slower than AP, since it only moves half-way toward each set. On two lines the per-step factor is (1+cosθ)/2.
- Iterates generally lie in none of the sets until the limit.
- Like AP, it can stall at non-solutions for nonconvex sets.
Douglas–Rachford
DR Douglas & Rachford 1956 · Lions & Mercier 1979Reflect through A, reflect through B, then average with where you started. Reflections overshoot, and the averaging calms that down. The result is an iteration that explores rather than greedily descending. In the substeps you can see the move from zn is parallel to the arrow from PAzn to PBRAzn.
The default scenario is the same nonconvex point set that traps AP: B is four points, and only one of them lies on the line. From most starting points DR still finds it. In the Disjoint scenario, notice that zn runs off to infinity while the shadow settles down.
Advantages
- Converges for any closed convex sets with a common point. The shadow PA(zn) lands in A ∩ B.
- Remarkably effective on nonconvex problems (phase retrieval, Sudoku, matrix completion), where it often succeeds when AP stagnates. There are proofs for some cases, such as a line and a circle.
- For inconsistent convex problems, the shadow still approaches a best-approximation point even though zn diverges.
- Same cost as AP (two projections per step) and no parameters. It generalizes to splitting methods for optimization (ADMM).
Disadvantages
- The iterates aren't the answer. You have to track the shadow sequence, which is less intuitive.
- Progress is non-monotone: iterates spiral, and the error can go up before it goes down. On simple convex problems it can be slower than AP (rate cosθ vs cos²θ on two lines).
- In nonconvex settings it can cycle or wander, and the theory is still incomplete.
- Defined for two sets. More sets need a product-space reformulation or cyclic variants.
Peaceman–Rachford
PR Peaceman & Rachford 1955Douglas–Rachford without the averaging: just reflect, reflect, repeat. Each reflection is nonexpansive, so the composition can't blow up, but nothing forces it to settle down either. On two lines, RBRA is a pure rotation by twice the angle between them, so PR orbits the solution forever.
Use the λ slider to move between the methods. Any λ < 1 adds some damping and the orbit becomes a converging spiral. λ = ½ is exactly DR, and values above ½ are “over-relaxed” DR, which sometimes converges faster.
Advantages
- Takes full steps with no damping. In favourable geometries it converges in fewer iterations than DR.
- For optimization problems where one function is strongly convex, convergence is guaranteed and often fast.
- Same per-step cost as DR. The relaxed family gives a single dial between speed (λ→1) and stability (λ→½).
Disadvantages
- No convergence guarantee, even for two convex sets that intersect. It can orbit or cycle indefinitely.
- Sensitive to geometry and starting point, and erratic on nonconvex problems.
- In practice it's mostly used through its relaxed (λ < 1) versions rather than in pure form.
Racing the methods
All four methods on the same problem from the same start. The chart below plots the feasibility gap of each method's current estimate, dist(x,A) + dist(x,B), on a log scale. A line that drops steadily means linear convergence. A line that flattens out above zero means the method is stuck or the sets are disjoint.
Convergence speed on two lines
For two lines meeting at angle θ every rate can be worked out exactly. Each number is the factor the error is multiplied by per iteration (closer to 0 is faster). Drag the angle to see how all of them degrade as the lines get closer to parallel.
At a glance
| AP | Averaged | DR | PR | |
|---|---|---|---|---|
| Update | PBPAz | ½(PA+PB)z | ½(I + RBRA)z | RBRAz |
| Solution estimate | zn | zn | PA(zn) | PA(zn) |
| Convex, intersecting | Converges | Converges | Converges (shadow) | Not guaranteed |
| Typical speed | Good, but slow at shallow angles | Slower than AP | Comparable; non-monotone | Fast when it works |
| Disjoint sets | Best-approximation pair | Least-squares point | zn diverges; shadow converges | No guarantee |
| Nonconvex | Often stagnates | Often stagnates | Often succeeds; may cycle | Erratic |
| Many sets / parallel | Cyclic, sequential | Natural, fully parallel | Product space or cyclic variants | Product space |
| Parameters | None | Weights (optional) | None (λ if relaxed) | None |
Related variants worth knowing
Dykstra's algorithm
Alternating projections with correction terms. It converges to the point of A ∩ B nearest to z0, not just any point.
Relaxed / over-relaxed AP
Move past each projection by a factor between 1 and 2. This often fixes AP's zig-zagging at shallow angles.
RAAR
Luke's relaxed averaged alternating reflections blend DR with AP via a parameter. It was designed for phase retrieval, where it's more robust when there is no exact solution.
Cyclic DR & product space
Two ways to extend DR to many sets: cycle DR steps over consecutive pairs (as in the Multi-Set visualizer), or stack copies of the point into one big two-set problem.