余麗峰, 王川龍

(1.山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山西 太原　030006；2.太原師范學(xué)院 工程科學(xué)計(jì)算山西省高等學(xué)校重點(diǎn)實(shí)驗(yàn)室，山西 太原　030012)

?

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

余麗峰1, 王川龍2*

(1.山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山西 太原030006；2.太原師范學(xué)院 工程科學(xué)計(jì)算山西省高等學(xué)校重點(diǎn)實(shí)驗(yàn)室，山西 太原030012)

摘要：在奇異值閾值法的基礎(chǔ)上，針對循環(huán)矩陣的特殊結(jié)構(gòu)分別對一般低秩復(fù)循環(huán)矩陣和特殊低秩實(shí)循環(huán)矩陣作保結(jié)構(gòu)的均值算法.首先給出構(gòu)造低秩循環(huán)矩陣的方法；其次，給出了修正的保結(jié)構(gòu)算法；最后通過數(shù)值實(shí)驗(yàn)驗(yàn)證結(jié)果.

關(guān)鍵詞：循環(huán)矩陣；矩陣填充；算法；閾值

0引言

自從Candés和Recht在2009年提出通過凸優(yōu)化進(jìn)行矩陣填充[1]，矩陣填充就在信息領(lǐng)域快速發(fā)展，研究人員后續(xù)提出了很多理論[2-5]和算法[6-9].矩陣填充問題可以應(yīng)用到很多領(lǐng)域，例如：控制[10]、計(jì)算機(jī)圖像[3]和機(jī)器學(xué)習(xí)[11,12]等.循環(huán)矩陣在信息處理和圖像處理上都有重要的應(yīng)用.目前，還沒有人研究循環(huán)矩陣的保結(jié)構(gòu)算法，本文就將針對循環(huán)矩陣的特點(diǎn)對其進(jìn)行研究.

對循環(huán)矩陣的填充問題可以表示為下面的凸優(yōu)化問題

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

(1)

其中:X和M均是循環(huán)矩陣，Ω?{-n+1,…,-1,0,1,…,n-1} .

定義一個(gè)位移矩陣Rl：

(2)

l=0,…,n-1

一般而言，循環(huán)矩陣都是方陣，因此這里的n1,n2相等記為n.

1生成低秩循環(huán)矩陣

循環(huán)矩陣的特殊結(jié)構(gòu)導(dǎo)致了循環(huán)矩陣幾乎都是滿秩的，對于矩陣填充問題，一般意義上針對的是低秩矩陣，所以生成一個(gè)低秩的循環(huán)矩陣就是首要解決的問題.

1.1特殊低秩循環(huán)矩陣

最容易構(gòu)成的是一類由循環(huán)向量生成的循環(huán)矩陣，這類矩陣只要滿足：用來生成循環(huán)向量的數(shù)組元素個(gè)數(shù)可以整除該向量的維數(shù)即可，這樣生成的循環(huán)矩陣的秩即數(shù)組的個(gè)數(shù).

其實(shí)，這是由一個(gè)秩較小的滿秩循環(huán)矩陣構(gòu)成的一個(gè)分塊循環(huán)矩陣，該分塊矩陣中只有這一個(gè)矩陣.

例設(shè)a=(1,2,3)，則由a構(gòu)成的循環(huán)向量為c={1,2,3,1,2,3}，c的維數(shù)6可以整除a的維數(shù)3，因此由a,c構(gòu)成的循環(huán)矩陣分別為

和

顯然，

若c={1,2,3,1,2}，則可生成循環(huán)矩陣

顯然，上述矩陣是滿秩的.

對于采樣數(shù)據(jù)結(jié)構(gòu)有特殊循環(huán)矩陣定義那樣的特點(diǎn)，可以按照分塊矩陣做填充.稍后對其進(jìn)行分析.下面描述生成普通低秩循環(huán)矩陣的方法.

1.2低秩循環(huán)矩陣

對于一個(gè)n×n的循環(huán)矩陣C有n個(gè)互不相同的特征值，文獻(xiàn)[13]有：

