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

山東科技大學 李 帥

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

1.低秩表示

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

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

2.1 MF-LDLRR模型

則MF-LDLRR模型為：

2.2 MF-LDLRR的求解算法

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

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

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

解得：

解得：

求解Ck+1：

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

求解Nk+1：

對上(13)式求導得：

求解Ek+1：

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

求解拉格朗日乘子，則：

最后更新懲罰參數：

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

3.實驗結果及分析

應用Extended Yale B數據庫對MF-LDLLR算法進行驗證，與現行LRR,LRSC,SSC等算法相比較。由表1呈現不用算法的分別實驗數據結果。

表1 不同算法對Extened Yale B人臉數據集的聚類錯誤率(%)

從表1知，MF-LDLRR的聚類錯誤率相對于對象數的增長保持穩定，說明了該算法的魯棒性。當n ≥5時，提出的算法都比其它算法的聚類錯誤率低得多。說明了該算法的聚類效果好，且當對象數多的時候，這種優勢突出。

4.結論

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

[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．