基于Bregman迭代的l_1模極小化方法及其應用

1、中圖分類號：TN911單位代碼：10425學 號：S11090936I十閡石冷Z孝工程碩士學位論文China University of PetroleumDegree Thesis of Engineering Master基于Bregman迭代的，i模極小化方法及其應用Zj-norm Minimization MethodBased on Bregman Iteration and Its Applications學科專業(yè)：數(shù)學研究方向：非線性微分方程理論及其數(shù)值解法作者姓名：金富國指導教師：徐亞飛 高級工程師李維國教授二。一四年五月I -norm Minimization Method1

2、Based on Bregman Iteration and Its ApplicationsA Thesis Submitted for the Degree of MasterCandidate： Jin FuguoSupervisor： Prof. Xu YafeiProf. Li WeiguoCollege of ScienceChina University of Petroleum (EastChina)關(guān)于學位論文的獨創(chuàng)性聲明本人鄭重聲明：所呈交的論文是本人在指導教師指導下獨立進行研究工作所取得 的成果，論文中有關(guān)資料和數(shù)據(jù)是實事求是的。盡我所知，除文中已經(jīng)加以標注和致 謝外，本

3、論文不包含其他人已經(jīng)發(fā)表或撰寫的研究成果，也不包含本人或他人為獲得 中國石油大學（華東）或其它教育機構(gòu)的學位或?qū)W歷證書而使用過的材料。與我一同 工作的同志對研究所做的任何貢獻均己在論文中作出了明確的說明。若有不實之處，本人愿意承擔相關(guān)法律責任。學位論文作者簽名： 日期： 年 月 日學位論文使用授權(quán)書本人完全同意中國石油大學（華東）有權(quán)使用本學位論文（包括但不限于其 印刷版和電子版），使用方式包括但不限于：保留學位論文，按規(guī)定向國家有關(guān) 部門（機構(gòu)）送交、贈送和交換學位論文，允許學位論文被查閱、借閱和復印， 將學位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進行檢索，采用影印、縮印或其他 復制手段保存學位

4、論文。保密學位論文在解密后的使用授權(quán)同上。學位論文作者簽名：指導教師簽名：日期：年月日日期：年月日摘要隨著Bregman正則化理論的提出與發(fā)展，該理論在以稀疏表示為核心的信號與圖像 處理等領(lǐng)域有著重大應用價值，并成為研究者關(guān)注的焦點。本文主要基于4范數(shù)最優(yōu)化 理論與Bregman迭代，研究基追蹤問題求解算法以及相關(guān)算法在信號與圖像處理方面的 應用，其主要研究成果及創(chuàng)新點有以下三方面：第一：利用矩陣廣義逆等理論，給出基追蹤問題的另一種等價形式，然后通過等價 形式對基追蹤問題求解進行研究，推導出A+線性Bregman迭代公式。第二：對于解決在壓縮感知領(lǐng)域中常見的基追蹤問題min| :Au = g,

5、uER我們 提出一種簡單快速的方法。這種方法是基于線性Bregman方法等價于對偶梯度下降方 法，并給出收斂性分析，同時，提出一種加速A+線性Bregman迭代算法來解決基追蹤 問題,并且對4線性Bregman迭代算法的迭代復雜度進行了分析，展示為獲得一 丁最優(yōu) 解，新方法將迭代復雜度為從。4）降低到。（-）。數(shù)值試驗表明：新方法可以在稀疏8寸信號恢復問題上，能夠比較準確地從觀測信號中重構(gòu)信號，并且與A+線性Bregman迭 代算法相比，具有速度快，迭代次數(shù)少，可有效地減少停滯現(xiàn)象等優(yōu)點。第三：由于對范數(shù)約束的基追蹤模型在圖像與信號恢復上的缺點，把A范數(shù)約束 改為4范數(shù)約束，給出4范數(shù)約束的基

6、追蹤問題模型，給出新模型的Bregman迭代方法, 在數(shù)值試驗方面，從圖像與信號恢復兩個角度展現(xiàn)新模型不僅能從含噪聲的條件下重構(gòu) 出原信號，而且迭代次數(shù)與迭代時間顯著減少。關(guān)鍵詞：基追蹤問題，Bregman迭代，A*線性Bregman迭代，梯度下降方法，加 速A+線性Bregman迭代/, -norm Minimization Method Based on Bregman Iterationand Its ApplicationsJinFuguo(Mathematics)Directed by Piof. XuYafei and Li WeiguoAbstractWith the devel

7、opment of regularization Bregman iteration and its theory. The theory on the sparse representation, which is the core of the signal and image processing field has an important application value, and becomes many scholars fbcus of study. This dissertation is mainly based the optimization theory about

8、 the /, -norm and Bregman iteration, studies the algorithms of the basis pursuit problem and the applications in image and signal processing fields. The main research results and innovations consist of three parts:Firstly, making use of the matrix theory, we give out an equivalent form of the basis

9、pursuit problem, then solve the problem of the equivalent form, and deduce the A+ linearized Bregman iterative.Secondly, We propose simple and extremely efficient methods for solving the basis pursuit problem: Au = g,u &R, which is used in compressed sensing. We prove that the linearized Bregman wit

10、h some steps is equivalent to the dual problem and provide a convergence analysis for the linearized Bregman with some steps. We can find one way to accelerate the A+ linearized Bregman method for solving the basis and related sparse optimization problems. We show that the new method can reduce this

