ISTA

L1范数产生稀疏解###

$\min F(x) = ||Ax-b||^2 + \lambda ||x||_p^p$ 假设最优解为$x^*$，则原问题等价于： $\min_x F(x) = ||Ax-b||^2 \qquad s.t. \quad ||x||_p^p \le C \quad C=||x^*||_p^p$

proximal gradient descent###

在梯度下降中，如果 $\nabla f(x)$ 满足L-Lipschitz，即： $\left \| \nabla f(x_{k+1}) - \nabla f(x_k) \right \| \le L \left \| x_{k+1} - x_k \right \|$ , 在$x_k$点泰勒展开：

$$f(x,x_k) = f(x_{k}) + \left \langle x-x_{k},\nabla f(x_{k}) \right \rangle + \frac {L}{2} \left \| x-x_{k} \right \|^2 \\ = \frac {L}{2} \left \| x- (x_{k} -t_k \nabla f(x_{k})) \right \|^2 + \varphi (x_k)$$

最小在 $x_{k+1} = x_{k} - \frac {1}{L} \nabla f(x_{k+1})$。 如果优化目标中，加入非光滑的惩罚项，比如L1，对光滑的部分做上述展开，则称为proximal gradient descent(PGD)。

Proximal Gradient Descent for L1 Regularization

ISTA###

ISTA算法解决非平滑的，不可求导的凸优化问题，比如带能够产生稀疏解的L1范数问题，$\min \{ f(x) + \lambda \left \| x \right \|_1 \}$。

通过对目标函数进行分解，将其平滑的部分用近端正则逼近。即每步在优化原问题的一个变化上界。 每一步迭代中，优化变量完全解耦，且子问题存在闭式解。

列：$\min F(x) = \left \| Ax-b \right \|^2 + \lambda \left \| x \right \|_p^p$。 该问题等价于：$\min_x \left \| Ax-b \right \|^2 \quad s.t. \left \| x \right \|_p^p \lt C \quad C=\left \| x^* \right \|_p^p \quad x^*\text{是最优解}$。

每一步迭代求解：

$$x_k = \arg \min_x \{ {\color{Blue} {f(x_{k-1}) + \left \langle x-x_{k-1},\nabla f(x_{k-1}) \right \rangle + \frac {1}{2t_k} \left \| x-x_{k-1} \right \|^2 }} + \lambda \left \| x \right \|_1 \} \\ \approx \arg \min_x \{ \frac {1}{2t_k} \left \| x- (x_{k-1} -t_k \nabla f(x_{k-1})) \right \|^2 + \lambda \left \| x \right \|_1 \}$$

存在闭式解：

$$x_k = \tau_{\lambda t_k} (x_{k-1} -t_k \nabla f(x_{k-1})) \\ \tau_{\alpha}(x) = sign(x) \max \{0, \left| x \right| -\alpha\}$$

收敛： $\left \| x_k - x_{k-1} \right \|^2 \to 0$时收敛，上界等于原目标函数。

如何确定$t_k$？

from MLAPP: Chapter 13. Sparse linear models (page 446)

FISTA###

《A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems》

关于Nesterov’s method可以见SGD的Nesterov Momentum。

Python implementation of the Fast Iterative Shrinkage/Thresholding Algorithm.