一種求解低秩矩陣填充問題的新方法

王燕榮,尹佳杰,閆喜紅

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

0 引言

低秩矩陣填充問題是指,主要研究的是在已知采樣矩陣部分元素的前提下,合理精確地填充一個低秩矩陣,此類問題已經(jīng)成為了圖像恢復(fù)[1]、人臉識別[2]等信息科學(xué)領(lǐng)域和工程領(lǐng)域關(guān)注的焦點.其數(shù)學(xué)模型為:

(1)

其中X,D∈Rm×n,PΩ(D)是已知的矩陣,Ω是所有已知元素的下標集合,PΩ(D)是Ω的正交投影.問題(1)是一個典型的非凸問題.Candes和Recht[3]提出低秩矩陣可以通過解決如下的凸優(yōu)化問題實現(xiàn)矩陣的填充:

(2)

對于求解模型(2)的算法Wang等人最近提出了兩種簡單且高效的算法來解決低秩矩陣的填充問題.這兩種算法的基本理論依據(jù)是當r固定時,在r維流形上用標準的SVD或最小二乘法找到最優(yōu)的可行矩陣.并且逐步更新流形的維數(shù),即更新矩陣的秩,實現(xiàn)可行矩陣收斂于問題(1)的最優(yōu)解.

但這兩種算法本質(zhì)上都是對矩陣的秩采用逐步加一的方法進行更新,這樣導(dǎo)致收斂最優(yōu)解的速度較慢.本文用割線法更新秩,從而建立一種求解低秩矩陣填充問題的新方法,并通過數(shù)值實驗驗證了新方法的有效性.

1 相關(guān)算法介紹[4]

1.1 算法1:最優(yōu)低秩矩陣近似(OLRMA)算法

1.2.1 基本理論依據(jù)

在r維流形上可行矩陣和它的投影之間的距離:

(3)

結(jié)合模型(1)和模型(3),當r0,當r=minr(X)時mind(Y,r)=0.基于標準的SVD來填充矩陣Yk,搜索在可行矩陣集合中重復(fù)的可行矩陣,直到d(Y,r)的值達到最小即可行矩陣收斂于最優(yōu).

1.1.2 算法1的具體步驟

第一步:首先給定下標集合Ω,樣本元素PΩ(D),參數(shù)0

第二步:計算矩陣YK的SVD:[Uk,Σk,Vk]=lansvd(Yk,r,L);

第三步:令Xk=Uk∑kVkT;

第四步:如果‖PΩ(D)-PΩ(Xk)‖F(xiàn)≤‖PΩ(D)‖F(xiàn),rk+1=rk否則rk+1=rk+1;

第六步:判斷‖PΩ(D)-PΩ(Xk)‖F(xiàn)/‖PΩ(D)‖F(xiàn)≤ε.如果成立,停止,否則轉(zhuǎn)到第二步.

輸出矩陣Yk.

1.2 算法2優(yōu)化的最優(yōu)低秩矩陣近似基于Ω(OLRMAO)算法

1.2.1 基本理論依據(jù)

(4)

這樣的解決方案將比算法1更加接近最優(yōu)解,顯然,這將會是解決優(yōu)化問題(4)的時間.在算法2中給出了主要的步驟,對(4)的一致性進行了重寫(見步驟三),d和mi分別是矩陣PΩ(D)和矩陣PΩ(Mik)的向量形式,而且Mik=(m1k,m2k,…,mrk)是它等于所觀察到的條目總數(shù)的大小.

1.2.2 算法2的具體步驟

第一步:首先給定下標集合,樣本元素P(D),參數(shù)0

第二步:計算矩陣YK的SVD:[Uk,Σk,Vk]=lansvd(Yk,r,L);

第五步:如果‖PΩ(D)-PΩ(Xk)‖F(xiàn)≤‖PΩ(D)‖F(xiàn),rk+1=rk否則rk+1=rk+1;

第七步:判斷‖PΩ(D)-PΩ(Xk)‖F(xiàn)/‖PΩ(D)‖F(xiàn)≤ε.如果成立,停止,否則轉(zhuǎn)到第二步.

2 新算法的提出

2.1 基本理論依據(jù)

在算法1和算法2中,在每次更新流形的維數(shù)上采用逐步加一的方法,這種方法雖然能夠保證所求的矩陣是低秩矩陣,但這種方法,對于更新流形的維數(shù)比較慢,特點是當目標矩陣的秩比較大時,運行時間較長,效率較低.針對以上算法中的缺點,我們提出了流形維數(shù)的新方法.

基本理論是把誤差看成是流形維數(shù)的函數(shù),利用割線法尋找最優(yōu)的流形維數(shù).把這種思想結(jié)合算法1和算法2,形成如下新的算法3秩更新的最優(yōu)低秩矩陣近似(OLRMA2)算法和算法4秩更新優(yōu)化的最優(yōu)低秩矩陣近似基于 (OLRMAO2)算法.

2.2.1 算法3的具體步驟

第一步:首先給定下標集合,樣本元素P(D),參數(shù)0

第二步:計算矩陣YK的SVD:[Uk,Σk,Vk]=lansvd(Yk,r,L);

第三步:令Xk=Uk∑kVkT;

第四步:如果‖PΩ(D)-PΩ(Xk)‖F(xiàn)≤‖PΩ(D)‖F(xiàn),rk+1=rk.否則令

第六步:判斷‖PΩ(D)-PΩ(Xk)‖F(xiàn)‖PΩ(D)‖F(xiàn)≤ε.如果成立,停止,否則轉(zhuǎn)到第二步.

得到的矩陣Yk就是我們需要的矩陣.

2.2.2 算法4的具體步驟

第一步:首先給定下標集合,樣本元素P(D),參數(shù)0

第二步:計算矩陣Yk的SVD:[Uk,Σk,Vk]=lansvd(Yk,r,L);

第五步:如果‖PΩ(D)-PΩ(Xk)‖F(xiàn)≤‖PΩ(D)‖F(xiàn),rk+1=rk;

第七步:判斷‖PΩ(D)-PΩ(Xk)‖F(xiàn)/‖PΩ(D)‖F(xiàn)≤ε.如果成立,停止,否則轉(zhuǎn)到第二步.

3 數(shù)值實驗

針對隨機矩陣的矩陣填充,對兩種算法(將割線法更新秩的算法和Wang等人的算法)進行比較,所有數(shù)值實驗語言的編寫使用軟件Matlab7.0.

表1和表2中可以看到在矩陣維數(shù)n較小的時候,割線法更新秩的新算法所需要的時間和效率比原來的算法要好;當n逐漸增大時,割線法更新秩的弊端逐漸顯示出來,時間和效率都略微低于原先的算法.

當矩陣的秩r較大的時,割線法更新秩的算法需要的時間比原算法要少;但當矩陣的秩r較小時,割線法更新秩的算法需要的時間比原算法要多.

表1 算法1和算法3隨機矩陣填充問題的數(shù)值結(jié)果

表2 算法2和算法4隨機矩陣填充問題的數(shù)值結(jié)果

本文首先用割線法更新秩的方法來得到新的算法.然后對隨機矩陣的矩陣填充進行了數(shù)值實驗.實驗結(jié)果顯示:割線法更新秩的算法在矩陣較小的時候,在準確性和效率上都比原先的算法要好;對秩較大的矩陣填充問題,割線法更新秩的算法顯示其本身具有的優(yōu)越性.但是對于大型矩陣的填充,割線法更新秩的算法還有待進一步改進.