基于增廣拉格朗日交替方向法的矩陣秩最小化算法研究

陳勇勇，王永麗，于慧慧

(山東科技大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，山東 青島 266590)

?

基于增廣拉格朗日交替方向法的矩陣秩最小化算法研究

陳勇勇，王永麗，于慧慧

(山東科技大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，山東 青島 266590)

摘要：針對含有較大奇異值的矩陣秩最小化問題，采用對數(shù)行列式函數(shù)代替核范數(shù)作為秩函數(shù)的非凸近似，應(yīng)用增廣拉格朗日交替方向法求解矩陣秩最小化問題。當(dāng)罰參數(shù)β>1時，證明此算法產(chǎn)生的迭代序列收斂到原問題的穩(wěn)定點。最后利用實際數(shù)據(jù)和隨機數(shù)據(jù)，通過數(shù)值實驗驗證所提出的算法較現(xiàn)有的求解核范數(shù)矩陣秩最小化問題的算法更高效。

關(guān)鍵詞：對數(shù)行列式函數(shù)；核范數(shù)；增廣拉格朗日交替方向法；低秩矩陣表示

1引言

考慮矩陣秩最小化問題

(1)

其中，X∈Rm×n，A∈Rp×m,B∈Rp×n是數(shù)據(jù)矩陣。

矩陣秩最小化問題在機器學(xué)習(xí)、數(shù)據(jù)挖掘、計算機視覺、圖像處理、控制、生物信息學(xué)等領(lǐng)域有廣泛的應(yīng)用，由于求解此問題是NP-hard問題，學(xué)者們往往使用核范數(shù)作為矩陣秩函數(shù)的凸近似[15 ]，即通過求解如下核范數(shù)最小化問題來得到問題(1)的近似解：

(2)

(3)

求解核范數(shù)無約束最小化問題常用的算法有加速近似梯度法(accelerated proximal gradient method with line-search,APGL)[1]、增廣拉格朗日法(augmented lagrangian method， ALM)[2]、交替方向乘子法(alternating direction method of multiplier,ADMM)[3,4]、坐標(biāo)下降法(coordinate descent)[5]等。當(dāng)矩陣的某些奇異值較大時，彭沖等[7]求解子空間聚類問題時發(fā)現(xiàn)，利用對數(shù)行列式函數(shù)對矩陣秩函數(shù)進行近似的效果較好，而核范數(shù)的近似效果較差?；诖?，本文用對數(shù)行列式函數(shù)代替核范數(shù)作為矩陣秩函數(shù)的近似，同時考慮到對數(shù)行列式函數(shù)的非凸性，應(yīng)用增廣拉格朗日交替方向法求解問題(3)，提出一個新的算法，在適當(dāng)條件下證明了算法的收斂性，并通過實例驗證了算法的有效性。

2對數(shù)行列式函數(shù)最小化問題

2.1問題描述

在問題(3)中，利用對數(shù)行列式函數(shù)代替核范數(shù)，可得如下形式：

(4)

圖1　核范數(shù)與對數(shù)行列式函數(shù)對“magic”矩陣秩的近似效果比較

2.2增廣拉格朗日交替方向法

引入輔助變量Y∈Rm×n，將問題(4)轉(zhuǎn)化成如下等價形式：

(5)

問題(5)的增廣拉格朗日函數(shù)為

(6)

(7a)

(7b)

(7c)

子問題(7a)有封閉解：

(8)

(9)

這樣就可以將一個n×n的矩陣求逆轉(zhuǎn)化成一個m×m的矩陣求逆。

子問題(7b)等價于

(10)

此問題同樣有封閉解，下面給出求解此問題的幾個定理。

(11)

(12)

由上述結(jié)論可得本文的算法框架如下。

算法1： 求解問題(5)的增廣拉格朗日交替方向法(ALADMLD)

初始化：任給矩陣X0∈Rm×n，Λ0∈Rm×n，置迭代次數(shù)k=0；

步驟1： 根據(jù)式(8)或者(9)計算Yk+1；

步驟2： 根據(jù)(10)和性質(zhì)1計算Xk+1；

輸出：X*=Xk。

備注1：算法ALADMLD步驟3中γ是為了加快算法的收斂速度。本文的實例中取γ=1.5。

3算法的收斂性分析

本節(jié)中，我們將證明本文所提出的算法收斂到原問題的穩(wěn)定點。

問題(5)的KKT條件為：

(13)

證明：子問題(7b)的最優(yōu)解Xk+1必須滿足一階最優(yōu)性條件

(14)

將式(7c)代入(14)式，得到：

(15)

由定理1可得

(16)

證明：1) 由增廣拉格朗日函數(shù)的定義(6)及算法步驟可得

上式的最后一個等式由(7c)得出。因此

(17)

X*-Y*=0。

