ISTA算法求解L1正则化问题

L1正则化问题：

$$min_{x} f(x)+lambdaVert xVert_1$$
若 $f(x)$可导，且 $f(x)$满足 L-Lipschitz条件，即存在常数 $L> 0$使得

$$Vertnabla f(x')-nabla f(x)Vert_2^2leq LVert x'-xVert_2^2(forall x,x')$$
则在 $x_k$附近可将 $f(x)$二阶taylor展开近似为：
$$begin{aligned} hat f(x)&simeq f(x_0)+left<nabla f(x_0),x-x_0right>+frac{L}{2}Vert x-x_0Vert^2 &=frac{L}{2}Vert x-(x_0-frac{1}{L}nabla f(x_0))Vert_2^2+const end{aligned}$$
上式的最小值为：
$$x = x_0-frac{1}{L}nabla f(x_0)$$

若通过梯度下降法对$f(x)$进行最小化，则每一步迭代等价于最小化二次函数$hat f(x)$.

L1正则化问题的迭代公式为：

$$x_{k+1}=argmin_xfrac{L}{2}Vert x-(x_k-frac{1}{L}nabla f(x_k))Vert_2^2+lambdaVert xVert_1$$
令 $z=x_k-frac{1}{L}nabla f(x_k)$,然后求解：
$$x_{k+1}=argmin_xfrac{L}{2}Vert x-zVert_2^2+lambdaVert xVert_1$$
解得：
$$begin{aligned} x_{k+1}^i=begin{cases} z^i-frac{lambda}{L},&frac{lambda}{L}<z^i 0,&|z^i|lefrac{lambda}{L} z^i+frac{lambda}{L},&frac{lambda}{L}>z^i end{cases} end{aligned}$$
其中， $x_{k+1}^i$与 $z^i$分别是 $x_{k+1}$与 $z$的第 i 个分量。