矩陣補(bǔ)全問題的研究與應(yīng)用

1、中圖分類號(hào)：TN911單位代碼：10425學(xué) 號(hào)：S11090947I中闞石冷上粵碩士學(xué)位論文China University of Petroleum Master Degree Thesis矩陣補(bǔ)全問題的研究與應(yīng)用The research and Application of Matrix CompletionProblem學(xué)科專業(yè)：數(shù)學(xué)研究方向：圖像處理作者姓名：伏路 指導(dǎo)教師：李維國(guó)教授二。一四年六月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)關(guān)于學(xué)位論文的獨(dú)創(chuàng)性聲明本人鄭重聲明：所呈交的論文是本人在指導(dǎo)教師指導(dǎo)下獨(dú)立進(jìn)行研究工作所取得 的成果，論文中有關(guān)資料和數(shù)據(jù)是實(shí)事求是的。盡我所知，除文中已經(jīng)加以標(biāo)注和致 謝外，本論文不包含其他人已經(jīng)發(fā)表或撰寫的研究成果，也不包含本人或他人為獲得 中國(guó)石油大學(xué)（華東）或其它教育機(jī)構(gòu)的學(xué)位或?qū)W歷證書而使用過的材料。與我一同工 作的同志對(duì)研究所做的任何貢獻(xiàn)均已在論文中作出了明確的說明。若

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

4、提高現(xiàn)有的理論，使其應(yīng)用在壓縮感知等稀疏問題。本文的創(chuàng)新點(diǎn)有以下幾點(diǎn)：第一:提出了改進(jìn)的線性Bregman迭代算法以及應(yīng)、與線性殘差迭代算法。第二：推導(dǎo)了臨近點(diǎn)算子和軟閾值算子之間的關(guān)系，并將莫洛包絡(luò)思想應(yīng)用 于求解基追蹤問題。第三：運(yùn)用加速超松弛技術(shù)，使矩陣補(bǔ)全的低秩矩陣擬合算法得以實(shí)現(xiàn)。第四：用新的方法推導(dǎo)交替迭代算法，并將其用于分解非負(fù)矩陣。關(guān)鍵詞：壓縮感知，矩陣補(bǔ)全，矩陣分解，交替迭代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矩陣補(bǔ)全問題的論述2 HYPERLINK l bookmark21 o Current Document 第二章預(yù)備知識(shí)

10、32.1凸優(yōu)化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距離的定義與性質(zhì)123.2基追蹤公式推導(dǎo)及木目關(guān)證明 123.2.1問題陳述123.2.2 線性Bregman迭代算法133.2.3線性殘差迭代算法203.3莫洛包絡(luò)算法243.4數(shù)值模擬29 HYPERLINK l b

11、ookmark105 o Current Document 第四章軟閾值算法344.1基追蹤問題的軟閾值迭代344.2矩陣補(bǔ)全問題的軟閾值 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 第六章交替迭代算法求解非負(fù)因子的矩陣補(bǔ)全426. 1非負(fù)矩陣分解的定義426.2相關(guān)的算法436.3主要算法446.4 收斂性分析476.5非線

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

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

14、零分量的個(gè)數(shù) 不斷增加，一直趨向于原始信號(hào)，同時(shí)對(duì)于單個(gè)非零分量而言，它的信號(hào)范數(shù)也 隨著迭代次數(shù)的增加而單增不減（這也和它的收斂性理論是吻合的）；其它方法 （比如分裂算子不動(dòng)點(diǎn)迭代方法，梯度下降法的Landweber迭代法）的非零分量 個(gè)數(shù)逐漸趨向于原始信號(hào)。我們開始以為，稀疏信號(hào)，會(huì)導(dǎo)致相對(duì)較少的迭代次 數(shù)。實(shí)際上通過實(shí)驗(yàn)，我們發(fā)現(xiàn)對(duì)于非稀疏的向量，Bregman迭代算法的恢復(fù)效 果也是比較好的。基追蹤問題是矩陣補(bǔ)全問題中的一個(gè)很典型的例子：由一維問題（向量）向 二維問題（矩陣）轉(zhuǎn)變，它是許多新型算法的試金石。隨著研究的深入，我們發(fā)現(xiàn)在許多應(yīng)用中出現(xiàn)了極小化矩陣秩的問題，比如： 控制系統(tǒng)理

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

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

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

