史加榮，劉 晨

(西安建筑科技大學(xué) 理學(xué)院, 陜西 西安 710055)

在人工智能與大數(shù)據(jù)時(shí)代，推薦系統(tǒng)[1]、圖像處理[2]和計(jì)算機(jī)視覺(jué)[3]等諸多應(yīng)用領(lǐng)域的科學(xué)研究需要處理數(shù)據(jù)矩陣。大數(shù)據(jù)不僅具有大量、高速、多樣、低價(jià)值密度、真實(shí)性5大特點(diǎn)，更重要的特點(diǎn)是高維度。數(shù)據(jù)維度過(guò)高，可用的數(shù)據(jù)信息有限，往往會(huì)造成數(shù)據(jù)采樣不足的問(wèn)題，而且易被噪聲所污染，導(dǎo)致建立的模型難以發(fā)現(xiàn)數(shù)據(jù)中所隱含的規(guī)律。如何對(duì)這些高維度數(shù)據(jù)進(jìn)行有效的建模，從而挖掘數(shù)據(jù)的潛在規(guī)律，進(jìn)一步對(duì)未知的空間進(jìn)行預(yù)測(cè)，是對(duì)研究者的一個(gè)重大挑戰(zhàn)。

低秩矩陣分解[4-5]是解決上述問(wèn)題的一類(lèi)常用方法，系利用數(shù)據(jù)集的近似低秩結(jié)構(gòu)來(lái)恢復(fù)低秩成分、移除噪聲和補(bǔ)全缺失值。通常假設(shè)數(shù)據(jù)集存在于單個(gè)低維線性子空間中。矩陣分解方法主要包括傳統(tǒng)的主成分分析(principal component analysis, PCA)[6]、奇異值分解(singular value decomposition, SVD)[7]和線性判別分析(linear discriminant analysis, LDA)[8]等。當(dāng)數(shù)據(jù)集存在于多個(gè)低維線性子空間中時(shí)，主要的矩陣分解方法有二維PCA、二階雙向二維PCA、二維SVD、二維LDA和魯棒廣義低秩矩陣逼近(robust generalized low rank approximations of matrices, RGLRAM)等方法[9-10]。

傳統(tǒng)的矩陣分解方法一般采用L2范數(shù)來(lái)度量逼近誤差，但對(duì)數(shù)據(jù)中的異常值具有很高的敏感性。為了克服PCA對(duì)異常值的敏感性，文獻(xiàn)[11]提出魯棒主成分分析(robust principal component analysis, RPCA)，假設(shè)干凈數(shù)據(jù)矩陣是低秩的，且誤差矩陣是稀疏的，對(duì)于給定的數(shù)據(jù)矩陣，RPCA通過(guò)最小化核范數(shù)和L1范數(shù)的加權(quán)組合來(lái)恢復(fù)低秩成分與稀疏噪聲。文獻(xiàn)[12]討論了RPCA目標(biāo)函數(shù)的下界，隨后部分學(xué)者提出了一系列基于RPCA的其他優(yōu)化模型[13-14]。作為RPCA的一個(gè)重要擴(kuò)展，低秩表示(low-rank representation, LRR)[15]中的低秩約束增強(qiáng)了矩陣行列之間的相關(guān)性，也提高了模型對(duì)噪聲的魯棒性。但與RPCA一樣，LRR也假定誤差項(xiàng)是稀疏的。

文獻(xiàn)[16-17]提出了基于雙核范數(shù)矩陣分解(double nuclear norm-based matrix decomposition, DNMD)方法，將每個(gè)數(shù)據(jù)矩陣分解為低秩干凈數(shù)據(jù)和低秩誤差數(shù)據(jù)之和，但沒(méi)有考慮稀疏噪聲的腐蝕?；诖?，本研究提出一種基于雙核范數(shù)的魯棒矩陣分解(robust DNMD, RDNMD)方法，將每個(gè)數(shù)據(jù)矩陣分解為低秩干凈數(shù)據(jù)、低秩誤差數(shù)據(jù)和稀疏噪聲之和，建立最小化矩陣雙核范數(shù)與L1范數(shù)之和，并利用交替方向乘子法對(duì)模型進(jìn)行求解。

1 相關(guān)知識(shí)

1.1 魯棒主成分分析

