1、中圖分類號：TN911單位代碼：10425學 號：S11090947I中闞石冷上粵碩士學位論文China University of Petroleum Master Degree Thesis矩陣補全問題的研究與應用The research and Application of Matrix CompletionProblem學科專業：數學研究方向：圖像處理作者姓名：伏路 指導教師：李維國教授二。一四年六月The research and Application of MatrixCompletion ProblemA Thesis Submitted for the Degree of M

2、asterCandidate： Fu LuSupervisor： Prof. Li WeiguoCollege of ScienceChina University of Petroleum (EastChina)關于學位論文的獨創性聲明本人鄭重聲明：所呈交的論文是本人在指導教師指導下獨立進行研究工作所取得 的成果，論文中有關資料和數據是實事求是的。盡我所知，除文中已經加以標注和致 謝外，本論文不包含其他人已經發表或撰寫的研究成果，也不包含本人或他人為獲得 中國石油大學（華東）或其它教育機構的學位或學歷證書而使用過的材料。與我一同工 作的同志對研究所做的任何貢獻均已在論文中作出了明確的說明。若

3、有不實之處，本人愿意承擔相關法律責任。學位論文作者簽名： 日期： 年 月 日摘 要矩陣補全問題是指通過利用低秩或近似低秩的未知矩陣的部分已知元素恢 復出其它未知元素，由于該問題在控制，計算機視覺，網絡調查等廣泛的應用領 域具有重要的價值。近年來，關于該問題的算法和理論均得到了快速的發展，尤 其在控制論、人臉識別等視覺應用領域有顯著的應用價值,近一段時間有關該問 題的求解和理論都得以迅速的開展。在互聯網推薦系統上也有很多的應用，比如 協同過濾等，其中包括著名的網飛問題(Netflix problem)0這篇碩士論文討論 了其在稀疏問題中應用，我們通過系統的學習和研究，發現了新的解決方法，進 一步

4、提高現有的理論，使其應用在壓縮感知等稀疏問題。本文的創新點有以下幾點：第一:提出了改進的線性Bregman迭代算法以及應、與線性殘差迭代算法。第二：推導了臨近點算子和軟閾值算子之間的關系，并將莫洛包絡思想應用 于求解基追蹤問題。第三：運用加速超松弛技術，使矩陣補全的低秩矩陣擬合算法得以實現。第四：用新的方法推導交替迭代算法，并將其用于分解非負矩陣。關鍵詞：壓縮感知，矩陣補全，矩陣分解，交替迭代The research and application of matrixcompletion problemFu Lu (Mathematics)Directed by Prof. Li Weiguo

5、AbstractMatrix completion problem is widely used in control, computer version(face recognition and so on),internet survey and other areas, in recent years ,the algorithms and theories about the problem are obtained rapid development. On the internet recommendation system it has also a lot of applica

6、tions, such as collaborative filtering, etc, including the famous Netflix problem. This masters thesis studies its application in sparse problem ,and we adopt systematic study and research, and find some new algorithms and further improve the existing theory ,and make applications in sparse problems

7、 such as compressive sensing.This thesis has some innovation points below:Firstly, A modified linearized Bregman iteration algorithm and A novel A , A* linearized residual iteration algorithm are proposed.Secondly, the relationship between the proximal operator and the soft threshold operater is ded

8、uced, and Also we resolve the basic pursuit problems by the Moreau envelope approach.Thirdly, we use overrelaxation techniques to abtain the low-rank matrix fitting algorithm solving matrix completion problem.At last, we propose a new derivation method of alternating iterative algorithm and use this

9、 algorithm for solving the nonnegative matrix decomposition problem.Key words: compressive sensing, matrix completion, matrix decomposition,alternating iterative TOC o 1-5 h z HYPERLINK l bookmark18 o Current Document 第一章緒論11.1研究的背景及其意義11.2矩陣補全問題的論述2 HYPERLINK l bookmark21 o Current Document 第二章預備知識

10、32.1凸優化32.2正則化方法42.2.1適定性正則化方法42.2.2迭代正則化方法52.2.3信賴域方法6Lanczos 方法7Lavrentiev 正貝U化方法72.2.6奇異值分解算法82.2.7 Landweber-Fridman迭代算法10 HYPERLINK l bookmark30 o Current Document 第三章基追蹤問題123.1 Bregman距離的定義與性質123.2基追蹤公式推導及木目關證明 123.2.1問題陳述123.2.2 線性Bregman迭代算法133.2.3線性殘差迭代算法203.3莫洛包絡算法243.4數值模擬29 HYPERLINK l b

11、ookmark105 o Current Document 第四章軟閾值算法344.1基追蹤問題的軟閾值迭代344.2矩陣補全問題的軟閾值 35 HYPERLINK l bookmark111 o Current Document 第五章低秩分解模型算法365.1交替極小化格式385.1.1 非線性 Gauss-Seidal 方法385.1.2非線性類SOR格式38 HYPERLINK l bookmark123 o Current Document 第六章交替迭代算法求解非負因子的矩陣補全426. 1非負矩陣分解的定義426.2相關的算法436.3主要算法446.4 收斂性分析476.5非線

