陳勇勇，王永麗，于慧慧

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

?

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

陳勇勇，王永麗，于慧慧

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

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

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

1引言

考慮矩陣秩最小化問(wèn)題

(1)

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

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

(2)

(3)

求解核范數(shù)無(wú)約束最小化問(wèn)題常用的算法有加速近似梯度法(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)矩陣的某些奇異值較大時(shí)，彭沖等[7]求解子空間聚類問(wèn)題時(shí)發(fā)現(xiàn)，利用對(duì)數(shù)行列式函數(shù)對(duì)矩陣秩函數(shù)進(jìn)行近似的效果較好，而核范數(shù)的近似效果較差?；诖?，本文用對(duì)數(shù)行列式函數(shù)代替核范數(shù)作為矩陣秩函數(shù)的近似，同時(shí)考慮到對(duì)數(shù)行列式函數(shù)的非凸性，應(yīng)用增廣拉格朗日交替方向法求解問(wèn)題(3)，提出一個(gè)新的算法，在適當(dāng)條件下證明了算法的收斂性，并通過(guò)實(shí)例驗(yàn)證了算法的有效性。

2對(duì)數(shù)行列式函數(shù)最小化問(wèn)題

2.1問(wèn)題描述

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

(4)

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

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

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

(5)

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

(6)

(7a)

(7b)

(7c)

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

(8)

(9)

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

子問(wèn)題(7b)等價(jià)于

(10)

此問(wèn)題同樣有封閉解，下面給出求解此問(wèn)題的幾個(gè)定理。

(11)

(12)

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

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

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

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

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

輸出：X*=Xk。

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

3算法的收斂性分析

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

問(wèn)題(5)的KKT條件為：

(13)

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

(14)

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

(15)

由定理1可得

(16)

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

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

(17)

X*-Y*=0。

(18)

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

(19)

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

(20)

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

(21)

(22)

4實(shí)驗(yàn)結(jié)果與分析

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

實(shí)驗(yàn)分為三類：

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

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

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

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

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

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

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

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

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

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

4.1APGL與ALADMLD的實(shí)驗(yàn)結(jié)果

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

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

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

4.2LADM與ALADMLD的實(shí)驗(yàn)結(jié)果

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

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的實(shí)驗(yàn)結(jié)果

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

4.4實(shí)驗(yàn)總結(jié)

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

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

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

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

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

5結(jié)論

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

參考文獻(xiàn)：

[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

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(11241005)

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

中圖分類號(hào)：N949

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

文章編號(hào)：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