11、 iteration complexityNumerical results are presented that for sparse signal recovery problems,the new algorithm can reconstruct signal exactly from the observational signal. Meanwhile. The new method can be faster, less iterative steps, specially, reduce the stagnation of iterative procedure efficie

12、ntly compared with the A+ linearized Bregman iterative procedure.At last, because of some faults about /2 norm constraint in image and signal processing fields, we change the /, -norm constraint into -norm constraint. Simultaneously, a new model of the split Bregman iterative algorithm is deduced. T

13、he numerical results show that the new model can reconstruct the origin signal from the noise signal in both image and signal processing. At the same time, the number of iteration and iterative time are significantly reduced.Key words: the basis pursuit problem, Bregman iteration, A+ linearized Breg

14、maniteration, Gradient descent method, Accelerated A+ linearized Bregman iteration TOC o 1-5 h z HYPERLINK l bookmark22 o Current Document 第一章緒論1 HYPERLINK l bookmark25 o Current Document 1.1研究背景及意義1 HYPERLINK l bookmark28 o Current Document 1.2國內(nèi)外研究現(xiàn)狀概述2 HYPERLINK l bookmark34 o Current Document 13

15、本文的主要內(nèi)容及安排4 HYPERLINK l bookmark37 o Current Document 第二章 基于Bregman距離的迭代預備知識5 HYPERLINK l bookmark40 o Current Document Bregman 迭代6 HYPERLINK l bookmark45 o Current Document 線性 Bregman 迭代方法8 HYPERLINK l bookmark54 o Current Document 23 分裂 Bregman 迭代方法9 HYPERLINK l bookmark63 o Current Document 第三章 基

16、追蹤A+線性Bregman迭代11 HYPERLINK l bookmark75 o Current Document 第四章 加速A*線性Bregman迭代方法14 HYPERLINK l bookmark78 o Current Document 4.1新方法的推導14 HYPERLINK l bookmark84 o Current Document 加速 A*線性 Bregman 迭代19 HYPERLINK l bookmark87 o Current Document 43數(shù)值結(jié)果23 HYPERLINK l bookmark90 o Current Document 第五章4范數(shù)

17、約束的加速分裂Bregman迭代算法27 HYPERLINK l bookmark93 o Current Document 5.1新模型建立27 HYPERLINK l bookmark96 o Current Document 5.2新模型的加速分裂Bregman迭代方法27 HYPERLINK l bookmark99 o Current Document 5.3數(shù)值試驗30 HYPERLINK l bookmark102 o Current Document 第六章結(jié)論與展望33 HYPERLINK l bookmark105 o Current Document 6.1主要創(chuàng)新點33

18、 HYPERLINK l bookmark108 o Current Document 6.2后續(xù)研究工作展望33 HYPERLINK l bookmark111 o Current Document 參考文獻27 HYPERLINK l bookmark155 o Current Document 碩士研究生期間取得的學術(shù)成果37 HYPERLINK l bookmark160 o Current Document 致謝38第一章緒論1.1研究背景及意義在過去的50年里，信號處理已經(jīng)發(fā)展成為一門活躍的多學科領(lǐng)域的科學，其覆蓋 了數(shù)學、統(tǒng)計、工程及計算科學等多學科的知識內(nèi)容。隨著對信號處理領(lǐng)域

19、的不斷深入, 信號的稀疏表示有著重要的應用價值。我們的目標是如何通過信號的稀疏表示來獲得更 好的原信號。同時由于4模具有稀疏性等特性，從而引發(fā)了對含有4模的最小化問題的 密切關(guān)注。事實上，早在80年代Fadil Santosa和William Symes就提出了 模的最小化 問題，然而由于4模的不可微性，使得極小化含有4模的問題時無法滿足優(yōu)化條件，從 而在計算方面存在著很大的困難，所以4模未得到廣泛的運用。1998年，Donoho對信號稀疏處理問題提出了一種新的原理基追蹤原理。基追 蹤目的可以概括的說是尋找下面帶4模約束的最小優(yōu)化問題：min(H：AW=g(1-1)利用凸優(yōu)化知識，建立合理模型

20、尋找信號的稀疏表示，簡言之，用最低限度的基來 準確地重構(gòu)表示出原信號，進而獲得信號本質(zhì)特征。由于4模的存在，使得這種優(yōu)化原理具有許多優(yōu)點，特別是與其他常用模相比，例 如：在信號處理方面，由于4模的光滑性沒有模的好，并且不易求解，但是通過4模 求得的解具有稀疏性，并且能夠很好地用最少的信息量表達出最優(yōu)的信號；在圖像去噪 方面，模的光滑性會使得圖像在去噪過程中變的模糊，而運用4模不僅能夠很好的去 噪而且還能保留細節(jié)和紋理等特征。而且，我們知道通過4模求解問題所得到的解具有 很好的稀疏性，雖然在適當?shù)臈l件下極小化4模問題等價于極小化零模問題，但是在計 算方面，前者要比后者更容易駕馭。此外，由于上述極

