迭代软阈值算法（Iterative soft thresholding algorithm, ISTA）

迭代软阈值算法用于求解如下的稀疏信号重构问题：
$\min_{\bf{x}} \|{\bf{y}} - {\bf{Hx}}\|_2^2 + \lambda \|{\bf{x}}\|_1.$
理解ISTA算法的由来，需要从几块内容着手：

Majorization-minimization
软阈值函数的由来
迭代软阈值算法

Majorization-minimization (MM) 简介

核心思想

MM 是一个应对优化问题的思想框架，它通过迭代的方式求解一个无约束待优化问题 $\min_{\boldsymbol{x}} J({\boldsymbol{x}})$ 。其主要思路为，在第 $k+1$ 步迭代（假设上一步求得 ${\boldsymbol{x}}_k$ ），通过寻找另一个容易优化求得全局最优（极小）的函数 $G_k ({\mathbf{x}})$ ，使其满足
$G_k ({\bf{x}}) \ge J({\bf{x}}), \forall {\bf{x}} \\ G_k ({\bf{x}}_k) = J({\bf{x}}_k).$ 然后，将 $G_k ({\mathbf{x}})$ 的极小值点作为新的迭代值 ${\boldsymbol{x}}_{k+1}$ 。这样，可以保证
$J({\boldsymbol{x}}_{k+1}) <= G({\boldsymbol{x}}_{k+1}) < G({\boldsymbol{x}}_{k}) = J({\boldsymbol{x}}_{k}),$ 即保证每步迭代都能使目标函数 $J({\boldsymbol{x}})$ 的值下降。

一种构造 $G_k ({\mathbf{x}})$ 的方法

一种很好用的构造 $G_k ({\mathbf{x}})$ 的方法，是在原始函数 $J({\boldsymbol{x}})$ 上加入一个半正定的 $\mathbf{x}$ 的二次型，如下所示：
$G_k ({\bf{x}}) = J({\bf{x}}) + ({\bf{x}} - {\bf{x}}_k)^\top (\alpha {\bf{I}} - {\bf{H}}^\top{\bf{H}}) ({\bf{x}} - {\bf{x}}_k),$ 需要满足 $\alpha \ge max {\rm{eig}}({\boldsymbol{H}}^\top{\boldsymbol{H}})$ 。
还有一些其他的 $G_k ({\mathbf{x}})$ 的构造方式，对应额外的一些算法，不在此介绍了。

举个例子：Landweber 迭代

考虑 $J({\mathbf{x}}) = \|{\bf{y}} - {\bf{Hx}}\|_2^2$ ，并且采用上面的方法进行迭代式的优化求解，那么步骤如下：

第 $k+1$ 次迭代时，构造
$G_k ({\mathbf{x}}) = \|{\mathbf{y}} - {\mathbf{Hx}}\|_2^2 + ({\mathbf{x}} - {\mathbf{x}}_k)^\top (\alpha {\mathbf{I}} - {\mathbf{H}}^\top{\mathbf{H}}) ({\mathbf{x}} - {\mathbf{x}}_k), \tag{1} \label{eq1}$
其全局极小值点通过一阶梯度为 $0$ 求得
$\frac{\partial }{\partial {\boldsymbol{x}}} G_k ({\boldsymbol{x}}) = 2 \alpha {\boldsymbol{x}} - 2 {\boldsymbol{H}}^\top {\boldsymbol{y}} - 2 (\alpha {\boldsymbol{I}} - {\boldsymbol{H}}^\top {\boldsymbol{H}}) {\boldsymbol{x}}_k = 0, \\ \Rightarrow {\boldsymbol{x}}_{k+1} = {\boldsymbol{x}}_K + \frac{1}{\alpha} {\boldsymbol{H}}^\top({\boldsymbol{y}} - {\boldsymbol{Hx}}_k).$ 上式即是 Landweber 迭代公式。

