TwIST算法

---

软阈值(Soft Thresholding)函数

参考资料：

• CSDN 软阈值函数解读

软阈值函数一般写作：

$$soft(x,T) = \left\{\begin{aligned}x&+T && x\le -T,\\&\ 0 && |x|\le T,\\x&-T && x\ge T.\end{aligned}\right.$$

或

$$soft(x,T) = sgn(x)(|x|-T)_+$$

或

$$soft(x,T) = sgn(x)\max\{0,|x|-T\}$$

对于优化问题：

$$\arg\min_x\|X-B\|_2^2+\lambda\|X\|_1$$

的解为：$soft(B,\frac{\lambda}{2}) $

因此同理，对于优化问题$\arg\min_x\frac1 2|X-B|_2^2+\lambda|X|_1$，可以等价为优化问题$\arg\min_x|X-B|_2^2+2\lambda|X|_1$，因此解为：$soft(B,\lambda)$

python可以这么实现soft函数：

def soft(x,T):
    return np.sgn(x) * np.maximum(0, np.fabs(x)-T)

Majorization-Minimization 优化框架

• CSDN Majorization-Minimization优化框架

当目标函数$J(x)$比较难优化的时候，我们可以寻找另外一个更易优化的函数$G(x)$，当$G(x)$满足一定条件时，它的最优解能够无限逼近$J(X)$的最优解。

$G(x)$应该满足3个条件：

1. 容易优化
2. $G_k(x)\ge J(x_k)\ \ for\ \ all \ \ x$
3. $G_k(x_k)=J(x_k)$

迭代软阈值(Iterative Soft Thresholding, IST)

对于基追踪降噪问题(Basis Pursuit De-Noising, BPDN)：

$$\arg\min_x\frac 1 2 \|y-\Phi x\|_2^2 + \lambda\|x\|_1$$

对于目标函数 $f(x) = \frac 1 2 |y-\Phi x|_2^2 + \lambda|x|_1$，并不容易优化，更具MM框架，将其替代为目标函数：$u(x,z) = \frac 1 2 |y-\Phi x|_2^2 + \lambda|x|_1 - \frac 1 2 |\Phi x-\Phi z|_2^2 + \frac 1 2 |x-z|_2^2$

其中，由 $|\Phi|_2<1$，得到: $u(x,z)\ge f(x),u(z,z) = f(z)$

化简该函数，可以得到：

$$u(x,z) = \frac 1 2 \|x- [z+\Phi^T(y-\Phi z)]\|_2^2 + \lambda \|x\|_1 + K$$

其中，K与x无关，于是原问题等价于优化：

$$u^*(x,x^*) = \frac 1 2 \|x-x^*\|_2^2+\lambda\|x\|_1$$

其中，$x^* = z+\Phi^T(y-\Phi z)$

显然，这个问题的解就是软阈值函数 $soft(x^*,\lambda)$