21、小優(yōu)化原理是一個全局凸優(yōu)化問 題，因此能夠具有很穩(wěn)定的超分辨率。極小化4模的應用與極小化其他模的應用相比很長時間以來被認為是獲得稀疏解得 一種實際有效的途徑，從而模也被廣泛的應用到信號處理、統(tǒng)計以及其他相關(guān)領(lǐng)域的 特征提取等方面。尤其是在2006年左右，Donoho、Cabdes以及Tao*在信號稀疏情形下提出了一種 新的信息獲取理論壓縮感知(Compressed Sensing, CS)O這種新的信息理論與傳統(tǒng) 的Shannon信息論有著很大的差別。由于求解信號的稀疏表達問題應用前景很大，這就 使得f模的最小化問題備受關(guān)注，從而使得國內(nèi)外學者開始對含模的最小優(yōu)化問題及 其相關(guān)求解方法進行深入

22、研究。此外，變模極小化問題還被廣泛的應用于壓縮圖像、MRI和CT、多感網(wǎng)絡和分布 感知、模擬到信息的轉(zhuǎn)化、生物傳感器和芯片處理，此外4模極小化問題還被用于圖像 分解和計算機視覺任務、圖像修復和丟失數(shù)據(jù)恢復等等圖像處理領(lǐng)域。匕模極小化問題 也因此變得越來越備受關(guān)注。通過上述分析可見，關(guān)于4模極小化問題的深入研究無論在理論還是實際應用中都 具有廣闊的前景和重要的意義。4模極小化問題的研究來源導師主持國家自然科學基金 項目的部分內(nèi)容。1.2國內(nèi)外研究現(xiàn)狀概述國外，1998年Donoho對求解信號稀疏問題提出了一種新方法，并建立模型一一基 追蹤模型，求解基追蹤問題就是求解一個帶有約束的4模極小化問題。

23、實際上到目前 為止，對目標信號的稀疏恢復，最成功的就是基于4模的基追蹤問題。現(xiàn)在，基追蹤在 一維信號處理、圖像去噪與去模糊等領(lǐng)域都有廣泛應用，并取得一定的效果，尤其以 David L.Donoho為代表的斯坦福大學統(tǒng)計系工作組利用基追蹤原理在一維信號去噪和 超分辨率方面取得重大突破。模的最小化問題本身是一個不可微凸優(yōu)化問題，因此對不可微凸優(yōu)化問題的求解方 法也是適用于L模的最小化問題的求解。如：1985年，N.Z.Shor提出的橢圓體方法或次 梯度方法，但是這些方法本身求解的速度比較慢，不適合大規(guī)模的4模極小化問題的 求解。在一定限制條件下，4模的最小化問題等價于線性規(guī)劃問題，由于對線性規(guī)劃問

24、題 的研究相對比較成熟，因此許多求解線性規(guī)劃問題的理論與方法可以用來求解A模極小 化問題。1999年，David等人將基追蹤關(guān)于4模的最小化問題等價于線性規(guī)劃問題， 并采用內(nèi)點法E求解了A模的最小化問題。雖然內(nèi)點法收斂性能比較穩(wěn)定，數(shù)值試驗效 果還可以，但是由于它是一種大規(guī)模、大尺度的線性算法，算法的迭代復雜度高，所耗 費的計算時間非常的長，總體代價很高，所以它實際應用價值不高。此外，在內(nèi)點法的 基礎(chǔ)上又出現(xiàn)了許多改進的方法，如：適合于小中型問題的標準內(nèi)點法罔和適合于大規(guī) 模問題的特殊內(nèi)點法9等，而且在標準內(nèi)點法的實施過程中可以運用迭代算法來計算搜 索步，如CG和LSOR算法。2000年，M.

25、Osborne等在對最小二乘問題變量選擇方面瞰得的重大突破，提出了 一種新的方法一一同態(tài)算法，這種方法在計算復雜度方面相對較低，同樣也被用于求解 A模極小化問題。此外，最近出現(xiàn)的算法還有：CDM方法、序列子空間優(yōu)化方法U3、有界優(yōu)化方 法Ml、迭代壓縮方法回、梯度投影方法不動點連續(xù)方法W，2。和Bregman迭代方 法21-26等，這些方法都能夠應用于大規(guī)模模極小化問題的求解。到目前為止，在基追蹤求解方面，給予關(guān)注最多的是不動點連續(xù)迭代方法a和 Bregman迭代方法21260它們被認為是一種求解4模最小化方法問題的非常有效的方法 而且這些方法的適應范圍也非常廣泛。Cait22等人推導線性Br

26、egman迭代方法，具有以下優(yōu)點:矩陣向量乘法與取閾值操作 便于編程，耗費時間較少。同時，運用光滑函數(shù)思想，對其迭代的收斂性進行了研究， 證明線性Bregman迭代產(chǎn)生的序列收斂到以下問題的解，并且解是唯一的:(1-2)瀏響+陽呻:而=8其中H為4范數(shù)，8均為參數(shù)，并且證明了當時，序列的極限趨于(1-1) 的一個解。根據(jù)線性Bregman迭代產(chǎn)生的序列的性質(zhì)，Cai等人證明其收斂性的】。收斂 性的證明對線性Bregman迭代的廣泛應用打下了很好地基礎(chǔ)。但是在進行數(shù)值試驗時發(fā) 現(xiàn)線性Bregman迭代出現(xiàn)滯留現(xiàn)象心】，大大減少了收斂速度。為克服這一缺點，引入“剔 除技巧，這大大減少了停滯現(xiàn)象出現(xiàn)

