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

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

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