12、性SOR算法506.6數值實驗51 HYPERLINK l bookmark128 o Current Document 結論與展望54本文的主要創新點54后續研究工作展望54 HYPERLINK l bookmark131 o Current Document 參考文獻55 HYPERLINK l bookmark187 o Current Document 攻讀碩士學位期間成果59 HYPERLINK l bookmark190 o Current Document 致謝61第一章緒論1.1研究的背景及其意義在2005年，Osher等人利用Bregman迭代正則化方法來討論全變分圖像去 噪

13、，它是一種有別于以前的正則化方法。后來此種方法和小波基結合，被應用到 醫療核磁共振（簡稱MRI）處理、信號（圖像）去噪、非線性逆尺度空間等問 題的研究。在此之后，在壓縮感知（Compressed sensing簡稱CS）解碼問題中， Bregman方法取得了顯著的效果。最近一段時間，它成為一個熱點的研究對象, 是因為其稱為解決與匕范數、特別是，。、匕之等范數有關的一大類優化問題的行 之有效的方法。目前我們知道線性Bregman迭代方法可以用來處理基追蹤問題，而且它的 理論研究已經較為成熟。它的目標函數僅僅是向量的范數，它廣泛地應用在信 號處理、控制論等領域。數值模擬表明，在求解過程中，向量的非

14、零分量的個數 不斷增加，一直趨向于原始信號，同時對于單個非零分量而言，它的信號范數也 隨著迭代次數的增加而單增不減（這也和它的收斂性理論是吻合的）；其它方法 （比如分裂算子不動點迭代方法，梯度下降法的Landweber迭代法）的非零分量 個數逐漸趨向于原始信號。我們開始以為，稀疏信號，會導致相對較少的迭代次 數。實際上通過實驗，我們發現對于非稀疏的向量，Bregman迭代算法的恢復效 果也是比較好的?；粉檰栴}是矩陣補全問題中的一個很典型的例子：由一維問題（向量）向 二維問題（矩陣）轉變，它是許多新型算法的試金石。隨著研究的深入，我們發現在許多應用中出現了極小化矩陣秩的問題，比如： 控制系統理

15、論，最低訂購控制合成，圖像流運動，模型簡化，恢復形狀，模式識 別，數據挖掘和機器學習例如潛在語義索引，低維鑲嵌和協同預測等。對于小規 模的問題，已經提出了很多成熟的解決方案，而在實際問題中，往往規模很大, 快速有效地求解，收斂速度的提高、計算機存儲的縮減等方面依然有待我們進一第一章緒論步地研究和處理。1.2矩陣補全問題的論述矩陣補全問題是指通過利用低秩或近似低秩的未知矩陣的部分已知元素恢 復出其它未知元素。由于該問題在控制，計算機視覺，網絡調查等廣泛的應用領 域具有重要的價值，近年來,關于該問題的算法和理論均得到了快速的發展。定義1.1 假設未知矩陣M e R5 是低秩的，其樣本元素的集合為