(18)

當(dāng)k→∞，由(14),(15)式得

(19)

由(7a)式的一階最優(yōu)性條件，可得

(20)

將(7c)代入(20)式得到

(21)

(22)

4實驗結(jié)果與分析

本節(jié)對已有的求解核范數(shù)矩陣秩最小化問題的較先進的算法—APGL[1]，LADM[3]，LSA[10]，SCC[11]，LRR[12]，LRSC[13]，SSC[14]與本文提出的ALADMLD算法進行比較。需要指出的是APGL代碼可以從軟件包SLEP中獲得。本文所有的實驗都是在Windows8系統(tǒng)MATLABR2013a中運行的。

實驗分為三類：

1) 4.1節(jié)采用實際數(shù)據(jù)(Scene和股票數(shù)據(jù))，比較APGL與ALADMLD求解多元線性分析系數(shù)問題；

2) 4.2節(jié)采用隨機數(shù)據(jù)，比較LADM與ALADMLD算法的高效性；

3) 4.3節(jié)采用ExtendedYaleB數(shù)據(jù)應(yīng)用到人臉識別，比較ALADMLD算法與LSA，SCC，LRR，LRSC，SSC的有效性。

由于算法中參數(shù)比較多，首先給出實驗的基本細節(jié)。

3) 參數(shù)μ。為了驗證算法ALADMLD的有效性，實驗采用多個μ值進行測試，如表1所示。

4) 終止準(zhǔn)則。ALADMLD和LADM算法的終止準(zhǔn)則：

其中，tol=10-6是終止參數(shù)。實驗的最大迭代次數(shù)kmax=100。

5) 評價標(biāo)準(zhǔn)。均方根誤差(rootmeansquareerror，RMSE)

表1給出了所有實驗數(shù)據(jù)的統(tǒng)計信息。

表1　實驗中的數(shù)據(jù)集統(tǒng)計信息

4.1APGL與ALADMLD的實驗結(jié)果

本小節(jié)采用兩種實際數(shù)據(jù)：Scene和Stock，這些數(shù)據(jù)都可以從網(wǎng)上下載。為了使算法具有可比性，本實驗采用的都是APGL算法使用的默認參數(shù)。圖2給出了算法APGL和ALADMLD利用兩種實際數(shù)據(jù)計算得出的均方根誤差隨迭代次數(shù)的變化。圖2(a)中算法APGL和ALADMLD的迭代次數(shù)分別是100和5，圖2(b)中算法APGL和ALADMLD的迭代次數(shù)分別是6和5。雖然圖2(b)中的迭代次數(shù)很相近，但是就均方根誤差來說，算法ALADMLD的精度比APGL高出很多。

圖2(a)　測試Scene數(shù)據(jù)的均方根誤差

圖2(b)　測試Stock數(shù)據(jù)的均方根誤差

4.2LADM與ALADMLD的實驗結(jié)果

因為算法LADM與ALADMLD都屬于增廣拉格朗日方法，故兩種算法的比較更具有說服力。為了更好地驗證算法的有效性，此實驗采用文獻[3]的方式生成數(shù)據(jù)矩陣A，具體產(chǎn)生過程如下：

1)sqrt_lam=sqrt(lam_max);

2) [P,～] = qr(randn(p));

3) d = [1:1 + rand(min(p,m) -2,1) * (sqrt_lam -1);sqrt_lam ];

4) [Q,～] = qr(randn(m));

5) A=P*spdiags(d,0,p,m)*Q’。

4.3LSA,SCC,LRR,SSC,LRSC與ALADMLD的實驗結(jié)果

表2　算法LADM和ALADMLD的結(jié)果比較

4.4實驗總結(jié)

通過實驗結(jié)果的比較發(fā)現(xiàn)，本文提出的算法ALADMLD算法在許多方面較現(xiàn)有的求解核范數(shù)的有效算法—APGL和LADM更高效，具體可歸結(jié)為以下幾點：

1) 三種算法都屬于一階方法，即在每次迭代過程中，只需要計算函數(shù)值和梯度信息，因此三種算法都可用于求解大規(guī)模數(shù)據(jù)問題，但是當(dāng)終止準(zhǔn)則相同時，ALADMLD的計算速度更快；

2) APGL和LADM算法的有效性嚴格依賴于近似映射，近似參數(shù)τ的選取不容易把握；而ALADMLD算法則不需要對子問題進行近似映射，不涉及近似參數(shù)τ的選取，因此更加高效。

3) 當(dāng)矩陣的某些奇異值比較大時，采用對數(shù)行列式函數(shù)近似矩陣秩函數(shù)的近似效果優(yōu)于核范數(shù)的近似效果。

表3　應(yīng)用Extended Yale B數(shù)據(jù)的聚類誤差

5結(jié)論

