1
$\begingroup$

I'm trying to derive the proximal operator of the $L_2$ norm for myself. Here is my effort: let

$$g(x)=\gamma ||x||_2.$$

The prox-operator of $g$ at the point $x$ is defined as follows: $$\text{prox}_g(x)={\arg\,\min}_u \, g(u) + \frac{1}{2} \|u-x\|_2^2 .$$

In order to minimize it, we can take the derivatives of it :

$$0 \in \gamma \partial||u||_2 + u-x$$

then I can rewrite the above equation as follows: $u \in x- \gamma \partial |||u||_2$. From there, I do not know how to further simplify it. I was wondering whether can someone help me to understand it better ? I know that, people have simplified it and derived a closed formula solution for it, but I'm not sure how they did it.

$\endgroup$
2
$\begingroup$
  • Use the Moreau decomposition: $\forall \lambda > 0$, $$ \text{prox}_{\lambda g}(x) \equiv x - \lambda\text{prox}_{g^*/\lambda}(x/\lambda),$$

and note that

  • $g^*$ (the convex conjugate of $g$) is the indicator function of the $\ell_2$ unit-ball (because the $\ell_2$ norm is self-dual), i.e $$g^*(x) \equiv i_{\|x\|_2 \le \gamma} = \begin{cases}0, &\mbox{ if } \|x\|_2 \le \gamma,\\+\infty, &\mbox{ otherwise.}\end{cases}$$

  • Finally, note that if $C$ is a closed convex set, then $\text{prox}_{i_C}(x) \equiv \text{proj}_C(x)$.

Pull the pieces together and derive the answer to your question.

$\endgroup$
  • $\begingroup$ Could you please add more details such that it can be more helpful ? $\endgroup$ – user2806363 Mar 2 '17 at 22:20
  • $\begingroup$ Tell me exactly where you're stuck in the above roadmap, and I'll provide more input. $\endgroup$ – dohmatob Mar 3 '17 at 16:09
  • $\begingroup$ See also - math.stackexchange.com/questions/2264263. $\endgroup$ – Royi Aug 24 '17 at 7:06
0
$\begingroup$

In summary:

$$ \operatorname{Prox}_{\lambda \left\| \cdot \right\|_{2}} \left( v \right) = v - \operatorname{Proj}_{ \mathcal{B}_{ \left\| \cdot \right\|_{2} } } \left( \frac{v}{\lambda} \right) = \begin{cases} v - \lambda \frac{ \frac{v}{\lambda} }{ \left\| \frac{v}{\lambda} \right\|_{2} } & \text{ if } \left\| \frac{v}{\lambda} \right\|_{2} > 1 \\ v - \lambda \frac{v}{\lambda} & \text{ if } \left\| \frac{v}{\lambda} \right\|_{2} \leq 1 \end{cases} = \left(1 - \frac{\lambda}{ \left\| v \right\|_{2} } \right)_{+} v $$

Where $ \left( x \right)_{+} = \max \left\{ 0, x \right\} $.

See Proximal operator of the Euclidean norm.

$\endgroup$

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.