前端之家收集整理的这篇文章主要介绍了
ISTA算法求解L1正则化问题,
前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
L1正则化问题:
minxf(x)+λ∥x∥1
若
f(x)
可导,且
f(x)
满足 L-Lipschitz条件,即存在常数
L>0
使得
∥∇f@H_403_186@(x′)−∇f(x)∥22≤L∥x′−x∥22(∀x,@H_140_301@x′)
则在
xk
附近可将
f(x)
二阶taylor展开近似为:
@H_402_403@@H_772_404@f^(x)≃f(@H_502_471@x0)+⟨∇f(@H_526_502@x0),x−x0⟩+L2∥x−x0∥2=L2∥x−(x0−1L∇f(x0))∥22+const
上式的最小值为:
x=x0−1L∇f(x0)
若通过梯度下降法对
f(x)
进行最小化,则每一步迭代等价于最小化二次函数
f^(x)
.
L1正则化问题的迭代公式为:
xk+1=argminxL2∥x−(xk−1L∇f(xk))∥22+λ∥x∥1
令
z@H_301_1173@=xk−1L∇f(xk)
,然后求解:
xk+1=argminxL2∥x−z@H_301_1173@∥22+λ∥x∥1
解得:
xik+1=⎧⎩⎨⎪⎪⎪⎪z@H_301_1173@i−λL,0,z@H_301_1173@i+λL,λL<z@H_301_1173@i@H_502_1666@|z@H_301_1173@i|≤λLλL>z@H_301_1173@i
其中,
xi@H_301_1831@k+1
与
z@H_301_1173@i
分别是
xk+1
与
z@H_301_1173@
的第
i
个分量。