在實(shí)際應(yīng)用中可以將圖像集表示為矩陣X∈Rmn×s,并將其分解為X=D+G，其中，D∈Rmn×s是需要恢復(fù)的低秩矩陣；G∈Rmn×s是未知的噪聲矩陣。RPCA模型解決的問(wèn)題是從被稀疏大噪聲腐蝕的數(shù)據(jù)中精確地恢復(fù)出低秩矩陣。此問(wèn)題可以描述為如下優(yōu)化問(wèn)題：

(1)

由于秩函數(shù)的非凸性和不連續(xù)性，上述秩最小化問(wèn)題是NP難的，現(xiàn)有的算法無(wú)法有效求解秩最小化問(wèn)題。文獻(xiàn)[18]證明了秩函數(shù)的凸包絡(luò)為核范數(shù)，可用于近似秩函數(shù)，可將問(wèn)題(1)進(jìn)行凸松弛。因此RPCA模型可以表示為：

(2)

求解RPCA模型的算法有迭代閾值法、加速近端梯度法、對(duì)偶法和增廣拉格朗日乘子法等[19]。RPCA已經(jīng)被應(yīng)用于視頻監(jiān)控[2]、協(xié)同過(guò)濾[1]、人臉識(shí)別[16]等領(lǐng)域。RPCA模型還可以作為矩陣補(bǔ)全問(wèn)題[20]的延伸，擴(kuò)展到處理一小部分元素丟失的情況。

1.2 雙核范數(shù)矩陣分解(DNMD)

(3)

將問(wèn)題(3)進(jìn)行凸松弛，即可得到雙核范數(shù)矩陣分解模型：

(4)

2 雙核范數(shù)魯棒矩陣分解(RDNMD)

2.1 模型建立

RPCA模型未考慮低秩噪聲，DNMD未考慮稀疏噪聲。假設(shè)數(shù)據(jù)集同時(shí)受到低秩噪聲和稀疏噪聲的腐蝕，將圖像集分解為Xi=Di+Ei+Gi，其中Gi∈Rm×n為噪聲矩陣且服從均值為零的拉普拉斯分布，i=1,2,…,s。

記G=(vec(G1),…,vec(Gs))，建立雙核范數(shù)魯棒矩陣分解模型：

(5)

其中,λ≥0和τ≥0為正則化參數(shù)。

使用交替方向乘子法(ADMM)來(lái)求解優(yōu)化問(wèn)題(5)。為此，構(gòu)造增廣拉格朗日函數(shù)：

(6)

其中：‖·‖F(xiàn)為矩陣的Frobenius范數(shù)，μ>0為懲罰系數(shù)，〈·,·〉為內(nèi)積算子，拉格朗日乘子矩陣Y=(vec(Y1),…,vec(Ys))，Yi∈Rm×n,i=1,2,…,s。

2.2 模型求解

借助優(yōu)化問(wèn)題(5)及函數(shù)(6)關(guān)于變量的可分性，ADMM采用交替優(yōu)化的方法，即分別在固定其他變量的情況下得到感興趣變量的最優(yōu)解。下面給出主要的迭代過(guò)程。

當(dāng)E,G,Y固定時(shí)，更新D:

(7)

因此D的更新公式為：

D:=D1/μ(X-E-G+Y/μ)，

(8)

其中，Dυ(·):Rm×n→Rm×n為奇異值閾值算子[21]。

Lμ關(guān)于Ei是可分離的。當(dāng)D,G,Y固定時(shí)，更新Ei:

(9)

因此Ei的更新公式為：

Ei:=Dλ/μ(Xi-Di-Gi+(1/μ)Yi)。

(10)

當(dāng)D,E,Y固定時(shí)，更新G:

(11)

因此G的更新公式為：

G:=Sτ/μ(X-D-E+Y/μ)，

(12)

其中，Sδ(·):Rm×n→Rm×n為絕對(duì)值閾值算子[11]。

當(dāng)D,E,G固定時(shí)，更新Y:

Y:=Y+μ(X-D-E-G)。

(13)

更新μ：

μ:=min(ρμ,μmax),

(14)

其中：μmax是μ的最大值，ρ為大于1的常數(shù)。

算法1 求解RDNMD的ADMM算法

1.初始化:Y=0,E=0,G=0,μ=1/mean(svd(X))；

2.D:=D1/μ(X-E-G+Y/μ)；

3.Ei:=Dλ/μ(Xi-Di-Gi+(1/μ)Yi),i=1,2,…,s；

4.G:=Sτ/μ(X-D-E+Y/μ)；

