本文簡要敘述當前流行的Bregman迭代算法的一些原理。

1、簡介

近年來，由于壓縮感知的引入，L1正則化優化問題引起人們廣泛的關注。壓縮感知，允許通過少量的數據就可以重建圖像信號。L1正則化問題是凸優化中的經典課題，用傳統的方法難以求解。我們先從經典的圖像復原問題引入：

在圖像復原中，一種通用的模型可以描述如下：?
?e.q.(1)

f：觀測到的圖像（m維向量）?
u：未知的真實圖像（n維向量）?
A：線性算子，例如反卷積問題中的卷積算子，壓縮感知中則是子采樣測量算子。?

：噪聲，通常是高斯加性白噪聲。方差為：sigma^2。?

目標：由f得到u。

在式（1）中，我們僅知道觀察到的圖像f，其他的一概不知。因此這種問題是病態的，我們可以通過正則化把它變成良態的。

正則化方法：?
假定對未知的參數 μ 引入一個先驗的假設，例如稀疏性，平滑性。正則化問題的常見方法Tikhonov方法，它通過求解下面的優化問題：?

其中 μ 是一個大于零的標量，事先設定的常數，用于權衡觀測圖像f和正則項之間的平衡。雙絕對值符號是L2范數。L2條件約束。

下面，為了引入Bregman迭代算法，需要對兩個重要的概念進行描述（次梯度和Bregman距離）。

2、Bregman距離

這里先復習一下梯度和導數的概念：

導數：lim(△x->0) ( f(x+△x) - f(x) ) / △x?
方向導數：lim( dis(P0,P1) ->0) ( f(P1) - f(P0) ) / dis(P0,P1)。。上面講的導數就是沿著 x 軸 方向的方向導數。?
！！導數是 f(x) 在某個方向的變化率，是一個值，標量。

梯度：沿方向導數最大值的方向，大小為該方向導數的值。?
！！梯度是一個向量。

次梯度

subgradient（次梯度，又稱子梯度、弱梯度等），?
泛函 J 在 u 點的次梯度定義如下：?

J： X->R， 凸函數。?
u：作用域X中的一點。?
v：作用域 X 中的任一點。?
p：X 的對偶空間 X* 的中的某一點。?
： 是內積運算。如果泛函 J 是簡單的一元函數，則就是兩個實數相乘。

J 在 u 點的所有次梯度的集合成為 J 在 u 點的次微分，記為。

次梯度有什么好處呢？?
對于一般的導數定義，例如 y=|x| 在0點是不可導的，但是對于次梯度，它是存在的。

Bregman距離

點u和v之間的Bregman距離定義如下：?

J：X->R， 凸函數。?
。。所以 p 是 J 在 u 點的一個次梯度。?
凸函數兩個點u，v之間的Bregman距離：等于其函數值之差，再減去其次梯度點p與自變量之差的內積。

注意：這個距離不滿足對稱性，這和一般的泛函分析中距離定義是不一樣的。

！！Bregman 距離有一些十分良好的性質，使得他在解決 L1 正則化問題時十分有效。

2. ?Bregman距離

? ? ? ? ? ??

? ? ? ? ? ? 注意這個定義，它是對泛函J在u點的subgradient的定義，p點是其對偶空間的中的某一點。subgradient可以翻譯為次梯度，子梯度，弱梯度等。等式左邊最右邊一項是內積運算。如果泛函J是簡單的一元函數，則就是兩個實數相乘。次梯度有什么好處呢？對于一般的導數定義，例如y=|x|在0點是不可導的，但是對于次梯度，它是存在的。

? ? ??? ? ? ?

? ? ? ? ? ? ? ? 上面的這個定義就是Bregman距離的定義。對于凸函數兩個點u，v之間的Bregman距離，等于其函數值之差，再減去其次梯度點p與自變量之差的內積。要注意的是這個距離不滿足對稱性，這和一般的泛函分析中距離定義是不一樣的。

? ?

3、Bregman迭代算法

要解決的問題：求u(最小化)

Bregman迭代算法可以高效的求解下面的泛函的最小值問題。

J：X->R， 凸函數，非負。u∈X。?
H：X->R， 凸函數，非負。u∈X，f 是已知常數（通常是一個觀察得到的圖像數據，是矩陣或向量）。?
X：作用域，是凸集也是閉集。

注意：上述泛函會根據具體問題的不同具有不同的具體表達式。例如，對于簡介中的圖像復原問題， J(u) 是平滑先驗約束，是正則化項；而H則是數據項。

Bregman迭代算法

首先，初始化相關的參數為零；?
然后，再迭代公式u。。直到 uk 滿足收斂條件。?
u，左邊一項是泛函 J 的Bregman距離。?
p，右邊一項是泛函 H 的梯度（次梯度）。

可以看出：?
·?第一次迭代，?
u1=argmin(u) { D(u, 0) + H(u) }， 其中D(u, 0)=J(u) - J(0) - <0, u>=J(u)?
?
·?再經過多次的迭代，?
就能夠收斂到真實的最優解。

對于具體的問題:?
定義的具體形式是不同的。?
例如對于壓縮感知使用的基追蹤算法，J是L1范數；?

而對于圖像去噪問題，可能就是u的梯度L1范數，同時A也變成了恒等算子了。

3. ?Bregman迭代算法?

? ? ? ? Bregman迭代算法可以高效的求解下面的泛函的最小?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ?

