非精確交替方向法求解秩最小化問題

呂曉帆，李姣芬，周學林

(桂林電子科技大學 數學與計算科學學院，廣西 桂林　541004)

非精確交替方向法求解秩最小化問題

呂曉帆，李姣芬，周學林

(桂林電子科技大學 數學與計算科學學院，廣西 桂林541004)

摘要：針對秩最小化問題的非凸且不連續性質，利用核范數是秩函數在單位球內的最佳凸逼近，構造其凸近似模型。采用非精確交替方向法求解該模型，并證明了其收斂性。分析結果表明，該方法是有效的。

關鍵詞：秩最小化；核范數；凸逼近；非精確交替方向法

近年來，秩最小化問題[1]在實際中有重要研究意義，這一問題在圖像處理、信號處理等方面有著廣泛應用[2]。參考Lin等[3]提出的Lyapunov方程約束下秩最小化問題，將該問題的約束條件進行推廣。

問題1給定矩陣Ai∈Rn×n，Bi∈Rn×n，i=1,2,…,n，求C∈Rn×n，X∈SRn×n，使得

(1)

由內積的定義〈M,N〉=tr(NTM)知，f關于此內積的轉置算子定義為：

1奇異值閾值算法及凸包絡相關性質

考慮r階矩陣X∈Rm×n的奇異值分解X=UΣVT。其中：Σ=diag(σi)，1≤i≤r；U、V分別為有正交列的m×r、n×r階矩陣且奇異值σi為正。對任意τ≥0，奇異值搜索算子：

引理1[4]對任意的τ≥0以及Y∈Rm×n，奇異值收縮算子滿足：

定義1(凸包絡)[5]假設函數h:L→T，若函數g:L→T對于所有的x∈L均有g(x)?h(x)，則稱函數g為函數h的凸包絡。

2零空間參數化

秩函數是非凸且不連續函數，為克服秩函數的非凸性，Recht[5]證明了單位球內核范數是秩函數的凸包絡，提出可以用矩陣核范數代替秩函數，將最小秩問題轉化為最小核范數問題，等價于將問題(1)凸近似為：

(2)

為了解決問題(2)，利用零空間參數化[3]將問題(2)中跡約束及廣義Sylvester矩陣方程約束轉化。將約束條件tr(TjX)=gj轉化為：

[vec(T1),vec(T2),…,vec(TN)]Tvec(X)=g。

定義線性映射：

(3)

將實對稱矩陣X映射到向量g∶=[g1,g2,…,gn]T。式(3)的解為

(4)

其中：

重塑問題(2)，

(5)

由于式(5)中含有3個獨立變量C,X,z及2個耦合的線性約束，其形式不適合交替方向法[6-7]。為了將式(5)轉化為適合該算法的標準形式，定義

其中：ψ為關于C、X的凸可分函數；h為關于z的嚴格凸函數；φ(X)為指示符函數，

將式(5)改為適合交替方向法的標準形式：

(6)

3求解矩陣核范數極小化問題的非精確交替方向法

綜上所述，求解問題(1)等價于求解式(6)。目標函數所對應的增廣拉格朗日函數為：

其中：Y、Z為拉格朗日乘子；ρ>0為懲罰系數。傳統的增廣拉格朗日方法求解采用以下迭代形式：

但此迭代形式忽略了目標函數與約束條件具有可分離結構的良好特性，即將式(6)作為一般的最小化問題求解，在迭代式(7)中對C、X、z同時進行最小化。為了充分利用這一良好特性，可采用交替方向法，先對C、X求極小化，再對z求極小化，其迭代形式為：

(8)

故(C,X)的極小化問題可轉化為如下2個非耦合問題：

(9)

(10)

為了得到式(9)的顯式解，對c(zk)-Yk/ρ進行奇異值分解。由引理1可得：

(11)

(12)

對于問題(8)中的z子問題，

其顯示解歸結為求解正規方程：

(13)

式(13)的顯式解難以通過直接法求得。雖然求精確解是理想結果，但求解逆矩陣會產生大量的計算成本。故采用非精確交替方向法[8]，通過較小的計算成本得到收斂的迭代格式。同時，為了使相應的極小化子問題具有穩定的良態性質，對其進行正則化處理。對于z子問題，求解如下迭代：

(14)

(15)

(16)

或相對誤差標準：

(17)

并使得zk+1為下列方程的精確解：

(18)

(19)

(20)

(21)

若定義

(22)

算法1非精確交替方向法求解問題(1)。給定當前迭代(Ck,Xk,zk,Yk,Zk)，通過以下步驟生成新迭代(Ck+1,Xk+1,zk+1,Yk+1,Zk+1)：

4)Yk+1=Yk+ρ(c(zk+1)-Ck+1)；

5) Zk+1=Zk+ρ(x(zk+1)-Xk+1)。

取算法1的關于z子問題的第k步迭代矩陣zk作為初始矩陣，即令z0=zk。

1)

2)對i=0,1,2,…，繼續迭代。

a)

b)

e)si=ρi+1/qi。

f)θi+1=siαi+1。

j)zi+1=zi+(μi/qi)Mi。

k)Mi+1=Vi-(θi+1/qi)Mi。

4收斂性分析

