牛建華,王川龍

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

0 引言

矩陣填充問題近幾年發(fā)展迅速,它主要研究的是根據(jù)采樣矩陣的部分已知元素合理精確地填充一個(gè)低秩矩陣,著名的Netflix推薦系統(tǒng)[1]就是一個(gè)經(jīng)典的應(yīng)用. 該問題可以通過如下模型解決

minrank(X)

(1)

s.t.Xij=Mij(i.j)∈Ω.

其中X,M∈Rn1×n2,并且M表示采樣矩陣,Ω∈{1,…,n1}×{1,…,n2}表示采樣矩陣已知元素的下標(biāo)集合.事實(shí)上,由于矩陣關(guān)于秩是不連續(xù)的,所以模型(1)解決此問題存在一定的困難,所以Cand′es和Recht[2]提出模型(1)可以轉(zhuǎn)化為如下凸優(yōu)化問題:

min ‖X*‖

(2)

s.t.Xij=Mij(i.j)∈Ω.

此外,,Qiao等人[15]根據(jù)Lanczos方法和FFT技術(shù)提出的Hankel矩陣的奇異值分解算法其復(fù)雜度為O(n2logn),但是一般矩陣的復(fù)雜度為O(n3),并且Toeplitz矩陣可以通過行列變換轉(zhuǎn)化為Hankel矩陣,因?yàn)橛?jì)算奇異值分解時(shí)間在整個(gè)矩陣填充中所占比例很大,所以新算法在時(shí)間上占一定的優(yōu)勢(shì).

為了方便,我們先來給出一些定義.

定義1 一個(gè)n×n的Toeplitz矩陣T∈Rn1×n2有如下形式:

顯然,Toeplitz矩陣是由其第一行和第一列共2n-1個(gè)元素決定.

定義2([16]) (奇異值分解(SVD)). 秩為r的矩陣X∈Rn1×n2,一定存在正交矩陣U∈Rn1×r和V∈Rn2×r,滿足

其中σ1≥σ2≥…≥σr>0.

定義3([3]) (奇異值閾值算子). 對(duì)于任意參數(shù)τ≥0,矩陣的秩是r,X∈Rn1×n2,則存在X=UΣrVT,奇異值閾值算子Dτ定義為

Dτ(X)=UDτ(Σ)VT,Dτ(Σ)=diag({σi-τ}+)

并且令

1 算法

在本節(jié)中,我們提出了Toeplitz矩陣填充的一種新算法,上述問題可以轉(zhuǎn)化為如下凸優(yōu)化模型

min ‖X‖*

(3)

s.t.PΩ(X)=PΩ(M)

其中X,M均是Toeplitz矩陣,Ω∈{-n+1,…,n-1}. 并且為了方便,用[Uk,Σk,Vk]τk=lansvd(Yk)表示對(duì)矩陣Yk進(jìn)行奇異值分解.

算法1(Mid-SVT算法)

第一步:給定下標(biāo)集合Ω,樣本矩陣PΩ(M),參數(shù)τ0,0

第二步:計(jì)算矩陣(Yk)的奇異值

[Uk,Σk,Vk]τk=lansvd(Yk).

2 數(shù)值結(jié)果

表1 算法Mid-SVT和算法ALM算法的比較結(jié)果(p=0.1)

表2 算法Mid-SVT和算法ALM算法的比較結(jié)果(p=0.2)

表3 算法Mid-SVT和算法ALM算法的比較結(jié)果(p=0.3)

表4 算法Mid-SVT和算法ALM算法的比較結(jié)果(p=0.4)

注：由于采樣矩陣M隨機(jī)產(chǎn)生Toeplitz矩陣PΩ(M),其位置元素的位置不同,因此,個(gè)別實(shí)驗(yàn)的數(shù)據(jù)有所波動(dòng).

3 總結(jié)

在本文中,我們提出了Toeplitz矩陣填充的一種新算法——中值修正算法,根據(jù)表1-表4數(shù)據(jù),我們可以看出新算法在填充總時(shí)間、最終誤差等方面都比ALM算法優(yōu)勢(shì)明顯,尤其是當(dāng)p=0.1,p=0.2的時(shí)候,ALM算法收斂效果不理想,而新算法有較好的收斂性. 此外,從整體上看,隨著采樣率p的增大,計(jì)算時(shí)間越少,這也是合理的.