5.Y:=Y+μ(X-D-E-G)；

6.μ:=min(ρμ,μmax)；

7.如果滿(mǎn)足終止條件，終止算法；否則，轉(zhuǎn)步驟2。

輸出:D,E,G。

在算法1中，svd(X)表示矩陣X的所有奇異值，mean(·)表示均值算子。本實(shí)驗(yàn)中，取μmax=106,ρ=1.2,ε=10-10,Tmax=100，λ=0.125，τ=0.1。

2.3 算法分析

RDNMD求解算法的主要計(jì)算復(fù)雜度是由奇異值閾值算子產(chǎn)生的。給定一個(gè)m×n矩陣，不妨設(shè)m>n，對(duì)其進(jìn)行奇異值分解的計(jì)算復(fù)雜度為O(mn2)。對(duì)于算法1,在更新D時(shí)，需要對(duì)mn×s維的矩陣進(jìn)行奇異值分解，通常mn>s，于是計(jì)算復(fù)雜度為O(mns2)。在更新低秩誤差圖像Ei時(shí),需要對(duì)m×n維的s個(gè)矩陣進(jìn)行奇異值分解，計(jì)算復(fù)雜度為O(mn2s)。在更新稀疏誤差矩陣G時(shí),計(jì)算復(fù)雜度為O(mns)。在更新Y時(shí),計(jì)算復(fù)雜度為O(mns)。因此，算法1在一次迭代過(guò)程中的總體計(jì)算復(fù)雜度為O(mns2+mn2s)。

3 數(shù)值實(shí)驗(yàn)與結(jié)果分析

3.1 數(shù)據(jù)描述與準(zhǔn)備

在Extended Yale B人臉數(shù)據(jù)集[22]和Cuprite多光譜圖像集[23]上進(jìn)行實(shí)驗(yàn)。Extended Yale B人臉數(shù)據(jù)庫(kù)共有38人,每人64幅照片。根據(jù)人臉與攝像機(jī)的方向角將每人的64幅照片分為5個(gè)子集。對(duì)于每個(gè)人，5個(gè)子集的人臉數(shù)目分別為7、12、12、14、19。每幅圖像均被標(biāo)準(zhǔn)化為96×84的分辨率，提取了3人共192幅圖像，部分圖像見(jiàn)圖1。Cuprite多光譜圖像集選自NASA的AVIRIS數(shù)據(jù)集，共96個(gè)波段，每幅圖像的大小為103×123，部分圖像見(jiàn)圖2。先對(duì)每個(gè)圖像Di添加密度為p的椒鹽噪聲，再隨機(jī)加入連續(xù)遮擋，遮擋大小為d×d。

圖1 Extended Yale B數(shù)據(jù)集部分原始圖像

圖2 Cuprite多光譜圖像集部分原始圖像

連續(xù)遮擋的圖像選自于哥倫比亞大學(xué)圖像數(shù)據(jù)庫(kù)COIL-20[24]。該數(shù)據(jù)集包含對(duì)20個(gè)物體從不同角度的拍攝圖像，每隔5度拍攝一幅圖像，每個(gè)物體72幅圖像，總共1 440幅圖像。

(15)

式(15)中相對(duì)誤差RE越小，恢復(fù)性能越好。將RDNMD的實(shí)驗(yàn)結(jié)果與DNMD和RPCA的結(jié)果進(jìn)行比較。采用MATLAB R2014a進(jìn)行編程，所有實(shí)驗(yàn)在處理器為Intel?CoreTMi5-10210U CPU@1.60 GHz 2.11GHz的個(gè)人計(jì)算機(jī)上進(jìn)行。

3.2 實(shí)驗(yàn)結(jié)果與分析

在Extended Yale B數(shù)據(jù)集上設(shè)計(jì)了兩組實(shí)驗(yàn)來(lái)比較算法的性能。在第1組實(shí)驗(yàn)中，令d=20，p∈{0,0.1,0.2,0.3,0.4,0.5}，實(shí)驗(yàn)結(jié)果如圖3所示，其中p=0表示觀察到的圖像中沒(méi)有稀疏噪聲，只有連續(xù)遮擋，此時(shí)提出的RDNMD就轉(zhuǎn)化為DNMD。從圖3可以看出：p=0時(shí)DNMD和RDNMD性能相當(dāng)，均優(yōu)于RPCA，而當(dāng)p>0.1時(shí)，RDNMD得到的結(jié)果最好。

