# 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?

• You need the Prox for the Proximal Gradient Method. Not for the Sub Gradient Method. – Royi Aug 24 '17 at 5:35

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.

• @Drazick: Projection onto the $\mathcal{l}_{\infty}$ ball is not really relevant to the original question, but you can easily verify that it can be solved element-wise: $z_i = \textrm{sign}(x_i) \times \min(1, |x_i|)$ – Dallas Card Jun 15 '16 at 22:29
• I would add that the $\lambda$ form of the Proximal Operator is given by: $$\operatorname{prox}_{ \lambda {\left\| \cdot \right\|}_{\infty}} \left( x \right) = x - \lambda \operatorname{Proj}_{ \left\{ \left\| \cdot \right\|_1 \leq 1 \right\} }( \frac{x}{\lambda} )$$ – Royi Mar 20 at 16:51

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.

• explicit steps would help. – Alice Oct 18 '13 at 1:00