基于非凸函數的矩陣秩最小化理論

(山東科技大學 山東 青島 266590)

基于非凸函數的矩陣秩最小化理論

王淑琴

(山東科技大學山東青島266590)

近來，在計算機視覺、數據挖掘等領域人們越來越熱衷于利用秩最小化方法優化模型。由于在求解秩函數的過程是一個NP難的非凸優化問題，本文選取對數行列式函數作為秩函數的非凸近似，采取增廣拉格朗日乘子法(ALMM)求解對數行列式線性最小二乘模型。通過數值實驗驗證本文提出的算法較現有的求解核范數矩陣秩最小化問題的算法更高效。

矩陣秩最小化；對數行列式函數；增廣拉格朗日乘子法

一、引言

矩陣的秩最小化問題是為了尋找一個滿足給定約束條件的低秩矩陣X∈Rn×m，即：

(1)

這里，X是數據矩陣，A∈Rp×n，B∈Rp×m。這是一個NP難的非凸優化問題，學者們通常采用矩陣的核范數作為矩陣秩函數的凸近似來求解此類問題，即：

(2)

這里，||·||*為矩陣核范數，即矩陣的所有非零奇異值之和。然而，當矩陣的奇異值非常大時，用矩陣的核范數近似秩函數效果一般，彭沖等在文獻[1]中求解子空間聚類問題時發現，利用對數行列式函數對矩陣秩函數進行近似的效果較好，優于核范數近似效果。基于此，本文中我們考慮用對數行列式函數

(3)

近似矩陣的秩函數。這里的σi是X的奇異值，其中i=1,…,min{n,m}。

在實際應用中，數據矩陣B可能會被噪聲污染，引入最小二乘的思想[1,2]，建立如下的對數行列式函數正則化最小二乘模型：

(4)

這里，μ>0，||·||F表示矩陣的F范數。

二、增廣拉格朗日乘子法

引入一個輔助變量Y∈Rn×m，模型(5)可以被等價表示為:

s.t.X=Y

增廣拉格朗日函數為：

其中θ∈Rn×m是拉格朗日乘子，β>0是懲罰參數。當n

Yk+1=(I-AT(AAT+βμI)-1A)(ATB+βμXk-μθk)

因為LALMM的收斂性在前面已經分析過，這里我們只導出KKT條件

省略了ALMM的收斂性分析。

結合(7)式，ALMM算法被概括如下：

算法1ALMM輸入：A，B，μ>0，β>0，迭代的最大數量Kmax． 1：初始化：SetX0∈Rn×m，θ0∈RN×m，K=0．2：循環：a．Yk+1=(ATA+βμI)-1(ATB+βμXk-μθk)b．Dk+1=Yk+1-1βθk．c．利用命題1解Xk+1d．θk+1=θk-β直到Untilk>kmax或者{Xk，Yk，θk}收斂 輸出：X?=Xk．

三、實驗結果及分析

在本節中，我們采用Extended Yale B①[13]數據應用到人臉識別，將2、3章中提出的算法與LSA[5]，SCC6，LRR，LRSC[6]，SSC的有效性進行對比。本文所有的實驗都是在Windows 8系統MATLABR2013a中運行的。

表1 聚類誤差百分比

【注釋】

①http://vision.ucsd.edu/？leekc/ExtYaleDatabase/ExtYaleB.html

[1]M.Fazel,H.Hindi,P.B.Boyd.Log-det heuristic for matrix rank minimization with applications to Hankel and Euclidean distance matrices[C].American Control Conference,2003.Proceedings of the 2003.IEEE,3,2003,2156-2162

[2]C.J.Hsieh,P.A.Olsen.Nuclear norm minimization via active subspace selection[C].Proceedings of the 31st International Conference on Machine Learning(ICML-14).2014:575-583

[3]J.F.Sturm.Using SeDuMi 1.02,a MATLAB toolbox for optimization over symmetric cones[J].Optimization methods and software,11(1-4),1999,625-653

[4]R.Glowinski,P.Le Tallec.Augmented Lagrangian and Operator Splitting Methods in Nonlinear Mechanics[M].SIAM Studies in Applied Mathematics,Philadelphia.1989

王淑琴(1992-)，女，山東濱州，碩士研究生，山東科技大學，研究方向圖像處理。