? ? ? ?上式中的第一項J，定義為從X到R的泛函，其定義域X是凸集也是閉集。第二項H，定義為從X到R的非負可微泛函，f是已知量，并且通常是一個觀測圖像的數據，所以f是矩陣或者向量。上述泛函會根據具體問題的不同具有不同的具體表達式。例如，對于簡介中的圖像復原啊問題，J(u)就是平滑先驗約束，是正則化項；而H則是數據項。

?

? ? ?Bregman迭代算法首先是初始化相關的參數為零，再迭代公式u，其左邊一項是泛函J的Bregman距離。再來看p點的迭代公式，其最右邊一項是泛函H的梯度。

? ? ?其迭代一次產生的輸出是公式3.2，經過多次的迭代，就能夠收斂到真實的最優解。這個證明過程可以參考后面的文獻。

? ? ?對于具體的問題，泛函3.1定義的具體形式是不同的。例如對于壓縮感知使用的基追蹤算法，J是L1范數。而對于圖像去噪問題，可能就是u的梯度L1范數，同時A也變成了恒等算子了。

4、線性Bregman迭代算法

Bregman算法對于基追蹤問題來說是一種很好的工具。但是，算法中的每一步都要求解公式的最小值，從而使得計算復雜度非常高。?
因此提出了——

線性Bregman迭代算法推導

首先，利用矩陣的泰勒公式，將公式?
?
中的 H(u) 線性展開，得到：

但是這種近似展開只有在u和uk十分接近的時候上式才準確。因此，把泰勒公式中的二次項加上，則原來的問題就變成了：

可以看到，二次項可以使 u 和 uk 很靠近。因為向量的平方就是L2范數的平方。

又因為：?

注意??和??是關于 u 的常數。

所以，?

考慮基追蹤算法，令 H(u) =

得到：?

考慮該式的一個特殊情況，?。并將pk回代，得到：

C是一個常量，與uk有關的常量。uk也是一個常量。

分3種情況來考慮 u，則?

進一步整理，得到：?

定義shrink算子，當a>0時，有：?

線性Bregman算法總結

4. 線性Bregman迭代算法

Bregman 迭代算法的每一步迭代都要求解泛函4.1的最小值，這一步的計算代價是很高的。線性Bregman迭代的思路是對泛函4.1的第二項進行線性展開，根據矩陣函數的泰勒公式，泛函4.1的第二項可以展開為上面4.2的形式。

? ? ? ? ?注意，上述公式4.2省略了泰勒公式中二次項。把二次項加上，帶入前面基本的Bregman迭代算法公式的第一步，我們得到公式4.3。如果我們計算4.3和4.4中間那個表達式，比較其相同項，很容易得到公式4.4.

? ? ? ? ?如果我們考慮基追蹤算法，則H等于 ||Au - f||^2 /2, 將H的導數帶入公式4.4,我們得到公式4.5, 公式4.6是基本Bregman迭代算法的第二步，注意上述4.6公式中u的上標是錯的，應該改為 k+1 ，這樣才可能得到公式4.7，公式4.8，4.9, 4.10, 4.11都是顯而易見的。

? ? ? ? ? 下面我們把4.11和前面定義的Bregman距離帶入到4.5里面去,具體如下：

? ? ? 在上面的推導中，u_k是常量，C是與u_k有關的一個常量，將上式對u求導，由于有絕對值項，所以要分開討論，得到上面這個分段表達式。進一步整理得到：

? ? ? ? ? ? ?這里，我們定義了一個shrink操作，這個收縮算子很重要，在后面所有的Bregman算法中都有這個操作。根據這個操作，我們導出下面的表達式，并最終把線性Bregman迭代算法總結如下：

5. ?Split Bregman 算法

? ? ? ? ?Split Bregman 算法是另一種高效的算法。我們已經知道，Bregman迭代算法用于求解下面的凸優化問題：

? ? ? ? ? ? ? ? ? ? ??

? ? ?我們可以把上面的表達式變換為下面的等價形式：

? ? ?這一步，看似是多此一舉，但是Bregman經過推導，得出了一種高效的迭代算法，分裂Bregman迭代。

? ? ?上面的5.2是一個等式約束優化問題，把它轉化為無約束優化問題如下：

? ? ? ? 上面這個公式中，優化變量多了一個d。做如下的變量替換：

?如果我們對5.5，應用最前面提到Bregman 迭代算法，很容易寫出下面的迭代序列：

? ? 式5.9是根據5-6按照Bregman距離展開的結果。式5.7,5.7后面一項是對5-5分別對u，d求其偏導數得到。如果我們對5.7迭代展開，于是得到：

?同理，對于5.8，有

? ? ? ? ? ? ? ? ? ?

?

注意到式5.11和5.12有一個公共的SIGMA求和項，把它重新定義如下：

? ? 把5.14,5.15帶入5.9，具體如下：

? ? ? ? ? 在對5.16的化簡中，要注意的是u，d為變量，其它看做常量。

? ? ? ? ? 到此，我們可以給出Split Bregman迭代算法的通用優化步驟：

? ? ? ? ? 對u的迭代，把u看做自變量，其它所有變量看做常數，對d的迭代則是d為自變量，其它變量都是常數。?之所以說是通用迭代優化過程，是因為對于具體的問題，其迭代的具體表達式不同。例如，對于基于各向異性TV的去噪模型，各向同性TV去噪模型，其迭代的具體表達式是不同的。

總結

以上是生活随笔為你收集整理的Split-Bregman迭代方式的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。