Implementation for Projection

In no standard textbook, projection implementation is ever talked about, in this writing we will try to close this gap.

defintion: Projection

Projection: Given a space we define the projection on to as,

Depending on how easy the space are, we may be able to write down a close form. A standard example is the simplex,

Simplex:

.
Then projection onto this set can be computed in time by sorting.

hint: Use Lagrangian multiplier and write down all the optimality conditions.

Another example the PSD cone which has a closed form as follows

There could be more complicated space which we will discuss now.

Intersection of spaces.

Suppose you are given spaces for and we wish to compute
Here we will assume that each individual space has a easy to compute projection i.e. is easy to compute for all . Note that in general

So the most naive way of projecting to each space iteratively will not work. Even though this method will not work but applying it indefinitely time by cycling the projection the point will eventually converge to inside though it will not be the closest point. To fix this we need to add a correction term,

Dykstra Projection:

Initialize .
Repeat for

Where we will refer as the corrective term for the space . Then this algorithm will converge to the projection.

More complicated form

For more complicated form we may need to use newton’s method. For example let . Then we can cast the projection into an optimization problem which becomes,

Thus we can use newton’s method to solve this iteratively.