針對矩陣秩最小化問題，提出了對數(shù)行列式函數(shù)作為矩陣秩函數(shù)的非凸近似。雖然此矩陣秩最小化問題是非凸的，通過引入輔助變量，應(yīng)用增廣拉格朗日交替方向法求解此矩陣秩最小化問題。當(dāng)罰參數(shù)β>1時，證明了提出的算法—ALADMLD產(chǎn)生的序列收斂到非凸矩陣秩最小化問題的穩(wěn)定點。利用隨機數(shù)據(jù)和實際數(shù)據(jù)，將ALADMLD算法與基于核范數(shù)的先進算法進行數(shù)值實驗比較，驗證提出的算法高效性，同時表明了隨著大數(shù)據(jù)問題的引入與推廣，ALADMLD算法將比現(xiàn)有的LADM算法具有更廣闊的應(yīng)用前景。

參考文獻：

[1]TOH K,YUN S.An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems[J].Pacific Journal of Optimization,2010,6(615-640):15.

[2]LIN Z,CHEN M,MA Y.The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices[J].arXiv preprint arXiv:1009.5055,2010.

[3]YANG J,YUAN X.Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization[J].Mathematics of Computation,2013,82(281):301-329.

[4]CHEN C,HE B,YUAN X.Matrix completion via an alternating direction method[J].IMA Journal of Numerical Analysis,2012,32(1):227-245.

[5]DUDIK M,HARCHAOUI Z,MALICK J.Lifted coordinate descent for learning with trace-norm regularization[C]//AISTATS-Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics-2012.2012,22:327-336.

[6]SHERMAN J,MORRISON W.Adjustment of an inverse matrix corresponding to a change in one element of a given matrix[J].The Annals of Mathematical Statistics,1950:124-127.

[7]PENG C,KANG Z,LI H,et al.Subspace clustering using log-determinant rank approximation[C]//Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2015：925-934.

[8]LEWIS A,SENDOV H.Nonsmooth analysis of singular values:Part I:Theory[J].Set-Valued Analysis,2005,13(3):213-241.

[9]SHEN Y,WEN Z,ZHANG Y.Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization[J].Optimization Methods and Software,2014,29(2):239-263.

[10]YAN J,POLLEFEYS M.A general framework for motion segmentation:Independent,articulated,rigid,non-rigid,degenerate and non-degenerate[M]//Computer VisionCECCV 2006.Springer Berlin Heidelberg,2006:94-106.

[11]CHEN G,LERMAN G.Spectral curvature clustering (SCC)[J].International Journal of Computer Vision,2009,81(3):317-330.

[12]LIU G,LIN Z,YU Y.Robust subspace segmentation by low-rank representation[C]//Proceedings of the 27th international conference on machine learning (ICML-10).2010:663-670.

[13]VIDAL R,FAVARO P.Low rank subspace clustering (LRSC)[J].Pattern Recognition Letters,2014,43:47-61.

[14]ELHAMIFAR E,VIDAL R.Sparse subspace clustering:Algorithm,theory,and applications[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(11):2765-2781.

[15]FAZEL M.Matrix rank minimization with applications[D].Palo Alto：Stanford University,2002.

(責(zé)任編輯：傅游)

收稿日期：2016-01-08

基金項目：國家自然科學(xué)基金項目(11241005)

作者簡介：陳勇勇(1989—)，男，山東泰安人，碩士研究生，研究方向為系統(tǒng)優(yōu)化及應(yīng)用、低秩矩陣恢復(fù)、分布式優(yōu)化算法等. 王永麗(1977—)女，山東棲霞人，副教授，博士，研究方向為非線性優(yōu)化理論與算法、分布式優(yōu)化算法及數(shù)據(jù)挖掘等，本文通信作者.E-mail：wangyongli@sdkd.net.cn

中圖分類號：N949

文獻標(biāo)志碼：A

文章編號：1672-3767(2016)04-0106-08

Matrix Rank Minimization Algorithm Based on Augmented Lagrangian Alternating Direction Method

CHEN Yongyong，WANG Yongli，YU Huihui

(College of Mathematics and Systems Science,Shandong University of Science and Technology,Qingdao,Shandong 266590,China)

Abstract:To solve the matrix rank minimization problem with large singular values,the log-determinant function was used as a rank approximation instead of the nuclear norm and an augmented Lagrangian alternating direction method was proposed.When penalty parameter β>1,the sequence of iterations generated by the proposed algorithm was proved to be convergent to a stationary point of the original problem.Finally,numerical experiments were conducted based on real data and random data.The results demonstrate that the proposed algorithm is more efficient than the existing nuclear norm method in solving the problem of matrix rank minimization.

Key words:log-determinant function;nuclear norm;augmented Lagrangian alternating direction method;low rank representation