迭代軟閾值算法（Iterative soft thresholding algorithm, ISTA）

迭代軟閾值算法用于求解如下的稀疏信號重構(gòu)問題：
$\min_{\bf{x}} \|{\bf{y}} - {\bf{Hx}}\|_2^2 + \lambda \|{\bf{x}}\|_1.$
理解ISTA算法的由來岩灭，需要從幾塊內(nèi)容著手：

Majorization-minimization
軟閾值函數(shù)的由來
迭代軟閾值算法

Majorization-minimization (MM) 簡介

核心思想

MM 是一個應(yīng)對優(yōu)化問題的思想框架抛计，它通過迭代的方式求解一個無約束待優(yōu)化問題 $\min_{\boldsymbol{x}} J({\boldsymbol{x}})$ 审磁。其主要思路為吁系，在第 $k+1$ 步迭代（假設(shè)上一步求得 ${\boldsymbol{x}}_k$ ），通過尋找另一個容易優(yōu)化求得全局最優(yōu)（極忻庸ぁ）的函數(shù) $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}),$ 即保證每步迭代都能使目標函數(shù) $J({\boldsymbol{x}})$ 的值下降。

一種構(gòu)造 $G_k ({\mathbf{x}})$ 的方法

一種很好用的構(gòu)造 $G_k ({\mathbf{x}})$ 的方法棒呛，是在原始函數(shù) $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}})$ 的構(gòu)造方式簇秒，對應(yīng)額外的一些算法鱼喉，不在此介紹了。

舉個例子：Landweber 迭代

考慮 $J({\mathbf{x}}) = \|{\bf{y}} - {\bf{Hx}}\|_2^2$ 宰睡，并且采用上面的方法進行迭代式的優(yōu)化求解蒲凶，那么步驟如下：

第 $k+1$ 次迭代時，構(gòu)造
$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$ 從而得到相同的迭代式。

軟閾值函數(shù)的由來

考慮求解如下形式的問題（類似于基于稀疏約束的去噪）
$\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$ 的這個操作叫做軟閾值函數(shù)灵巧，記為 ${\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.$

根據(jù) MM 的思想瓤球，在每一步迭代時，通過添加半正定二次型敏弃，構(gòu)造
$\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}})$ 卦羡，根據(jù)上一節(jié)中的軟閾值方法，可輕易求得
${\mathbf{x}}_{k+1} = {\rm{soft}} ({\mathbf{x}}_k + \frac{1}{\alpha} {\mathbf{H}}^\top ({\mathbf{y}} - {\mathbf{Hx}}_k), \frac{\lambda}{2 \alpha})$ 即為迭代軟閾值算法的步驟麦到，其中參數(shù)需要滿足 $\alpha \ge max~{\rm{eig}}({\boldsymbol{H}}^\top{\boldsymbol{H}})$ 绿饵。

算法收斂性

關(guān)于算法的收斂性和收斂速度研究待閱讀其他文獻

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

最后編輯于：2022.04.11 21:07:14

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市瓶颠，隨后出現(xiàn)的幾起案子拟赊，更是在濱河造成了極大的恐慌，老刑警劉巖粹淋，帶你破解...
沈念sama閱讀 219,270評論 6贊 508
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件吸祟，死亡現(xiàn)場離奇詭異，居然都是意外死亡桃移，警方通過查閱死者的電腦和手機屋匕，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,489評論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來谴轮，“玉大人炒瘟，你說我怎么就攤上這事吹埠〉诓剑” “怎么了？”我有些...
開封第一講書人閱讀 165,630評論 0贊 356
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵缘琅，是天一觀的道長粘都。經(jīng)常有香客問我，道長刷袍，這世上最難降的妖魔是什么翩隧？我笑而不...
開封第一講書人閱讀 58,906評論 1贊 295
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮呻纹，結(jié)果婚禮上堆生，老公的妹妹穿的比我還像新娘。我一直安慰自己雷酪，他們只是感情好淑仆，可當我...
茶點故事閱讀 67,928評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著哥力，像睡著了一般蔗怠。火紅的嫁衣襯著肌膚如雪墩弯。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,718評論 1贊 305
城市分裂傳說
那天寞射，我揣著相機與錄音渔工，去河邊找鬼。笑死桥温，一個胖子當著我的面吹牛引矩，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播侵浸，決...
沈念sama閱讀 40,442評論 3贊 420
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼脓魏，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了通惫？” 一聲冷哼從身側(cè)響起茂翔，我...
開封第一講書人閱讀 39,345評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎履腋，沒想到半個月后珊燎，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 45,802評論 1贊 317
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡遵湖，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,984評論 3贊 337
?白月光啟示錄
正文我和宋清朗相戀三年悔政，在試婚紗的時候發(fā)現(xiàn)自己被綠了。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片延旧。...
茶點故事閱讀 40,117評論 1贊 351
活死人
序言：一個原本活蹦亂跳的男人離奇死亡谋国，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出迁沫，到底是詐尸還是另有隱情芦瘾，我是刑警寧澤，帶...
沈念sama閱讀 35,810評論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布集畅，位于F島的核電站近弟，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏挺智。R本人自食惡果不足惜祷愉，卻給世界環(huán)境...
茶點故事閱讀 41,462評論 3贊 331
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望赦颇。院中可真熱鬧二鳄，春花似錦、人聲如沸媒怯。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,011評論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽沪摄。三九已至躯嫉，卻和暖如春纱烘，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背祈餐。一陣腳步聲響...
開封第一講書人閱讀 33,139評論 1贊 272
情欲美人皮
我被黑心中介騙來泰國打工擂啥，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人帆阳。一個月前我還...
沈念sama閱讀 48,377評論 3贊 373
代替公主和親
正文我出身青樓哺壶，卻偏偏與公主長得像，于是被迫代替她去往敵國和親蜒谤。傳聞我的和親對象是個殘疾皇子山宾，可洞房花燭夜當晚...
茶點故事閱讀 45,060評論 2贊 355