黃瓊慧， 段雪峰

(桂林電子科技大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，廣西 桂林 541004)

考慮下述非負(fù)矩陣的正則化低秩逼近問(wèn)題。

在信息時(shí)代，結(jié)構(gòu)化矩陣的低秩逼近頻繁出現(xiàn)在金融工程[1]、圖像與信號(hào)處理[2]、潛在語(yǔ)義分析[3]及機(jī)器學(xué)習(xí)[4]等學(xué)科與領(lǐng)域。Park等[5]提出了Hankel矩陣低秩逼近的總體最小范數(shù)算法，隨后此算法被應(yīng)用于Sylvester矩陣的低秩逼近計(jì)算。與上述算法相比，Cadzow算法[6]對(duì)于求解結(jié)構(gòu)矩陣低秩逼近問(wèn)題更加簡(jiǎn)單便捷?；谂ｎD法和交替最小二乘算法，Schost等[7]提出類牛頓迭代算法求解結(jié)構(gòu)低秩逼近問(wèn)題，且該迭代算法能夠局部收斂于一個(gè)低秩結(jié)構(gòu)矩陣。Duan等[8-9]基于Gramian representation和特殊三角函數(shù)變換將相關(guān)矩陣的低秩逼近問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題，并構(gòu)造共軛梯度算法進(jìn)行求解。隨后，他提出非單調(diào)譜投影梯度法求解Q范數(shù)下的相關(guān)矩陣低秩逼近問(wèn)題。Chu等[10]系統(tǒng)地研究了結(jié)構(gòu)低秩逼近問(wèn)題及其在信號(hào)處理和蛋白質(zhì)折疊等方面的應(yīng)用。

求解問(wèn)題1的關(guān)鍵在于如何刻畫問(wèn)題中的可行集

鑒于此，利用矩陣的滿秩分解處理可行集中的秩約束，基于交替最小二乘法求解等價(jià)的非負(fù)矩陣分解問(wèn)題，提出投影梯度法求解相關(guān)子問(wèn)題并證明其收斂性，并用數(shù)值例子驗(yàn)證方法的可行性。

1 主要結(jié)果

1.1 交替最小二乘法

引理1n×n階矩陣X的秩小于等于r，當(dāng)且僅當(dāng)存在矩陣W∈Rn×r,H∈Rr×n，使得X=WH。

由引理1，問(wèn)題1的可行集可刻畫為如下形式：

Ω={X=WH|W≥0,H≥0,W∈Rn×r,

H∈Rr×n}。

因此問(wèn)題1可等價(jià)轉(zhuǎn)化成問(wèn)題2。

其中，

應(yīng)用如下交替最小二乘算法求解問(wèn)題2。

算法11)初始化W1≥0,H1≥0。

2)當(dāng)k=1,2,…時(shí)

(1)

(2)

該算法也稱作有界約束優(yōu)化中的塊坐標(biāo)下降算法[11]，即其中一個(gè)向量塊對(duì)應(yīng)的目標(biāo)函數(shù)在相應(yīng)的約束條件下被最小化，而其余的塊是固定的。該算法處理的是最簡(jiǎn)單的情況，即只有W、H兩個(gè)塊向量。

由文獻(xiàn)[12]中的推論2，有如下收斂性結(jié)果。

定理1算法1所產(chǎn)生序列{Wk,Hk}的任意收斂點(diǎn)為問(wèn)題2的穩(wěn)定點(diǎn)。

實(shí)現(xiàn)算法1的關(guān)鍵在于求解式(1)和(2)，其中式(1)和(2)都為有界約束優(yōu)化問(wèn)題，故設(shè)計(jì)投影梯度方法進(jìn)行求解。

1.2 投影梯度法

考慮下列有界約束優(yōu)化問(wèn)題的標(biāo)準(zhǔn)形式：

其中：f(x):Rn→R為連續(xù)可微函數(shù)，l和u分別為上界和下界。則投影梯度方法的迭代規(guī)則為

xk+1=P[xk-αkf(xk)]，

其中，

的作用是將點(diǎn)映射至有界可行域中。

利用Armijo線搜索下的投影梯度法求解上述有界約束優(yōu)化問(wèn)題。

算法21)給定0<β<1，0<σ<1，初始化任意可行點(diǎn)x1。

2)當(dāng)k=1,2,…時(shí)，

xk+1=P[xk-αkf(xk)]。

其中：αk=βtk，且tk為滿足不等式

f(xk+1)-f(xk)≤σf(xk)T(xk+1-xk)

的最小非負(fù)整數(shù)t。

關(guān)于式(2)，可將其重寫為

s.t.Hij≥0,?i,j。

(3)

其中，A、B、C、W為常數(shù)矩陣。

根據(jù)Shepherd的描述[13]，式(1)和(2)應(yīng)用投影梯度法的更新規(guī)則為

Wk+1=max(0,Wk-αkWf(Wk,Hk)),

Hk+1=max(0,Hk-αkHf(Wk,Hk))，

其中αk為步長(zhǎng)。因此，求解式(2)的投影梯度算法如下。

2)計(jì)算投影梯度

的最小非負(fù)整數(shù)t，令

將式(1)重寫為與式(3)同樣形式：

s.t.Wij≥0,?i,j，

其中H為常數(shù)矩陣，則可應(yīng)用與算法3類似的算法獲得式(1)的解Wk+1。

2 數(shù)值實(shí)驗(yàn)

利用數(shù)值例子驗(yàn)證交替最小二乘算法求解問(wèn)題2的可行性。實(shí)驗(yàn)在MATLAB 2016a環(huán)境下運(yùn)行。

在數(shù)值實(shí)驗(yàn)中，設(shè)(Wk,Hk)處的投影梯度為Pf(Wk,Hk)，其中(Wk,Hk)為算法1中第k次迭代值，停機(jī)標(biāo)準(zhǔn)為‖Pf(Wk,Hk)‖F(xiàn)≤ε‖f(W1,H1)‖F(xiàn)。

例1給定矩陣

設(shè)α=0.3，r=2，初始值：

用算法1求解，經(jīng)13次迭代得到問(wèn)題2的最優(yōu)解：

從而問(wèn)題1的最優(yōu)解為

圖1 n=3，r=2時(shí)的梯度范數(shù)曲線

例2給定矩陣：

A=

B=

C=

設(shè)α=0.3，r=3，初始值：

H0=

用算法1求解，經(jīng)26次迭代得到問(wèn)題2的最優(yōu)解：

從而問(wèn)題1的最優(yōu)解為

圖2 n=5，r=3時(shí)的梯度范數(shù)曲線

3 結(jié)束語(yǔ)

利用矩陣的滿秩分解及其相關(guān)性質(zhì),將非負(fù)矩陣的正則化低秩逼近問(wèn)題轉(zhuǎn)化為等價(jià)的非負(fù)矩陣分解問(wèn)題，并利用交替最小二乘方法求解非負(fù)矩陣分解問(wèn)題，用投影梯度法求解相關(guān)的子問(wèn)題。數(shù)值實(shí)驗(yàn)表明，此方法是可行的。