The Proximal Operator of the $ {L}_{\infty} $ (Infinity Norm) What is the proximal operator of the $ \left\| x \right\|_{\infty} $ norm:
$$ \operatorname{Prox}_{\lambda \left\| \cdot \right\|_{\infty}} \left( v \right) = \arg \min_{x} \frac{1}{2} \left\| x - v \right\|_{2}^{2} + \lambda \left\| x \right\|_{\infty} $$
I know we have to take the subgradient and compute it but I am a bit stuck.
Can anyone show me steps?
 A: Let $f(x) = \|x\|_{\infty}$, so $f^*$ is the indicator function of $B$, where $B$ is the 1-norm unit ball.
The Moreau decomposition expresses the prox operator of $f$ in terms of the prox operator of $f^*$, which simply projects onto $B$.  So we need to know how to project onto $B$.
This is explained in ch. 8 ("the proximal mapping") of Vandenberghe's 236c notes.  See slide 8-15 here.
A: If you want to find the proximal operator of $\|x\|_{\infty}$, you don't want to compute the subgradient directly. Rather, as the previous answer mentioned, we can use Moreau decomposition:
$$ v = \textrm{prox}_{f}(v) + \textrm{prox}_{f^*}(v)$$
where $f^*$ is the convex conjugate, given by:
$$ f^*(x) = \underset{y}{\sup}\;(x^Ty - f(y))$$
In the case of norms, the convex conjugate is an indicator function based on the dual norm, i.e. if $f(x) = \|x\|_p$, for $p \geq 1$, then $f^*(x) = 1_{\{\|x\|_q \leq 1\}}(x)$, where $1/p + 1/q = 1$, and the indicator function is:
\begin{equation}
  1_S(x)=\begin{cases}
    0, & \text{if $x \in S$}.\\
    \infty, & \text{if $x \notin S$}.
  \end{cases}
\end{equation}
For your particular question, $f(x) = \|x\|_{\infty}$, so $f^*(x) = 1_{\{\|x\|_1\leq 1\}}(x)$.
We know
$$\textrm{prox}_{f}(x) = x - \textrm{prox}_{f^*}(x)$$
Thus we need to find
$$\textrm{prox}_{f^*}(x) = \underset{z}{\arg\min} \; \left(1_{\{\|z\|_1 \leq 1\}} + \|z - x\|_2^2 \right)$$
But this is simply projection onto the $L_1$ ball, thus the prox of the infinity norm is given by:
$$ \textrm{prox}_{\|\cdot\|_{\infty}}(x) = x - \textrm{Proj}_{\{\|\cdot\|_1 \leq 1\}}(x)$$
The best reference for this is Neal Parikh, Stephen Boyd - Proximal Algorithms.
