基于矩陣分解和非凸秩近似的低秩表示算法

山東科技大學(xué) 李 帥

低秩表示(Low Rank Repersentation，LRR)是針對(duì)高維數(shù)據(jù)集可近似地認(rèn)為存在于一個(gè)或多個(gè)相互獨(dú)立的低維子空間中，且子空間的類別與觀測(cè)數(shù)據(jù)中是否存在未知的異常值的問題，將給定的觀測(cè)數(shù)據(jù)進(jìn)行聚類到各自對(duì)應(yīng)的獨(dú)立子空間中，同時(shí)檢測(cè)異常值。提出了基于矩陣分解與對(duì)數(shù)行列式函數(shù)的低秩表示模型(Matrix Factorization and Log-determinant Rank Approximation based low-rank representation，MF-LDLRR)，利用矩陣分解技術(shù)將大規(guī)模矩陣化為三個(gè)小矩陣，再以非凸近似函數(shù)對(duì)數(shù)行列式函數(shù)替代矩陣核范數(shù)來近似矩陣秩函數(shù)，解決了核范數(shù)秩估計(jì)偏差問題，并采用交替方向乘子法求解，最后用譜聚類方法規(guī)范化割[1]求的聚類結(jié)果。通過實(shí)驗(yàn)對(duì)比，提出的算法提高計(jì)算精確度和效率。

1.低秩表示

在求解(2)式中存在每一次迭代均需進(jìn)行奇異值分解，求解算法的計(jì)算復(fù)雜度很高和用核范數(shù)秩近似誤差的問題。

2.基于矩陣分解和非凸秩近似的低秩表示算法

2.1 MF-LDLRR模型

則MF-LDLRR模型為：

2.2 MF-LDLRR的求解算法

下面用交替方向乘子法求解MF-LDLRR模型，引入輔助變量N，模型(3)轉(zhuǎn)化為：

模型(5)的部分增廣拉格朗日函數(shù)為：

其中Uk+1和Vk+1為Orthogonal Procrustes問題[2]。

解得：

解得：

求解Ck+1：

由定理1[3]定理2[3]和性質(zhì)1[3]求解問題Ck+1的封閉解。

求解Nk+1：

對(duì)上(13)式求導(dǎo)得：

求解Ek+1：

有封閉解Ek+1，Ek+1的第 j 列為：

求解拉格朗日乘子，則：

最后更新懲罰參數(shù)：

綜上所述，具體MF-LDLRR求解算法流程如下所示。

3.實(shí)驗(yàn)結(jié)果及分析

應(yīng)用Extended Yale B數(shù)據(jù)庫對(duì)MF-LDLLR算法進(jìn)行驗(yàn)證，與現(xiàn)行LRR,LRSC,SSC等算法相比較。由表1呈現(xiàn)不用算法的分別實(shí)驗(yàn)數(shù)據(jù)結(jié)果。

表1 不同算法對(duì)Extened Yale B人臉數(shù)據(jù)集的聚類錯(cuò)誤率(%)

從表1知，MF-LDLRR的聚類錯(cuò)誤率相對(duì)于對(duì)象數(shù)的增長(zhǎng)保持穩(wěn)定，說明了該算法的魯棒性。當(dāng)n ≥5時(shí)，提出的算法都比其它算法的聚類錯(cuò)誤率低得多。說明了該算法的聚類效果好，且當(dāng)對(duì)象數(shù)多的時(shí)候，這種優(yōu)勢(shì)突出。

4.結(jié)論

提出了基于矩陣分解和非凸秩近似的低秩表示模型，該算法復(fù)雜度低、精確度高，并在Extended Yale B 數(shù)據(jù)庫上進(jìn)行實(shí)驗(yàn)對(duì)比，驗(yàn)證了MF-LDLRR算法有效性。在以后的工作中，模型參數(shù)地選擇也是研究的重點(diǎn)內(nèi)容之一。

[1]SHI J, MALIK J．“Normalized cuts and image segmentation”,IEEE Trans[J]．IEEE Transactions on Pattern Analysis & Machine Intellige nce,2000,22(8)∶888-905．

[2]SCHONEMANN P H．A generalized solution of the orthogonal procrustes problem[J]． Psychometrika,1966,31(1)∶1-10．

[3]PENG C,KANG Z,Li H,et al,Subspace Clustering Using Logdeterminant Rank Approximation[C]//Acm Sigkdd International Conference on Knowledge Discovery & Data Mining．Queensland∶ACM,2015∶925-934．

[4]YANY J, YIN W,ZHANG Y, et al． A Fast Algorithm for Edge-Preserving Variational Multichannel Image Restoration[J]．Siam Journal on Imaging Sciences,2009,2(2)∶569-592．