18、1 -(y)，對(duì)于02/(x) + (Vf(x)r(y-x).定理2.1.2對(duì)于凸規(guī)劃問題，目標(biāo)函數(shù)的任一局部極小點(diǎn)都是目標(biāo)函數(shù)在 非空可行集上的全局極小點(diǎn)。定理2.1.3對(duì)于凸規(guī)劃問題，若目標(biāo)函數(shù)在非空可行集上是嚴(yán)格凸函數(shù)， 則此問題的全局極小點(diǎn)是唯一的。2.2正則化方法正則化方法開始于二十世紀(jì)四十年代，經(jīng)過二十多年的發(fā)展，形成了系統(tǒng)的 理論支持，在上個(gè)世紀(jì)八十年代趨向于成熟，九十年代開始朝著實(shí)際應(yīng)用方面發(fā) 展。人們?cè)谇蠼獾谝活惙e分方程的基礎(chǔ)上發(fā)明了正則化方法。因?yàn)檫@種方法是最 早由前蘇聯(lián)院士 Tikhonov AN提出來，所以這種方法又被稱為Tikhonov正則化 方法。首先看看正則化算子

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

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

21、 是由Ryzhikov和Biryulina提出的，他們提出的適定性正則化方法就是根據(jù) H = 0)t得到的，進(jìn)而我們得到(2 +a/)r =中產(chǎn)，我們?cè)龠M(jìn)一步討論，我們就可以得到適定性正則化方法具有比Tikhonov正 則化方法更強(qiáng)的正則化，我們?cè)诖瞬辉儋樖?，有興趣的，可參考相關(guān)文獻(xiàn)。2.2.2迭代正則化方法我們都知道用迭代的方法可以求解不同的正向問題(有限維數(shù)或無窮維數(shù) 的），而且迭代法還有一個(gè)好處：當(dāng)將無窮維變?yōu)榫€性代數(shù)方程組后（有限維）, 系數(shù)矩陣的結(jié)構(gòu)在求解過程并不會(huì)得到損壞，而且可以節(jié)省存儲(chǔ)空間，這有利于 求解大規(guī)模問題。后來我們發(fā)現(xiàn)通過迭代還可以求解反問題，但是在解決問題的 過程中

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

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

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

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

26、r0)的加x復(fù)矩陣，則存在m階酉矩陣/與階酉矩陣V , 有H 01uhav= =ao o其中Z7 = 6/詼(,，?), D (Z = 1,2,，,)是矩陣A的全部非零奇異值。證明 設(shè)埃爾米特矩陣AhA的n個(gè)特征值按如下優(yōu)先次序排列：有卒=人=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.設(shè)1=

27、4%萬-1,則U?U=E,。記U=g%,.），因此我們可將 i，2,擴(kuò)充成C的一組標(biāo)準(zhǔn)正交基，記擴(kuò)充的m-r個(gè)向量分別為, 并且組成的矩陣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的奇異值分解的簡(jiǎn)化表達(dá)形式。定理2. 2. 6. 2 假設(shè)AeCmxw, A的非零奇異值分別為 cr2 ,i，2,是對(duì)應(yīng)于奇異

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

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

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

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

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

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

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

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

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

37、的初始值/及O?(,/),%() = ?|則7烏()=疽(如一。)，據(jù) PFBS 算 法可知，求解(3.4)的迭代公式為(3. 11)U =/（/ ） = /A/ _人）因?yàn)?|VE（）-VK（u）|dA5M-U|,由定理 3. 1,知參數(shù) Ov3v2IM時(shí)，取頊，則迭代(3.11)收斂到(3.7)的一個(gè)解。在具體的計(jì)算過程中，我們 只會(huì)迭代有限步數(shù)，我們將迭代步數(shù)設(shè)為Mk，則=此.由于pMa/W， 再根據(jù)最值函數(shù)的一階必要條件知道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結(jié)合上面的討論，我們將用PFBS算法來求解Bregman迭代正則化的過程歸 結(jié)為下面的線性Bregman迭代算法。算法 3. 3 Linear Bregman Iterative Algorithm初始化：30,=0,迭代次數(shù)序列虬當(dāng)不收斂時(shí)，do i = 0-Mk -1舟uk, uk J 舟-3At (A/ b);k1_k . 2uk,l+i arg min M /nDj (,*)u u ;結(jié)束內(nèi)層循環(huán)25E質(zhì)；pEL(E虹 T)L 疽(A/M-l人)；jd8k k + 1;結(jié)束外層循環(huán)，輸出氣以上是PFBS求解一般函數(shù)的步驟，內(nèi)層循環(huán)采用不動(dòng)

