矩阵填充的混合型增广拉格朗日乘子算法

郭 婕，王川龙

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

0 引言

近年来，矩阵填充问题引起了许多学者的研究兴趣.矩阵填充问题是根据采样矩阵的部分已知元素来填充低秩矩阵，从而用重构的低秩矩阵来逼近采样矩阵，它在计算机视觉[1]，模式识别[2]，图像重构[3，4]，机器学习[5]，数据挖掘[6]，控制论[7]及视频去噪[8]等领域有着广泛的应用.

矩阵填充问题首次由Cand’es和Recht[9]提出，它的凸优化数学表述为：

min‖A‖*

(1)

s.t.PΩ(A)=PΩ(M)，

有关凸优化问题(1)的研究，已经有大量的成果.例如，Fazel[10，11]首先将凸优化问题(1)转化为半定规划(Semidefinite Programming，SDP)问题，通过使用一些基于内点的通用SDP方法即可求解凸优化问题(1);Recht等[12]提出模型(1)还可以利用投影梯度算法来求解;Toh和Yun[1]提出了加速近端梯度法(Accelerated Proximal Gradient Algorithm，APG);Ma和Goldfard[13]将近似奇异值分解技术应用到不动点延续算法(Fixed Point Iteration，FPC)，提出了FPCA算法；Cai等[14]提出了奇异值阈值算法(Singular Value Threshold，SVT)，该算法可类比求解向量l0范数最小问题的软阈值迭代算法[15]；Lin等[16]提出了增广拉格朗日乘子算法(Augmented Lagrange Multiplier，ALM)，并且在一定条件下证明ALM算法比SVT算法和APG算法收敛性更准确、收敛速度更快.

本文提出的混合型增广拉格朗日乘子矩阵填充算法是通过定义混合型奇异值阈值算子，将经典的增广拉格朗日乘子算法进行改进后得到的.具体是对ALM算法运行中奇异值分解所产生的阈值进行混合型奇异值阈值算子处理.当迭代次数逐渐增加时，就会发现在奇异值数量减少，奇异值的数值减小的同时，矩阵填充的计算效率极大提高，从而节约了计算花费.因此，新算法在求解矩阵填充问题上明显优于经典的增广拉格朗日乘子算法.

首先先给出一些定义：

定义1(奇异值分解(SVD))[17]秩r的矩阵X∈Rn1×n2，则必存在正交矩阵U∈Rn1×r和V∈Rn2×r，满足

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

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

定义2(硬阈值算子)[15]给定参数τ≥0，硬阈值算子ηh定义为:

其中变量σ∈R，τ是阈值.

定义3(软阈值算子)[15，18]给定参数τ≥0，软阈值算子soft(•)定义为:

其中变量σi∈R，τ是阈值，sign(•)是符号函数.

定义4(奇异值阈值算子)[14]对于任意参数τ≥0，矩阵的秩是r，X∈Rn1×n2，则存在X=UΣrVT，奇异值阈值算子Dτ定义为:

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

在本文中，我们提出一种新的混合型奇异值阈值算子：当阈值σi≥z·τ时，阈值进行硬阈值处理；当阈值σi

定义5(混合型奇异值阈值算子) 对于任意参数τ≥0，z>1，矩阵的秩是r，X∈Rn1×n2，则存在X=UΣrVT，混合阈值算子Hτ，z(X)定义为:

其中X=UΣrVT∈Rn1×n2，soft(•)是软阈值算子.

也就是说，当σi

1 算法

1.1 增广拉格朗日乘子算法

在这一节中，我们简要介绍增广拉格朗日乘子算法，以便于后文数值实验中算法比较.

增广拉格朗日乘子法[16]主要求解如下问题：

min ‖A‖*

s.t.A+E=D，PΩ(E)=0，

(2)

这里A，D=PΩ(M)∈Rn1×n2，M∈Rn1×n2，Y∈Rn1×n2，Ω⊂{1，…，n1}×{1，…，n2}.同时，为了方便，我们用

[Uk，Σk，Vk]τ=svd(Yk)

算法1 增广拉格朗日乘子法(ALM算法)[16，19].