圖3 3種模型在不同p下的相對(duì)誤差Fig. 3 Relative errors of three models under different p

第2組實(shí)驗(yàn)中，固定稀疏噪聲的密度p=0.2,考慮由于連續(xù)遮擋的變化導(dǎo)致相對(duì)誤差的變化情況，取d∈{0,20,28,35,40,45,49,53,57}，實(shí)驗(yàn)結(jié)果如圖4所示，其中d=0表明觀察到的圖像中沒(méi)有低秩遮擋噪聲，只有稀疏噪聲，此時(shí)RDNMD轉(zhuǎn)化為RPCA。從圖4可以看出：d=0時(shí)，RPCA的恢復(fù)效果優(yōu)于RDNMD和DNMD；1

圖4 3種模型在不同連續(xù)遮擋d下的相對(duì)誤差Fig. 4 Relative errors of three models under different continuous occlusion d

每人隨機(jī)選取1幅圖像進(jìn)行可視化。令p=0.2,d=30，圖5～7分別顯示了RPCA、DNMD和RDNMD的實(shí)驗(yàn)結(jié)果，可以看出，RPCA和DNMD未能分離出低秩噪聲和稀疏噪聲，而RDNMD能較好地分離出低秩噪聲和稀疏噪聲；RDNMD將干凈圖像和噪聲圖像分離的最好。因此RDNMD具有最好的恢復(fù)性能。

圖5 Extended Yale B在RPCA下的恢復(fù)結(jié)果Fig. 5 Recovered results of RPCA on Extended Yale B

在Cuprite多光譜圖像集上進(jìn)行實(shí)驗(yàn)，僅可視化地比較不同方法的恢復(fù)性能。取p=0.2,d=30，圖8～10分別顯示了RPCA、DNMD和RDNMD的部分實(shí)驗(yàn)結(jié)果。

由圖8～10可以看出：RDNMD恢復(fù)出的低秩干凈圖像效果最好，DNMD次之，RPCA效果較差；RDNMD能較好地分離出低秩噪聲和稀疏噪聲，而DNMD和RPCA卻不能有效地分離。此外，RPCA、DNMD和RDNMD的運(yùn)行時(shí)間分別為15.98、22.69和26.36 s，即RDNMD需要的計(jì)算時(shí)間最長(zhǎng)，RPCA的計(jì)算時(shí)間最短。

圖6 Extended Yale B在DNMD下的恢復(fù)結(jié)果

圖7 Extended Yale B在RDNMD下的恢復(fù)結(jié)果

圖8 Cuprite在RPCA下的恢復(fù)結(jié)果

4 結(jié)論

本研究提出一種基于雙核范數(shù)魯棒矩陣分解方法,該方法假設(shè)低秩數(shù)據(jù)矩陣同時(shí)受到連續(xù)遮擋和稀疏噪聲的腐蝕，使用低秩假設(shè)和稀疏假設(shè)來(lái)描述圖像。所提出的方法不僅可以在一定程度上恢復(fù)干凈的低秩數(shù)據(jù)，消除遮擋或前景引起的結(jié)構(gòu)誤差，而且通過(guò)L1范數(shù)消除稀疏誤差。利用最小化矩陣雙核范數(shù)與L1范數(shù)的加權(quán)組合建立優(yōu)化模型，并使用交替方向乘子法進(jìn)行求解。實(shí)驗(yàn)結(jié)果表明：本研究提出的方法對(duì)于同時(shí)受到連續(xù)遮擋和稀疏噪聲腐蝕的矩陣更加魯棒。

圖9 Cuprite在DNMD下的恢復(fù)結(jié)果

圖10 Cuprite在RDNMD下的恢復(fù)結(jié)果

對(duì)于RGB彩色圖像集，可以先分別在每個(gè)通道上進(jìn)行RDNMD,再按照RGB通道進(jìn)行合成。當(dāng)圖像集很大時(shí)，矩陣分解的計(jì)算復(fù)雜度較大。為了加快矩陣分解的速度，減小對(duì)內(nèi)存的需求，可以考慮采用隨機(jī)梯度下降法[25]來(lái)求解RDNMD，這將是一個(gè)值得研究的問(wèn)題。今后將進(jìn)一步研究基于Schatten-q范數(shù)的矩陣分解和基于雙核范數(shù)的概率矩陣分解，并將其應(yīng)用于矩陣補(bǔ)全問(wèn)題。