10
$\begingroup$

Write down explicitly the optimal solutions to the Moreau-Yosida regularization of the function $f(x)=\lambda\|x\|_1$, where $f:\mathbb{R}^n\to(-\infty,+\infty]$.

I have found that the answer is

$x_i=sgn(x_i)\max\{|x_i|-1,0\}$

Here is my attempt to get the answer:

The proximal operator to $f(x)$ is $\min_{y\in\mathbb{R}^n}\lambda\|y\|_1+\frac{1}{2}\|y-x\|^2_1$. I need to minimize this over y.

I have no idea how to continue. I have read a lot of references but I cannot find an explicit step-by-step solution to this problem.

Any help would be appreciated!

$\endgroup$
3
  • 2
    $\begingroup$ You have to use the 2-norm instead of the 1-norm in the prox function: $\min_y \lambda\|y\|_1 + \frac12\|y-x\|_2^2$ $\endgroup$
    – daw
    Commented Oct 10, 2016 at 11:38
  • 2
    $\begingroup$ The prox operator is defined to use the 2 norm. You want to minimize $\min_{y} \lambda \| y \|_{1} + /frac{1}{2} \| y-x \|_{2}^{2}$. This problem is easy to solve because the objective function decomposes into a sum of very simple terms $\sum_{i=1}^{n} | y_{i} | + \frac{1}{2} (y_{i}-x_{i})^{2}$, Minimize each term by finding a point where 0 is in the subgradient. $\endgroup$
    – Brian Borchers
    Commented Oct 10, 2016 at 14:59
  • $\begingroup$ Answered here: math.stackexchange.com/a/1767083/168758 $\endgroup$
    – dohmatob
    Commented Oct 11, 2016 at 5:56

1 Answer 1

Reset to default
16
$\begingroup$

The Optimization Problem given by the Prox Operator:

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

This problem is separable with respect to both $ u $ and $ x $ hence one could solve the following problem:

$$ \arg \min_{ {u}_{i} } \left\{ \frac{1}{2} {\left( {u}_{i} - {x}_{i} \right)}^{2} + \lambda \left| {u}_{i} \right| \right\} $$

Now, you can proceed using First Order Optimality Condition and the Sub Gradient of the $ \operatorname{abs} \left( \cdot \right) $ function or you can employ simple trick.

The trick is to understand that $ {u}_{i} $ can be either positive, zero or negative.

Assuming $ {u}_{i} > 0 $ the derivative is given by $ {u}_{i} - {x}_{i} + \lambda $ which vanishes for $ {u}_{i} = {x}_{i} - \lambda $ and holds for $ {x}_{i} > \lambda $.
The same procedure for the case $ {u}_{i} < 0 $ yields $ {u}_{i} = {x}_{i} + \lambda $ for $ {x}_{i} < -\lambda $.
For values of $ {x}_{i} $ in between, since ${u}_{i} = 0 $ and hence the derivative (Sub Gradient) of $ {u}_{i} $ can freely be chosen on the range $ \left[ -1, 1 \right] $ the value of $ {u}_{i} = 0 $ holds.

In summary:

$$ \operatorname{Prox}_{\lambda {\left\| \cdot \right\|}_{1}} \left( x \right)_{i} = \operatorname{sign} \left( {x}_{i} \right) \max \left( \left| {x}_{i} \right| - \lambda, 0 \right) $$

As @NicNic8 noted, this operation is called Soft Threshold.

$\endgroup$
3
  • $\begingroup$ The site software says that this answer is a exact copy of another answer by yourself. That is an indication that there is a rule against self-plagiarism. Any thoughts? $\endgroup$
    – Jyrki Lahtonen
    Commented Jan 12, 2017 at 21:06
  • $\begingroup$ Is it better to leave question unanswered? I can change few words if needed :-). $\endgroup$
    – Royi
    Commented Jan 13, 2017 at 9:53
  • $\begingroup$ The need to do anything is not that pressing :-). I close this one as a duplicate of the other since apparently both answerers of the target agree that they are the same question. $\endgroup$
    – Jyrki Lahtonen
    Commented Jan 13, 2017 at 10:25

Not the answer you're looking for? Browse other questions tagged .