Toeplitz矩陣填充的中值修正的奇異值閾值算法

牛建華,王川龍

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

0 引言

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

minrank(X)

(1)

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

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

min ‖X*‖

(2)

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

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

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

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

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

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

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

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

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

并且令

1 算法

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

min ‖X‖*

(3)

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

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

算法1(Mid-SVT算法)

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

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

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

2 數(shù)值結果

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

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

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

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

注：由于采樣矩陣M隨機產生Toeplitz矩陣PΩ(M),其位置元素的位置不同,因此,個別實驗的數(shù)據有所波動.

3 總結

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