基于交替閾值迭代的稀疏–低秩矩陣分解

基于交替閾值迭代的稀疏–低秩矩陣分解

1稀疏–低秩矩陣分解在工程應(yīng)用中，許多復(fù)雜的系統(tǒng)通常由幾個(gè)簡(jiǎn)單的系統(tǒng)組成。為了更好地理解復(fù)雜系統(tǒng)的行為和性質(zhì)，人們經(jīng)常使用復(fù)雜系統(tǒng)的分解來(lái)研究一些簡(jiǎn)單的系統(tǒng)。特別是，如果復(fù)雜系統(tǒng)的矩陣是稀疏矩陣和低秩矩陣的總和，則復(fù)雜系統(tǒng)的分解可以概括為稀疏矩陣和低秩矩陣的分解：已知矩陣d可以表示為低秩矩陣a和稀疏矩陣e的對(duì)應(yīng)矩陣，a的秩序信息和稀疏結(jié)構(gòu)信息未知。如何正確分解矩陣a和e？問(wèn)題的數(shù)學(xué)模型如下。其中rank(A)表示矩陣A的秩,∥E∥顯然,稀疏–低秩矩陣分解問(wèn)題通常是病態(tài)的(NP-hard).受壓縮感知與統(tǒng)計(jì)領(lǐng)域相關(guān)研究工作這里∥·∥然而,實(shí)際中的系統(tǒng)往往會(huì)受噪聲影響,矩陣D不能嚴(yán)格地表示成低秩矩陣與稀疏矩陣之和.為此,文獻(xiàn)[7]在假設(shè)∥D-A-E∥為求解優(yōu)化問(wèn)題(2)與(3),文獻(xiàn)[7]基于目標(biāo)函數(shù)的一階信息提出了閾值迭代框架,但算法的收斂速度很慢,且每次迭代都要進(jìn)行一次奇異值分解,無(wú)法快速求解大型實(shí)際問(wèn)題.此后,文獻(xiàn)[8]提出了直接求解原始問(wèn)題的APG算法和求解相應(yīng)對(duì)偶問(wèn)題的梯度上升算法,并通過(guò)實(shí)驗(yàn)說(shuō)明這兩種算法在處理1000×1000的矩陣時(shí)相較于閾值迭代算法加速了50倍.進(jìn)一步地,文獻(xiàn)[9]基于Lagrange乘子技術(shù)提出了不精確ALM算法(簡(jiǎn)稱為ALM算法),在顯著提高計(jì)算精度的同時(shí)其計(jì)算速度是APG算法的5倍,這是目前已知的求解大規(guī)模問(wèn)題的最好算法.稀疏–低秩矩陣分解問(wèn)題可理解成從稀疏矩陣與低秩矩陣組成的過(guò)完備字典中尋找矩陣D的(近似)最簡(jiǎn)單表示A+E,其中稀疏矩陣E的簡(jiǎn)單程度用其非零元素的個(gè)數(shù)即矩陣的l近年來(lái)已發(fā)展成熟的l其中考慮到S與目前最好的ALM算法相比,大量的模擬實(shí)驗(yàn)說(shuō)明本文所提出的交替閾值迭代算法具有以下優(yōu)點(diǎn):達(dá)到收斂所需迭代次數(shù)與時(shí)間代價(jià)大幅降低,對(duì)噪聲有更強(qiáng)的穩(wěn)健性,分解出的低秩矩陣的秩更接近于真實(shí)值,同時(shí)算法的可靠性對(duì)矩陣A的低秩程度依賴更少.另外,在監(jiān)控視頻背景建模2基于admm的迭代閾值迭代算法2.1求解新模型的lagrange乘子更新ADMM是一類用于求解分布式凸優(yōu)化問(wèn)題的簡(jiǎn)單有效算法,它采用分解–協(xié)同過(guò)程(decomposition-coordinationprocedure)處理問(wèn)題,同時(shí)具備對(duì)偶上升算法的可分解性和增廣Lagrange乘子法的收斂性,一般用于求解如下形式的優(yōu)化問(wèn)題:考慮問(wèn)題的增廣Lagrange乘子形式:其中y表示線性等式約束的乘子,μ>0表示對(duì)不滿足線性等式約束的懲罰因子,也稱為增廣Lagrange參數(shù),則ADMM主要由以下3個(gè)子迭代過(guò)程構(gòu)成:顯然,ADMM與對(duì)偶上升法和乘子法非常相似,由x極小化、z極小化和對(duì)偶變量y更新組成,且對(duì)偶變量的更新步長(zhǎng)與乘子法一樣取為μ.雖然ADMM的收斂性理論建立在目標(biāo)函數(shù)f(·)和g(·)為凸函數(shù)的基礎(chǔ)上,但其思想可推廣到非凸優(yōu)化問(wèn)題的求解,本文正是基于這樣的推廣來(lái)設(shè)計(jì)求解新模型(4)的交替閾值迭代算法.我們先考慮新模型的增廣Lagrange乘子形式:其中Y∈R通過(guò)對(duì)更新矩陣A和E所需求解子問(wèn)題的目標(biāo)函數(shù)進(jìn)行分解與重組,可得到如式(9)的簡(jiǎn)化形式:uf8f1上述交替閾值迭代算法的關(guān)鍵是在每次迭代中交替更新低秩矩陣、稀疏矩陣和Lagrange乘子,直到滿足預(yù)先設(shè)定的收斂條件.因此,算法整體的計(jì)算精度與時(shí)間代價(jià)在很大程度上取決于式(10)中兩個(gè)子問(wèn)題的求解.2.2最優(yōu)的顯式求解式(10)中更新稀疏矩陣和低秩矩陣所需要求解的兩個(gè)子問(wèn)題可分別簡(jiǎn)化成如下形式:問(wèn)題(11)的求解比較簡(jiǎn)單,文獻(xiàn)[9]已證明a=1時(shí)的最優(yōu)解為ST其中sgn(·)是符號(hào)函數(shù).由于在a=1與1/2這兩種情形下,問(wèn)題(11)的目標(biāo)函數(shù)與約束條件關(guān)于矩陣的元素都是逐個(gè)可分的,采用類似的方法可證明a=1/2時(shí)的最優(yōu)解為H其中問(wèn)題(12)的求解相對(duì)困難,我們以下述定理1給出它的顯式解.將非凸優(yōu)化問(wèn)題(12)的目標(biāo)函數(shù)展開(kāi)可得由于Q(U參考文獻(xiàn)[11]中有關(guān)向量Half閾值算子的推導(dǎo)過(guò)程可得σ記g(t顯然,上述問(wèn)題的最優(yōu)解u綜上,由于矩陣W的秩為r,則問(wèn)題(12)的最優(yōu)解為X2.3admm框架下的算法更新條件利用問(wèn)題(11)與(12)的顯式解,我們給出實(shí)現(xiàn)求解問(wèn)題(4)的交替閾值迭代算法如下:1)初始化{Y2)更新低秩成分A3)更新稀疏成分E由于ADMM框架下算法的收斂速度與參數(shù)μ的取值有關(guān),為避免算法收斂速度對(duì)參數(shù)μ初始值選取的依賴性并同時(shí)加速其收斂,我們可在每次迭代中使用不同的參數(shù)為便于后文敘述,如下約定不同參數(shù)取值與更新方式下的算法:a=1/2時(shí),若參數(shù)μ3估計(jì)子空間矩陣的秩序誤差本節(jié)將在有、無(wú)噪聲干擾兩種情形下,比較AHH,IHH,AHO和ALM這4種算法實(shí)現(xiàn)(近似)稀疏–低秩矩陣分解的精度與效率,并研究算法對(duì)低秩成分的低秩程度與稀疏成分的稀疏程度的穩(wěn)健性.對(duì)于待分解的矩陣D∈R1)獨(dú)立生成隨機(jī)矩陣L,R∈R2)均勻隨機(jī)選取稀疏矩陣E∈R3)生成各元素獨(dú)立服從均值為0標(biāo)準(zhǔn)差為σ的正態(tài)分布的矩陣N∈R由于4種算法都要預(yù)估計(jì)子空間矩陣的秩,而模擬實(shí)驗(yàn)中真實(shí)秩是已知的,我們通過(guò)大量的模擬實(shí)驗(yàn)發(fā)現(xiàn):當(dāng)秩估計(jì)偏小時(shí),AHH與AHO算法不收斂;當(dāng)秩估計(jì)不小于真實(shí)秩也不超過(guò)真實(shí)秩的10倍時(shí),4種算法都收斂且計(jì)算精度與迭代次數(shù)隨秩估計(jì)的增大基本保持穩(wěn)定,但時(shí)間代價(jià)明顯增加.因此,模擬實(shí)驗(yàn)中4種算法的秩估計(jì)都取為真實(shí)秩的1.5倍.另外,根據(jù)經(jīng)驗(yàn)取模型(4)中的正則化參數(shù)3.1模型2:ihh和ahh算法當(dāng)矩陣D不受噪聲干擾,可分解成嚴(yán)格低秩矩陣與嚴(yán)格稀疏矩陣的加和時(shí),S1)計(jì)算精度與效率:考慮不同大小矩陣D(m=500:500:4000),令lr=0.01,sr=0.05.在每組參數(shù)設(shè)置下重復(fù)實(shí)驗(yàn)20次.記算法的分解結(jié)果為(A分析結(jié)果發(fā)現(xiàn):在計(jì)算精度方面,3種算法分解出的低秩成分與稀疏成分的相對(duì)誤差都很小,但ALM算法得到的低秩矩陣的秩略微偏大,IHH與AHH算法能得到正確的秩,且AHH算法分解出的稀疏矩陣的稀疏度更接近于真實(shí)值;在計(jì)算速率方面,隨著問(wèn)題規(guī)模的增大,ALM和IHH算法的時(shí)間代價(jià)呈近似指數(shù)增長(zhǎng)且迭代次數(shù)穩(wěn)定在27附近,而AHH算法的時(shí)間代價(jià)始終更小且增長(zhǎng)相對(duì)平緩,迭代次數(shù)穩(wěn)定為7次.2)對(duì)低秩程度與稀疏程度的穩(wěn)健性:稀疏–低秩矩陣分解要求低秩成分A足夠低秩同時(shí)稀疏成分E足夠稀疏,即lr和sr足夠小,下面將比較3種算法對(duì)這兩個(gè)指標(biāo)的穩(wěn)健性.我們對(duì)m=1000的矩陣設(shè)計(jì)了兩組實(shí)驗(yàn),一組是固定sr=0.05而變化lr=0.005:0.005:0.06,另一組則固定lr=0.01而變化sr=0.03:0.03:0.6.圖3和4分別記錄了兩組實(shí)驗(yàn)在不同參數(shù)設(shè)置下重復(fù)20次時(shí),3種算法分解出低秩矩陣的秩與相對(duì)誤差、迭代次數(shù)、時(shí)間代價(jià)這4項(xiàng)指標(biāo)的平均值.分析結(jié)果發(fā)現(xiàn):隨著lr的增大,3種算法計(jì)算精度與迭代次數(shù)基本不變,而AHH算法的時(shí)間代價(jià)與迭代次數(shù)始終少于ALM算法,且總能得到正確的rank(A3.2alm算法的穩(wěn)定性考慮到上節(jié)中AHH算法表現(xiàn)出的高效性,下面在有高斯噪聲的情形下比較AHO,AHH和ALM這3種算法進(jìn)行近似稀疏–低秩矩陣分解的能力.1)計(jì)算精度與效率:對(duì)不同大小的矩陣D(變化m=500:500:4000),固定lr=0.01與sr=0.05,變化高斯噪聲的標(biāo)準(zhǔn)差σ=0.1:0.1:1.每一組參數(shù)設(shè)置下重復(fù)實(shí)驗(yàn)10次,記錄3種算法分解出的低秩矩陣的秩與相對(duì)誤差、達(dá)到收斂所用迭代次數(shù)與時(shí)間代價(jià)這4項(xiàng)的平均值(圖5展示σ=0.3時(shí)的結(jié)果).分析結(jié)果發(fā)現(xiàn):ALM算法分解出的低秩矩陣的相對(duì)誤差約為AHO和AHH算法的三倍,而秩也遠(yuǎn)高于實(shí)際秩,達(dá)到收斂所需迭代次數(shù)(約36次)是AHO算法(約6次)的6倍且時(shí)間代價(jià)隨矩陣維數(shù)的增加呈指數(shù)增長(zhǎng)趨勢(shì),而AHO和AHH算法的時(shí)間代價(jià)則緩慢增加.2)對(duì)低秩程度與稀疏程度的穩(wěn)健性:對(duì)m=1000的方陣,取高斯噪聲標(biāo)準(zhǔn)差σ=0.3,一方面固定sr=0.05而變化lr=0.005:0.005:0.06,另一方面固定lr=0.01而變化sr=0.03:0.03:0.6.每組參數(shù)設(shè)置下重復(fù)實(shí)驗(yàn)20次,記錄分解出的低秩成分的秩與相對(duì)誤差、算法達(dá)到收斂所需的迭代次數(shù)與時(shí)間代價(jià)這4項(xiàng)指標(biāo)的平均值(圖6和7).當(dāng)固定sr而變化lr時(shí),ALM算法基本失效,rank(A3)對(duì)高斯噪聲的穩(wěn)健性:為研究3種算法對(duì)高斯噪聲的穩(wěn)健性,考慮m=1000,r=10,sr=0.05的方陣,變化高斯噪聲標(biāo)準(zhǔn)差σ=0.05:0.05:1.對(duì)σ的每個(gè)取值重復(fù)實(shí)驗(yàn)10次,表3記錄了3種算法恢復(fù)出低秩矩陣的秩與相對(duì)誤差和達(dá)到收斂所需迭代次數(shù)與時(shí)間代價(jià)的平均值.分析結(jié)果發(fā)現(xiàn):3種算法的errA綜合3.1與3.2兩小節(jié)的實(shí)驗(yàn)結(jié)果可得到以下結(jié)論:1)ALM算法僅能較好地求解無(wú)噪聲情形下的稀疏–低秩矩陣分解問(wèn)題,對(duì)噪聲不具有穩(wěn)健性,分解出的低秩矩陣的秩遠(yuǎn)遠(yuǎn)高于真實(shí)秩.2)在無(wú)噪聲的情形下,AHH與IHH算法在很小的時(shí)間代價(jià)下就能達(dá)到與ALM算法相同的誤差水平,且得到的低秩成分的秩準(zhǔn)確,稀疏成分的非零元個(gè)數(shù)也更接近真實(shí)值.3)在有高斯噪聲的情形下,AHO與AHH算法具有更強(qiáng)的穩(wěn)健性,且計(jì)算效率也遠(yuǎn)高于ALM算法.4在視頻監(jiān)控中的應(yīng)用背景建模與監(jiān)控視頻的活動(dòng)檢測(cè)密切相關(guān),可自然地用稀疏–低秩矩陣分解模型進(jìn)行建模.若將視頻的每一幀對(duì)應(yīng)于待分解矩陣D的每一列,則每幀中提取出的背景由于具有很強(qiáng)的相似性而構(gòu)成低秩矩陣A,少量的運(yùn)動(dòng)目標(biāo)和背景變化如光照等則對(duì)應(yīng)于稀疏矩陣和噪聲矩陣E+N.本節(jié)將分析文獻(xiàn)[4]中的兩段視頻,有顯著前景變化的數(shù)據(jù)集Hall中每幀的大小是176×144,有很多光照變化的數(shù)據(jù)集Lobby中每幀的大小是168×120.由于每幀的背景非常相似,所有幀的背景構(gòu)成的矩陣應(yīng)具有相當(dāng)?shù)椭鹊慕Y(jié)構(gòu),因此實(shí)驗(yàn)中Hall的背景矩陣秩預(yù)估計(jì)為10,Lobby的背景矩陣秩預(yù)估計(jì)為5.模型中參數(shù)λ的選取與前面模擬實(shí)驗(yàn)一致.用ALM,AHO,AHH,IHH這4種算法對(duì)250幀Lobby與300幀Hall進(jìn)行背景建模,表4記錄了各算法的時(shí)間代價(jià)、達(dá)到收斂所需迭代次數(shù)和構(gòu)建的背景矩陣的秩,圖8展示了AHO算法對(duì)兩個(gè)數(shù)據(jù)集進(jìn)行背景建模后各兩幀的效果,其中第1,4列對(duì)應(yīng)于原始幀