劉 丹，羅申星

（河北工業(yè)大學(xué) 理學(xué)院，天津 300401）

0 引 言

非負(fù)矩陣分解（NMF）[1]是一種有效的降維技術(shù)，它將非負(fù)矩陣V∈R+m×n近似分解成低秩非負(fù)矩陣W∈Rm×r和H∈Rr×n++的乘積，即

其中r＜＜min{m,n}.NMF具有存儲(chǔ)空間小、實(shí)現(xiàn)簡單等優(yōu)點(diǎn)，并已成功應(yīng)用于信號處理[2]、醫(yī)學(xué)[3]、計(jì)算機(jī)視覺[4]和聚類[5]等.

為了得到矩陣W和H，人們通常用Frobenius范數(shù)度量V與WH的距離

其中W≥0和H≥0表示W(wǎng)和H的元素是非負(fù)的.

由于稀疏性便于數(shù)據(jù)的分析以及圖像的特征提取，Hoyer等[6]考慮稀疏NMF，在問題（1）中引入L1正則項(xiàng)，提出L1-NMF模型

其中λ﹥0，，i=1，2…r，j=1，2…n.因?yàn)镠≥0，所以.

Xu等[7]發(fā)現(xiàn)與L1正則項(xiàng)相比，引入L1/2正則項(xiàng)能得到更稀疏的解.進(jìn)一步，Cui等[8]在問題（1）中引入L1/2正則項(xiàng)，得到L1/2-NMF模型

為了得到更稀疏的系數(shù)矩陣H，本文在模型（1）中引入L1和L1/2正則項(xiàng)，提出L1-L1/2-NMF模型，這樣可以同時(shí)保留這兩個(gè)正則項(xiàng)帶來的稀疏性效果，即

其中參數(shù)λ﹥0，β﹥0.我們提出兩種算法求解L1-L1/2-NMF：（1）梯度下降算法；（2）受文獻(xiàn)[9]的啟發(fā)，基于交替非負(fù)最小二乘算法框架[10]，提出塊坐標(biāo)下降算法.數(shù)值實(shí)驗(yàn)中，測試了ORL、CBCL、YALE和Extended-YALE 4個(gè)人臉數(shù)據(jù)集.實(shí)驗(yàn)結(jié)果表明，與其他稀疏NMF模型相比，求解L1-L1/2-NMF得到的矩陣更稀疏，相對誤差更小.

本文將詳細(xì)介紹求解問題L1-L1/2-NMF的梯度下降算法和塊坐標(biāo)下降算法.同時(shí)給出相應(yīng)的數(shù)值實(shí)驗(yàn)結(jié)果，并對結(jié)果進(jìn)行分析.

1 稀疏非負(fù)矩陣分解算法

1.1 梯度下降算法

下面給出GDSNMF算法的推導(dǎo)過程.我們對問題（4）中H的列H:j求導(dǎo)，求導(dǎo)公式為

表1給出了GDSNMF算法的詳細(xì)框架.

表1 GDSNMF算法的詳細(xì)框架

1.2 塊坐標(biāo)下降算法

基于交替非負(fù)最小二乘算法框架，提出一種塊坐標(biāo)下降算法（CDSNMF）求解L1-L1/2-NMF.算法對矩陣W的列和H的行進(jìn)行分塊，實(shí)現(xiàn)對矩陣W每一列和H的每一行進(jìn)行更新.L1-L1/2-NMF的兩個(gè)子問題可表示為：

問題（7）的KKT條件為：

其中符號⊕表示（A⊕B）ij=AijBij.由KKT條件知，問題（7）的極小點(diǎn)滿足Hi:F(Hi:)=0，所以H:i的更新規(guī)則為

問題（8）的KKT條件為：

同理，W:i的更新規(guī)則為

表2給出了CDSNMF算法的詳細(xì)框架.

表2 CDSNMF算法的詳細(xì)框架