39、點(diǎn)迭代的算法，但是 對(duì)于極小化目標(biāo)函數(shù)的分量可以分離的，可以給出具體的算子公式，對(duì)基追蹤問 題我們就可以采用這種技巧。由=/矛(必)= /，5疽(A/一人)，并且令Mk =1,Bregman 迭代 (3. 11)變?yōu)?+1=4用血11心心/(。-|1-(,*,-*) + 備。-(*-3人7(人*-/?)。0, “是不變常量。并且設(shè)sgn（）為符號(hào)函數(shù)，定義如下：sgn(x) = 01, % 0(3. 17)(3. 18)則求解/（x） = a|x| + |-（x-/?）極小值的算子為:項(xiàng)）=其中2（”）就是函數(shù)f的極小點(diǎn)。設(shè)=（綺,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為正則化參數(shù)，30為步長(zhǎng)參數(shù)。因?yàn)楫?dāng)30時(shí)， 隊(duì)四廣）= %（，），所以不（汗山）=以（盧1），從而（3.21）可以簡(jiǎn)化為：k+i = vk +（b-Auk uk+1 = 6Tvk+1）（3.22）uQ =vQ =0為了后面的討論的方便，我們對(duì)（3.22）做規(guī)范化處理。令gk+1 = gk +（Jb-Auk g = 0 ,則 gS = （人 - Az/）,從而z=0疽gE=文疽(八做村廣.z=0因而(3.2

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

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

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

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

45、代正則化過程中，當(dāng)* = 1日寸，艮P b2 = b1 + V1 =b + vr =ur +2( - I?) + 2w表明殘 差鏟被加回到原噪聲圖像人中，與b1=b = u1+(u-u1) + w比，可知。之包含兩倍 的要恢復(fù)的有用信息和兩倍的噪聲成分w,我們進(jìn)一步求出= / + 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.利用數(shù)學(xué)歸納法并借助b=b + (bF)可以很容易地推出上面的公式，為 了方便陳述，設(shè)C (L-W)表示單項(xiàng)式U-U1中/的系數(shù)，從上面的遞推公式可以 看出，文C(LW) = -佐+ 1),恰好與w的系數(shù)的代數(shù)和為零。i=l在Bregman迭代求解/過程中，一方面，極小化Bregman距離使/繼承了 W的信息；另一方面，極小化k-釧時(shí)的/恢復(fù)了部分（_/）信息，這使得/ 比/更好地逼近L .盡管由于/收斂于力=1 + w使得uk總包含一些噪聲成分， 但是，|p -Z?|趨于|R-嚇的性質(zhì)使得Bregman迭代正則化恢復(fù)的圖像/與R

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

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

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

50、)，則z的分量解析表達(dá)式為: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根據(jù)閾值算子的定義，我們有(i)當(dāng)|z|a貝【J y = 0, (ii)當(dāng)貝!| y = sgn(z)(|z| u) = z sgn(z)a ,f ()=號(hào) + 忙sgn(z)a|1.I：因此，我們得到如下結(jié)論：|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 冊(cè)11|z _ “II： + 號(hào) +_ sgn(z)a|,詳細(xì)地有,(i)當(dāng)|z|a,則z = argmin|-|z-aau + aaur + a貝lj z = argmin j|-|z-ua鍋=赤、化 ocuME 當(dāng)|2 +_+ L|_sgn(z)a|1 ,我們記T(z) = ：|z “I+號(hào)+z_sgn(z)a|, zE %)=捉zd) + W_,對(duì)稱軸式2= $，當(dāng)

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

