2
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Michael Grant Dec 26 '16 at 19:51
  • $\begingroup$ @MichaelGrant, I voted it for reopen. Certainly can be amswered. $\endgroup$ – Royi Aug 1 '19 at 11:03
  • $\begingroup$ @Royi alas, I think a question of this age is not likely to be reopened regardless of merit. $\endgroup$ – Michael Grant Aug 1 '19 at 15:17
  • 1
    $\begingroup$ Well, You can believe as it happened :-). $\endgroup$ – Royi Aug 1 '19 at 16:21
  • $\begingroup$ 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. $\endgroup$ – Royi Aug 6 '19 at 7:40
1
$\begingroup$

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.

$\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.