Alternating Projection
Project. Switch. Repeat.
When direct projection is too hard, bounce your way in. Project. Switch. Repeat.
Alternating projection is a simple, yet effective strategy: to find a point in the intersection of two sets, project back and forth between them. Start with any point, project onto the first set, then project that result onto the second, and repeat. If the sets are closed, convex, convex and have nonempty intersection, this process converges to a point in their intersection.
Why not just project directly onto the intersection?
In many cases, that projection is hard or even impossible to compute in closed form. But, projections onto the individual sets might be simple, like projecting onto a half-space, a simplex, a box, or an ellipsoid. Alternating projection lets you solve a hard problem by solving a sequence of easier ones. It’s easy to implement, requires no gradients, and connects beautifully to geometry, fixed-point theory and optimization.
Below is a short YouTube overview.
⸻
👨🏼🏫 Questions and feedback are welcome in the comments.