[Math] How to Derive the Proximal Operator of the Euclidean Norm

convex optimizationconvex-analysisoptimizationproximal-operators

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.

Best Answer

  • 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.

Related Question