IST

基本原理

迭代软阈值（Iterative Soft Thresholding, IST）利用LASSO回归模型将问题表述为

$$ \arg\min_\mathbf x \lVert{\mathbf y-\Phi\mathbf x}\rVert_2^2+\lambda\lVert \mathbf x\rVert_1, $$

可以得到其迭代方法

初始化：$\mathbf x^{(0)}=0$或$\mathbf x^{(0)}=\Phi ^\text T \mathbf y$
计算梯度下降：$\mathbf r^{(k)}=\mathbf x^{(k)}-t\nabla\lVert\mathbf y-\Phi \mathbf x^{(k)}\rVert_2^2$
迭代优化直至收敛：$\mathbf x^{(k+1)}=S_{\lambda t}(\mathbf r^{(k)})$ 其中$t$为步长，$S_\omega(x)$表示软阈值函数，即 $$ [S_\omega(x)]_i = \left\{ \begin{align*} &x_i-\omega, \quad x_i>\omega\\ &0, \quad \lvert x_i\rvert\le\omega\\ &x_i+\omega, \quad x_i<-\omega \end{align*}\right. $$

推导过程

IST的推导需要使用近端梯度下降（PGD）方法，可以将原问题修改为

$$ \mathbf x = \arg\min_\mathbf x {\frac12\lVert A\mathbf x-\mathbf b\rVert_2^2+\lambda\lVert\mathbf x\rVert_1}, $$

令$f(\mathbf x)=\frac12\lVert A\mathbf x-\mathbf b\rVert_2^2+\lambda\lVert\mathbf x\rVert_1$，对其求导

$$ f^\prime(\mathbf x) = A^\text T (A\mathbf x-\mathbf b)+\lambda\text{sgn}(\mathbf x), $$

求其最小值即令$f^\prime(\mathbf x)=0$。

特殊情况$A=I$

特别的当$A=I$时，$f^\prime(\mathbf x) = (\mathbf x-\mathbf b)+\lambda\text{sgn}(\mathbf x)=0$，其解为软阈值函数

$$ \mathbf x = S_\lambda(\mathbf b) = \left\{ \begin{align*} &b+\lambda, \quad b< -\lambda \\ &0, \quad b\le\lvert\lambda\rvert \\ &b-\lambda, \quad b>\lambda \end{align*}\right.. $$

一般情况

回到一般情况，令$f(\mathbf x) = \lVert A\mathbf x-\mathbf b\rVert^2_2$。对$f(\mathbf x)$在$\mathbf x^{(k)}$处做二阶泰勒展开，令$L=\nabla^2f(\mathbf x)=\frac1t$

$$ \begin{align*} \arg\min_\mathbf x f(\mathbf x) &= \arg\min_\mathbf x{f(\mathbf x^{(k)})+\nabla f(\mathbf x^{(k)})^\text T (\mathbf x -\mathbf x^{(k)})+\frac12(\mathbf x-\mathbf x^{(k)})^\text T\nabla^2f(\mathbf x^{(k)})(\mathbf x-\mathbf x^{(k)})} \\ &= \arg\min_\mathbf x\frac1{2t}\sum_i{t^2[\nabla f(\mathbf x^{(k)})]_i^2+2t[\nabla f(\mathbf x^{(k)})]_i (x_i -x_i^{(k)})+(x_i-x_i^{(k)})^2} \\ &= \arg\min_\mathbf x\frac1{2t}{\lVert\mathbf x-[\mathbf x^{(k)}-t\nabla f(\mathbf x^{(k)})]\rVert^2_2} \\ \end{align*}. $$

此时，令$\mathbf z^{(k)}=\mathbf x^{(k)}-t\nabla f(\mathbf x^{(k)})$，原凸优化问题转换为$A=I$的形式（注意这里是$\mathbf x^{(k+1)}=\text{prox}_{h,t}(\mathbf z^{(k)})$），于是有

$$ \begin{align*} \mathbf x^{(k+1)} &= \arg\min_\mathbf x \frac1{2t}\lVert\mathbf x-\mathbf z\rVert^2_2+\lambda\lVert\mathbf x\rVert_1 \\ &= \arg\min_\mathbf x \frac1{2}\lVert\mathbf x-\mathbf z\rVert^2_2+\lambda t\lVert\mathbf x\rVert_1 \\ &= S_{\lambda t}(\mathbf z^{(k)}) \end{align*}. $$

步长选取

固定步长

假设函数$f(\mathbf x) = \lVert A\mathbf x-\mathbf b\rVert^2_2$满足梯度上的Lipschitz连续。当步长$t\le\frac1L$时，能保证多次迭代后最终收敛至梯度为0的点，$L$表示$\nabla f$的Lipschitz常数。

$$ L = \sup\frac{\lVert\nabla f(a)-\nabla f(b)\rVert_2}{\lVert a-b\rVert_2} $$

令$a=\mathbf x+\mathbf x_0,b=\mathbf x$则

$$ \begin{align*} L &= \sup\frac{\lVert\nabla f(\mathbf x+\mathbf x_0)-\nabla f(\mathbf x)\rVert_2}{\lVert\mathbf x_0\rVert_2} \\ &= \sup\frac{\lVert 2A^\text T [A(\mathbf x+\mathbf x_0)-\mathbf b]-2A^\text T (A\mathbf x-\mathbf b)\rVert_2}{\lVert\mathbf x_0\rVert_2} \\ &= \sup\frac{2\lVert A^\text TA\mathbf x_0\rVert_2}{\lVert\mathbf x_0\rVert_2} \\ &\le\frac{2\lVert\lambda_\text{max}(A^\text TA)\mathbf x_0\rVert_2}{\lVert\mathbf x_0\rVert_2} \\ &=2\lambda_\text{max}(A^\text TA) \end{align*} $$

其中$\lambda_\text{max}(\cdot)$表示取最大特征值，令$t=\frac1L=\frac1{2\lambda_\text{max}(A^\text TA)}$

回溯型步长

当矩阵$A$很大时，不容易计算$A^\text TA$的特征值，或者不知道矩阵$A$时，可以通过回溯搜索的方式估计Lipschitz常数。将$f(\mathbf x)$泰勒展开并放缩得到上界函数

$$ \begin{align*} f(\mathbf x) &={f(\mathbf x_0)+\nabla f(\mathbf x_0)^\text T (\mathbf x -\mathbf x_0)+\frac12(\mathbf x-\mathbf x_0)^\text T\nabla^2f(\mathbf x_0)(\mathbf x-\mathbf x_0)}+o(x^3) \\ &\le{f(\mathbf x_0)+\nabla f(\mathbf x_0)^\text T (\mathbf x -\mathbf x_0)+\frac L2(\mathbf x-\mathbf x_0)^\text T(\mathbf x-\mathbf x_0)} \\ &=Q(\mathbf x,\mathbf x_0;L) \end{align*}, $$

令$\mathbf x=\mathbf x^{(k+1)},\mathbf x_0=x^{(k)}$，不断增大$\hat L$，直到$f(\mathbf x^{(k+1)})\le Q(\mathbf x^{(k+1)},\mathbf x^{(k)};\hat L)$满足。

1
2
3
4
5
6
7
8
9


\begin{algorithm}
\caption{BackTracking}
\begin{algorithmic}
	\STATE 初始化$L_0>0, \eta>1, \mathbf x_0\in\mathbb R^n$
	\REPEAT
		\STATE $\hat L = \eta L_\text{before}$
	\UNTIL{$f(\mathbf x^{(k+1)})\le Q(\mathbf x^{(k+1)},\mathbf x^{(k)};\hat L)$}
\end{algorithmic}
\end{algorithm}