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

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

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

王淑琴

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

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

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

一、引言

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

(1)

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

(2)

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

(3)

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

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

(4)

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

二、增廣拉格朗日乘子法

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

s.t.X=Y

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

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

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

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

省略了ALMM的收斂性分析。

結合(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．

三、實驗結果及分析

在本節(jié)中，我們采用Extended Yale B①[13]數(shù)據(jù)應用到人臉識別，將2、3章中提出的算法與LSA[5]，SCC6，LRR，LRSC[6]，SSC的有效性進行對比。本文所有的實驗都是在Windows 8系統(tǒng)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-)，女，山東濱州，碩士研究生，山東科技大學，研究方向圖像處理。