孫青青,王川龍

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

0 引言

近幾年，矩陣填充問題是一個引人注目的新研究領域，它主要應用在模型降階[1]，機器學習[2,3]，模式識別[4]，控制[5]和圖像恢復[6]等領域.矩陣填充問題首次由Cand`es和Recht[7]提出并通過求解如下凸優(yōu)化問題：

min ‖X‖*

(1)

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

矩陣填充問題是從采樣矩陣的部分已知元素合理精確地填充一個低秩矩陣.著名的Netflix推薦系統(tǒng)[8]就是關于矩陣填充問題的一個典型應用.因此求解優(yōu)化模型(1)成為眾多學者的研究熱點,目前已有大量的算法被提出來解決問題(1).Fazel[9,10]首先提出了半正定規(guī)劃的內(nèi)點算法,但此算法不適合求解大型矩陣的填充問題.Toh和 Yun[11]提出了迭代復雜度為的加速的近端梯度法(APG).Ma和Goldfard[12]將近似奇異值分解技術應用到不動點延續(xù)算法(FPC),提出了FPCA算法，完善并改進了FPC算法.幾乎同時，Cai等人[13]提出了奇異值閾值算法(SVT)，該算法保持了填充矩陣的稀疏性，可以有效地處理大規(guī)模矩陣填充問題.隨后，Lin等人[14]提出了閾值的增廣Lagrange乘子算法(ALM)，并經(jīng)過一系列數(shù)值實驗證明ALM算法比SVT算法和APG算法收斂速度快.另外，一些其他學者還研究了無奇異值分解的快速奇異值閾值法(FastSVT[15])，加速奇異值閾值法(ASVT[16])，梯度投影算法[17]，圖像修復中截斷P范數(shù)正則化[18]等方法來解決矩陣填充問題.

在實際應用過程中，采樣矩陣往往具有形如循環(huán)，Toeplitz，Hankel和Toeplitz-plus-Hankel等特殊結(jié)構，因此研究特殊矩陣的填充問題很有意義.循環(huán)矩陣作為一類很重要的矩陣，已有眾多學者對它的特殊結(jié)構及性質(zhì)等進行過深入研究，它在編碼理論、數(shù)理統(tǒng)計、濾波算法、結(jié)構計算、數(shù)學圖像處理，壓縮感知等方面都有著廣泛的應用[19-22].一個n×n的循環(huán)矩陣C具有如下形式：

其中c0,c1,…,cn-1∈C.顯然，循環(huán)矩陣完全由第1行來確定，是一種特殊形式的Toeplitz矩陣.盡管循環(huán)矩陣很常見，但近些年針對它的填充方法卻很少.循環(huán)矩陣的特殊結(jié)構導致一般的循環(huán)矩陣均是滿秩的，而對于矩陣填充問題，通常使用的是低秩矩陣，因此需要生成一個低秩的循環(huán)矩陣，余和王曾在[23]中給出生成低秩循環(huán)矩陣的方法，還提出矩陣填充的均值保結(jié)構算法.由之前已有的矩陣填充算法可知，當前很多算法需要計算矩陣的SVD.而循環(huán)矩陣具有特殊的性質(zhì)：它可以通過二維離散傅立葉變換進行對角化[24].與標準(例如MATLAB的eig函數(shù))求特征值的方法相比，使用FFT計算循環(huán)矩陣特征值是非?？斓模渌惴◤碗s度為O(nlog2n)，而標準方法的算法復雜度為O(n3).因此，基于FFT 來研究循環(huán)矩陣的填充問題十分有意義.本文我們主要研究循環(huán)矩陣填充的快速傅里葉變換算法.首先給出一些定義.

定義1(Fourier矩陣) 設矩陣

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

X=UΣrVT， ∑r=diag(σ1,…,σr)

其中

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

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

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

其中

定義4(硬閾值算子[26]) 給定λ≥0，硬閾值算子ηh定義為

其中變量x∈R,λ是閾值.

此外，定義一個位移矩陣：

(2)

本文的結(jié)構如下：第1節(jié)首先簡單回顧已有算法，然后詳細給出低秩循環(huán)矩陣填充的快速傅里葉變換算法；第2節(jié)通過數(shù)值實驗與CMA算法比較來驗證新算法的有效性和精確性；最后在第3節(jié)對全文進行總結(jié).

1 算法

在這一節(jié)中，為了數(shù)值實驗中算法比較的需要，我們首先對已有算法進行簡單回顧.

1.1 矩陣填充的SVT算法

奇異值閾值算法[7]求解如下優(yōu)化問題：

(3)

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

Cai等在[7]中，理論上證明了當τ→時，優(yōu)化問題(3)的最優(yōu)解收斂到優(yōu)化問題(1)的最優(yōu)解.其算法如下：

算法1 SVT算法[7]

第1步：給定下標集合Ω，樣本矩陣PΩ(M)，參數(shù)τ，步長δ，誤差ε，初始矩陣Y0=k0δPΩ(M),k:=0；

第2步：計算矩陣Yk比閾值τ大的SVD：

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

第3步：若‖PΩ(Xk+1-M)‖F(xiàn)/PΩ(M)≤ε，停止；否則，轉(zhuǎn)第4步；

第4步：Yk+1=PΩ(Yk)+δPΩ(M-Xk+1).

1.2 循環(huán)矩陣填充的算法

1.2.1 循環(huán)矩陣填充的均值保結(jié)構算法

算法1對循環(huán)矩陣等帶有特殊結(jié)構的矩陣進行填充時不能保持矩陣原有的結(jié)構，因此，對算法中產(chǎn)生的迭代矩陣做均值處理來確保循環(huán)矩陣的結(jié)構.其算法如下：

算法2循環(huán)矩陣填充的均值保結(jié)構算法[24](A mean value algorithm for circulant matrix completion，簡稱CMA)

初始化：Ω是下標集合，PΩ(M)是樣本值，τ0為參數(shù)，c為常數(shù)且0

第1步：對矩陣Yk進行奇異值分解：

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

第2步：計算

Rl是(2)中的Rl且令

第3步：若‖Yk+1-Yk‖F(xiàn)/‖Yk‖F(xiàn)<ε，停止；否則τk+1=cτk,k:=k+1，轉(zhuǎn)第1步.

1.2.2 循環(huán)矩陣填充的快速傅里葉變換算法

算法3循環(huán)矩陣填充的快速傅里葉變換算法(Fast Fourier Transform Algorithm for Circulant Matrix Completion，簡稱CFFT)

第1步：將傅里葉變換矩陣作用到矩陣Yk，求Yk的特征值

第3步：若‖Yk+1-Yk‖F(xiàn)/‖Yk‖F(xiàn)<ε,停止，否則k=k+1；轉(zhuǎn)第1步.

注：該算法第1步中的τk為定義4中的硬閾值算子.

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

在本節(jié)中，通過數(shù)值實驗給出CFFT算法和CMA算法對低秩循環(huán)矩陣填充的比較結(jié)果.這里所有的數(shù)值實驗都是在相同的工作環(huán)境下進行的，即實驗中所取的M和PΩ(M)具有相同的數(shù)據(jù).

從5個表中我們看到CFFT算法在時間上總是優(yōu)于CMA算法的.針對相同大小的矩陣而言，隨著采樣率p的增加，CFFT算法的迭代次數(shù)和運行時間都明顯減少；針對相同的采樣率而言，隨著矩陣大小的變化，CFFT算法的運行時間比CMA算法都少，特別是矩陣階數(shù)越大越明顯，這些都說明新算法的有效性和可行性.

表1 CFFT算法與CMA算法的比較(當p=m/n=0.6時)

表2 CFFT算法與CMA算法的比較(當p=m/n=0.5時)

表3 CFFT算法與CMA算法的比較 (當p=m/n=0.4時)

表4 CFFT算法與CMA算法的比較(當p=m/n=0.3時)

表5 CFFT算法與CMA算法的比較(當p=m/n=0.2時)

3 總結(jié)

在本文中，我們針對低秩循環(huán)矩陣提出一種新的填充算法，即快速傅里葉變換算法.在新提出的算法中，根據(jù)循環(huán)矩陣的特殊結(jié)構和性質(zhì)，利用快速傅里葉變換求其特征值比原算法中直接求奇異值節(jié)省了大部分時間,能夠有效地填充矩陣.這些都是基于實循環(huán)矩陣而言的，對于低秩復循環(huán)矩陣的構造與填充，將是我們后期研究工作的重點.