王展梁，劉新國

(中國海洋大學數學科學學院，山東 青島 266100)

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

(1)

或者其拉格朗日形式

(2)

式中：X∈Rm×n為要恢復的目標矩陣;b∈Rp為觀測數據;A：Rm×n→Rp為仿射變換;參數ε≤0反映噪聲水平；λ>0為正則化參數。當仿射變換A為矩陣的取樣算子時，仿射秩最小化問題就轉化為矩陣填充問題[4]。

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

(3)

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

1 算法

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

引理1設X∈Rm×n，γ≤1，則

(4)

證明 由矩陣行列式的性質可知

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

(5)

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

(6)

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

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

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

②當y→+時，對?z∈Proxαg(y)，有z→+且

③當y1

②當y→+時，對?z∈Proxαg(y)，z必為f(x)的一個駐點，即由于則，并且

③當y1

(z2-y2)(y2-y1)

對上述不等式化簡可得z1

(7)

(8)

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

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

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

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設μ>λmax(A*A)/2，則由PGA算法得到的序列{Xk}具有如下性質：

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

證明 ①由(10)式可得

(12)

將Xk+1帶入上式，則

(13)

由式(12)和(13)可得

則

因為μ>λmax(A*A)/2，結論①得證。

2 數值實驗

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

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

則視為恢復成功。對每個r重復100次實驗，設恢復成功的次數為Sr，則定義恢復概率為Sr/100。我們將PGA算法與采用核范數的IADM[13]算法進行比較。由于側重比較模型的恢復能力，我們希望算法能夠得到充分迭代，因此設置停機準則為

由圖3可以看出，當r≤29時，PGA和IADM算法都能夠恢復成功；當r>32時，IADM算法恢復失??；而當r≤42時，PGA算法仍可恢復成功。

圖3 無噪聲情形下的矩陣填充結果

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

圖4 有噪聲情形下的矩陣填充結果

3 結語

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