1
$\begingroup$

I am trying to minimize the following function $$argmin_x||x-y||^2_2 + ||x-z||_2^2 + \lambda || \frac{x- w}{c}||_1$$

I have been doing it for while but i am not sure how to do it. I have already been through few of the examples for simple cases such as this one (Derivation of soft thresholding operator).

Taking the derivative w.r.t $x$ is given by

$$\frac{x{-w}}{\left|c\right|\left|x{-w}\right|}+4x{-2z}{-2y}$$, i would like to know that how i would be able to go from here to the soft thresholding function described in the above link.

Any help regarding this would be quite useful

$\endgroup$
  • 1
    $\begingroup$ Why not just perform a variable substitution: $\tilde{x} = (x - w)/c$ so that your objective becomes $$\|c\tilde{x}+w-y\|_2^2+\|c\tilde{x}+w-z\|_2^2+\lambda\|\tilde{x}\|_1?$$ $\endgroup$ – Michael Grant Oct 27 '15 at 14:44
  • $\begingroup$ Do @MichaelGrant's variable substitution, and then complete the square in $c\tilde{x}$ $\endgroup$ – dohmatob Oct 28 '15 at 8:09
2
$\begingroup$

After applying @MichaelGrant 's variable substitution $u=(x-w)/c$ you end up with

$$ \arg \min_u \Vert cu+w-y\Vert^2 + \Vert cu+w-z\Vert^2 + \lambda \Vert u \Vert_1$$

which basically looks like the standard soft-thresholding $$\arg \min_u (1/2)\Vert u-p\Vert^2 + \lambda \Vert u\Vert_1 $$

after some manipulation of the two other terms i.e.

$$\Vert cu+w-y\Vert^2 + \Vert cu+w-z\Vert^2 = 2 c^2 \left\Vert u-\frac{2w-y-z}{c} \right\Vert^2 + f(w,y,z) $$

and it becomes

$$ \begin{eqnarray} \arg \min_u 2 c^2 \left\Vert u-\frac{2w-y-z}{c} \right\Vert^2 + \lambda \Vert u\Vert_1 & = & 4c^2 \arg \min_u \frac{1}{2}\left\Vert u-\frac{2w-y-z}{c} \right\Vert^2 + \frac{\lambda}{4c^2} \Vert u\Vert_1 \\ & = & 4c^2 S_{\lambda / 4c^2} \left( \frac{2w-y-z}{c} \right) \end{eqnarray} $$

where $S_\rho$ is the soft-thresholding function with parameter $\rho$.

$\endgroup$

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.