Projection of vector onto convex set We consider set $S = \{x \in \mathbb{R}^d : \lvert\lvert x\rvert\rvert_{1} \leq 1\}$. For any point $y$, how do we compute the projection of $y$ onto set $S$?
My intuition is just to scale down every element of $y = (y_1, y_2, \dots, y_d)$ by some factor such that $\sum_{i=1}^d |y_i| = 1$. Does this make sense? How do we prove this rigorously?
 A: do you know the "projection theorem"? 
It states that for a nonempty closed and convex subset $C$ of $\mathbb{R}$ there exists a unique vector that minimizes the distance between a point $z \in \mathbb{R}$ over $C$, the unique minimizer is called the projection of $z$ in $C$. 
So basically, you have to solve the minimization problem $$ \min_{x \in C} ||z-x||^2_2.$$
For this you can use for example Lagrange Multiplier. 
For example for $d = 2$ we have the following Lagrange function:
$$ L(x,\lambda) = (z_1 - x_1)^2 + (z_2 - x_2)^2 - \lambda \left( |x_1| + |x_2| - 1 \right) $$
Looking at the derivatives we get
$$ \frac{\partial L}{\partial x_i} = -2(z_i - x_i) - \lambda \frac{x_i}{|x_i|} \overset{!}{=} 0$$
and
$$ \frac{\partial L}{\partial \lambda} = - |x_1| - |x_2| +1  \overset{!}{=} 0$$
Basically, you will get a candidate for the minimizer but also a candidate for a maximizer (the point at the opposite side). But you can easily verify which one is the minimizer and maximizer by inserting the value into the expression $||z-x||^2_2$ and for that I would also refer to this post: Lagrange Min or Max
So what is with the special case if coordinate $i$ of $z$ is equal to zero?
This will lead to the fact, that
$$\frac{\partial L}{\partial x_i} = 2x_i - \lambda \frac{x_i}{|x_i|} = 0$$ This leads to $x_i = 0$. Than we can insert this condition into the last one and get a condition about the length of the other coordinates and than you can insert them into the other equations. But you still have to consider that $x_j$ can be positive or negative. 
Since we are only looking for critical points, we have to check also the points where we do not have differentiability: Link
Another way is to use the subgradient, like here. This document suggests also another way to solve the problem. 