53、法3. 13莫洛包絡(luò)迭代算法2初始化： 0, = g = 0;當(dāng)不收斂時(shí)，dogk+i gk +(b-Auk)uk+i =dshrmkenv(u,a,Ar gk+1)k k + 1;循環(huán)結(jié)束輸出迭代結(jié)果抄.定理3. 3. 2：由算法3.13、3.14迭代所得的解是原基追蹤的近似解。定理3.3.3：當(dāng)“TO,由算法3.13、3.14得到的解收斂到算法3.4得到的 解。證明：當(dāng)a T 0時(shí)，約束條件ut t + a ,變?yōu)閡tt ；約束條件-a v氣v r+a ,變?yōu)閠Uit9且Zj =奶，變?yōu)?=0；約束條件Ui t CC 9變?yōu)閃. t 9a+t即當(dāng)a T 0時(shí)*,shrinkenva.u,t

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

55、，于是對(duì)但A仍是滿秩的情況張慧等人給出一種改進(jìn)的線性Bregman迭代方法：廣1 頊+(g_M)=以(牙廣).其中A*為A的Moore-Penrose廣義逆，在該迭代的第二步中，仍可以利用 壓縮算子來壓縮極小化匕模解來獲得稀疏性解并同時(shí)達(dá)到去噪的目的，但這一 步也對(duì)極小化的J模解引入了誤差，因?yàn)锳*一般無法精確獲取。4.2.矩陣補(bǔ)全問題的軟閾值Xk =DT(Yk9X+=Z=argminXY-Z|,X cRgK 2其中應(yīng)是A的MP廣義逆。類似的，我們可以更新Y,Z同時(shí)在最新獲得值 要固定其他的值。這個(gè)過程產(chǎn)生了如下迭代計(jì)算格式：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分解計(jì)算出來。5.1.2非線性類SOR格式數(shù)值模擬表明在2.1節(jié)的簡(jiǎn)單方法，盡管很可靠，但是大型的低秩矩陣不是 高效的。一個(gè)可能的加速技巧可能涉及將擴(kuò)展的求解凸優(yōu)化的經(jīng)典增廣的拉格朗 日交替方向方法應(yīng)用到分解模型(看看文獻(xiàn)31, 41等ADM拓展方法)。然而, 在本文中，我們研究了一類非線性連續(xù)超松弛方法：我們發(fā)現(xiàn)這種方法在求解矩 陣補(bǔ)全問題上特別的高效。在數(shù)值線性代數(shù)中，求解

57、線性方程組的SOR方法通過應(yīng)用外推法到GS方 法來推導(dǎo)。也就是說，新的嘗試點(diǎn)是前一步迭代點(diǎn)和對(duì)每個(gè)分量的GS連續(xù)迭代 的加權(quán)平均。合適的加權(quán)會(huì)導(dǎo)致快速的收斂。應(yīng)用這個(gè)思想到基本格式(2.1),(2.3) , (2.4)給出一個(gè)非線性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)其中權(quán)重wlo明顯的，當(dāng)w = l給出了 GS方法。假設(shè)矩陣行滿秩，在(5.2)的兩個(gè)最小二

58、乘問題可以簡(jiǎn)化為一個(gè)像第二個(gè)基本格式(2.3)。讓我們用下面的表達(dá)式記做殘差：S = PM-XY(5.3)它將會(huì)用于測(cè)量最優(yōu)性。在每一次迭代后，變量乙 它是可行的,可以表達(dá)為Z = XY + S。令Z.是矩陣XY和S的加權(quán)之和，也就是:Zw=XY + wS = wZ + (l-w) XY,(5.4)式:注意到在我們的假設(shè)下，矩陣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分解的實(shí)現(xiàn)可以被使用正如在格式(2.4)中一樣。因?yàn)楣潭ǖ臋?quán)重w一般對(duì)于非線性問題是不高效的，因此接下來我們提出了 對(duì)w的更新策略：這和求解非線性規(guī)劃的信賴域方法中的調(diào)整信賴域半徑類似。 在點(diǎn)(X, (w), Y+ (w), Z+ (w)計(jì)算出后，我們計(jì)算殘差比率(

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