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

陳勇勇，王永麗，于慧慧

(山東科技大學 數學與系統科學學院，山東 青島 266590)

?

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

陳勇勇，王永麗，于慧慧

(山東科技大學 數學與系統科學學院，山東 青島 266590)

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

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

1引言

考慮矩陣秩最小化問題

(1)

其中，X∈Rm×n，A∈Rp×m,B∈Rp×n是數據矩陣。

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

(2)

(3)

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

2對數行列式函數最小化問題

2.1問題描述

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

(4)

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

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

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

(5)

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

(6)

(7a)

(7b)

(7c)

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

(8)

(9)

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

子問題(7b)等價于

(10)

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

(11)

(12)

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

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

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

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

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

輸出：X*=Xk。

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

3算法的收斂性分析

本節中，我們將證明本文所提出的算法收斂到原問題的穩定點。

問題(5)的KKT條件為：

(13)

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

(14)

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

(15)

由定理1可得

(16)

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

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

(17)

X*-Y*=0。

(18)

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

(19)

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

(20)

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

(21)

(22)

4實驗結果與分析

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

實驗分為三類：

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

2) 4.2節采用隨機數據，比較LADM與ALADMLD算法的高效性；

3) 4.3節采用ExtendedYaleB數據應用到人臉識別，比較ALADMLD算法與LSA，SCC，LRR，LRSC，SSC的有效性。

由于算法中參數比較多，首先給出實驗的基本細節。

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

4) 終止準則。ALADMLD和LADM算法的終止準則：

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

5) 評價標準。均方根誤差(rootmeansquareerror，RMSE)

表1給出了所有實驗數據的統計信息。

表1　實驗中的數據集統計信息

4.1APGL與ALADMLD的實驗結果

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

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

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

4.2LADM與ALADMLD的實驗結果

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

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的實驗結果

表2　算法LADM和ALADMLD的結果比較

4.4實驗總結

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

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

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

3) 當矩陣的某些奇異值比較大時，采用對數行列式函數近似矩陣秩函數的近似效果優于核范數的近似效果。

表3　應用Extended Yale B數據的聚類誤差

5結論

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

參考文獻：

[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.

(責任編輯：傅游)

收稿日期：2016-01-08

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

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

中圖分類號：N949

文獻標志碼：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