I want to solve the following optimization problem:
$$\mathop{\operatorname{arg\,min}}\limits_x \|y-Ax\|_2^2 + \lambda \|x\|_2^2 - \lambda \cdot 2c \cdot \|x\|_1$$
My idea was to use a proximal gradient descent approach, like:
$$x^* = \operatorname{prox}_H \left( x - A^H (Ax-y) \right),$$
with $H=\lambda(\|x\|_2^2 - 2c\|x\|_1)$. However, I struggle to find the analytic expression for the prox.
The optimality condition is:
$$ 0 = 2(z - x) + \lambda(2z - 2c \partial(\|z\|_1))$$
$$ 0 = z (1 + \lambda) - x - \lambda c\partial(\|z\|_1)$$
Then, for the three cases we have:
- $z = 0$: $\partial(\|z\|_1) = [-1,1]$
$$x = -\lambda c [-1,1] \iff \|x\|_1 \leq \lambda c$$
- $z > 0$: $\partial(\|z\|_1) = 1$
$$\frac{x + \lambda c}{1+\lambda} = z \stackrel{z > 0}\iff x > -\lambda c$$
- $z < 0$: $\partial(\|z\|_1) = -1$
$$\frac{x - \lambda c}{1+\lambda} = z \stackrel{z < 0}\iff x < \lambda c$$
Obviously, I) contradicts II) and III), so I guess something is wrong here. Can you help?
Edit:
Probably the solution is much simpler than I thought: From I-III we conclude:
if $x > \lambda c$, then using (2.): $z = \frac{x+\lambda c}{1+\lambda}$
if $x < -\lambda c$, then using (3.): $z = \frac{x-\lambda c}{1+\lambda}$
if $-\lambda c \leq x \leq \lambda c$, then using (1.): $z=0$