仿射秩最小化問(wèn)題的一種解法?

王展梁，劉新國(guó)

(中國(guó)海洋大學(xué)數(shù)學(xué)科學(xué)學(xué)院，山東 青島 266100)

近年來(lái)，基于仿射變換下的低秩矩陣恢復(fù)問(wèn)題在協(xié)同過(guò)濾[1]、圖像處理[2]、量子成像[3]等多個(gè)領(lǐng)域有重要應(yīng)用，發(fā)展求解此問(wèn)題的高效數(shù)值解法是當(dāng)前數(shù)值最優(yōu)化領(lǐng)域的研究熱點(diǎn)之一。仿射秩最小化問(wèn)題是指下述矩陣最優(yōu)化問(wèn)題

(1)

或者其拉格朗日形式

(2)

式中：X∈Rm×n為要恢復(fù)的目標(biāo)矩陣;b∈Rp為觀測(cè)數(shù)據(jù);A：Rm×n→Rp為仿射變換;參數(shù)ε≤0反映噪聲水平；λ>0為正則化參數(shù)。當(dāng)仿射變換A為矩陣的取樣算子時(shí)，仿射秩最小化問(wèn)題就轉(zhuǎn)化為矩陣填充問(wèn)題[4]。

Wen等[7-9]提出了一種基于矩陣分解的建模方法，避免了對(duì)矩陣進(jìn)行奇異值分解，但事先需要對(duì)矩陣的秩進(jìn)行合理的預(yù)測(cè)。Mohan等[10]利用矩陣的Schatten-p范數(shù)來(lái)代替秩函數(shù)，提高了模型的恢復(fù)能力。本文用下述新的松弛模型來(lái)求解秩最小化問(wèn)題

(3)

其中γ≤1，并且發(fā)展了模型(3)的數(shù)值解法，證明了數(shù)值算法的收斂性，數(shù)值實(shí)驗(yàn)表明了模型(3)相較于核范數(shù)模型的優(yōu)越性。

1 算法

下述引理用于得到模型(3)的等價(jià)形式。

引理1設(shè)X∈Rm×n，γ≤1，則

(4)

證明 由矩陣行列式的性質(zhì)可知

由引理1，可得到模型(3)的如下等價(jià)形式

(5)

定義1對(duì)于下半連續(xù)的正常函數(shù)g(x)：R→R及α>0，其鄰近算子Proxαg：R→R定義如下：

(6)

在本文中，我們討論y為矩陣奇異值的情況，因此只需要對(duì)y≤0進(jìn)行考慮。下面的三個(gè)定理給出了模型(5)中罰函數(shù)的鄰近算子的相關(guān)性質(zhì)及其顯式表達(dá)式。

定理1設(shè)g(x)=log(x+γ)，γ≤1，α>0，g(x)的鄰近算子滿足如下性質(zhì)：

①?c>0，?y∈[0,c]，Proxαg(y)=0。

②當(dāng)y→+時(shí)，對(duì)?z∈Proxαg(y)，有z→+且

③當(dāng)y1

②當(dāng)y→+時(shí)，對(duì)?z∈Proxαg(y)，z必為f(x)的一個(gè)駐點(diǎn)，即由于則，并且

③當(dāng)y1

(z2-y2)(y2-y1)

對(duì)上述不等式化簡(jiǎn)可得z1

(7)

(8)

圖1 log(x+γ)的鄰近算子在γ=1，α=0.8時(shí)的圖像

圖2 log(x+γ)的鄰近算子在γ=1，α=2時(shí)的圖像

設(shè)UDiag(σ)VT為X的奇異值分解，由鄰近算法[11]中的結(jié)論可知有ProxαG(X)的一個(gè)顯式解為

ProxαG(X)=UDiag(Proxαg(σ1),…,Proxαg(σd))VT。

(9)

(10)

式中A*是A的共軛算子，μ>λmax(A*A)/2，λmax(A*A)/2為A*A的最大特征值。

由(9)式我們得到迭代算法

(11)

令

下面的定理給出了上述算法的收斂性。

定理4設(shè)μ>λmax(A*A)/2，則由PGA算法得到的序列{Xk}具有如下性質(zhì)：

①{F(Xk)}單調(diào)遞減并收斂。

證明 ①由(10)式可得

(12)

將Xk+1帶入上式，則

(13)

由式(12)和(13)可得

則

因?yàn)棣?λmax(A*A)/2，結(jié)論①得證。

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

在本節(jié)中，我們通過(guò)矩陣填充問(wèn)題來(lái)驗(yàn)證模型(3)的有效性和算法的可行性。算法中涉及到的奇異值分解利用PROPACK[12]計(jì)算。

在無(wú)噪聲的情況下，我們模擬模型和算法的恢復(fù)能力。假定采樣率為50%，X=X1X2為目標(biāo)矩陣，其中X1∈R200×r，X2∈Rr×200為元素服從均值為0，方差為1的正態(tài)分布的隨機(jī)矩陣，整數(shù)r為矩陣的秩，其變化范圍為25～50。設(shè)X*為算法得到的解，當(dāng)相對(duì)誤差滿足

則視為恢復(fù)成功。對(duì)每個(gè)r重復(fù)100次實(shí)驗(yàn)，設(shè)恢復(fù)成功的次數(shù)為Sr，則定義恢復(fù)概率為Sr/100。我們將PGA算法與采用核范數(shù)的IADM[13]算法進(jìn)行比較。由于側(cè)重比較模型的恢復(fù)能力，我們希望算法能夠得到充分迭代，因此設(shè)置停機(jī)準(zhǔn)則為

由圖3可以看出，當(dāng)r≤29時(shí)，PGA和IADM算法都能夠恢復(fù)成功；當(dāng)r>32時(shí)，IADM算法恢復(fù)失?。欢?dāng)r≤42時(shí)，PGA算法仍可恢復(fù)成功。

圖3 無(wú)噪聲情形下的矩陣填充結(jié)果

PGA算法亦適用于含噪聲情況。假定采樣率和目標(biāo)矩陣X的構(gòu)造與上述實(shí)驗(yàn)相同，令Xnoise=X+0.1×E，其中E為元素服從均值為0，方差為1的正態(tài)分布的隨機(jī)矩陣。然后對(duì)Xnoise進(jìn)行采樣，矩陣的秩r變化范圍為25～50。我們對(duì)每個(gè)r做20次實(shí)驗(yàn)得到其平均誤差，并同IADM算法進(jìn)行了對(duì)比。由圖4可以看出當(dāng)r≤30時(shí)，IADM算法相對(duì)誤差高于0.05，且相對(duì)誤差逐漸增大，而PGA算法在r≤43時(shí)，相對(duì)誤差仍在0.05以下。

圖4 有噪聲情形下的矩陣填充結(jié)果

3 結(jié)語(yǔ)

本文提出了一種矩陣秩最小化問(wèn)題的松弛模型，并給出了鄰近梯度下降算法，證明了算法的收斂性。通過(guò)實(shí)驗(yàn)表明，模型的恢復(fù)能力要高于核范數(shù)松弛，是求解原問(wèn)題的一種好的模型，且在有噪聲污染的情況下，算法的表現(xiàn)也優(yōu)于核范數(shù)松弛，本研究為解決實(shí)際問(wèn)題提供了一種新的途徑。