2
$\begingroup$

I'm trying to solve the following proximal operator function (without using moreau decomposition, or conjugates, just straight up differentials):

$prox_{\lambda||\cdot||} = min_x \lambda||x||_2 + ||x-y||^2$

Took gradient, assuming the point y is not 0. (if it was, nondifferentiable)

Then, I got the following result:

$\frac{\lambda x}{||x||_2} + x - y = 0$

Trying to solve for x, it appears it's inseparable, so we can't solve for a single axis at once like the $L_1$ norm.

I then tried the following: $\frac{\lambda x_i}{||x||_2} = y_i-x_i \forall i$.

Squaring both sides so that the denominator looks nice:

$\frac{\lambda^2 x_i^2}{||x||^2_2} = (y_i-x_i)^2 \forall i$

Now we have:

$\frac{\lambda^2x_i^2}{y_i-x_i^2} = \sum_j x_j^2 \forall j$.

However, although we have n of these equations and n unknowns, the fact that it's not a set of linear equations makes me think that it's not possible to solve this any further. However, there is a solution for this in closed form without using the conjugate.

Any hints would be appreciated. Thanks!

$\endgroup$
  • $\begingroup$ What you have written in the beginning is a bit confusing... do you need to calculate the proximal of the norm, that is $\mathrm{prox}_{\lambda \|{}\cdot{}\|}(v)$? Then you need to solve the problem "Min.${}_x \|x\|+\tfrac{1}{2\lambda}\|x-v\|^2$". Take the optimality conditions for this problem and you'll get to the solution. By the way, the answer is: $\mathrm{prox}_{\lambda \|{}\cdot{}\|}(v)=v-\lambda \Pi_{\mathcal{B}}(v/\lambda)$. Why don't you want to use the Moreau decomposition? $\endgroup$ – Pantelis Sopasakis May 4 '17 at 2:43
  • $\begingroup$ Just because in my class, we haven't really gotten to that point yet, though I am familiar with it. Also I'm curious as to see how this is actually solvable without it. I also edited the notation - sorry, was in a rush :(. $\endgroup$ – OneRaynyDay May 4 '17 at 5:35
  • $\begingroup$ An additional comment: I think I have the answer but I will leave it open for a tad longer, in case more interesting solutions will come up. $\endgroup$ – OneRaynyDay May 4 '17 at 5:36
  • $\begingroup$ In the definition of $\mathrm{prox}$, $\min$ should rather be $\mathrm{argmin}$. $\endgroup$ – Pantelis Sopasakis May 4 '17 at 17:48
4
$\begingroup$

$\renewcommand{\Re}{\mathbb{R}}$ We need to solver the optimization problem $$ \mathrm{prox}_{\lambda\|{}\cdot{}\|}(v) = \mathrm{argmin}_{x\in\Re^n}\|x\| + \tfrac{1}{2\lambda}\|x-v\|^2. $$ For convenience and wlog, let $\lambda=1$. I assume that $x\neq 0$. The optimality condition we need to solve is \begin{align} \frac{x}{\|x\|} = v-x.\tag{1}\label{eq:1} \end{align} From \eqref{eq:1} we see that $x$ is parallel to $v$ (again, provided that $x\neq 0$). Indeed, $v=(1+1/\|x\|)x$. Let us assume that $x(v)$ has the parametric form $x(v) = \sigma(v)\cdot v$, where $\sigma:\Re^n\to\Re$. Substituting into \eqref{eq:1}, \begin{align} \frac{\sigma v}{|\sigma|\|v\|} = v-\sigma v,\tag{2} \end{align} From which we conclude that $\sigma(v) \cdot v$ may be either of the following candidates \begin{align} x(v) = \sigma v = \left(1 \pm \tfrac{1}{\|v\|} \right)v.\tag{3}\label{eq:3} \end{align} We plug in \eqref{eq:3} into \eqref{eq:1} and check whether it solves the optimality conditions (recall that there is a unique solution). We may verify that the following is indeed a solution \begin{align} x(v) = \left(1 - \tfrac{1}{\|v\|} \right)v,\tag{4}\label{eq:4} \end{align} but provided that $1 - \tfrac{1}{\|v\|}\geq 0$, that is $\|v\|\geq 1$.

$\endgroup$
  • $\begingroup$ Great answer sir. I have accepted your answer. I did it in a similar but slightly different approach. I will post mine as well. It can generalize to non-circular L2 norms as well. $\endgroup$ – OneRaynyDay May 4 '17 at 18:52
  • $\begingroup$ I think you should generalize and not assume $ \lambda = 1 $. Great answer. +1. $\endgroup$ – Royi Aug 24 '17 at 7:10
1
$\begingroup$

This is just my approach to solve the question, but I have accepted Pantelis's answer.

Starting from the beginning:

$prox_{\lambda||\cdot||}(y) = argmin_x ||x|| + \frac{1}{2\lambda}||x-y||^2$.

Setting gradient to zero:

$\lambda\frac{x}{||x||} + (x-y) = 0$

$(\frac{\lambda}{||x||} + 1)x = y$

Take the norm of both sides:

$(\frac{\lambda}{||x||} + 1)||x|| = ||y||$

Treat $||x||$ as z:

$\lambda + z = ||y||$. $z = ||y|| - \lambda$.

We now know $||x|| = ||y|| - \lambda$, so plug back into the equation:

$(\frac{\lambda}{||y|| - \lambda} + 1)x = y$ and solve for the equation accordingly. It should give the same answer as what Pantelis said.

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