# Proximal Operator of the ${L}_{2}$ Norm Cubed (Proximal Operator of Norm Composition - Cubic Euclidean Norm)

What is the proximal operator of $${\left\| x \right\|}_{2}^{3}$$ where $${\left\| x \right\|}_{2}$$ is the $${L}_{2}$$ norm?

Using Moreau Decomposition (Someone needs to create a Wikipedia page for it) one could solve it as following:

$$\operatorname{Prox}_{\lambda f \left( \cdot \right)} (v) = v - \Pi_B \left( v \right)$$

Where $$\Pi_B \left( \cdot \right)$$ is the projection of onto the unit ball of the dual norm.
Yet I'm not sure how to derive for the case mentioned above.

• It's not clear to me why this was closed without any sort of comment. It's certainly not a trivial question to answer. I do not think there is a nice simple answer that you can offer for a general norms, however. – Michael Grant Dec 26 '16 at 19:51
• @MichaelGrant, I voted it for reopen. Certainly can be amswered. – Royi Aug 1 '19 at 11:03
• @Royi alas, I think a question of this age is not likely to be reopened regardless of merit. – Michael Grant Aug 1 '19 at 15:17
• Well, You can believe as it happened :-). – Royi Aug 1 '19 at 16:21
• Pay attention that your function isn't a vanilla norm. So I'm not sure its support is a norm ball which means its dual function is the dual norm. – Royi Aug 6 '19 at 7:40

The solution isn't trivial.
The problem is given by:

$$\operatorname{Prox}_{\lambda f \left( \cdot \right)} = \arg \min_{x} \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + \lambda f \left( x \right) = \arg \min_{x} \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + \lambda {\left\| x \right\|}_{2}^{3}$$

I succeeded using identity of Euclidean Norm Composition (Calculus of the Prox Operator, From Amir Beck - First Order Methods in Optimization):

Norm Composition: Let $$f : E \to R$$ be given by $$f \left( x \right) = g \left( \left\| x \right\| \right)$$, where $$g : R \to \left(−\infty, \infty \right]$$ is a proper closed and convex function satisfying $$\operatorname{dom} \left( g \right) \subseteq \left[0, \infty \right)$$. Then:

$$\operatorname{Prox}_{\lambda f \left( \cdot \right)} \left( y \right) = \begin{cases} \operatorname{Prox}_{ \lambda g \left( \cdot \right) } \left( \left\| y \right\| \right) \frac{y}{\left\| y \right\|} & \text{ if } y \neq 0 \\ \left\{ x \in \mathbb{E} : \left\| x \right\| = \operatorname{Prox}_{ \lambda g \left( \cdot \right)} \left( 0 \right) \right\} & \text{ if } y = 0 \end{cases}$$

So in our case:

$$g \left( t \right) = \begin{cases} {t}^{3} & \text{ if } t \geq 0 \\ \infty & \text{ if } t < 0 \end{cases}$$

It is easy to derive that

$$\operatorname{Prox}_{\lambda g \left( \cdot \right)} \left( t \right) = \frac{-1 + \sqrt{ 1 + 12 \lambda {\left[ t \right]}_{+} }}{6 \lambda}$$

So for $$\operatorname{Prox}_{\lambda g \left( \cdot \right)} \left( 0 \right) = 0$$.
Hence the composition becomes:

$$\operatorname{Prox}_{\lambda f \left( \cdot \right)} \left( y \right) = \begin{cases} \frac{-1 + \sqrt{ 1 + 12 \lambda \left\| y \right\| }}{6 \lambda} \frac{y}{\left\| y \right\|} & \text{ if } y \neq 0 \\ 0 & \text{ if } y = 0 \end{cases} = \frac{2}{1 + \sqrt{1 + 12 \lambda \left\| y \right\|}} y$$

I validated the result comparing it to CVX solution. The MATLAB code is available at my Mathematics StackExchange Question 2071774 Repository.

## Remark

Your idea about using the Moreau Decomposition is valid (Though I don't think it will yield solution in this case).
Yet you must pay attention that your function $${\left\| \cdot \right\|}_{2}^{3}$$ isn't a norm (Hence it is not the support of a norm etc...). You can't use the projection in this case but you need to use the Dual Function which as I wrote, I don't think will create a simpler solution.