The Proximal Operator of the $ {L}_{\infty} $ (Infinity Norm)

Solution 1:

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.

Solution 2:

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.