Minimize a function with an absolute value.

Question

I'm given a function $0.5(y-\theta)^2 + \lambda |\theta| $, $\lambda \geq 0$ that should be minimized with respect to $\theta$.

The result should be $\hat \theta = sign(y)(|y|-\lambda) I(|y| >\lambda)$.

I don't understand why we have a sing and an indicator function. I would expect that we consider two cases (when $\theta \geq 0$ and $\theta < 0$) and just take derivatives and assign them to zero. In such a case, I would have $\hat \theta = y\pm \lambda$. Why is it wrong and how can I obtain the result above?

Answer 1

Hints: The minimum value in $(0,\infty)$ is attained when $\theta=y-\lambda$ and the minimum value in $(-\infty,0)$ is attained when $\theta=y+\lambda$ as you have rightly observed. The global minimum value is the least of the values at the points $\theta=y-\lambda, \theta=y+\lambda$ and $\theta=0$. When $|y| \leq \lambda$ (i.e. $-\lambda \leq \theta \leq \lambda$) you can check that the minimum is attained at $\theta=0$. This explains the presence of $I(|y|>\lambda)$ in the solution. Now observe that $sgn y (|y|-\lambda) $ is nothing but $y-\lambda$ if $y $ is positive and $y+\lambda$ if $y$ is negative. I will now let you finish the argument.

Answer 2

Making $|\theta| = \sqrt{\theta^2}$ we have

$$ \left(\frac 12(y-\theta)^2+\lambda \sqrt{\theta^2}\right)' = -(y-\theta)+\lambda \frac{\theta}{\sqrt{\theta^2}} = -(y-\theta)+\lambda \text{sign}(\theta) = 0 $$

but $\theta = |\theta|\text{sign}(\theta)$ then $\theta = |\theta|\text{sign}(\theta)-y +\lambda \text{sign}(\theta) = 0$ hence $y = (|\theta|+\lambda)\text{sign}(\theta)$ but as $\lambda \ge 0$ we have $\text{sign}(y) = \text{sign}(\theta)$ and finally

$$ \theta = (|y|-\lambda)\text{sign}(y)\ \ \text{as long as}\ \ |y|-\lambda > 0 $$