肖 云,溫瑞萍
(太原師范學(xué)院工程科學(xué)計(jì)算山西省高等學(xué)校重點(diǎn)實(shí)驗(yàn)室,山西晉中 030619)
矩陣填充問題假設(shè)當(dāng)目標(biāo)矩陣具有低秩或近似低秩的特性時(shí),其能夠?qū)写罅咳笔г氐木仃囘M(jìn)行近乎完美的填充.填充一個(gè)未知的低秩或近似低秩采樣矩陣是一個(gè)具有挑戰(zhàn)性的問題.目前,矩陣填充在機(jī)器學(xué)習(xí)[1-2]、推薦系統(tǒng)[3]、圖像處理[4]、控制理論[5]和計(jì)算機(jī)視覺[6]等數(shù)據(jù)科學(xué)領(lǐng)域中都有非常重要的應(yīng)用.
在 2009 年,Candès和 Recht[7]建立了關(guān)于矩陣填充問題的凸優(yōu)化模型:
對(duì)于求解問題(1),通常算法中的每次迭代都需要計(jì)算一個(gè)m×n階矩陣的奇異值分解(singular value decomposition,SVD).近年來,基于核范數(shù)最小化的研究,有不少的成果.如文獻(xiàn)[8]提出了一種易于實(shí)現(xiàn)的奇異值閾值算法(singular value thresholding,SVT),該算法可以得到具有低秩結(jié)構(gòu)的最優(yōu)解,并保證了填充矩陣的稀疏性,一定程度上節(jié)省了存儲(chǔ)空間,可以有效地處理低秩的大規(guī)模矩陣填充問題.但當(dāng)秩較大時(shí),此算法收斂速度緩慢甚至效果不是很理想,在文獻(xiàn)[9]給出了加速SVT算法.與此同時(shí),Toh和Yun[10]提出了加速臨近梯度算法(accelerated proximal gradient,APG);Lin 等[11]提出了比APG算法速度快、精度高的增廣拉格朗日乘子算法(augmented lagrange multiplier,ALM),該算法具有很好的操作性和收斂性,并且需要較小的存儲(chǔ)空間.
由以上算法結(jié)果報(bào)告,SVD計(jì)算花費(fèi)占去整個(gè)算法花費(fèi)的80%以上,而Toeplitz矩陣的SVD具有較低的算法復(fù)雜度,且一個(gè)n×n階的Toeplitz矩陣T ∈ Rn×n表達(dá)形式為
那是由2n-1個(gè)元素決定的,即表達(dá)式(2)的第一行和第一列元素.近年來,針對(duì)Toeplitz矩陣填充問題,方云蘭和鄭慧嬈[12]研究了Toeplitz塊矩陣填充的快速正交三角分解算法;于益華和李云翔[13]研究了基于快速小波變換的Toeplitz矩陣填充算法;Wang 和 Li[14-16]提出了 Toeplitz矩陣填充的均值算法、修正的ALM算法、保結(jié)構(gòu)算法[16];劉麗霞和王川龍[17]進(jìn)一步提出了子空間算法;Wen 等[18]、Wen和Li[19]研究了逐步結(jié)構(gòu)化的ALM算法以及l(fā)步結(jié)構(gòu)化的ALM算法.
本文主要是基于均值的增廣拉格朗日乘子算法(ALM based on mean value,MALM)算法,對(duì)中小型規(guī)模的低秩矩陣進(jìn)行填充.為了減少M(fèi)ALM算法中頻繁的數(shù)據(jù)傳輸量與結(jié)構(gòu)化操作所增加的計(jì)算量,采用ALM算法,當(dāng)?shù)仃囍饾u靠近目標(biāo)矩陣時(shí),開始對(duì)矩陣進(jìn)行尾部修正并結(jié)構(gòu)化,修正使迭代矩陣從數(shù)值上更加靠近目標(biāo)矩陣,結(jié)構(gòu)化使迭代矩陣與目標(biāo)矩陣保持同樣結(jié)構(gòu),可利用快速奇異值分解,從而減少迭代步數(shù),縮短奇異值分解時(shí)間,節(jié)約算法的整體花費(fèi).同時(shí)給出了算法收斂性分析,并通過數(shù)值實(shí)驗(yàn)驗(yàn)證了算法的有效性.下面給出一些定義:
可見,Γ(A)是由矩陣A派生的Toeplitz矩陣.換句話說,?A∈Rn×n,都可以通過結(jié)構(gòu)化算子 Γ(·)轉(zhuǎn)化為一個(gè)Toeplitz矩陣.
本文擬簡單回顧ALM和MALM,并分別比較2種算法所具有的優(yōu)缺點(diǎn),介紹關(guān)于Toeplitz矩陣填充的尾端修正ALM算法(Tailed-modification ALM,l-TMALM);運(yùn)用核范數(shù)的性質(zhì)給出新算法的收斂性分析;通過與l-MALM,MALM以及ALM算法作比較得出新算法的有效性.
符號(hào)說明.為方便起見,Rm×n表示的是m×n階的實(shí)數(shù)矩陣.矩陣A的核范數(shù)用‖A ‖*表示,而‖A ‖F(xiàn)表示矩陣A的Frobenius范數(shù).AT表示矩陣A的轉(zhuǎn)置.對(duì)于一個(gè)Toeplitz矩陣A ∈ Rn×n,diag(A ,l)表示矩陣A的第l條對(duì)角線元素,l=-n+1,…,n-1.Ω?{ - n+1,…,n-1}是采樣集,PΩ是相應(yīng)矩陣在Ω上的投影算子,滿足
其中0是一個(gè)零向量.
低秩Toeplitz矩陣的填充問題.為了方便比較,先簡單回顧ALM算法,并將其應(yīng)用到Toeplitz矩陣填充問題中.
當(dāng)問題(1)中的m=n時(shí),即矩陣A,E,D ∈ Rn×n為Toeplitz矩陣時(shí),求解式(1)的等價(jià)形式為
數(shù)值實(shí)驗(yàn)表明,ALM算法在理論和實(shí)際應(yīng)用中均有較好的效果,且該算法迭代快,具有線性全局收斂速度,但奇異值分解時(shí)間較長,精度較低,收斂效果不是很理想.
對(duì)偶算法是為了通過其對(duì)偶性求解問題(4),即首先要解決的問題是
對(duì)于最優(yōu)增廣拉格朗日乘子Y,有最速上升算法的約束集為{Y}可以用來解決問題(6),其中被約束的最速上升方向是通過將D投影在凸的目標(biāo)區(qū)域{Y}上而獲得.結(jié)果表明在尋找被約束的最速上升方向的過程中可以得到原問題(4)的最優(yōu)解.
填充Toeplitz矩陣的MALM,其思想是在ALM算法的基礎(chǔ)上,將迭代矩陣的對(duì)角元素均值化后重新賦值,使其保持Toeplitz結(jié)構(gòu).問題表述為
數(shù)值實(shí)驗(yàn)表明,與ALM和SVT算法相比,MALM算法的精度較高,收斂效果較好,對(duì)于在迭代過程中進(jìn)行結(jié)構(gòu)化處理的MALM算法保持了Toeplitz矩陣的結(jié)構(gòu),從而可以利用快速奇異值分解,使得在奇異值分解時(shí)間上要遠(yuǎn)短于其他2種算法;但是相比ALM算法,MALM算法在均值步增加了數(shù)據(jù)的傳輸.而對(duì)于一些計(jì)算機(jī)來講,數(shù)據(jù)傳輸頻繁會(huì)造成數(shù)據(jù)堆積而拖延計(jì)算時(shí)間,因此,基于減少數(shù)據(jù)傳輸量的思考,在迭代的尾端,即接近目標(biāo)矩陣時(shí)再進(jìn)行結(jié)構(gòu)化處理是增效的選擇.
對(duì)矩陣?yán)肁LM算法[11]的快速迭代l步之后,進(jìn)行尾部修正及結(jié)構(gòu)化處理.一方面,避免了均值步產(chǎn)生的頻繁數(shù)據(jù)傳輸;另一方面,尾部修正使得迭代矩陣更加靠近目標(biāo)矩陣,從而快速達(dá)到可行解,減少奇異值分解時(shí)間.算法步驟如下:
第1階段:ALM算法步.
第1步:給定下標(biāo)集合Ω,樣本Toeplitz矩陣D,參數(shù) ρ> 1,μ0> 0,以及初始矩陣 Y0,0=O,E0,0=O,k:=0,q=1,2,···,l-1.
該算法分為2個(gè)階段執(zhí)行:第1階段,使用ALM算法,利用ALM算法本身迭代速度快的性質(zhì),當(dāng)其迭代到一定程度,即迭代矩陣逐漸靠近目標(biāo)矩陣時(shí);進(jìn)入第2階段,對(duì)迭代矩陣序列進(jìn)行尾部修正并結(jié)構(gòu)化,結(jié)構(gòu)化使迭代矩陣與目標(biāo)矩陣保持同樣結(jié)構(gòu),從而可利用快速奇異值分解,修正使迭代矩陣從數(shù)值上更加逼近目標(biāo)矩陣,以便快速地達(dá)到可行解.該算法不僅減少了頻繁的數(shù)據(jù)傳輸量,而且在一定程度上節(jié)省了奇異值分解時(shí)間.
通過數(shù)值實(shí)驗(yàn)比較了 l-TMALM、l-MALM[19]、MALM[15]以及 ALM 算法[11],所有的數(shù)值實(shí)驗(yàn)均在相同工作環(huán)境中完成.實(shí)驗(yàn)中,通過對(duì)迭代步數(shù)(IT)、計(jì)算時(shí)間(time,單位為 s)、收斂誤差 1和 2(E1,E2)的分析和比較,表明l-TMALM算法無論在迭代步數(shù)上還是在奇異值的分解時(shí)間上,明顯優(yōu)于其他3種算法.E1和E2的計(jì)算式分別為
選取的樣本矩陣階數(shù)為m=n∈{800,1500,2 000,3000,4 000},經(jīng)過多次數(shù)據(jù)實(shí)驗(yàn)得出當(dāng)?shù)?階段迭代步數(shù)l=6時(shí),計(jì)算出的總迭代時(shí)間以及誤差均可達(dá)到最小,所以第1階段ALM算法步中的迭代步數(shù)l取值為6,采樣率為p∈{0 .6,0.5,0.4} ,樣本矩陣的秩為10.
4種算法的數(shù)值實(shí)驗(yàn)結(jié)果列于表1,4種算法均可成功地計(jì)算出滿足規(guī)定停止準(zhǔn)則的迭代矩陣.且l-TMALM算法在保證迭代步數(shù)和奇異值分解時(shí)間上均優(yōu)于l-MALM,MALM以及ALM算法的情況下,其迭代矩陣與原始矩陣的逼近程度最好,即E2最小,收斂效果最好.同一采樣率下,4種算法的時(shí)間比較如圖1所示.表明同一矩陣階數(shù)下,l-TMALM算法所用計(jì)算時(shí)間最短.
表1 不同采樣率時(shí)4種算法比較
圖1 不同采樣率時(shí)4種算法時(shí)間比較(a)p=0.4;(b)p=0.5;(c)p=0.6
對(duì)于Toeplitz矩陣填充問題,本文基于MALM提出了一種l-TMALM算法.算法通過尾部修正再結(jié)構(gòu)化,加速迭代矩陣與目標(biāo)矩陣的逼近過程,以便快速地達(dá)到可行解,較大程度地縮短迭代步數(shù);結(jié)構(gòu)化使迭代矩陣與目標(biāo)矩陣保持原有的Toeplitz結(jié)構(gòu),從而可利用快速奇異值分解縮短算法運(yùn)行時(shí)間,降低計(jì)算代價(jià).因此,新算法不僅克服了原始ALM算法較長的奇異值分解時(shí)間,也避免了MALM算法額外的數(shù)據(jù)傳輸量;此外,新算法的收斂效果要優(yōu)于l-MALM,MALM以及ALM算法.基于新算法的合理性和有效性,建立了與之相對(duì)應(yīng)的收斂性理論.理論分析和數(shù)值結(jié)果表明,l-TMALM算法是求解矩陣填充問題的一種有效算法.另外,未來擬將研究推廣到高維的張量填充問題,比如將其修正的思想進(jìn)一步推廣到張量填充問題,從而求解出對(duì)于具有Toeplitz結(jié)構(gòu)矩陣的張量填充算法.