给定采样集合Ω，采样矩阵D=PΩ(M)，参数μ0>0，ρ>1，以及初始矩阵Y0=0，E0=0，k:=0;

第3步：如果‖D-Ak+1-Ek+1‖F/‖D‖F<ε1，且μk‖Ek+1-Ek‖F/‖D‖F<ε2，停止；否则转第4步.

第4步：令Yk+1=Yk+μk(D-Ak+1-Ek+1).

如果μk‖Ek+1-Ek‖F/‖D‖F<ε2，则令μk+1=ρμk；否则转第1步.

1.2 混合型增广拉格朗日乘子(HALM)算法

在这一节中，我们提出新算法.具体步骤如下：

算法2 混合增广拉格朗日乘子(HALM)算法.

给定采样集合Ω，采样矩阵D=PΩ(M)，参数μ0>0，ρ>1，以及初始矩阵Y0=0，E0=0，k:=0;

第2步：

第3-4步同ALM算法.

与ALM算法相比，我们提出的新算法HALM是在其基础上进行改进后得到的，具体是将ALM算法运行中奇异值分解所产生的阈值进行混合型奇异值阈值算子处理.在数值实验中，我们发现，当迭代次数逐渐增加时，奇异值数量减少，奇异值的数值也在减小，矩阵填充的计算效率极大提高，从而节约了计算花费，进而优化了算法.

2 数值结果

在本节中，我们对ALM算法和HALM算法进行了比较，所有的数值实验都是在机器类型为Intel(R) Core(TM) i7-6700 CPU@3.40GHZ，内存16GB ，Windows 7系统的个人机上用 Matlab (R2016a)进行的，也就是说实验中所选取的M和PΩ(M)具有相同的数据.数值实验结果见表1-4.

在数值实验中，M∈Rn×n表示实矩阵，p表示采样率，且p∈{0.3，0.4，0.5，0.6}.同时，在实验结果中，r表示矩阵M的秩，#iter表示算法的迭代步骤数，运行时间CPU的单位为秒，误差(error1，error2)的具体定义为：

此外，对于两个算法，我们选取参数τ0=1/‖PΩ(M)‖2，ρ=1.217 2+1.858 8p，ε1=1×10-6，ε2=1×10-7.

表1 ALM算法与HALM算法的比较 (当p=0.3时)

表2 ALM算法与HALM算法的比较 (当p=0.4时)

接下来，在新算法HALM中混合阈值算子中参数z的选择，我们选取了n=1 000，1 500，2 000的矩阵，比较不同的z和n在运行时间上的差异.当n=1 000，1 500，2 000时，新算法HALM的运行时间始终随着z的变化而变化，而当参数z选取z=1.4时，新算法HALM的运行时间普遍较低.因此，在新算法HALM中，我们选择混合阈值算子的参数z=1.4.

表3 ALM算法与HALM算法的比较 (当p=0.5时)

表4 ALM算法与HALM算法的比较 (当p=0.6时)

从4个表中我们看到新算法HALM在计算时间上总是少于ALM算法的.针对同规模的矩阵而言，随着采样率p的增加，新算法HALM和ALM算法的迭代次数相差不大，但新算法HALM在时间上明显少于ALM算法；针对相同的采样率而言，随着矩阵大小的变化，当p∈{0.3，0.4，0.5，0.6}时，新算法HALM的收敛性和运行时间都优于ALM算法，特别是矩阵规模越大越明显，这些都说明新算法HALM的有效性和可行性.

3 总结

本文先提出了一种新的阈值算子:混合型奇异值阈值算子.然后将该算子与经典的算法增广拉格朗日算法相结合，得到了一种新的矩阵填充算法，即混合型增广拉格朗日乘子算法.与增广拉格朗日乘子算法相比，该算法具有更高的精度.由表1-4可以看出，在相同参数下，我们的算法在运行时间上明显优于增广拉格朗日乘子算法.在新提出的算法中，对阈值的混合处理节省了大部分时间，能够有效地填充矩阵.这些都是基于一般实矩阵而言的，对于低秩矩阵的重构问题的研究，将是我们后期研究工作的重点.