16、Mt j : (z,j) e。,則矩陣補全問題可敘述如下：rcmk(X)XZw Oj)eQ為了求解的方便，我們轉而求解下述的變min(Pl) XC1X2s.t.但是上述問題是一個NP難問題， 形問題II II*X =M. . (i. zUQmin(P2)X5s.t.其中符號| |是核范數，表示的是所有奇異值之和，從上述兩個模型可以看 出P1和P2問題僅僅只是目標函數不同而已，但是有一種特殊的情況：就是當 矩陣所有的奇異值均為1時,這兩個問題是等價的，其他情況下一般是不等價的； 但是在一定的條件下，P2是P1的緊凸松弛，Candes和Recht B經證明，在一定 的條件下，問題P1和P2有相同的

17、唯一解。如果令是定義在隨機集合Q上的正交投影，則相應的問題可以敘述為：血(P3)X 簫忡2 H I 皿(x)= %w)第二章預備知識矩陣補全問題之所以能夠受到如此廣泛的研究和關注，并成為一個圖像處理 問題中的熱點問題，與其強大的數學理論是分不開的。為了方便起見，在本章中 將介紹一些與本論文模型和算法緊密相關的一些基礎知識。2.1凸優化現有的矩陣補全的算法的設計都是建立在凸優化的基礎上的，對于更詳細的 理論知識可參閱有關凸分析的文獻等。在本小節，我們先介紹一些有關凸優化的 相關理論知識。定義2. 1. 1設f(x)是非空凸集Qur2上的函數，如果對任意的有不等式f (.+(1 - 人)力 + (

18、1 -(y)，對于02/(x) + (Vf(x)r(y-x).定理2.1.2對于凸規劃問題，目標函數的任一局部極小點都是目標函數在 非空可行集上的全局極小點。定理2.1.3對于凸規劃問題，若目標函數在非空可行集上是嚴格凸函數， 則此問題的全局極小點是唯一的。2.2正則化方法正則化方法開始于二十世紀四十年代，經過二十多年的發展，形成了系統的 理論支持，在上個世紀八十年代趨向于成熟，九十年代開始朝著實際應用方面發 展。人們在求解第一類積分方程的基礎上發明了正則化方法。因為這種方法是最 早由前蘇聯院士 Tikhonov AN提出來，所以這種方法又被稱為Tikhonov正則化 方法。首先看看正則化算子

19、的定義。定義2.2.1人們稱T(a,h), aeB (/為某一參數集合)為正則化算子，若T(a, h)對任意的a 2 均連續；對任何已知的h遷(K),如果有C auchy列仇 uH，使得hnh, 則有Cauthy列% u 8使得當 T 8時，7(%,九)T 70,力).2.2.1適定性正則化方法為了描述的簡便，我們使用線性代數語言對統計學中的正則化問題作如 下描述：線性控制系統如下：d = Qr-n,其中Q為一線性算子，,為輸入，d為輸出，為隨機向量，在信號或圖像 處理中，一般表示噪聲，協方差矩陣是 = Et .我們想計算出如下的向量,， 使其滿足下面的最優化問題min。W 蝴= (d Qr)

20、T S_1 (d - Qr),r令V = 0,則得到正規方程QTYiQr-QTYid=Q,進而我們將其換成如下形式Or-r = 0,其中=QQ為Fisher矩陣或Fisher算子，r =.上面的算子方程是不適定的，因為是一個病態的算子，會帶來數值計算的 不穩定。為了解決這一問題的一種方法就是利用正則化方法，按照這一思想，我 們對加上一懲罰項變為= + 0為一個正定矩陣。由V；= 0我們可以得到代數化的病態問題的 歐拉方程(O + a7/)r = r,選擇不同的H,會得到不同的解(光滑程度不一樣)。尤其當H =/時，這 樣我們就得到了最為經典的Tikhonov正則化方法，適定性正則化這個概念最初

21、 是由Ryzhikov和Biryulina提出的，他們提出的適定性正則化方法就是根據 H = 0)t得到的，進而我們得到(2 +a/)r =中產，我們再進一步討論，我們就可以得到適定性正則化方法具有比Tikhonov正 則化方法更強的正則化，我們在此不再贅述，有興趣的，可參考相關文獻。2.2.2迭代正則化方法我們都知道用迭代的方法可以求解不同的正向問題(有限維數或無窮維數 的），而且迭代法還有一個好處：當將無窮維變為線性代數方程組后（有限維）, 系數矩陣的結構在求解過程并不會得到損壞，而且可以節省存儲空間，這有利于 求解大規模問題。后來我們發現通過迭代還可以求解反問題，但是在解決問題的 過程中

22、會出現“半收斂現象”，即：在迭代的過程中，一開始迭代解會得到穩定 的改進，出現“自正則化”的現象，但是隨著迭代次數的增加，超過某一數值, 迭代結果就會趨向發散。因此關鍵的問題是要找到一個合適的停機準則，研究表 明，迭代步數與正則化參數有關，而正則化參數選擇亦和停機準則有關。我們以抽象的算子方程為例其中為有界線性算子，并且希爾伯特空間X和K均是可分的，那 么解決這問題的迭代的吉洪諾夫正則化方法如下定義：對,3 = ，（A A +6 = A + ax，；, Z = 1,2, . . .,其中8是與正則化參數a有關的參數。此外，還有另外幾種迭代正則化方法，比如“基于TV非光滑正則化方法”, Land

23、weber-Fridman 迭代法”等。2.2.3信賴域方法信賴域方法是一種比較新的研究方法，可以應用在非線性優化方向。它可以 確保問題全局收斂的同時又要求問題在局部的快速收斂性，比如我們考慮如下的 極小化問題：min/（x）,求解上述問題，要首先給定當前信賴域半徑，然后求解一個近似的二次子 問題min “ （ + g） = f 代）+ （g 任）,g） + ? （H, g）,可以看出信賴域半徑描述了二次模型逼近原問題的程度大小，在此基礎上我們研究得到了信賴域方法。Lanczos 方法此方法是在深刻挖掘信賴域方法的基礎上得到的，我們注意到問題的模型是 二次型，算子方程并且是線性算子，因此在涉及

24、子問題的求解上，我們可以利用 線性代數中的一些高效的求解方法。Lanczos方法是求解如下最優化問題min；f = !廣履#-（#*）+ ：（）,的一種Krylov子空間方法，它的迭代格式表示為：算法1：尋找正交基的Lanczos迭代方法Step 1 已知/o,設 gQ = grad（Jf0yQ =0,對頂= 0,1,迭代如下：Step 2計算弓=（為，為）;Step 3 計算幻=y. / y.；Step 4計算興=（們頊伏們）；Step 5 令 yj+i = KTKqj -djqj -y.q._x.Lavrentiev正則化方法假設A為一緊算子，求解如下方程Af = g,我們可以使用基洪若夫

25、正則化方法，就是求如下的最優化問題minJ（/,a） = |A/-g|+a|/|對于特殊的緊算子A,例如A為對稱的算子，我們可以使用基洪諾夫正則化 方法。但是當A*=A,這時吉洪諾夫正則化可以進一步簡化為Lavrentiev正則化 方法，此時我們解決的問題是和原問題相關聯的適定性的逆問題4T+=g,其中a 0為正則化參數。我們知道上式右端項g不可能準確地獲取，因此我們需要考慮算法的正則性問題。假定事先我們已知道受干擾項ga滿足 血頊* n)秩為r , A A的特征值為A +i = = =。則稱= 丁足(Z = 1,2,.,)為A的奇異值。定理2. 2. 6. 1奇異值分解定理假設A是秩是r (

26、r0)的加x復矩陣，則存在m階酉矩陣/與階酉矩陣V , 有H 01uhav= =ao o其中Z7 = 6/詼(,，?), D (Z = 1,2,，,)是矩陣A的全部非零奇異值。證明 設埃爾米特矩陣AhA的n個特征值按如下優先次序排列：有卒=人=0.則存在階酉矩陣V,有fa 2 rX2 oVh(AhAW=(2)1。將V分塊矩陣V =(的 馬)，其中的，嶺分別是V的前,列與后n-r列。并將(2)改寫為尸 Qahav = v uo o則有AA=峪萬 2, ahAV2=O.（3）由（3）第一式我們有% A A% =以或者（a%（人華）=Er.由（3）第二式我們有（A嶺）（A嶺）=0或者A嶺=O.設1=

27、4%萬-1,則U?U=E,。記U=g%,.），因此我們可將 i，2,擴充成C的一組標準正交基，記擴充的m-r個向量分別為, 并且組成的矩陣2=（雨，），則有U =（/1，2）=（綺，“2,，0，0+1，是m階酉矩陣，而且已知U；U=E，.因而我們可得 TOC o 1-5 h z tjh1 x 0UhAV=Uh（AVv AV2）= （ 0）=12 以1_0 0由（1）我們得到 X 0A = U VH = cyu + cr2w2vf + +（Jrurv .（4）稱（4）是A的奇異值分解的簡化表達形式。定理2. 2. 6. 2 假設AeCmxw, A的非零奇異值分別為 cr2 ,i，2,是對應于奇異

28、值的左奇異向量，幺埒，*是對應于奇異值的右奇異向 量，則我們有A = M + r2Z/2V2 * 7尸諾.上面的方程被稱之為矩陣A的奇異值表達式，對一個k V r ,截去A的一些 相對較小的數對應的奇異值，則矩陣是A =諾 + +凹諾.則&是一個秩為上的mx矩陣。我們已經表明了，在基于Frobenius范數的 意義下，右是在所有秩為k的矩陣中距離A最近的矩陣。這種意義在實際 的應用中是非常廣泛的。舉個例子，比如在圖像數字化技術中，一張圖片可以轉 換成一個mxzz階數值矩陣，存儲量為mxn。但是如果我們通過矩陣的奇異值展 開表達式，則我們只需要存儲A的奇異值，以及奇異分向量氣,、，總計為 ,(m

29、 + + l)個數。這樣存儲量會大大的減少。此外，我們令kcr2-(Jr 0.顯而易見，權系數比較大的項對矩陣A的影響也大，因此我們可以采取一種 策略：舍去哪些權系數比較小的一些項，剩余比較大的幾項依然可以很好的“靠 近”原先的矩陣A ,這種策略在圖像數字化處理方面很有效果。為了支持上述論述，我們附錄矩陣的秩上逼近的定義如下A = 代此 + cr2u2v2 *b.房lk r .我們稱秩,逼近就精確等于A ,而秩1逼近的誤差最大。Landweber-Fridman 迭代算法此種方法不僅可以求解線性反問題方程，也可以求解非線性反問題方程，我 們以線性算子方程為例，簡述一下:Ax = y.求其解的L

30、andweber-Fridman迭代法指的是按下面的迭代格式進行改+i =改+刃人*3_人改)為了使格式收斂，一般要求Ov/ J(v)+ yueRM .(3. 1)則稱p為向量值函數J(x)在u處的次梯度，所有在v處的次梯度的集合記為a/(v),并稱之為aj(x)在u處的次微分。定義3. 2凸函數8J(%):在，v兩點的Bregman距離為Dj (z/,v) := J(h) - J(v)- .(3. 2)其中向量peM為次微分d/(u)中的一個次梯度。Bregman距離的性質：性質 3. 1 Df(w,v)0.性質 3. 2 Z)/(w,v) = Z)f(v,w)不一定成立。性質3.3對于連結

