,,

(太原師范學(xué)院 數(shù)學(xué)系,山西 晉中 030619)

1 預(yù)備知識(shí)

在科學(xué)技術(shù)高速發(fā)展的新時(shí)代下,矩陣填充在機(jī)器學(xué)習(xí)[1,2]、控制[3]、圖像恢復(fù)[4]、和計(jì)算機(jī)視覺[5]等信息科學(xué)領(lǐng)域發(fā)揮著重要的作用.矩陣填充首先由 Cand’es 和 Recht[6]提出,主要研究的是在已知采樣矩陣部分元素的前提下,合理精確地填充一個(gè)低秩矩陣,其數(shù)學(xué)表達(dá)式為:

minrank(X)

st:PΩ(X)=PΩ(D),

(1)

其中X,D∈Rn1×n2,Ω∈{1,2,…,n1}×{1,2,…,n2}

上述問題是矩陣填充最原始的問題,對(duì)于(1) 解的存在性及唯一性,Recht[6]等分別通過限制等距的性質(zhì)和秩為r的矩陣D的相關(guān)性解決.近年來,在己知或者能夠估計(jì)矩陣X秩的情況下,已經(jīng)有許多學(xué)者提出了有效的算法,其中比較著名的是將X寫為兩個(gè)矩陣的乘積,即:X=UV,其中U∈Rn×r,V∈Rr×n. 基于這類簡單分解模型以及交替極小化方法Tanner等提出了交替最速下降算法 (Alternating Steepest Descent,簡稱ASD[7]),結(jié)合 Riemannian 優(yōu)化,Vandereycken 提出幾何共軛梯度法 (Geometric Conjugate Gradient,簡稱GCG[8]).隨后,Boumal 等提出 Riemannian 信賴域法 (Riemannian Trust-Region,簡稱RTR[9]).Mishra 等提出Riemannian幾何法 (Riemannian Geometry,簡稱RG[10]),但是,這些算法的共同缺點(diǎn)是其梯度計(jì)算過程比較復(fù)雜.

另一方面,Cand’es 和Recht[6]提出大部分秩為r的低秩矩陣可以通過求解以下凸優(yōu)化問題來實(shí)現(xiàn)矩陣的填充:

min‖X‖*

st:Xij=Mij,(i,j)∈Ω

(2)

在實(shí)際應(yīng)用中,采樣矩陣往往具有特殊結(jié)構(gòu),如Toeplitz和Hankel結(jié)構(gòu)等,因此研究特殊矩陣的填充問題很有意義.Toeplitz矩陣作為一種重要的特殊矩陣,在廣泛的科學(xué)與工程領(lǐng)域,特別是在信號(hào)與圖像處理領(lǐng)域發(fā)揮著重要作用.一個(gè)n×n的Toeplitz矩陣T∈Rn×n具有如下形式:

顯然,Toeplitz矩陣由它的第1列和第1行共2n-1個(gè)元素決定.根據(jù)Toeplitz矩陣的特殊結(jié)構(gòu),Kailath和Sayed運(yùn)用快速Fourier變換(簡稱FFT),提出了計(jì)算n階Toeplitz矩陣與n維向量乘積的快速算法,其算法復(fù)雜度為O(nlogn).

在大多數(shù)的情況下,填充矩陣的秩是未知的,最近Wang等提出了基于正交匹配追蹤算法(Orthogonal Matching Pursuit,簡稱OMP[16])的正交秩1矩陣追蹤算法(Orthogonal Rank-One Matrix Pursuit,簡稱OR1MP[17]),但是,當(dāng)填充矩陣的秩達(dá)到預(yù)設(shè)的秩時(shí),誤差精確度較低.