27、的概率，并且提高收斂速度。由于線性Bregman 迭代局限性，受交替方向法啟發(fā)，GlodSteint25引入了分裂的Bregman迭代方法，此方 法在圖像去噪等方面效果顯著。Cai等人從物理角度出發(fā)對線性Bregman迭代過程進行 了解釋，并且從譜范數(shù)性質(zhì)出發(fā)，對線性Bregman迭代的迭代算法進行了一些處理，顯 著加快了收斂速度,并從另外一個角度證明其迭代算法收斂。到目前為止，國內(nèi)關(guān)于這方面的文章較少，但是由于Bregman迭代所特有的理論與 應用優(yōu)勢，漸漸引起了國內(nèi)研究人員關(guān)注。國防科學技術(shù)大學成禮智教授指導的學生張 慧等人在文獻27將矩陣的廣義逆EH、矩陣分解等技巧巧妙地引入線性Breg

28、man迭代， 大大簡化線性Bregman收斂性的證明，此外文章最后提出加速A*線性Bregman迭代， 但未對其進入深入研究。1.3本文的主要內(nèi)容及安排本文主要以Bregman迭代理論為基礎(chǔ)研究含 模的極小化問題，尤其對基追蹤問題。 通過系統(tǒng)的相關(guān)總結(jié)和研究，利用矩陣方面的一些知識，提出相關(guān)新的迭代算法。此外, 本文對原有算法的有關(guān)細節(jié)進行相關(guān)改進，從對偶梯度下降方法進行分析，改善原有算 法。此論文主要由以下六章組成：第一章，首先大體介紹了本文研究的背景及意義，總結(jié)國內(nèi)外對Bregman迭代方法 相關(guān)理論與方法，為提出新的算法做必要的準備；此外對本論文安排做了相關(guān)介紹。第二章，介紹相關(guān)Breg

29、man迭代方法理論來源以及其相關(guān)的迭代公式，并對各類方 法的優(yōu)勢進行了闡述，同時介紹相關(guān)的收斂性結(jié)論。第三章，給出基追蹤問題的另一種等價形式，然后通過等價形式對基追蹤問題求解 進行研究，推導出A*線性Bregman迭代公式。第四章，提出一種新的求解基追蹤問題的方法加速4線性Bregman方法，然 后對其迭代復雜度、收斂性進一步進行分析，以稀疏信號恢復問題為例進行相關(guān)數(shù)值試 驗，結(jié)合數(shù)值試驗結(jié)果，與A*線性Bregman迭代進行比較，分析新算法的效率。第五章，由于對L范數(shù)約束的基追蹤模型在圖像與信號恢復上的缺點，把L范數(shù)約 束改為4范數(shù)約束，給出4范數(shù)約束的基追蹤問題模型，給出新模型的Bregm

30、an迭代方 法，接下來在數(shù)值試驗方面，從圖像與信號恢復兩個角度展現(xiàn)新模型不僅能從含噪聲的 條件下重構(gòu)出原信號，而且迭代次數(shù)與迭代時間顯著減少。第六章，總結(jié)本文研究成果以及對以后的研究工作進行展望。第二章 基于Bregman距離的迭代預備知識Bregman迭代正則化方法，無論是在壓縮感知理論還是在信號與圖像處理中，均有 重要的研究價值。本章首先回顧一下描述Bregman迭代方法和線性Bregman迭代方法 等內(nèi)容的一些基礎(chǔ)知識。定義2.1設(shè)凸函數(shù)J(x):RJR,如果向量peR滿足：J(u) /(v)+ 則稱向量P為函數(shù)J(x)在V處的次梯度，所有在V處的次梯度的集合記為渺(u),并 稱為J(x

31、)在U處的次微分。其中向量p e R為次微分渺(V)中的一個次梯度。定義2.2t22設(shè)/為凸函數(shù)，則u,veRn；兩點的關(guān)于/的Bregman距離定義為：Dj= J(u) J(y) 其中，向量P崩J(v)為J在u處的次梯度。注意并不是一般意義上的距離, 因為u)主 W)，但D；(u, v) 0 D；(u,v)D；(w,v)對位于，的線段上任意的 點w都成立，可見它是對，u遠近程度的一種度量。定義2.332設(shè)A e Rmxn,稱矩陣B e Rnxm是A的Moore-Penrose廣義逆，記為妒，如 果滿足以下四個條件(常稱為Moore-Penrose條件)：(1) ABA = A, (2) BA

