同时包含一范数和二范数的公式求解问题

Iterative Shrinkage Thresholding Algorithm （ISTA）求解

现有目标函数：
$$f(x)=\frac{1}{2}\parallel \mathbf{b}-\mathbf{A}\mathbf{x}{\parallel }_2^2+\lambda |\mathbf{x}-\mathbf{u}|$$
其中的变量都为向量，求 $\mathbf{x}$的解

将这样一个问题转化为标量形式
$$f(x)=\frac{1}{2}(x-x_0{)}^2+\lambda |x-u|$$
式子中有绝对值，需要分类讨论这个问题

1. 当 $x-u>0$ 即 $x>u$ 时
   $$f(x)=\frac{1}{2}(x-x_0{)}^2+\lambda (x-u)$$
   有
   $$f^{\prime }(x)=x-x_0+\lambda$$
   令$f^{\prime }(x)=0$，则
   $$x=x_0-\lambda$$
   前提是需要满足 $x>u$，即 $x_0-\lambda >u$
   所以当 $x_0>u+\lambda$ 时 $x=x_0-\lambda$

2. 同理，当 $x-u<0$ 即 $x<u$ 时
   $$f(x)=\frac{1}{2}(x-x_0{)}^2-\lambda (x-u)$$
   有
   $$f^{\prime }(x)=x-x_0-\lambda$$
   令$f^{\prime }(x)=0$，则
   $$x=x_0+\lambda$$
   前提是需要满足 $x<u$，即 $x_0+\lambda <u$
   所以当 $x_0<u-\lambda$ 时 $x=x_0+\lambda$

综上，
$$x=\{\begin{array}{l}{x}_0+\lambda ,x_0<u-\lambda \\ u,u-\lambda \le x_0\le u+\lambda \\ x_0-\lambda ,x_0>u+\lambda \end{array}$$
这里解释一下，中间值为什么是 $u$，将边界值 $x_0=u+\lambda$ 代入到 $x=x_0-\lambda$中，以及 $x_0=u-\lambda$ 代入到 $x=x_0+\lambda$中, 恰好可以得到 $x=u$
以自变量为 $x_0$ , 应变量为 $x$ ， 画出函数图像是这样的

这其实就是一个软阈值函数，用符号 $S(\cdot )$ 来表示, 定义为
$$S_{\lambda ,u}(t)=\{\begin{array}{l}t+\lambda ,t<u-\lambda \\ u,u-\lambda \le t\le u+\lambda \\ t-\lambda ,t>u+\lambda \end{array}$$

则上式的解可以表示为
$$x=S_{\lambda ,u}(x_0)$$
这里的 $x_0$ 是二次项的极值。

让我们回到目标函数：
$$f(x)=\frac{1}{2}\parallel \mathbf{b}-\mathbf{A}\mathbf{x}{\parallel }_2^2+\lambda |\mathbf{x}-\mathbf{u}|$$
二次项的导数为（如果不会求导的详见这里）
$$\frac{\partial f_1(x)}{\partial x}=A^T(Ax-b)$$

则梯度下降求其迭代解（非闭式解）为
$$x^{(t+1)}=x^{(t)}-\frac{1}{c}{\mathbf{A}}^T(\mathbf{A}\mathbf{x}-\mathbf{b})={\mathbf{x}}^{(t)}+\frac{1}{c}{\mathbf{A}}^T(\mathbf{b}-\mathbf{A}\mathbf{x})$$
所以将上式代入软阈值函数里可得

$$x^{(t+1)}=S_{\lambda ,u}({\mathbf{x}}^{(t)}+\frac{1}{c}{\mathbf{A}}^T(\mathbf{b}-\mathbf{A}\mathbf{x}))$$
这就是目标函数的迭代阈值解法。