# The Proximal Operator of the ${L}_{1}$ Norm Function [duplicate]

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!

• 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$ – daw Oct 10 '16 at 11:38
• Why? Can I choose any arbitrary norm? I am not sure. Thanks. – Yellow Skies Oct 10 '16 at 12:07
• 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. – Brian Borchers Oct 10 '16 at 14:59
• Answered here: math.stackexchange.com/a/1767083/168758 – dohmatob Oct 11 '16 at 5:56

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.

• 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? – Jyrki Lahtonen Jan 12 '17 at 21:06
• Is it better to leave question unanswered? I can change few words if needed :-). – Royi Jan 13 '17 at 9:53
• 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. – Jyrki Lahtonen Jan 13 '17 at 10:25
• @JyrkiLahtonen, Seems reasonable to lock. By the way, could you activate this: math.stackexchange.com/questions/2092145/…. I edited the question to be clear and I'd like to answer it. Thank You. – Royi Jan 13 '17 at 10:56
• Just a note that the name of this function (the proximal operator of the L1 norm) is "soft threshold". – NicNic8 Dec 26 '17 at 5:14