矩阵知识比较好的人，也可以直接将式 (1) 改写成如下形式
$G_k ({\mathbf{x}}) = \alpha \|{\mathbf{x}}_k + \frac{1}{\alpha} {\mathbf{H}}^\top ({\mathbf{y}} - {\mathbf{Hx}}_k) - {\bf{x}}\|_2^2 + C$ 从而得到相同的迭代式。

软阈值函数的由来

考虑求解如下形式的问题（类似于基于稀疏约束的去噪）
$\min \|{\boldsymbol{y}} - {\boldsymbol{x}}\|_2^2 + \lambda \|{\boldsymbol{x}}\|_1, \tag{2}\label{eq2}$ 可以对向量中的每个元素单独求解，即
$\min (y_i - x_i)^2 + \lambda |x_i|$ 通过求梯度为 0 的点可得
$y_i = x_i + \frac{\lambda}{2} {\rm{sign}}(x_i),$ 通过上式可以反求出
$x_i = \begin{cases} y_i + \frac{\lambda}{2} & y_i < - \frac{\lambda}{2} \\ 0 & |y_i | \le \frac{\lambda}{2} \\ y_i - \frac{\lambda}{2} & y_i > \frac{\lambda}{2} \end{cases}$ 将对 $y_i$ 的这个操作叫做软阈值函数，记为 ${\rm{soft}} (y_i, \frac{\lambda}{2})$ 。
即，问题 (2) 的解为 ${\boldsymbol{x}} = {\rm{soft}}({\boldsymbol{y}}, \frac{\lambda}{2})$ 。

迭代软阈值算法

求解如下问题
$\min_{\boldsymbol{x}} \|{\boldsymbol{y}} - {\boldsymbol{Hx}}\|_2^2 + \lambda \|{\boldsymbol{x}}\|_1.$

根据 MM 的思想，在每一步迭代时，通过添加半正定二次型，构造
$\begin{aligned} G_k({\mathbf{x}}) =& \|{\mathbf{y}} - {\bf{Hx}}\|_2^2 + \lambda \|{\bf{x}}\|_1 + ({\bf{x}} - {\bf{x}}_k)^\top (\alpha {\bf{I}} - {\bf{H}}^\top{\bf{H}}) ({\bf{x}} - {\bf{x}}_k) \\ =& \alpha \|{\bf{x}}_k + \frac{1}{\alpha} {\bf{H}}^\top ({\bf{y}} - {\bf{Hx}}_k) - {\bf{x}}\|_2^2 + C + \lambda \|{\bf{x}}\|_1 \end{aligned}$
需要求 ${\boldsymbol{x}}_{k+1} = \min_{\boldsymbol{x}} G_k({\boldsymbol{x}})$ ，根据上一节中的软阈值方法，可轻易求得
${\mathbf{x}}_{k+1} = {\rm{soft}} ({\mathbf{x}}_k + \frac{1}{\alpha} {\mathbf{H}}^\top ({\mathbf{y}} - {\mathbf{Hx}}_k), \frac{\lambda}{2 \alpha})$ 即为迭代软阈值算法的步骤，其中参数需要满足 $\alpha \ge max~{\rm{eig}}({\boldsymbol{H}}^\top{\boldsymbol{H}})$ 。

算法收敛性

关于算法的收敛性和收敛速度研究待阅读其他文献

参考：http://eeweb.poly.edu/iselesni/lecture_notes/sparse_signal_restoration.pdf

最后编辑于：2022.04.11 21:07:14

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 222,000评论 6赞 515
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 94,745评论 3赞 399
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 168,561评论 0赞 360
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 59,782评论 1赞 298
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 68,798评论 6赞 397
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 52,394评论 1赞 310
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,952评论 3赞 421
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,852评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 46,409评论 1赞 318
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 38,483评论 3赞 341
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,615评论 1赞 352
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 36,303评论 5赞 350
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,979评论 3赞 334
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 32,470评论 0赞 24
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,571评论 1赞 272
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 49,041评论 3赞 377
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 45,630评论 2赞 359