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

2022-03-23唐晓妮闫喜红

太原师范学院学报(自然科学版) 2022年1期

唐晓妮，闫喜红

(太原师范学院数学系，山西晋中 030619)

0 引言

近年来，随着互联网5G技术的高速发展和云计算等智能终端的普及，越来越多的大规模、高维数、结构复杂的数据需要进行分析、处理.作为一种有着广泛应用的数据处理方法，矩阵填充问题近几年发展迅速.矩阵填充是利用矩阵的低秩特性，由已知的部分元素将其余空缺元素合理准确地填充出来的问题.它在机器学习[1]，数据挖掘[2]，模式识别[3]，计算机视觉[4]，图像恢复[5]，视频去噪[6]等领域有着广泛的应用.

矩阵填充问题首先被Cand’es和Recht[7]提出，他们指出大多数低秩矩阵都可以通过求解如下凸优化问题从它们的采样矩阵中填充出来，

(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算法的启发，对交替方向算法(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 算法

在本节中，我们将矩阵填充的核范数模型(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迭代后的结果应用惯性策略进行加速，接着由加速后的结果继续进行下一次的迭代，从而得到加速交替方向算法，其算法步骤如下：

初始化：已知采样矩阵M,指下标集合为Ω，给定参数γ,β,ε,kmax，α,指设X0=Z0=0,指

令k=0.

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

步3：计算

2 数值实验

在本节中，我们通过随机矩阵填充的实验，为了验证我们提出新算法的有效性和可行性，对交替方向算法和加速交替方向算法进行了比较，所有数值实验结果均在类型为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的数值实验结果表明，在相同的运行环境及参数的情况下，我们提出的新算法B总是比原算法A迭代次数少，运行的CPU时间短，并且新算法的精度也优于原算法.这些都很好地验证了我们新算法的可行性和有效性.