F-1CF=diag(λ0,λ1,…,λn-1)

(3)

可知，假設(shè)給定一組向量λ1,λ2,…,λn-1，該向量有r(r

C=Fdiag(λ0,λ1,…,λn-1)F-1

(4)

如此就可得出一個(gè)低秩的循環(huán)矩陣C，記Λ=diag(λ0,λ1,…,λn-1).

由于F∈Cn×n，Λ=diag(λ1,λ2,…,λn-1) ，由Fourier矩陣的結(jié)構(gòu)特點(diǎn)知，生成的低秩循環(huán)矩陣C∈Cn×n，是個(gè)復(fù)矩陣.如何利用循環(huán)復(fù)矩陣的特點(diǎn)，得到一個(gè)保持循環(huán)矩陣結(jié)構(gòu)的算法，就是接下來要做的工作.

2算法

2.1低秩復(fù)循環(huán)矩陣填充

由(4)可知

C=Fdiag(λ0,λ1,…,λn-1)F-1，

則

運(yùn)算如下：

C*=(Fdiag(λ0,λ1,…,λn-1)F-1)*=

(F-1)*(diag(λ0,λ1,…,λn-1))*F*=

則

CC*=Fdiag(|λ0|2,|λ1|2,…,|λn-1|2)F-1

由文獻(xiàn)[14]可知，C的奇異值σi為|λi|,(i=1,…,n)對任意的C，F(xiàn)左奇異矩陣，F(xiàn)-1為右奇異矩陣，但直接利用傅里葉變換代替奇異值分解的算法并不收斂.

按照文獻(xiàn)[15]的算法，類似的對循環(huán)矩陣的奇異值分解做一個(gè)均值算法來保持結(jié)構(gòu).

算法1循環(huán)矩陣填充的均值保結(jié)構(gòu)算法(The Mean Algorithm for Circulate Matrix簡稱CMA算法)

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

第一步：對矩陣Yk進(jìn)行奇異值分解

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

令

Xk+1=UkDτk(Σk)Vk;

第二步：計(jì)算

cl=

Rl是(2)中的Rl且令

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

經(jīng)過實(shí)驗(yàn)發(fā)現(xiàn),均值算法對低秩循環(huán)復(fù)矩陣的填充效率并不理想，雖然結(jié)構(gòu)可以保持，但運(yùn)行時(shí)間過長，誤差變化不大，因此可以判斷出是求均值耗費(fèi)的時(shí)間過長.因此這個(gè)算法還需在均值修正或奇異值分解上做改進(jìn).

2.2特殊循環(huán)實(shí)矩陣填充

算法2特殊循環(huán)矩陣的均值算法(The Mean Value Algorithm for Special Circulate Matrix簡記為CMV)在CMA算法的基礎(chǔ)上，用Lanczos 方法對Yk進(jìn)行奇異值分解，只需將算法1的第一步更改為：

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

由此得到一個(gè)新的算法.

算法3特殊循環(huán)矩陣的降階奇異值算法(The Reduce Order Singular Value Thresholding Algorithm for Special Matrix簡記為RSVT) 改變算法的初始化采樣矩陣，

初始化：記樣本下標(biāo)集合Ω，Ω∈{-m+1,…,-1,0,1,…,m-1}，m=n/2，m/r∈Z+，樣本元素PΩ(M)，M是特殊循環(huán)矩陣C的m階順序主子矩陣，誤差ε，參數(shù)τ，c為常數(shù)且0

第一步：對矩陣Yk進(jìn)行奇異值分解

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

令

Xk+1=UkDτk(Σk)Vk;

第二步：計(jì)算

cl=

Rl是(2)中的Rl且令

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

由1.1的定義可知一類特殊的低秩循環(huán)矩陣，若存在一個(gè)秩為r的低階循環(huán)矩陣A，一個(gè)所有元素均是1的矩陣B，則有低秩循環(huán)矩陣：

C=B?A

(5)

則C的秩為r.

由文獻(xiàn)[16]可知Kronecker積關(guān)于范數(shù)和運(yùn)算的幾點(diǎn)性質(zhì)，所以根據(jù)(5)式得

‖C‖F(xiàn)=‖A‖F(xiàn)‖B‖F(xiàn)

(6)

由于B是所有元素均為1的矩陣，所以對于m階B就有

‖B‖F(xiàn)=m

(7)

可求得B的特征值λB等于奇異值σB等于m. 同樣由文獻(xiàn)[16]可知Kronecker 積有分配率，用式子可表示為：

C?A±C?B=C?(A±B)

(8)

利用式(6)，(7)和(8)可得如下簡單定理:

(9)

由式(9)可以看出，對于此類循環(huán)矩陣，只需要對其r階順序主子矩陣(即循環(huán)矩陣的前r行r列)進(jìn)行填充即可.由該類循環(huán)矩陣生成的方式可知，其r階順序主子矩陣是一個(gè)低階滿秩的矩陣，由此可知，要解決這個(gè)問題，就要解決低階滿秩填充的問題.

在解決填充問題之前，先發(fā)現(xiàn)了這類分塊循環(huán)矩陣與決定其秩的小塊循環(huán)矩陣的特征值和奇異值之間的關(guān)系，其關(guān)系見定理2.

定理2已知C=B?A，A是r階的循環(huán)矩陣，B是元素均為1的m階矩陣，若A的特征值為λ1,λ2,…,λr，則C的特征值為mλ1,mλ2,…,mλr.同理，若A的奇異值為σ1,σ2,…,σr，則C的奇異值為mσ1,mσ2,…,mσr.

證明：由循環(huán)矩陣的特點(diǎn)有

F-1CF=diag(ξ1,ξ2,…,ξr) ，

即

F-1(A?B)F=(F-1AF)?(F-1BF)=

diag(λ1,λ2,…,λr)?m

所以

ξi=mλi,(i=1,…,r),ξj=0,(j=r+1,…,n);

同理，得到奇異值為mσ1,mσ2,…,mσr.

因此，求得的局部誤差就等于全局誤差.

本文所有算法的收斂性分析均與文獻(xiàn)[15]相同，文獻(xiàn)[15]的全部引理定理仍然成立，具體引理定理及詳細(xì)證明過程見文獻(xiàn)[15].

3數(shù)值實(shí)驗(yàn)

表1　循環(huán)矩陣填充的SVT和CMV算法比較

表2　特殊循環(huán)矩陣填充的RSVT

由定理1可得到一個(gè)最簡循環(huán)填充矩陣，但得到的矩陣是一個(gè)低階滿秩矩陣，經(jīng)驗(yàn)證發(fā)現(xiàn)不能用已知的低秩矩陣填充方法求解，但這仍然提供了一種思路，RSVT算法就是在此基礎(chǔ)上得到的.由表2可知，將特殊循環(huán)矩陣按規(guī)律降階也能達(dá)到快速的效果，而且針對這類特殊矩陣，效果甚至略優(yōu)于均值算法.因此，可以通過取順序主子矩陣，順序主子矩陣的階數(shù)必須遠(yuǎn)大于秩.

4結(jié)論

本文針對低秩循環(huán)矩陣的復(fù)矩陣結(jié)構(gòu)，運(yùn)用其特殊性質(zhì)，對低秩循環(huán)矩陣做一個(gè)保結(jié)構(gòu)的算法.首先，給出求低秩循環(huán)矩陣的方法；其次，提出修正的保結(jié)構(gòu)算法；最后通過數(shù)值實(shí)驗(yàn)觀測分析.并對一類特殊結(jié)構(gòu)的實(shí)循環(huán)矩陣進(jìn)行填充，利用Kronecker積得到降階算法.在數(shù)值實(shí)驗(yàn)中得出對于一般的低秩復(fù)循環(huán)矩陣保結(jié)構(gòu)算法效果不理想，仍然可以進(jìn)行改進(jìn)，而對于特殊的實(shí)循環(huán)矩陣降階算法還可以繼續(xù)改進(jìn).

參考文獻(xiàn)

[1] E.J.Candés,B.Recht. Exact matrix completionvia convex optimization[J].Foundations of Computational Mathematics,2009,9:717-772.

[2] E.J.Candés,T.Tao.The power of convex relaxation:Nearoptimal matrix completion[J].IEEE Transactions on Information Theory,2010,56:2 053-2 080.

[3] R.H.Keshavan,A.Montanari,S.Oh.Matrix completion from a few entries[J].IEEE Transactions on Information Theory,2010,56:2 980-2 998.

[4] B.Recht.A simpler approach to matrix completion[J].Journal of Machine Learning Research,2011,12:3 413-3 430.

[5] G.A.Watson.Characterization of the sub-diffe-rential of some matrix norms[J].Linear Algebra and Its Application,1992,170:33-45.

[6] Z.Lin,M.Chen,Y.Ma.The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices[EB/OL].http://arxiv.org/abs/1009.5055,2010-09-26.

[7] J.F.Cai,E.J.Candés,Z.Shen.A singular value thresholding algorithm for matrix completion[J].SIAM Journal on Optimization,2010,20:1 956-1 982.

[8] D.Goldfarb,S.Ma.Convergence of fixed-point continuation algorithms for matrix rank minimization[J].Foundation of Computational Mathemtics,2010,11:183-210.

[9] B.Recht.A simpler approach to matrix completion[J].Journal of Machine Learning Research,2011,12:3 413-3 430.

[10] M.Mesbahi,G.P.Papavassilopoulos.On the rank minimization problem over a positive semi definite linear matrix inequality[J].IEEE Transactions on Automatic Control,1997,4:239-243.

[11] Y.Ami,M.Fink,N.Srebro,et al.Uncovering shared structures in multiclass classification[C]//Twenty-fourth International Conference on Machine Learning. New York:Association for Computing Machinery,ACM,2007:17-24.

[12] A.Argyriou,T.Evgeniou,M.Pontil.Multitask feature leafing[J].Advance in Neural Information Processing Systems,2007,19:41-48.

[13] 徐仲,張凱院,陸全.TOEPLITZ矩陣類的快速算法[M].西安:西北工業(yè)大學(xué)出版社,1998.

[14] G.H.Golub,C.F.Van Loan.Matrix computa-tions[M].3rd edition.Baltimore:The Johns Hopkins University Press,1996.

[15] Chuan Long Wang,Chao Li.A mean value algorithm for toeplitz matrix completion[J].Applied Mathematics Letters,2015,41:35-40.

[16] 王文丹，馬昌鳳.關(guān)于矩陣Kronecker積的幾個(gè)范數(shù)公式[J].福建師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,31(6):10-17.

【責(zé)任編輯：蔣亞儒】

A mean value algorithm for circulant matrix completion

YU Li-feng1，WANG Chuan-long2*

(1.School of Mathematical Science，Shanxi University，Taiyuan 030006，China；2.Higher Education Key Laboratory of Engineering Science Computing in Shanxi Province, Taiyuan Normal University, Taiyuan 030012, China)

Abstract:We propose a mean algorithm to preserving the structure according to the special structure of general low-rank complex circulant matrix and special low-rank real circulant matrix.Firstly,we construct a low-rank circulant matrix;Secondly,the preserving structure algorithm for the circulant matrix is proposed;Finally,the results are verified through numerical experiments.

Key words:circulate matrix; matrix completion; algorithm; threshold

*收稿日期:2016-06-11

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(11371275)

作者簡介:余麗峰(1992-),女,山西忻州人,在讀碩士研究生，研究方向：數(shù)值計(jì)算與優(yōu)化 通訊作者:王川龍(1964-),男,山西侯馬人，教授，博士，研究方向：數(shù)值計(jì)算與優(yōu)化，clwang1964@163.com

文章編號：1000-5811(2016)04-0182-05

中圖分類號：O241.6

文獻(xiàn)標(biāo)志碼：A