表3給出了GDSNMF和CDSNMF兩種算法的對比.在MATLAB中隨機(jī)生成一個(gè)非負(fù)矩陣進(jìn)行測試.采用文獻(xiàn)[11]提出的稀疏度計(jì)算公式計(jì)算矩陣W和H的稀疏度

表3 隨機(jī)生成矩陣的數(shù)值實(shí)驗(yàn)結(jié)果

其中n表示向量x的維數(shù).該函數(shù)的值域?yàn)閇0,1]，函數(shù)值越小，則向量x越稠密，反之則越稀疏.

從表3中發(fā)現(xiàn)當(dāng)r較小時(shí)，兩種算法表現(xiàn)相當(dāng)，但隨著r的增大，執(zhí)行步驟2的次數(shù)增多，使得滿足KKT條件的W的列數(shù)和H的行數(shù)增多，CDSNMF算法明顯優(yōu)于GDSNMF算法.

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

本節(jié)測試稀疏NMF問題，并將GDSNMF和CDSNMF算法與求解L1-NMF的NNSC[6]和求解L1/2-NMF的L1/2-SNMF[8]算法進(jìn)行比較.數(shù)值實(shí)驗(yàn)的測試環(huán)境為：Windows 10，Core i5-8250U，1.80 GHz，8 GB RAM.

在下列數(shù)值實(shí)驗(yàn)中，參數(shù)選取λ=30，β=5，ε=10-6.

首先，我們考慮文獻(xiàn)[9]提到的4個(gè)圖像數(shù)據(jù)集ORL、CBCL、Yale和Extended Yale.其中ORL圖像數(shù)據(jù)集包含400張圖像，每張圖像的像素為32×32，ORL圖像數(shù)據(jù)集表示為一個(gè)400×1 024的矩陣.CBCL圖像數(shù)據(jù)集包含2 429張圖像且每張圖像的像素為19×19，CBCL圖像數(shù)據(jù)集表示為一個(gè)2 429×361的矩陣.Yale數(shù)據(jù)集包含165張圖像且每張圖像的像素為32×32，Yale圖像數(shù)據(jù)集表示為一個(gè)1 024×165的矩陣.Extended-Yale圖像數(shù)據(jù)集包含2 414張圖像且每張圖像的像素為32×32，Extended-Yale圖像數(shù)據(jù)集表示為一個(gè)2 414×1 024的矩陣.公平起見，所有算法采用相同的終止條件，即最大迭代次數(shù)達(dá)到500次.如表4所示，與NNSC和L1/2-SNMF算法相比，在保證矩陣W稀疏度相差不大的情況下，GDSNMF和CDSNMF算法得到的系數(shù)矩陣H更稀疏，且相對誤差更小，其中CDSNMF算法的效果尤為明顯.

表4 4個(gè)數(shù)據(jù)集的數(shù)值實(shí)驗(yàn)結(jié)果 (r=49)

其次，從ORL圖像數(shù)據(jù)集中隨機(jī)選取3張人臉圖像，且從每張人臉圖像中得到一個(gè)112×92的矩陣.從表5中可以發(fā)現(xiàn)在4種算法得到的重構(gòu)圖效果和矩陣W稀疏度相差不大的情況下，GDSNMF和CDSNMF算法得到的系數(shù)矩陣H更稀疏，相對誤差更小.

表5 ORL數(shù)據(jù)集的數(shù)值實(shí)驗(yàn)結(jié)果 (r=10)

3 結(jié)論

本文介紹一種新的帶L1和L1/2正則項(xiàng)的稀疏NMF模型L1-L1/2-NMF，提出GDSNMF和CDSNMF算法求解該模型.數(shù)值實(shí)驗(yàn)表明，與求解L1-NMF的NNSC算法和求解L1/2-NMF的L1/2-SNMF算法相比，求解L1-L1/2-NMF的GDSNMF和CDSNMF算法得到的矩陣更稀疏，相對誤差更小.