基于非凸函數(shù)的矩陣秩最小化理論

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

基于非凸函數(shù)的矩陣秩最小化理論

王淑琴

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

近來，在計(jì)算機(jī)視覺、數(shù)據(jù)挖掘等領(lǐng)域人們?cè)絹碓綗嶂杂诶弥茸钚』椒▋?yōu)化模型。由于在求解秩函數(shù)的過程是一個(gè)NP難的非凸優(yōu)化問題，本文選取對(duì)數(shù)行列式函數(shù)作為秩函數(shù)的非凸近似，采取增廣拉格朗日乘子法(ALMM)求解對(duì)數(shù)行列式線性最小二乘模型。通過數(shù)值實(shí)驗(yàn)驗(yàn)證本文提出的算法較現(xiàn)有的求解核范數(shù)矩陣秩最小化問題的算法更高效。

矩陣秩最小化；對(duì)數(shù)行列式函數(shù)；增廣拉格朗日乘子法

一、引言

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

(1)

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

(2)

這里，||·||*為矩陣核范數(shù)，即矩陣的所有非零奇異值之和。然而，當(dāng)矩陣的奇異值非常大時(shí)，用矩陣的核范數(shù)近似秩函數(shù)效果一般，彭沖等在文獻(xiàn)[1]中求解子空間聚類問題時(shí)發(fā)現(xiàn)，利用對(duì)數(shù)行列式函數(shù)對(duì)矩陣秩函數(shù)進(jìn)行近似的效果較好，優(yōu)于核范數(shù)近似效果?；诖?，本文中我們考慮用對(duì)數(shù)行列式函數(shù)

(3)

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

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

(4)

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

二、增廣拉格朗日乘子法

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

s.t.X=Y

增廣拉格朗日函數(shù)為：

其中θ∈Rn×m是拉格朗日乘子，β>0是懲罰參數(shù)。當(dāng)n

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

因?yàn)長(zhǎng)ALMM的收斂性在前面已經(jīng)分析過，這里我們只導(dǎo)出KKT條件

省略了ALMM的收斂性分析。

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

算法1ALMM輸入：A，B，μ>0，β>0，迭代的最大數(shù)量Kmax． 1：初始化：SetX0∈Rn×m，θ0∈RN×m，K=0．2：循環(huán)：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．

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

在本節(jié)中，我們采用Extended Yale B①[13]數(shù)據(jù)應(yīng)用到人臉識(shí)別，將2、3章中提出的算法與LSA[5]，SCC6，LRR，LRSC[6]，SSC的有效性進(jìn)行對(duì)比。本文所有的實(shí)驗(yàn)都是在Windows 8系統(tǒng)MATLABR2013a中運(yùn)行的。

表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-)，女，山東濱州，碩士研究生，山東科技大學(xué)，研究方向圖像處理。