31、,u的線段上所有的點w有：Df(r/,v)Df(w,v).從上面的性質可以看出Bregman距離是Euclid距離的一種變體，是對長度 的另外一種度量。3.2基追蹤公式推導及相關證明3.2.1問題陳述假設A 6 NxM,b 6隈。6隈M ,基追蹤問題解決最小化問題：argminJ()= MR : Au=b.(3. 3)一般情況下，Au=b是一個不定方程，也就是NM (在許多情況下，NM), Au = b有多余一個解，我們的目的就是在許多解中，找到一個匕范數最小的解列.基追蹤問題起源于壓縮感知(CS)應用中，近年來，國際上許多 著名的學者，如Osher, Yin, Candes, Cai等，利用

32、Bregman迭代方法對其進行 了詳盡的理論和應用的研究。CS問題的基本原則是，通過最優化方法，信號的 稀疏度可以通過從它的不完整的測量中恢復得到。假設向量L e 表示高稀疏 信號(即，k = “IL ：= : ui 0| M ).我們可以對u通過線性變換Z? = Au e IR加 密，然后通過求解(3.3)從人中恢復L,經過證明恢復的效果是很好的，但是系數矩陣A要滿足一定的條件。本節，我們對于J() = W|L的簡單類型，也就是我們提出的基追蹤問題，借用Bregman相關概念推出解決這一問題的迭代公式， 也就是線性Bregman迭代公式，同時利用殘量迭代推導出相應的算法。問題(3.3)可以通

