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?
Best Answer
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.