15
$\begingroup$

I was going through the derivation of soft threholding at http://dl.dropboxusercontent.com/u/22893361/papers/Soft%20Threshold%20Proof.pdf.

It says the three unique solutions for

$\operatorname{arg min} \|x-b\|_2^2 + \lambda\|x\|_1$ is given by

$\operatorname{arg min} \|x-b\|^2 + \lambda x$ assuming $x > 0$

$\operatorname{arg min} \|x-b\|^2 - \lambda x$ assuming $x < 0$

$\operatorname{arg min} \|x-b\|^2 = 0 $ assuming $x = 0$

I am confused in the third case. For $x = 0$, how come the solution is zero. I mean when x = 0, I will have $\operatorname{arg min} \|x-b\|^2$. If I solve this, I will get x = b, the solution then how come it is $x = 0$

$\endgroup$
  • $\begingroup$ That's poorly written. What they mean is that you minimize the objective over the restricted domains $x\in(0,\infty)$, $x\in(-\infty,0)$ and $x\in\{0\}$ respectively. In the third case, at what point in $\{0\}$ is the minimum attained? Well, there is only one point in $\{0\}$; it is $x=0$. Still, this is not a very good way of going about it, and you may want to look for a better reference. $\endgroup$ – Rahul Aug 19 '13 at 16:42
28
$\begingroup$

I wrote a more detailed derivation of the soft-thresholding operator, following the source you mention and other ones. I hope it helps.

The soft-thresholding is just the proximal mapping of the $l_1$-norm. Let $f(x) = \lambda\|x\|_1$, then the proximal mapping of $f$ is defined as

\begin{equation} \operatorname{prox}_f(x) = \operatorname{argmin}_z\{\frac{1}{2}\|x-z\|^2_2 + \lambda\|z\|_1 \} \end{equation}

The optimality condition for the previous problem is

\begin{equation} 0 \in \nabla(\frac{1}{2}\|x-z\|^2_2) + \partial(\lambda\|z\|_1) \Leftrightarrow 0 \in z-x + \lambda\partial\|z\|_1 \end{equation}

The $l_1$-norm is separable and thus we can consider each of its components separately. Let's examine first the case where $z_i \neq 0$. Then, $\partial \|z_i\|=\operatorname{sign}(z_i)$ and the optimum $z_i^*$ is obtained as

\begin{equation} 0 = z_i-x_i + \lambda \operatorname{sign}(z_i) \Leftrightarrow z_i^* = x_i - \lambda \operatorname{sign}(z_i^*) \end{equation}

Note also that if $z_i^* < 0$, then $x_i < -\lambda$ and equivalently if $z_i^* > 0 \Rightarrow x_i > \lambda$. Thus, $|x_i| > \lambda$ and $\operatorname{sign}(z_i^*) = \operatorname{sign}(x_i)$. Substituting in the previous equation we get

\begin{equation} z_i^* = x_i - \lambda \operatorname{sign}(x_i) \end{equation}

In the case where $z_i = 0$, the subdifferential of the $l_1$-norm is the interval $[-1,1]$ and the optimality condition is

\begin{equation} 0 \in -x_i + \lambda[-1,1] \Leftrightarrow x_i \in [-\lambda,\lambda] \Leftrightarrow |x_i| \leq \lambda \end{equation}

Putting all together we get

\begin{equation} [\operatorname{prox}_f(x)]_i = z_i^* = \left\{ \begin{array}{lr} 0 & \text{if } |x_i| \leq \lambda \\ x_i - \lambda \operatorname{sign}(x_i) & \text{if } |x_i| > \lambda \end{array}\right. \end{equation}

The previous equation can also be written as

\begin{align*} [\operatorname{prox}_f(x)]_i &= \operatorname{sign}(x_i)\max(|x_i|-\lambda, 0) \\ &= \operatorname{sign}(x_i)(|x_i|-\lambda)_+ \end{align*}

where $(\cdot)_+$ denotes the positive part.

$\endgroup$
  • 1
    $\begingroup$ I think your derivation is totally wrong. You have mixed up x and z $\endgroup$ – user34790 Oct 5 '13 at 18:39
  • $\begingroup$ You are right there is indeed a mistake but it is only in the definition of proximal mapping, where I wrote x when it should be z. I think it is correct now $\endgroup$ – skd Oct 5 '13 at 20:35
  • 1
    $\begingroup$ Hey. if the the objective is argmin $1/2ax^2 bx + \lambda|c+x|_1$, the result is $x = -c + sign(c-b/a)max(|c-b/a|, \lambda/a),0)$. I didn't get how it was derived? $\endgroup$ – user34790 Oct 17 '13 at 1:06
  • $\begingroup$ Is that another question? What are a and b, scalars? In that case that problem is cubic in x?? Maybe you are missing something? $\endgroup$ – skd Oct 18 '13 at 12:06
  • 1
    $\begingroup$ @skd you forget 1/2 in front of $\|x-z \|^2_2$. $\endgroup$ – E.J. Oct 15 '14 at 2:20
2
$\begingroup$

Suppose $\hat{x} \in \mathbb R$ and we want to find a minimizer of $f(x) = |x| + \frac{1}{2t}(x - \hat{x})^2$. We want to make $|x|$ small without straying too far from $\hat{x}$.

Consider the case where $\hat{x} > 0$.

In this case there's no reason to let $x$ be negative. Because if $x$ is negative, then $-x$ is closer to $\hat{x}$ and $-x$ has the same absolute value as $x$.

So we need to minimize the quadratic function $g(x) = x + \frac{1}{2t} (x - \hat{x})^2$ over $[0,\infty)$. The graph of $g$ is a parabola that opens upwards, and we can minimize $g$ using techniques from pre-calculus.

The case where $\hat{x} < 0$ is similar.

$\endgroup$
  • $\begingroup$ Sorry to respond to such an old answer but I had a small question. Following your steps (with $t=1$), I came to the conclusion that $g$ is minimized when $x = \hat{x}-1$. Knowing what the soft threshhold operator looks like, this makes sense when $\hat{x} \geq 1$ but we only assumed that $\hat{x} >0$? $\endgroup$ – TSF Jan 30 '18 at 10:41
1
$\begingroup$

I wonder about something.

One could write the Soft Thresholding as:

$$ x - \lambda \operatorname{sgn} \left( x \right) \min \left( \left| \frac{x}{\lambda} \right|, 1 \right) $$

This is of the form $ x - \lambda g \left( \frac{x}{\lambda} \right) $.
Using the trick done here - https://math.stackexchange.com/a/2094088/33 it might suggest that $ \operatorname{sgn} \left( x \right) \min \left( \left| x \right|, 1 \right) $ is the projection to $ {L}_{1} $ Unit Ball (Which doesn't have closed form solution).

So what's wrong here?

Remark
As noted below - The formula states the projection to the dual ball.

$\endgroup$
  • $\begingroup$ The quantity you're contemplating is the projection onto the dual ball, namely the $\ell_\infty$ ball. This is because the convex conjugate of a norm is the indicator function of the dual ball. Now use Moreau's decomposition. Also, as you rightly noted (with some hesitation), projecting onto the L1 ball has no closed form solution... $\endgroup$ – dohmatob Mar 13 '18 at 21:05

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.