33、過轉化為一個線性規劃問題，然后采用傳統的線性規劃 方法來求解。然而這種算法對規模較大且完全稠密的矩陣或正交高斯矩陣或 DCT矩陣是不適用的。我們首先將(3.3)轉化為無約束問題(3.4)argmin/zHI +-|Azi _力|：3.2.2線性Bregman迭代算法我們已知J(u) = |此，運用Bregman距離替換J(u),獲到另外一個迭代正則 化模型，并且令H() = ：|即-叩，我們對H(們運用一階泰勒展開式在抄展開 得H()=A“一叩 qH(z/) + (VH(/),“一/) +土(3. 5) 其中約等號右邊的第三項是為了更好地逼近函數H()而添加，同時我們也將J()用其在, u兩點

34、的Bregman距離代替Df (u,uk) = J(u)-J(uk)-(pk,u-uk .(3. 6)其中p*是J()在抄處的次梯度，將(3.5)和(3.6)分別代入(3.4)得到一個求解列的迭代公式：uk+i ?(”) + ().(3. 7b)經證明這兩個迭代公式只是相差一個常數(在滿足AA=/時)。這種方法可以采用Bregman迭代正則化來求解一般化/()的最值問題min“w略 /()+ ()其中J()和H()均是凸函數，且要求H()是可微的。算法3. 1 Linear Bregman iterative regularization初始化：k = 0, n = 0, p =。;當不收斂時

35、，開始uk+i arg min ?(,/) + H()；pk+i j pk-VH) g dJ(uk+1);kZr +1;結束并輸出結果七從算法3. 1我們可以看出線性Bregman迭代正則化的每一步迭代中，最為關鍵是計算如下最優化問題uk+i arg min zZ) + H().(3. 8)由于正則化函數J()不一定可微，使得(3.8)不能被直接求解。在此，我們使用向前向后分裂法(簡稱PFBS),推導出求解E的迭代公式。PFBS求解的一般極小化問題為minG(u) = g()+ %().(3. 9)UE.R烏()：R“ tR,Z = 1,2全是凸函數，4() 一般不可微，旦()可微。設抄是第上

