11
$\begingroup$

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?

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

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @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|)$ $\endgroup$ – Dallas Card Jun 15 '16 at 22:29
  • $\begingroup$ 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} ) $$ $\endgroup$ – Royi Mar 20 at 16:51
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ explicit steps would help. $\endgroup$ – Alice Oct 18 '13 at 1:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.