淺談凸優化問題中的Bregman迭代演算法

淺談凸優化問題中的Bregman迭代演算法

        對於搞影象處理的人而言,不懂變分法,基本上,就沒法讀懂影象處理的一些經典文獻。當然,這已經是10年之前的事情了。

         現在,如果不懂得Bregman迭代演算法,也就沒法讀懂最近幾年以來發表的影象處理的前沿論文了。國內的參考文獻,基本上都是直接引用Bregman迭代演算法本身,而對於其原理基本上找不到較為詳細的論述。本文簡要敘述當前流行的Bregman迭代演算法的一些原理。

    

1. 簡介

         近年來,由於壓縮感知的引入,L1正則化優化問題引起人們廣泛的關注。壓縮感知,允許通過少量的資料就可以重建影象訊號。L1正則化問題是凸優化中的經典課題,用傳統的方法難以求解。我們先從經典的影象復原問題引入:

        在影象復原中,一種通用的模型可以描述如下:    

   

         我們目標是從觀測到的影象f,尋找未知的真實影象u,u是n維向量空間中的元素,f是m維向量空間中的元素。f 在壓縮感知的術語叫做測量訊號。 是高斯白噪聲其方差為sigma^2。A是線性運算元,例如反摺積問題中的卷積運算元,壓縮感知中則是子取樣測量運算元。

        

          上述方程中,我們僅僅知道f,其它變數都不知道的。而且這種問題通常情況都是病態的,通過引入正則項可以使之成為良態的。正則化方法假定對未知的引數u引入一個先驗的假設,例如稀疏性,平滑性。正則化問題的常見方法Tikhonov方法,它通過求解下面的優化問題:

                                                                                                    

        其中mu是一個大於零的標量,事先設定的常數,用於權衡觀測影象f和正則項之間的平衡。雙絕對值符號是L2範數。

    

        下面,為了引入Bregman迭代演算法,需要對兩個重要的概念進行描述。

2.  Bregman距離

            

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

             

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

   

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 迭代演算法的每一步迭代都要求解泛函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去噪模型,其迭代的具體表示式是不同的。

最後列出本文的參考文獻如下:

http://download.csdn.net/detail/celerychen2009/5552551