令F(C)=‖C‖*,G(X)=φ(X)，對于式(6)的一階最優條件等價于尋求

滿足如下變分不等式：

(23)

其中f′(C*)∈?F(C*)，?(C,X,z,Y,Z)∈H。若

則式(23)可改為緊湊格式：

(24)

容易證明Q(W)是單調的，即

由變分不等式的解和投影方程的等價關系可知，求解式(23)等價于求(C*,X*,z*,Y*,Z*)∈H滿足:

(25)

對?γ>0，若定義

(26)

則求解式(25)等價于求式(26)的零點。

引理3令W*=(C*,X*,z*,Y*,Z*)∈H*為式(24)的一個解，其中H*為式(24)的解集，對于當前迭代步(Ck,Xk,zk,Yk,Zk)，記(Ck+1,Xk+1,zk+1,Yk+1,Zk+1)為算法1生成的新迭代步，則有如下不等式成立：

1)

2)

3)存在常數a1,使得k≥0時，有

4)令2個分塊矩陣M=(C1,C2,…,Cq), N=(X1,X2,…,Xq)，則

引理3的證明與文獻[9]類似。

定理1令W*=(C*,X*,z*,Y*,Z*)∈H*為式(24)的一個解，對于當前迭代步(Ck,Xk,zk,Yk,Zk)，記(Ck+1,Xk+1,zk+1,Yk+1,Zk+1)為算法1生成的新迭代步，則序列{Wk+1}收斂于W∞∈H*。

由引理1可知：

設k0為任意整數，由式(27)可知，對?k>k0有

(28)

由此可得，

(29)

由式(29)可知，序列{Wk}有界，且由式(27)、(28)知，

因此，

故

因為vk→0，由引理1得，

W∞為式(24)的一個解，即W∞∈H*。對于任意的ε>0，由Wkj→W∞可知，存在整數l,使得

(30)

因此，對任意的k>kl，由式(28)、(30)可得

5結束語

針對廣義Sylvester矩陣方程和跡約束條件下秩最小化問題，將秩最小化問題轉化為核范數最小化問題，并將該問題分化為若干個較易獲得顯式解的子問題，利用交替方向法進行求解。但由于部分顯式解仍難以利用直接法求得，采用非精確交替方向法，針對不同的約束條件對算法進行修改加以解決，減少了計算成本。

參考文獻:

[1]李文峰,許愛強,戴豪民，等.基于矩陣秩最小化和統計修正的信號降噪方法研究[J].振動與沖擊，2015,34(15):38-44.

[2]唐中和.低秩逼近理論及其在自然圖像去噪中的應用[D].西安：西安電子科技大學，2013:22-68.

[3]LIN F,JOVANOVIC M R,GEORGIOU T T.An ADMM algorithm for matrix completion of partially known state covariances[C]//52nd IEEE Conference on Decision and Control,2013:1684-1689.

[4]CAI J F,CANDES E F,SHEN Z.A singular value thresholding algorithm for matrix completion[J].Siam Journal on Optimization,2010,20(4):1956-1982.

[5]RECHT B,FAZEL M,PARRILO P A.Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization[J].Siam Review,2007,52(3):471-501.

[6]SHOULIE X,SUSANTO R.Alternating direction method for balanced image restoration[J].IEEE Transactions on Image Processing,2012,21(11):4557-4567.

[7]YUAN X.Alternating direction method for covariance selection models[J].Journal of Scientific Computing,2012,51(2):261-273.

[8]XIAO Y H,SONG H N.An inexact alternating directions algorithm for constrained total variation regularized compressive sensing problems[J].Journal of Mathematical Imaging and Vision,2012,44(2):1-14.

[9]MICHAEL N G,WANG F,YUAN X.Inexact alternating direction method for image recovery[J].Siam Journal on Scientific Computing,2011,33(4):1643-1668.

[10]PAIGE C C,SAUNDERS M A.LSQR:an algorithm for sparse linear equations and least spares problems[J].Acm Transactions on Mathematical Software,1982,8(2):195-209.

編輯：張所濱

Inexact alternating direction method for rank minimization problem

LYU Xiaofan, LI Jiaofen, ZHOU Xuelin

(School of Mathematics and Computational Science, Guilin University of Electronic Technology, Guilin 541004，China)

Abstract：In view of non-convex and discontinuous of rank minimization problem, the nuclear norm is the best convex approximation of the rank function within the unit ball. This problem can be formulated as a convex approximation model which is solved by inexact alternating direction method. The convergence of the proposed method is proved. The results show that the approach is effective.

Key words：rank minimization; nuclear norm; convex approximation; inexact alternating direction method

收稿日期：2015-12-31

基金項目：國家自然科學基金(11226323)，廣西自然科學基金(2013GXNSFBA019009)

通信作者：李姣芬(1984-)，男，湖南湘潭人，副教授，博士，研究方向為矩陣優化問題的理論及算法、張量方程的有效算法。E-mail:lixiaogui1290@163.com

中圖分類號：O241.7

文獻標志碼：A

文章編號：1673-808X(2016)02-0154-06

引文格式： 呂曉帆，李姣芬，周學林.非精確交替方向法求解秩最小化問題[J].桂林電子科技大學學報，2016,36(2)：154-159.