36、次迭代的結果，PFBS法首先沿()的負梯度方向在護的一個下降點 癢=/一汐氣(護)，其中30為步長，然后在疔的周圍求一個使4()下降的點-ku-u(3. 10)PFBS算法的具體步驟如下：算法3. 2 PFBS迭代算法初始化：當不收斂時，開始U uk -3VF2(uk);k k +1;循環結束結束并輸出七PFBS算法的收斂性由下面的定理描述定理3. 1設函數E(u),i = l,2滿足下面兩個條件(1 ) W),i = l,2是正則的下半連續凸函數且強制的，即 呻W)+ E()T8,(2)巴()滿足Lipschitz連續可微，艮叫|%()一徽(訓刨“一訓.2假設(3.9)至少有一個解，則對任意

37、的初始值/及O?(,/),%() = ?|則7烏()=疽(如一。)，據 PFBS 算 法可知，求解(3.4)的迭代公式為(3. 11)U =/（/ ） = /A/ _人）因為 |VE（）-VK（u）|dA5M-U|,由定理 3. 1,知參數 Ov3v2IM時，取頊，則迭代(3.11)收斂到(3.7)的一個解。在具體的計算過程中，我們 只會迭代有限步數，我們將迭代步數設為Mk，則=此.由于pMa/W， 再根據最值函數的一階必要條件知道d/LtDjk (u,uk) (uk,Mkl-5Auk,Mkx _)| | = uk,Mk = 0. (3. 12) 從而有pk+1 = pk (uk+1 -ukM

38、k-AukMk-x -b.(3. 13)/li5結合上面的討論，我們將用PFBS算法來求解Bregman迭代正則化的過程歸 結為下面的線性Bregman迭代算法。算法 3. 3 Linear Bregman Iterative Algorithm初始化：30,=0,迭代次數序列虬當不收斂時，do i = 0-Mk -1舟uk, uk J 舟-3At (A/ b);k1_k . 2uk,l+i arg min M /nDj (,*)u u ;結束內層循環25E質；pEL(E虹 T)L 疽(A/M-l人)；jd8k k + 1;結束外層循環，輸出氣以上是PFBS求解一般函數的步驟，內層循環采用不動

39、點迭代的算法，但是 對于極小化目標函數的分量可以分離的，可以給出具體的算子公式，對基追蹤問 題我們就可以采用這種技巧。由=/矛(必)= /，5疽(A/一人)，并且令Mk =1,Bregman 迭代 (3. 11)變為*+1=4用血11心心/(。-|1-(,*,-*) + 備。-(*-3人7(人*-/?)。0, “是不變常量。并且設sgn（）為符號函數，定義如下：sgn(x) = 01, % 0(3. 17)(3. 18)則求解/（x） = a|x| + |-（x-/?）極小值的算子為:項）=其中2（”）就是函數f的極小點。設=（綺,2，肱）七略，定義向量閾值算子如下:7；()=心(妃，婦(2t

40、a g )T (3. 19)則（3.16）的求解公式為:(3.20)(3.21)uk+i=T6vk+1).因此，求解本章問題的Bregman迭代算法為：k+i =vk +Ar(b-Auk)0為正則化參數，30為步長參數。因為當30時， 隊四廣）= %（，），所以不（汗山）=以（盧1），從而（3.21）可以簡化為：k+i = vk +（b-Auk uk+1 = 6Tvk+1）（3.22）uQ =vQ =0為了后面的討論的方便，我們對（3.22）做規范化處理。令gk+1 = gk +（Jb-Auk g = 0 ,則 gS = （人 - Az/）,從而z=0疽gE=文疽(八做村廣.z=0因而(3.2

41、2)變為如下形式：gk+l = gk +(b_Al)(3.23) 0,5 0,次 = g = 0;當不收斂時，dogEjg*+d*）廣J 以（A，gS）k k + 1;循環結束輸出迭代結果七當A行滿秩時，但是AAtI,為了加快收斂速度，我們通過預優技術，獲 到下面的線性A+Bregman迭代算法算法 3. 5 Linear A+ Bregman Iterative Algorithm初始化：/ 0,5 0, = g = 0;當不收斂時，dogE*+d/）舟iy（A，gE）k k + 1;循環結束輸出迭代結果其中A+=A（AA），當A非行滿秩時，我們用A一代替占C A = pinv（A）, Ma

42、tlab 中 MP 逆的計算公式），進而得到線性ABregman迭代算法算法 3. 6 Linear A Bregman Iterative Algorithm初始化：/ 0,5 0, = g = 0;當不收斂時，dogE*+d/)uk+i=6TA-gk+1)k k + 1;循環結束輸出迭代結果七下面為了加快收斂速度，提出線性Bregman迭代算法的改進形式，并且對A，, A+, A這三種形式的改進是一致的，先一并陳述如下算法 3. 7 Modified Linear Ax Bregman Iterative Algorithm初始化：/ 0,5 0, = g = 0;當不收斂時，dogf g

43、*+E0-Az?) (E = Adiag), 2和對角線參數要根據具體情 況而定)uk+1 =6TAxgk+l) (X :=,+, )上。上+1;循環結束輸出迭代結果七3.2.3線性殘差迭代算法在線性Bregman迭代算法之外，許多人對Bregman迭代過程進行了研究， 他們將其理解為“將殘量加回去”的技巧，并以此來解釋所謂“殘量法”的優點。 在實際的運算中，只需要將bk+i=b + (bk-uk)理解為新的噪聲圖像，那么Bregman 迭代正則化方法求解的每步迭代均可簡化為ROF模型，其中。=。=0,則有 迭代公式廣云+ (/-心,得到bl=b,也就是說Bregman迭代正則化方法求 解迭代

44、的每步迭代等價于Emin/() + 1|.(3.24)令w表示人中含有的噪聲部分，艮= 1 + 當上=0時，b=u=O,因此(3. 24)將噪聲圖像時分解為/+J,由于當正則化參數日較大時，則最優化問 題(3. 24)主要極小化全變分項J()，這導致圖像W可以過于光滑，從而不包 含任何噪聲圖像(甚至部分圖像的邊沿和紋理也被濾掉)，所以，W可以理解為 原始清晰圖像的一部分,而殘量v1 =bv - u =b-u = (-J) + w則理解為未被恢 復的有用信號(L-/)與噪聲信號w的和。自然地，我們希望從殘差鏟中恢復 (),于是可以考慮將鏟代替ROF模型中的人并再次求解。但是，在Bregman 迭

45、代正則化過程中，當* = 1日寸，艮P b2 = b1 + V1 =b + vr =ur +2( - I?) + 2w表明殘 差鏟被加回到原噪聲圖像人中，與b1=b = u1+(u-u1) + w比，可知。之包含兩倍 的要恢復的有用信息和兩倍的噪聲成分w,我們進一步求出= / + 2( 2) + ( )+ 3w,b* = I/，+ 2( 3) + ( / ) + ( i) + 4w,= 4 + 2( 4) + ( 3) + (2) + ( _1) + 5w ,b* = ii，+ 2(u uk i) + ( 2) + ( /) + ( )+ kw,bk+i = / + 2( -uk) + (u-

46、 ukl)( _ ) + ( _ z?) + (上 + l)w.利用數學歸納法并借助b=b + (bF)可以很容易地推出上面的公式，為 了方便陳述，設C (L-W)表示單項式U-U1中/的系數，從上面的遞推公式可以 看出，文C(LW) = -佐+ 1),恰好與w的系數的代數和為零。i=l在Bregman迭代求解/過程中，一方面，極小化Bregman距離使/繼承了 W的信息；另一方面，極小化k-釧時的/恢復了部分（_/）信息，這使得/ 比/更好地逼近L .盡管由于/收斂于力=1 + w使得uk總包含一些噪聲成分， 但是，|p -Z?|趨于|R-嚇的性質使得Bregman迭代正則化恢復的圖像/與R