32、B = B, (3)(AB)T = AB, (4)(時=BAA1,3表示滿足和的矩陣BeRnxm的集合，則稱為A的1,3逆，可以表示 為f定義2.4如果aeR,矩陣P e Rnxn ,是對稱半正定的，則可定義如下加權(quán)半范數(shù)： = J# Pa加權(quán)半范數(shù)滿足以下三條性質(zhì)：網(wǎng),NO網(wǎng)產(chǎn)神IL(3) |奸琲珈IL+帆定理2主32設(shè)AeR心,ueRn, g* ,則當u = A(13)g時，|初-訕最小。對于線 性系統(tǒng)A = g,向量是一個最小二乘解當且僅當Au = AA(,3g從而，最小二乘解的通解為：u=Ag + (In-AA)z,e Rn特別地，我們可以選擇占作為某一個A(h3) o對于 =arg

33、min|A”由定理2.1知其通解可表示為：ueRH =A+g + (/, -A+A)z,SR(2-1)上式等價于A+Au=A+g(2-2)2.1 Bregman 迭代Bregman迭代是2005年Osher等人在研究圖像去噪時提出的一種新型的迭代正則 化方法，此方法在壓縮感知、信號與圖像處理等領(lǐng)域有著廣泛應用，同時取得很好地效 果。對一幅未知的灰度圖像，其全變分(Total Variation.可以寫成TV)定義為：J(w) :=7V(w) = j|Vw|其中，表示梯度算子，則全變分去噪ROF (Rudin-OsherFatemi)模型網(wǎng)為：min/()+-|w-|(2-3)“2/z其中，日為

34、正則化參數(shù)，g表示對清晰圖像，加噪后的噪聲圖像。(2-3)模型的求解備受關(guān)注。2005年，Osher等人在文獻17中引入了 Bregman距A+1離，提出了如下迭代模型3。：k =0,1,2,其中，0=p0=0。正則化技巧是ROF模型和Bregman迭代正則化方法的主要區(qū)別：ROF只是通過直 接極小化全變分來正則化，而Bregman迭代正則化則是極小化與*之間的Bregman 距離。由于全變分J()并非處處可微使得/(“)的次微分渺(x)包含多個次梯度，導致 Bregman迭代過程中關(guān)于次梯度P的選擇有多個，但是根據(jù)凸優(yōu)化理論，P可由前一步 迭代的結(jié)果P*唯一確定。事實上，設(shè)廣是Bregman

35、迭代正則化，第k步迭代的最優(yōu)解, 則 0 _ P* +廿朽 _ f ,因此可以取 pA+1 := pk +f-uk+x eJ(wA+l) o 此外，文獻17還證明了由Bregman迭代正則化生成的序列*：HII單調(diào)收斂于0當p-/|w-/|時，必按Bregman距離D； (u,uk)單調(diào)趨于無噪聲圖像訂。 因此，可以根據(jù)第二個結(jié)論設(shè)計迭代的停止準則，即|帕-| N b就|w-/|時Bergman迭代停止，其中為噪聲水平的估計。在圖像去噪方面，文獻17給出了 Bregman迭代 正則化具體數(shù)值試驗。一般的問題minJ(W) + 2/f(W),其中/()為凸函數(shù)，H(u)為可微的凸函數(shù)。Osher

36、 等人在文獻17中給出了 Bregman迭代正則化過程：Step 1 初始化：k =0 , u = 0 ,= 0 ；Step2 : whilenot converge, douk+min D/u,uk)+AH(u)；upZ - pk _ 沱H (z ) e dJ (“z )；k -k + l；end while此外，Wotao Yin針對基追蹤問題，即J(w) = /z|w|i, H(u) =i|A-/|2的情況給出了兩種迭代形式：情形一：必 0, p 0 ；For Z: =0,1,- douk+ min D/ (m,ma)4-|Am /|2(2-4)pip*_A+T)(2-5)情形二：必 -

37、0,p-0；For k = 0,1,- dofk+f + (fk-Auk)(2_6)uk+ argmin J(m)+|a /A+1|2(2-7)情形二可以理解為“將殘量加回去：將r+，：=f+(fk-uk )理解為新的噪聲圖像，則第二章 基于Bregman距離的迭代預備知識Bregman迭代正則化方法求解的每一步迭代均可簡化為ROF模型，其中。=/=0；文 中證明了這兩種情形的等價性，同時還給出了 Bregman迭代的收斂性的證明。2.2線性Bregman迭代方法Darbon和Osher在求解圖像去模糊時提出的一種新正則化方法 線性Bregman 迭代。該方法是對Bregman迭代的最后項進行

38、線性簡化，由于僅僅涉及向量與矩陣相乘 運算，易便于編程，同時，在理論研究方面取得了很多成果，多方面原因使其得到廣泛 應用。結(jié)合不動點連續(xù)迭代方法和Bregman迭代方法】，Cait22等人最近針對基追蹤問 題提出了一種線性的Bregman迭代方法，其迭代公式為：vA+1 = vk (Auk g)疽=%($產(chǎn))其中，u =v =0, a(w):=w(l)禹(w(2),為軟閾值算子，且0sgn(f)(回-;l)該算法非常的簡單，僅涉及到矩陣向量乘和尺度壓縮。對于矩陣向量乘可以通過快 速的算法來提高整個迭代算法的速度，而通過壓縮算子又可以實現(xiàn)解稀疏性和去噪能 力，Cai23給出了該迭代算法的收斂證明

39、。Cai等人對上述迭代算法進行規(guī)范化，即令 廿十=人言 ,得到一種變形的線性的Bregman迭代方法：妒* =8 +(g_ 時)疽=以以，舟)但是該迭代針對A是滿秩并且有AAr=I的情形提出的。實際中，大部分問題里的 矩陣A并不具有這樣的性質(zhì)，于是文章中對，但A仍是滿秩的情況給出一種修 正的線性Bregman迭代方法：gk+1 =gk +(gAuk)F =竺心其中，A*為A的Moore-Penrose廣義逆，其滿足四個條件：AX4 = A, X4X = X, (AX)T = AX , (X4)r = XA在該迭代的第二步中，仍可以利用壓縮算子來壓縮極小化L模解來獲得稀疏性解并 同時達到去噪的目

