一種求解低秩矩陣填充的加速交替方向算法

唐曉妮，閆喜紅

(太原師范學(xué)院 數(shù)學(xué)系，山西 晉中 030619)

0 引言

近年來，隨著互聯(lián)網(wǎng)5G技術(shù)的高速發(fā)展和云計算等智能終端的普及，越來越多的大規(guī)模、高維數(shù)、結(jié)構(gòu)復(fù)雜的數(shù)據(jù)需要進(jìn)行分析、處理.作為一種有著廣泛應(yīng)用的數(shù)據(jù)處理方法，矩陣填充問題近幾年發(fā)展迅速.矩陣填充是利用矩陣的低秩特性，由已知的部分元素將其余空缺元素合理準(zhǔn)確地填充出來的問題.它在機(jī)器學(xué)習(xí)[1]，數(shù)據(jù)挖掘[2]，模式識別[3]，計算機(jī)視覺[4]，圖像恢復(fù)[5]，視頻去噪[6]等領(lǐng)域有著廣泛的應(yīng)用.

矩陣填充問題首先被Cand’es和Recht[7]提出，他們指出大多數(shù)低秩矩陣都可以通過求解如下凸優(yōu)化問題從它們的采樣矩陣中填充出來，

(1)

其中，M∈Rm×n是未知的待填充的矩陣，Ω={(i,j)|i∈{1,2,…,m},j∈{1,2,…,n}}是已知采樣元素下標(biāo)的指標(biāo)集；Mij表示矩陣M的已知元素；X∈Rm×n,指核范數(shù)‖A‖*定義為矩陣A的奇異值之和.

國內(nèi)外的研究工作中已經(jīng)有許多種針對模型(1)的矩陣填充問題的有效算法.Cai[8]等人在2008年提出了奇異值閾值算法(Singular Value Thresholding，SVT),它是解決模型(1)的正則化近似對偶問題的有效的梯度方法；Ma[9]等人在2008年提出了近似不動點延拓法(Fixed Point Continuation with Approximate，F(xiàn)PCA),是一種解決核范數(shù)正則化最小二乘問題的方法；Toh和Yun[10]在2009年提出了加速鄰近梯度算法(Accelerated Proximal Gradient，APG)；Lin[11]等人提出了增廣拉格朗日算法(Augmented Lagrange Multiplier，ALM)； Chen[12]等人在2012年提出了將交替方向算法(alternating direction method，ADM)應(yīng)用到低秩矩陣填充問題中，并在2015年提出了慣性近端ADMM算法[13].

眾所周知，適當(dāng)?shù)募铀偌记煽梢允顾惴ㄔ谟嬎阈噬系玫胶艽蟮奶岣撸疚乃岢龅募铀俳惶娣较蛩惴?，正是受到Chen[13]的慣性近端ADMM算法的啟發(fā)，對交替方向算法(ADM)迭代后所得的結(jié)果進(jìn)行慣性加速，從而設(shè)計出了一種加速交替方向算法，不僅可以減少計算過程的迭代的次數(shù)，也可以大幅地減少計算的時間.文章的最后通過數(shù)值實驗也驗證了新算法的可行性和有效性.

下面給出本文所用到的相關(guān)定義：

定義1(奇異值分解，SVD[14]) 對任意秩為r的矩陣X∈Rn1×n2,指則必存在正交矩陣U∈Rn1×r和V∈Rn2×r,指使得

X=UΣrVT，Σr=diag(σ1,σ2,…,σr)

其中有σ1≥σ2≥…≥σr≥0.

定義2(奇異值閾值算子[15]) 對任意秩為r的矩陣X∈Rn1×n2,指存在X=UΣrVT,指對任意τ≥0,指則奇異值閾值算子Dτ滿足

Dτ(X)=UDτ(Σ)VT,Dτ(Σ)=diag(soft(σi))

其中，soft(σi)=sign(σi)max(σi-π,0).

1 算法

在本節(jié)中，我們將矩陣填充的核范數(shù)模型(1)轉(zhuǎn)化為如下的等價的可分模型：

(2)

模型(2)的Lagrangian函數(shù)為

其中，Z是線性約束的拉格朗日乘子,β>0是懲罰參數(shù),〈X,Y〉=tr(XTY).

1.1 交替方向算法

基于模型(2)，Chen等人已經(jīng)在文獻(xiàn)[12]中提出了如下交替方向算法(ADM)用來求解低秩矩陣填充問題，其算法步驟如下：

初始化：已知采樣矩陣M,指下標(biāo)集合為Ω，給定參數(shù)γ,β,ε,kmax,指設(shè)X0=Z0=0，k=0.

步2：計算Zk+1=Zk-γβ(Xk-Yk+1);

步3：計算

1.2 加速交替方向算法

對于模型(2)，我們的新算法是在1.1中原始交替方向算法的基礎(chǔ)上，為提高計算的效率，在其子問題X迭代后的結(jié)果應(yīng)用慣性策略進(jìn)行加速，接著由加速后的結(jié)果繼續(xù)進(jìn)行下一次的迭代，從而得到加速交替方向算法，其算法步驟如下：

初始化：已知采樣矩陣M,指下標(biāo)集合為Ω，給定參數(shù)γ,β,ε,kmax，α,指設(shè)X0=Z0=0,指

令k=0.

步2：計算Zk+1=Zk-γβ(Xk-Yk+1);

步3：計算

2 數(shù)值實驗

在本節(jié)中，我們通過隨機(jī)矩陣填充的實驗，為了驗證我們提出新算法的有效性和可行性，對交替方向算法和加速交替方向算法進(jìn)行了比較，所有數(shù)值實驗結(jié)果均在類型為Intel(R) Core(TM) i5-1135G7 @ 2.40 GHz，內(nèi)存為16 GB的計算機(jī)上進(jìn)行計算，所有代碼由MATLAB(R2019b)軟件編寫.數(shù)值實驗結(jié)果見表1—3.

表1 算法A與算法B的比較(當(dāng)p=0.3時)

表2 算法A與算法B的比較(當(dāng)p=0.4時)

表3 算法A與算法B的比較(當(dāng)p=0.5時)

在數(shù)值實驗中，M∈Rm×n為已知觀測到的實矩陣，我們用n來表示矩陣M的大小，r來表示矩陣M的秩，用I表示算法所需要的迭代次數(shù)，運行時間CPU的單位為s，p表示矩陣的采樣率，試驗中分別取值為0.3，0.4和0.5 .數(shù)值實驗結(jié)果表1—3中，我們用算法A表示文獻(xiàn)[12]中的交替方向算法，用算法B表示我們的加速交替方向算法.將設(shè)定參數(shù)為ε=2e-4，β=2.5/n，γ=1.6,α=0.1， 并定義了以下兩種誤差：

由表1—3的數(shù)值實驗結(jié)果表明，在相同的運行環(huán)境及參數(shù)的情況下，我們提出的新算法B總是比原算法A迭代次數(shù)少，運行的CPU時間短，并且新算法的精度也優(yōu)于原算法.這些都很好地驗證了我們新算法的可行性和有效性.

3 總結(jié)

本文基于原始交替方向算法，將慣性加速技巧嵌入到原始求解矩陣填充問題的交替方向算法當(dāng)中，提出了一種新的加速的交替方向算法.由數(shù)值實驗結(jié)果可知，在相同的參數(shù)以及運行環(huán)境下，新算法明顯比原算法迭代次數(shù)少，運行時間短，大大提高了低秩矩陣填充問題的計算效率.