文章的結(jié)構(gòu)如下:第二節(jié)對(duì)現(xiàn)有的算法進(jìn)行簡單的回顧,然后再詳細(xì)的介紹基于中值理論的OR1MP與EOR1MP算法;第三節(jié)通過數(shù)值實(shí)驗(yàn)將新算法與OR1MP、EOR1MP算法進(jìn)行比較,驗(yàn)證算法的有效性;第四節(jié)對(duì)全文進(jìn)行總結(jié).

2 算法

2.1 算法回顧

2.1.1 正交秩1矩陣追蹤算法(簡稱OR1MP)

第一步:設(shè)采樣矩陣YΩ=PΩ(D),maxiter,tol=10-3,初始矩陣X0=0,k:=1;

第六步:如果k≥maxiter或者‖Rk‖F(xiàn)/‖YΩ‖F(xiàn)≤tol,停止計(jì)算;否則,令k:=k+1,跳轉(zhuǎn)到第二步.

2.1.2 經(jīng)濟(jì)正交秩1矩陣追蹤算法(簡稱EOR1MP)

第一步:設(shè)采樣矩陣YΩ=PΩ(D),maxiter,tol=10-3,初始矩陣X0=0,k:=1;

第三步:計(jì)算Xk-1和Mk的最優(yōu)權(quán)向量αk,min‖α1Xk-1+α2(Mk)Ω-YΩ‖2;

第六步:如果k≥maxiter或者‖Rk‖F(xiàn)/‖YΩ‖F(xiàn)≤tol,停止計(jì)算;否則,令k:=k+1,跳轉(zhuǎn)到第二步.

2.2 基于中值修正的兩種新算法

2.2.1 中值修正的正交秩1矩陣追蹤算方法(簡稱MOR1MP)

第一步:設(shè)采樣矩陣YΩ=PΩ(D),maxiter,tol=10-3,初始矩陣X0=0,k:=1;

第六步:如果k≥maxiter或者‖Rk‖F(xiàn)/‖YΩ‖F(xiàn)≤tol,停止計(jì)算;否則,令k:=k+1,跳轉(zhuǎn)到第二步.

2.2.2 中值修正的經(jīng)濟(jì)正交秩1矩陣追蹤算法(簡稱MEOR1MP)

第一步:設(shè)采樣矩陣YΩ=PΩ(D),maxiter,tol=10-3,初始矩陣X0=0,k:=1;

第六步:如果k≥maxiter或者‖Rk‖F(xiàn)/‖YΩ‖F(xiàn)≤tol,停止計(jì)算;否則,令k:=k+1,跳轉(zhuǎn)到第二步.

3 數(shù)值實(shí)驗(yàn)

表1 當(dāng)p=0.4且maxiter=20時(shí),算法OR1MP和MOR1MP的比較

表2 當(dāng)p=0.5且maxiter=20時(shí),算法OR1MP和MOR1MP的比較

表3 當(dāng)‖Rk‖F(xiàn)/‖YΩ‖F(xiàn)≤tol時(shí),算法OR1MP和MOR1MP的比較

注. 在表 3.3 中,設(shè)置最大迭代次數(shù)為 100.

表4 當(dāng)p=0.4且maxiter=20時(shí),算法EOR1MP和MEOR1MP的比較

表5 當(dāng)p=0.5且maxiter=20 時(shí),算法 EOR1MP和MEOR1MP的比較

表6 當(dāng)‖Rk‖F(xiàn)≤tol時(shí),算法 EOR1MP和 MEOR1MP 的比較.

4 總結(jié)

本文中,基于中值理論,提出了兩種修正的Toeplitz矩陣填充的新算法,在進(jìn)行實(shí)驗(yàn)的過程中,使得被填充矩陣始終保持Toeplitz矩陣的結(jié)構(gòu),保證了矩陣的快速奇異值分解,這在很大程度上縮短了矩陣填充的奇異值分解的時(shí)間,從而降低了算法的整體時(shí)間,通過數(shù)值實(shí)驗(yàn),說明新算法無論在精確度方面,還是時(shí)間上,都有更好的優(yōu)勢(shì).