40、的，但這一步也對極小化的Z,模解引入了誤差。2.3分裂Bregman迭代方法最近，4模極小化問題由于壓縮感知的引入得到了廣泛的關(guān)注，但是仍然還有許多 的問題有待解決，特別是對一些特殊的問題還需要特殊的技巧。針對經(jīng)典的基追蹤問題, 線性Bregman迭代可以很好的求解，但是在工程、計算機科學和圖像處理中，經(jīng)常會遇 到下面更一般的4模極小化問題：nyin|(D()J| + H()(2-8)其中 g):R TR”,且|()|t為凸可微的向量值函數(shù)，H()為凸函數(shù)。不難看出，該 問題是基追蹤問題的更一般形式。2008年，Tom Glodstein等小】針對上述一般的模極 小化問題，結(jié)合算子分裂技術(shù)和B

41、regman迭代方法，提出了分裂的Bregman迭代算法。式(2-8)可以等價的寫為：削尸|同| + H(), s.t. d = D(w)(2-9)根據(jù)凸優(yōu)化理論，可以將上式約束問題最優(yōu)化轉(zhuǎn)化為無約束問題最優(yōu)化：min|d|L +H()+f | 刁中()(2-10)令 J(W,)=|4，萬(0 = /7()+：| 刁一中()，貝IJ有：minJ (a, d) + H (u, d)(2-11)為了實現(xiàn)該最值問題的求解，可以直接對其應用Bregman迭代方法的(2-4)和(2-5), 得：(ma+1 ,dM) = minDJf (,uk,d,dk) + - dP =p；一九(中)(Z (2-12)

42、 p尸= p,f-么疔-(I)”) uo=do = p：=pd=O其中，D/(u,uk,d,dk) = J(u,d)-, P*=(P；，P：)。此外，還可以對其運用Bregman迭代方法的(2-4)和(2-6)來求解，從而得到分裂 Bregman迭代的另一種形式，即伊十=+(#)-心(“a, dk+x) = arg min|d |L + H (“)+ 區(qū) g (D() 伊十)(2-13)0 = dl = = 0關(guān)于（2-13）的執(zhí)行，第一式要具體的求解。（2-13）的求解可以利用交替極小化方法對 其進行了求解（詳細參考25）。Cai等人U9對該算法做出了比較全面的收斂性證明并將 其應用在圖像恢

43、復方面。此外，文獻25中的試驗表明分裂的Bregman迭代算法的收斂 速度很快，并且該方法又容易進行并行化，而且在實際應用中分裂的Bregman迭代方法 還非常的易于編程實現(xiàn)，因此分裂的Bregman迭代算法適合處理大型的圖像問題。然而, 目前對分裂的Bregman迭代方法的理論研究還不是很充分，特別是對收斂速度的分析還 有待進一步的研究和探討。第三章 基追蹤A+線性Bregman迭代對于帶有線性約束的極小化問題：min J(m), s.t.Au = gueR其中，的)為連續(xù)的凸函數(shù)，為行滿秩。當/(“)=|4=文|妃時，上述Jt=l求解過程就是著名的基追蹤問題。此時是可逆的，方程A = g是

44、欠定的，至少有一 個解；u = AT(AATrg,此時也是L范數(shù)最小解。本章節(jié)都是針對J()= ll，來進行 研究和討論的。但在實際應用中，A往往不是滿秩的，這時遇到非常棘手的問題一一線性系統(tǒng) A“ = g不一定存在解。因此一般情況下，我們會考慮通過最小二乘解，艮“ = argmin|A“-g(3-1)ueR代替線性系統(tǒng)Au=g的求解。文中|表示范數(shù)，一般來說，(3-1)的解并不是唯 一，u:=A+g是其所有解中使么范數(shù)最小的解，但其一般并不是稀疏的。因為4模求解 具有很好的稀疏性，從而引發(fā)了人們對4模范數(shù)最小化問題的關(guān)注，即通過求解:唧啊L : = argmin|A_g(3-2)來獲得(3-

45、1)的一個稀疏解。注意當A滿秩時，(3-2)等價于(1-1),此外A+是A的Moore-Penrose逆，不一定是,因為A非滿秩時Ar(A4r)_l不一定存在。求解方面，一般情況下，問題(1-1)的解可以通過解一個無約束最優(yōu)化問題來獲得, 其中，日為正則化參數(shù)。(3-3)史加()事實上，(3-3)和(1-1)并不等價，除非存在零解。但是與求解(1-1)相比，問題(3-3) 的求解更易于實現(xiàn)。而我們感興趣的是，求解(3-2)問題是否任然可以利用線性 Bregman迭代，對于任意的矩陣A收斂性定理是否仍然成立。我們可以把任意矩陣分為兩類：滿秩矩陣與非滿秩矩陣，對于滿秩矩陣的研究已經(jīng) 非常成熟，在文

46、獻22、23中已經(jīng)闡述了滿秩矩陣可以線性Bregman迭代進行求解?；趯M秩矩陣的研究，我們接下來研究非滿秩矩陣的情況。定理 3.1 =argmin|A g等價于 =argmin|A g|ueRHueRueRI2(AAT)+ 證明：根據(jù)加權(quán)半范數(shù)的定義2.4與對于任意矩陣A , (&4)+=(A+)A+,可得:|如 - g=(Au - g)T AA)+Au - g)= uTAT(A+)TA+Au-2uTAT(A+yA+g+gT(A+yA+g因此可得:.,L)+ueR=2Ar (A+)r A+Au - 2AT (A+ )T A+g =0 =AT(A+)TA+Au = 2AT(A+)TA+g=(

47、A+A)T A+Au = (A+A)T A+g=A+Au = A+g=arg min I A-gueRu = arg min | Aw12注：從上面討論中可得問題職nW() + $k|； : = argmin|血-g等價于2: = arg min | Aw gI2 M)+|2在數(shù)值分析中，方程= g的法方程為而=心，=髡卿|加3，當且僅當ATAu =ATg。問題(3-2)等價于下面問題哩!1:= A+g。(3-4)一般情況下，求解帶無約束優(yōu)化問題都會將其轉(zhuǎn)化成無約束最優(yōu)化問題:由定理3.1可得上述問題可以寫成:卿叫+*-人擲，其中，|同=J/A+期是向量。的加權(quán)半范數(shù)。定理3.2對于任意矩陣A

