基于中值修正的兩種Toeplitz矩陣填充的低秩逼近算法

,,

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

1 預備知識

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

minrank(X)

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

(1)

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

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

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

min‖X‖*

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

(2)

在實際應用中,采樣矩陣往往具有特殊結構,如Toeplitz和Hankel結構等,因此研究特殊矩陣的填充問題很有意義.Toeplitz矩陣作為一種重要的特殊矩陣,在廣泛的科學與工程領域,特別是在信號與圖像處理領域發揮著重要作用.一個n×n的Toeplitz矩陣T∈Rn×n具有如下形式:

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

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

文章的結構如下:第二節對現有的算法進行簡單的回顧,然后再詳細的介紹基于中值理論的OR1MP與EOR1MP算法;第三節通過數值實驗將新算法與OR1MP、EOR1MP算法進行比較,驗證算法的有效性;第四節對全文進行總結.

2 算法

2.1 算法回顧

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

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

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

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

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

第三步:計算Xk-1和Mk的最優權向量αk,min‖α1Xk-1+α2(Mk)Ω-YΩ‖2;

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

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

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

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

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

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

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

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

3 數值實驗

表1 當p=0.4且maxiter=20時,算法OR1MP和MOR1MP的比較

表2 當p=0.5且maxiter=20時,算法OR1MP和MOR1MP的比較

表3 當‖Rk‖F/‖YΩ‖F≤tol時,算法OR1MP和MOR1MP的比較

注. 在表 3.3 中,設置最大迭代次數為 100.

表4 當p=0.4且maxiter=20時,算法EOR1MP和MEOR1MP的比較

表5 當p=0.5且maxiter=20 時,算法 EOR1MP和MEOR1MP的比較

表6 當‖Rk‖F≤tol時,算法 EOR1MP和 MEOR1MP 的比較.

4 總結

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