47、OF 正則化恢復的圖像相比，具有更好的清晰度和更高的對比度，從而提高了圖像的 去噪的質量。下面我們給出線性殘差迭代算法，對于推導過程可以參考文獻4算法3.8 Linear Residual Iterative Algorithm1.初女臺化：/ 0” 0, = w。= 0;2.當不收斂時，循環3.儼+i 儼+人（人一A/）；4.林+3（2皆+1皆）；5.廣TW；6.k j k + 1;循環結束.7.輸出迭代結果氣或者規范化如下:算法 3. 9 Linear Ar Residual Iterative Algorithm初始化： 0” 0, = g = 0;當不收斂時，循環gEg*+d）；wE1

48、+3疽（2gE g。；uk+i 0” 0, = g = 0; 當不收斂時，循環 gE g+d/); vfE*+3A(2gEg。； uk+1 0” 0, = g = 0;當不收斂時，循環3.vfE*+3A+(2gE g*);uk+i T- Ts(wk+1y,k k + 1;循環結束輸出迭代結果七當A為奇異矩陣時，我們可以用逆代替A,在Matlab中的計算公式 是pinv(),為了標記方便，我們令人一 =pinv(A) 是我們得到如下公式算法 3. 11 Linear A Residual Iterative Algorithm3.3莫洛包絡算法將不可微函數變得光滑的一個典型的方法就是使用莫羅包絡

49、的思想。定義3.3.1C1表示所有下半連續凸函數的集合，我們定義 ”0商)，指標為“，在點z的包絡函數為:g伽=噱 ,性質3. 3.11包絡函數是可微的，且對上述的函數有:V (河伽)= (/_尹。饑)證明:我們假設y* = arg min所以, 、1(3.3.1)伽(劉=?斯朕_4：+心*)=萬何_：/),再根據臨近點算子的定義，我們知道y* = argmin” (3.3.2)= argmin+(y)j=Pg伽.將(3. 3.2)式代入(3.3.1),我們得到結論V 即伽(z) = (l-prox) 我們首先給出給出臨近點算子莫洛包絡的閉形式解。定理3. 3. 1 1令=proxtenv (

50、)，則z的分量解析表達式為:shrinkenv+ (t, a. ui)=； = t + attj v t OL證明：由 z = pg,enw)，令 f= env洲，則fILz = proxtf(u) = argminJ|z-w| +/(z) |zeRm 12J其中華)*叫)=呼1=!噪少1；+小|2ii我們首先分析/(z):+abl根據閾值算子的定義，我們有(i)當|z|a貝【J y = 0, (ii)當貝!| y = sgn(z)(|z| u) = z sgn(z)a ,f ()=號 + 忙sgn(z)a|1.I：因此，我們得到如下結論：|zf(z) = Jz|z = proxtf (w)

51、= argmin|z-z/|p +/(z)ZeRm 12J2郭甘k心土怵(ii)(z) = ： + |z sgn(z)a|iz = proxtf(u) = argminJ|z-z/|P +/(z) | zeRm 2J=arg 冊11|z _ “II： + 號 +_ sgn(z)a|,詳細地有,(i)當|z|a,則z = argmin|-|z-aau + aaur + a貝lj z = argmin j|-|z-ua鍋=赤、化 ocuME 當|2 +_+ L|_sgn(z)a|1 ,我們記T(z) = ：|z “I+號+z_sgn(z)a|, zE %)=捉zd) + W_,對稱軸式2= $，當

52、 z2a , zn =u-t ； 當 z2 a , a .1 9 1 9 1(2) cc, T(z) + u oct,對稱軸乙2 = + ，當2 V oc ,而=+ f;當2 2 a ,式而=a .綜上所述，得到結論。解的函數圖像為:Fig 3-1解函數圖像根據圖像的對稱性，我們構造出關于u軸對稱的解的形式：shrinkenv (t, a. =t-a1 + 0, = g = 0;當不收斂時，dogk+i gk +(b-Aukuk+i = 6shrinkenv+gk+i)k k + 1;循環結束輸出迭代結果七如果我們將算法3.12中的包絡表達式換成表達式(3.3.3),則可以得到算法3.13,算

53、法3. 13莫洛包絡迭代算法2初始化： 0, = g = 0;當不收斂時，dogk+i gk +(b-Auk)uk+i =dshrmkenv(u,a,Ar gk+1)k k + 1;循環結束輸出迭代結果抄.定理3. 3. 2：由算法3.13、3.14迭代所得的解是原基追蹤的近似解。定理3.3.3：當“TO,由算法3.13、3.14得到的解收斂到算法3.4得到的 解。證明：當a T 0時，約束條件ut t + a ,變為utt ；約束條件-a v氣v r+a ,變為tUit9且Zj =奶，變為4=0；約束條件Ui t CC 9變為W. t 9a+t即當a T 0時*,shrinkenva.u,t

54、) = shrinkenv(O,u,t) = shrink = t0, -t ut 0).八sgn(我蛙成)，礦I共八)此算法十分簡單，僅僅涉及到矩陣向量乘法和規模壓縮的運算。而且對于矩 陣向量乘法我們可以通過快速算法來提高整個迭代算法的運算速度，而且通過壓 縮算子不僅可以實現解的稀疏性而且可以實現去噪的功能，在20中作者證明了 該迭代算法的收斂性。同時Cai等人對上述迭代算法進行了規范化處理，即令 廣1 =疽gE ,得到一種變形的線性的Bregman迭代方法22jk+i=gk+(g-Auk)但是該迭代針對A是滿秩并且有AAr=I的情形提出的。實際中，在大部分 問題中的矩陣A并不具備這樣的特性