48、, A*線性Bregman迭代可對于問題(3-4)利用Bregman迭 代方法推導而來。證明：利用Bregman迭代正則化方法，對于問題(3-4)可得uk+1(,“*)+?|仔A”|2其中，A = 0,1,“=p=0。上式最后一項進行線性化得|A+AMk A+|-g）,“-，所II2以得到下面迭代形式:uk+1min/Z)J (,*)+A* (A必一g),“一必+ ?JI對與P的更新可由上式最優(yōu)性條件得到:Pk+ p A+(Auk _g)_=(E -u)o TOC o 1-5 h z kk+= . = YA+(g-Au)-i=0O.z 產(chǎn)uk+ik引進中間變量vA+l = pk+ 4 = pk

49、 -A+(Auk g)=, = A+(gAu ), /k ,OO;=o可得:k+1K- 我1-涉1景+/2ku/ k,uu,/-22k,uu,/1 - $-f - du, + 23(A+(Auk -g) pk=min(/zJ() + (|u| -2(u,uk + 28(A+ (Auk -g),“-2Sp*,) =嗦心)+&|u-2S+ 羅 妒(而*_g)_pJ% )o=史汛（”）+土（l|u一-g）- p* -十,“ 唯1心）+陽|u-Sv所以vk+1 =vk +A+(g-Auk)uk+1 = argmin/zJ(u)+-|w 。，線性Bregman方法解決如下問題：minueR,g”(“)：

50、= kill |wll2 stAu=g(4-1)而不是解決問題(l-l)o最近文獻36表明線性Bregman方法可以看作應用于(4-1)拉格朗 日對偶問題的梯度下降方法。其對偶問題的無約束最優(yōu)化的形式表達式如下：minGt (y) := -J(vv ) +?T -(4-2)這里(4-3)w :=argmin(J(vv)+|vv| w2因為&,()是嚴格凸的，所以Q(y)是可微的國,對應用對偶問題的典型梯度下降 方法很多加速技巧可以應用其中，比如Barzilai-Borwein步-38.BFGS方法網(wǎng)。文獻36 中對于基追蹤的數(shù)值計算結(jié)果展示應用于上述技巧可以大幅度改進線性Bregman方法。因

51、為G,(y)的梯度是李普希茨連續(xù)的，所以帶有合適步長的典型梯度下降方法可以在 。泠迭代中得到(4-2)的一個最優(yōu)解(也就是逼近解y*滿足(/)-(/)o在文獻40中，Nesterov提出了 一種對于解決(4-2)問題加速梯度下降方法的技巧，并且證明 了這個加速技巧可以把需要獲得八最優(yōu)解的迭代次數(shù)從。(L)降低到。(&)。在此基礎(chǔ)8上我們提出加速妒線性Bregman方法。針對原始Bregman迭代，我們有算法1：算法1原始Bregman算法1：輸入 = p =02： Fork =0,1,do3： =argminZ)f-u.R”24： pk+ = p完全相 同。wA+1 := argmin( J(

52、w) 4-|Am |244)2fc+1 :=2fc-(Awfc+1-g)其中，= 0 o證明：根據(jù)算法1的第4步可得：fk = Pl AT(Allk g)P_ = p2Ag)Vpi = p-Ar(Au -g)累項相加可得：P*-8)i=l同理： =/_(A必 _g)/T =疔_(.廣_8)/() J(mk) |Aw (4-6)u&R，12=arg min(J(w) +|Aw _ g|ueR2(4-4)的目標函數(shù)：(4-7)uk+x = argmin(J(m) +|Aw |)n2=arg min J(w) +|Aw if2可得算法1與(4-4)的目標函數(shù)相同，所以得證。令J(x) = q|,算法

53、1的第3步可以簡化成4正則化問題:(4-8)把式(4-8)中做一線性近似,再加一臨近項*u u|2根據(jù)最優(yōu)性條件:0 g dJ (ukx) pk + A (A必g) +(*+i *)下面給出算法2,這個算法在原始線性Bregman的基礎(chǔ)上增加上了一個參數(shù)，這 個參數(shù)對應于對偶問題的梯度步長。算法2修正的線性Bregman迭代方法 1 ：輸入必=p = 0, # 0, r 0 ,2:FoM =0,1,do3： uk+ = arg minDj (u,uk) 4- r H 也wA | ueR2 pk+ = pk _tA7 (Aw*+1 _g) (* _uk)5： End for當#|A 2 ,線性B

54、regman迭代收斂到(4-1)問題的解，這里|況表示矩陣A的最大 奇異值El。線性Bregman等價于應用問題(4-2)的梯度下降。其中梯度下降方法(gradient descent method) 為：(4-9)(4-10)(4-11)(/)為了展現(xiàn)。(y)是連續(xù)可微的，我們可以把Q(y)改寫成:Gp (y) = -o”y)+& | a，y一 g，y這里:O. (v) = minJ(vv) +-|vv v|2/II)呻Avv = a r g m / n中 (u)是嚴格凸的并且是連續(xù)可微的， 0, T 0, y = Tg ,2： For比=0,1,do3： wk+ = arg min( J(

55、vv)Hllvvll w2jU4： yk+i =yk-T(Awk+-g)5： End for TOC o 1-5 h z vvA+l = arg min(J(w) + -IIvp| w2jU=aig min J(w) +-llvvll w2/z=aig min J(w) +-llvvll w2jU=aig min J(w) + r llvvll - KJL2ZJL2Z+ + g gw2lill=arg min J(w) +tw=aig min J(vv) +t通過比較上面兩個等式，會發(fā)現(xiàn)“z與H/+等價。n：上面等式的推導都是充要條件，顯然，如果疽與討+|等價，我們可以推出式 (4-12)o所

56、以算法2產(chǎn)生的廣與算法3產(chǎn)生的等價當且僅當A7 yk = pk TAT(Auk g)+uk定理4.3算法2產(chǎn)生的序列護與算法3產(chǎn)生wk是相同的。證明：根據(jù)引理4.2,我們只需證明對與VkZO式(4-12)成立即可。用數(shù)學歸納 法來證明：當化=0時，因為“=p= 0和y Tg ,顯然# = 0時成立。假設(shè)。球時，也成立，那么根據(jù)引理4.2,式(4-12)成立，根據(jù)算法3的第3 步，可得：y =_r(Awn -g) = Y t(Auj - g)7=0根據(jù)算法2的第4步，可得：n-Ip = g)un7=0JU通過比較上面兩個等式可得：P-tA1 (Aun-g)+u = (Auj-g) = ATynj

57、Uj=o所以當n = k時，式(4-12)成立；所以對與VANO,式(4-12)成立。我們定義v =Ary對算法3的第3步目標函數(shù)最后兩項做如下處理：wI -wk+ = argmin( J(vv) + !卬2=argmin(J(vv) +=argmin(J(vv) +1-2/z1-2/z7 T A 一A - kvvv那么，算法3的第3步與第4步可以用:12(4-13)v/+1 = argminJ(vv) + -|w-/zvw2/zvA+l = vk t Ar (Avvk+ g)其中，v =rATg來代替。因為算法2與算法3等價，梯度下降方法的收斂性可以運用上，那么，我們有如下 收斂性結(jié)果。定理

58、4.4 7(”)三|岫，對偶問題(4-2)中，Q(y)是連續(xù)可微的，它的梯度是李普希2茨連續(xù)的，其中李普希茨常數(shù)LaH|如果步長&沛，那么算法2產(chǎn)生的序列 必與算法3產(chǎn)生的序列/收斂到問題(4-1)的最優(yōu)解。證明：當JW三|岫，(4-13)中討十可以簡化為號=聞；(時)，因為g(“)是嚴格凸 的，所以()，)是連續(xù)可微的。因為 Q(y) = Aw-g,根據(jù)閾值算子的非擴張性，也就是|(s)_7；(圳 g|sT|,W。所以|VG (y1)- VG (/)| 0,r 02： Fork =0,1,do3： uk+ = arg minDj (u,uk) + T - |仇-g ueRn2/7 *jk14

59、： pk+ = p tAAu _g)(wA+l u )5： = akuk+ +(1 ak )uk6： p =akpk+ +(l-ak)pk7: End for像(4-13)線性Bregman方法推導過程一樣，我們可以得到如下算法:wk+ = aig min( J(w) H w jllv JA(-8,8,并且對于任意潔R，如果z+ = arg min 燦饑)+?|- 0(乙+)+ ?|k+，Vw e R下面定理4.6給出對于加速A*線性Bregman迭代復雜度的分析，這一定理的證明與 文獻42中推論2的證明非常相似。定理4.6序列必是由加速A*線性Bregman方法產(chǎn)生的(算法4),是(4-1)

60、(4-16)最優(yōu)原始和對偶變量問題的解，序列%選擇如下:=1 + 0(紀 T)2：T0=M(4-17)序列寸是由(4-14)產(chǎn)生的，并且步長r|,這里的乙是Q(y)的李普希茨常數(shù), 對于(4-1)的拉格朗日方程如下:(4-18)L(，y) =|“| 我們可以得到:G (/) -G ()，*) 2七了 (4-19)此外，如果有這里0/?1,那么(必七寸)是(4-1)的拉格朗日問題(4-18)的 一個最優(yōu)解，其中kN廄,這里。證明：根據(jù)(4-19),可得 GM(yk)=-L(uk+,yk)o(4-20)令=，我們對Q(y)進行線性化表示如下：妃(“；y) ：= Gt(y)+ Gt(w)因此V*V*