唐曉妮，閆喜紅

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

0 引言

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

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

(1)

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

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

眾所周知，適當的加速技巧可以使算法在計算效率上得到很大的提高，本文所提出的加速交替方向算法，正是受到Chen[13]的慣性近端ADMM算法的啟發(fā)，對交替方向算法(ADM)迭代后所得的結果進行慣性加速，從而設計出了一種加速交替方向算法，不僅可以減少計算過程的迭代的次數，也可以大幅地減少計算的時間.文章的最后通過數值實驗也驗證了新算法的可行性和有效性.

下面給出本文所用到的相關定義：

定義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é)中，我們將矩陣填充的核范數模型(1)轉化為如下的等價的可分模型：

(2)

模型(2)的Lagrangian函數為

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

1.1 交替方向算法

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

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

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

步3：計算

1.2 加速交替方向算法

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

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

令k=0.

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

步3：計算

2 數值實驗

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

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

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

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

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

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

3 總結

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