55、，于是對但A仍是滿秩的情況張慧等人給出一種改進的線性Bregman迭代方法：廣1 頊+(g_M)=以(牙廣).其中A*為A的Moore-Penrose廣義逆，在該迭代的第二步中，仍可以利用 壓縮算子來壓縮極小化匕模解來獲得稀疏性解并同時達到去噪的目的，但這一 步也對極小化的J模解引入了誤差，因為A*一般無法精確獲取。4.2.矩陣補全問題的軟閾值Xk =DT(Yk9X+=Z=argminXY-Z|,X cRgK 2其中應是A的MP廣義逆。類似的，我們可以更新Y,Z同時在最新獲得值 要固定其他的值。這個過程產生了如下迭代計算格式：X+=ZY =ZYt(YYt)匕=(XjZ 三(XXj(X：Z),Z

56、+ = X+K + %w_x其中乙=A(ArA)fAr =QQt是A的值域空間R(A)的上的正交投影。Q = orth(A)是R(A)的正交基。A的廣義逆，R(A)的正交基和R(A)的正交投影可 以從A的SVD分解或QR分解計算出來。5.1.2非線性類SOR格式數值模擬表明在2.1節的簡單方法，盡管很可靠，但是大型的低秩矩陣不是 高效的。一個可能的加速技巧可能涉及將擴展的求解凸優化的經典增廣的拉格朗 日交替方向方法應用到分解模型(看看文獻31, 41等ADM拓展方法)。然而, 在本文中，我們研究了一類非線性連續超松弛方法：我們發現這種方法在求解矩 陣補全問題上特別的高效。在數值線性代數中，求解

57、線性方程組的SOR方法通過應用外推法到GS方 法來推導。也就是說，新的嘗試點是前一步迭代點和對每個分量的GS連續迭代 的加權平均。合適的加權會導致快速的收斂。應用這個思想到基本格式(2.1),(2.3) , (2.4)給出一個非線性SOR格式：(5.2a)X+=ZYt(YYt)X+(w) = wX+(l w)X,(5.2b)* =(X+(w)X(仞滬(X+3/Z),(5.2c)Y+(w) = wY+(l-w)Y,(5.2d)z+ (w) = X+ (w)K (w) + X+ (仞K (w),(5.2e)其中權重wlo明顯的，當w = l給出了 GS方法。假設矩陣行滿秩，在(5.2)的兩個最小二

58、乘問題可以簡化為一個像第二個基本格式(2.3)。讓我們用下面的表達式記做殘差：S = PM-XY(5.3)它將會用于測量最優性。在每一次迭代后，變量乙 它是可行的,可以表達為Z = XY + S。令Z.是矩陣XY和S的加權之和，也就是:Zw=XY + wS = wZ + (l-w) XY,(5.4)式:注意到在我們的假設下，矩陣YYt(YYtY是單位矩陣，我們獲得:ZwYt (YYt )f = (wZ + (1-w)XY)Yt (YYt )fwZYt (YYt )* + (1 w)XYYt (YYt )fwZY，(yyr)* +(iw)x.它就是步驟(5.2b).在(2.3), (2.4)中用

59、Zw取代Z,我們有下面的SOR-Like格Zw=wZ + (l-w)XY,(5.5a)x+(w)= zwytzwyt(t)(5.5b)y+ 3) = (X+ (w)r X+ (w)f (X+ (w)T ZJ,(5.5c)2c(z+(w)= %(x+(w)匕(仞)，(5.5d)兄(Z+(w) = ),(5.5e)再一次，帶有一次的QR分解的實現可以被使用正如在格式(2.4)中一樣。因為固定的權重w一般對于非線性問題是不高效的，因此接下來我們提出了 對w的更新策略：這和求解非線性規劃的信賴域方法中的調整信賴域半徑類似。 在點(X, (w), Y+ (w), Z+ (w)計算出后，我們計算殘差比率(

60、5.6)/(w) =其中S+M = PM-X+(w)Y+M).(5.7)如果/(而1,這個新的點對是可以接受的作為下一個迭代點因為達到了減 少殘差|5|f =M-XY)l的目的。在這種情形下，步驟稱為是“成功的”；否 則，步驟是不成功的，則我們必須使用新的權重刃使得保證Z(w)0,是增量，小1是上界。根據上面的考慮，我們得 到下面的算法：A low-rank matrix fitting algotithm(LMaFit)輸入指標集Q,數據集(M)和秩估計K r ；令 y G RKxn. Z=e(M),刃=1,莎 1,$0, /3(0,1),和#=0；當不收斂時，循環根據(X,Y,Z)=(X*