0引言
低秩矩阵补全是恢复二维矩阵缺失信息的一种新兴技术[1,2]。该技术利用缺失信息与观测数据之间的相关性，通过优化秩最小化模型获得一个与原观测矩阵近似的低秩矩阵，从而恢复矩阵中的缺失元素[3]。由于相关恢复算法的收敛精度较高，低秩矩阵现已成为机器学习领域的研究热点之一[4,5]。
加权核范数最小化方法(Weighted Nuclear
Norm Minimization,WNNM)是Shuhang Gu 等人[6]于2017年提出的一种改进版本的奇异值阈值化方法。该方法能够根据阈值决策函数动态调整矩阵奇异值的阈值：奇异值越大，获得的阈值越小。这种策略能够更好地保留矩阵中的有效信息并抑制矩阵中的噪声信息[1]。与奇异值阈值化算法(SVT)[7]等基于核范数最小化的补全方法相比,WNNM 算法具有更高的收敛精度。因此，该算法一经提出就受到机器学习[8-10]等领域的广泛关注。
然而,WNNM 算法因阈值决策函数单一，导致该算法在不同数据矩阵上的恢复性能不稳定的问题也越来越受到许多学者的重视。为了获得收敛精
度高的恢复结果，必须针对特定的测试数据合理设置相应参数的取值。这样,WNNM 算法批量化处理大量矩阵数据的能力必然受到一定的限制：很难到统一的参数设置使得WNNM 算法在不同数据上都能获得较好的收敛效果。
与WNNM 类似，同时期的其他多种类型的加权核范数最小化方法则尝试不同的加权方式来提升算法的恢复精度。2016年，胡尧[11]等人提出截断核范数正则化低秩矩阵补全方法，强调矩阵的前几个较大的奇异值主要用来恢复矩阵的有效信息，不对其进行阈值化操作能够尽可能多的保留矩阵的主体信息；因此，只对剩余的较小奇异值进行优化，在一定程度上提升了算法的收敛精度。2019年,Liu [3]等人提出一种泛化的加权核范数最小化方法，也即加权L 2,1范数最小化的矩阵补全方法。该方法的最优化模型在理论上能够收敛到加权核范数最小化模型，具有与加权核范数最小化方法类似的收敛精度。2020年，冯伟[12]等人提出一种基于加速近似梯度的加权核范数最小化方法(APGL-WNNM)。该方法利用加速近似梯度搜索方法，优化传统的加权核
粒子优化的加权核范数低秩矩阵补全算法
陈笑笑，任丹丹，刘
清
(安徽理工大学数学与大数据学院，安徽淮南232001)
摘要：针对加权核范数最小化矩阵补全方法存在阈值决策函数单一、收敛精度不高等问题，提出一种粒子优化的加权核范数最小化低秩矩阵补全算法。改进算法利用粒子的启发式智能搜索能力，为待恢
复矩阵的奇异值自适应地匹配恰当的阈值，以提升算法的收敛性能。改进工作主要包括:(1)设计多种奇异值阈值决策函数，为矩阵提供多种阈值分配策略;(2)改进粒子的速度迭代公式，提出基于余弦函数的速度惯性调节公式以增强粒子的全局搜索性能;(3)利用改进的粒子优化算法为阈值决策函数搜索最优的参数组合，然后再通过阈值决策函数生成奇异值的阈值，重构恢复结果并提升算法的收敛精度。在人工数据和图像数据上的实验结果表明，与加权核范数最小化方法、奇异值阈值化方法以及低秩矩阵拟合方法相比，改进方法具有收敛精度更高、恢复结果更清晰等优势。
关键词：加权核范数；粒子；低秩；矩阵补全中图分类号:O151;TP931文献标识码:A
文章编号:1673-260X(2023)05-0022-07
Vol.39No.5May 2023
赤峰学院学报(自然科学版)
Journal of Chifeng University (Natural Science Edition)
第39卷第5期2023年5月
收稿日期:2023-03-05
通讯作者：任丹丹，女，安徽淮北人，博士，副教授，研究方向：图像处理、最优化理论与算法研究,E-mail:****************。基金项目：国家自然科学基金(11801008,62102002)；安徽省自然科学基金(2008085QF291)
范数最小化模型。由于APGL-WNNM算法是一种贪婪算法，其算法收敛速度比传统WNNM算法有
较大的提升。然而,APGL-WNNM算法与WNNM
算法一样，也存在频繁调整关键参数的问题。
综上所述，基于加权核范数最小化的低秩矩阵补全方法，比如WNNM以及截断核范数正则化方
法等，都具有较好的算法收敛精度。然而，这些算法
都存在阈值决策函数较为单一、算法的数据依赖性较强等问题。因此，开发一种算法稳定性强，参数自
适应调整的矩阵补全方法是十分有意义的。
为了进一步提升WNNM算法的收敛精度，提
出一种基于粒子优化的加权核范数最小化方法。
粒子优化算法[13]主要模拟鸟类体的觅食行为：算法保留粒子的全局学习能力以及个体的记忆能
力。因此，粒子优化算法具有较强的全局收敛能
力，并因此受到广泛关注[14-16]。改进方法主要利用粒子的启发式智能搜索能力，为阈值决策函数匹配
最优参数组合，然后为矩阵的每个奇异值自动分配
恰当的阈值。由于粒子算法的全局搜索能力较
强，改进方法具有更高的收敛精度以及更好的稳定
性。
1基础知识介绍
1.1相关定义及其说明
假设,M(M∈R m×n)是一个只有部分元素已知的含有缺失信息的矩阵，且0<m≤n。若M i,j是M中的观测元素，其下标(i,j)的集合用Ω表示。低秩矩阵补全的目的就是到一个低秩矩阵X近似逼近矩阵M。核范数
最小化算法在优化过程中，都需要使用矩阵X的奇异值分解(SVD)，其定义如下:
X=UΛV T,(1)其中,Λ∈R m×n是一个对角矩阵，其对角线元素Λi,i=σi(X)是X第i个奇异值；矩阵的核范数:
||X||=∑m i=1σi(X)。(2)
一般假定σi(X)按非增次序排列:σi(X)≥σj(X), (i<j);U∈R m×m,V∈R n×m分别是矩阵X的左右奇异矩阵。
1.2加权核范数最小化低秩矩阵补全方法(WN⁃NM)
WNNM算法是Gu[6]于2017年提出的一种加权核范数低秩矩阵补全方法，其优化模型如下:
min
x
||X||w,*,s.t.PΩ(X+E)=M,PΩ(E)=0,(3)其中,||X||w,*是加权核范数:||X||w,*=∑m i=1w iσi(X)且w i按非减次序排列:w i≤w j(i<j);E∈R n×m是一个稀疏的噪声数据矩阵。模型(3)主要通过Lagrange 交替方向乘子法(ADMM)求解[1]。在第k次迭代中，目标变量X通过求解如下子问题获得其最优解:
min
x
||X||w,*+μ2||X-T k||F2,(4)其中,μ>0是一个平衡系数,T k∈R m×n是一个中间变量;T k=E k+1-Y-1μk L k，其中,Y是观测数据矩阵,L k是Lagrange乘子系数矩阵,E k+1是稀疏的噪声矩阵。由加权核范数阈值化算子[6]可知，问题(4)的最优解如下:
X=Udiang(Λi,i-w i/μ,i=1,2,…,m)+V T,(5)其中,(x)+=max(x,0),x为任意实数;UΛV T是T k 的奇异值分解形式。
WNNM算法的权值设定方法如下:
w i=c/(σi(T k)+ε),(6)其中,c>0，是一个正则化参数,ε>0是一个值很小的实数，其作用是避免出现分母为零的情况出现。WNNM算法的主要步骤如表1所示:
实际上，对于给定的一组权值(w1,w2,…,w n)，问题(4)的最优解一定是公式(5)给出的解。然而，影响算法最终收敛精度的关键在于如何选择合适的权值(w1,w2,…,w n)。
2粒子优化的加权核范数低秩矩阵补全算法初始化:μc、ρ、ε>0,k=0,X k=Y=M,L k=zeros(m,n);
输入：观测矩阵M，已知元素位置集合Ω，阈值向量W; Repeat:
Step1:E k+1=argmin E Y+1μ
k
L k-X k-E2
F
,PΩ(E)||2F=0;
Step2:[U,Λ,V]=SVD E k+1-Y-1μ
k
L k
();
Step3:UPDATE(w1,…,w m)：公式(6);
Step4:UPDATE X k+1公式(5);
Step5:L k+1=L k+μk(Y-X k+1-E k+1);
μk+1=ρ·μk;k=k+1;
Until:||V-X k+1-E k+1||F
||Y||F>ε
输出:X=X k+1。
表1加权核范数最小化算法WNNM的主要步骤
针对WNNM算法存在的参数鲁棒性较差，收敛精度不高等问题，提出一种基于粒子优化的加权核范数低秩矩阵补全算法(Particle Swarm Opti⁃mization based Weighted Nuclear Norm Minimiza⁃tion,PWNNM)。PWNNM算法的主要思想为：利用
三个子分别优化三种阈值决策函数的关键参数，选择最优函数并让其生成对应于当前恢复数据的最优阈值，然后进行奇异值的阈值化操作，最后重构结果矩阵。
2.1三种阈值决策函数
现有研究表明奇异值的阈值应当按递减次序排列，即奇异值越大，则其阈值越小。然而，阈值决策函数应当以何种方式递减是最优的，目前尚无统一的定论。因此，提出三种阈值决策函数，其表达式如下:
F1(x)=
1,if x<a
x-b a-b,if a≤x<b
0,if x≥b
⎧
⎩
⏐⏐
⏐⏐
⏐⏐
⏐⎨
⏐⏐
⏐⏐
⏐⏐
⏐
,(7)
F2(x)=
1,if x<a
(x-b)h(a-b)
h,if a≤x<b
0,if x≥b
⎧
⎩
⏐⏐
⏐⏐
⏐⏐
⏐⎨
⏐⏐
⏐⏐
⏐⏐
⏐
,(8)
F3(x)=
1,if x<a
sin t(x-b)
sin t(a-b),if a≤x<b
0,if x≥b
⎧
⎩
⏐⏐
⏐⏐
⏐⏐
⏐⎨
⏐⏐
⏐⏐
⏐⏐
⏐
,(9)
其中,a、b、h和t是三个函数的参数，且0<a< b<1,h>1且0<t<1;h的大小直接决定F2(x)下凸的程度;t的取值决定F2(x)下凹的程度。由公式(7)(8)和(9)可知:
(1)当0<x<a时:F1(x)=F2(x)=F3(x)=1；这样，小的奇异值可以被赋予最大的阈值，从而过滤噪声信息;
(2)当a≤x<b时:F1(x)线性递减,F2(x)是递减的凸函数,F3(x)是递减的凹函数；三种不同的递减方式，能够为不同结构的矩阵提供合适的阈值决策函数，提升恢复精度;
(3)当x≥b时:F1(x)=F2(x)=F3(x)=0：对于大于b 的奇异值，不做阈值化处理，以尽可能保留矩阵的有效信息。
为了更加直观地展示F1(x)、F2(x)和F3(x)这三种决策函数的性质，图1给出了这三种函数在不同参数下的图像曲线。
从图1可以看出,F2(x)在[a,b]区间内是递减函数，参数h越大，函数曲线下凸程度越高,h越接近1，函数曲线越接近于线性递减函数；与之类似，参数t的取值直接影响F2(x)在[a,b]区间内的下凹程度:t越小，函数图像的下凹程度越高。虽然奇异值的阈值应当按照递减次序排列已经得到理论上的证明，但是，阈值的具体下降方式，比如按照线性函数递减、下凸函数递减以及下凹函数递减等，目前尚无定论。
因此，本文提出上述三种不同类型的阈值决策函数，作为生成奇异值阈值的备选函数。然后，由三个粒子分别搜索三个阈值决策函数的最优参数组合，并在三个子中选出最优函数；最后，使用最优函数生成矩阵奇异值的所有阈值，并重构恢复结果矩阵。
2.2改进的粒子优化算法
粒子优化算法[13]是一种基于体智能的启发式搜索算法，具有较强的全局搜索能力和局部搜索能力。由于传统线性权重粒子优化算法(WPSO)[13]存在易陷入局部极小区域的问题，提出一种改进的粒子优化算法。在第ith次迭代中，每个粒子P i 的速度V i按如下公式迭代进化:
V i=ZkV i+c1r1(P i_best-X i)+c2r2(Gbest-X i)(10)其中,c1和c2分别是社会学习因子与个体历史学习因子，一般设置为大于零的实数，在迭代过程中保持不变;r1和r2是(0,1)范围内的随机数;X i 是粒子P i的位置,P i_best表示粒子P i所经历的历史最优位置,i=1,2,…,N,N是粒子的种规模，也即粒子的总数;Gbest表示粒子已经搜索到的全局最优位置。Z ith是在第ith次迭代中，粒子P i的速度衰减因子。传
统线性权重粒子优化算法(WPSO)采用如下方式调整速度衰减因子Z k :
(A)F1(x)的图像(B)F2(x)的图像(C)F3(x)的图像
图1三种阈值决策函数的示例图，其中,a=0.2,b=0.8
Z ith =Z max -ith
·(Z max -Z min )termax
,(11)
其中,0<Z min <Z ith <Z max ,itermax 表示粒子的最
大迭代次数。现有研究表明，采用公式(11)的线性衰减公式调节公式(10)的速度惯性因子，可能会导致粒子优化算法易于陷入局部极优区域，而形成早熟现象。为避免这一问题，提出改进的速度衰减因子，调节公式如下:
Z ith =α·cos mod
ith ·πitermax ·Q
,π
()()+β,(12)
其中,α>0,β>0,mod(x,y)表示x 整除y 后得到的余数,Q 是大于零的整数；根据公式(12)可知，权值衰减因子Z ith ，将在整个迭代期间周期性循环递减的变化趋势。图2给出了Z ith 在itermax=2000,α=
0.2,β=0.6,Q=4条件下的变化曲线图。
从图2可以看出，速度惯性衰减因子呈现周期性的递减变化趋势，变化的周期数由变量Z 控制。改进的速度惯性因子调节公式(12)能够有效地避免粒子陷入局部极优区域，在寻优期间保持着全局搜索能力。粒子的位置更新公式如下:
X i =X i +V i 。
(13)
改进的粒子优化算法的主要步骤与传统的
线性权重粒子优化算法WPSO 的主要步骤一致，故在此不做重复描述，感兴趣的读者可参考文献[13]。为方便后续算法描述，将改进的基于余弦速度衰减因子的粒子优化算法简记为COSWPSO。2.3
粒子优化的加权核范数最小化方法
本文使用三个子分别优化这三个函数的关键参数。子A 1优化函数F 1(x)的参数a 和b，种
规模为N 1；子A 2优化函数F 2(x)的参数a、b 和h，种规模为N 2；子A 3优化函数F 3(x)的参数a、b 和t，种规模为N 3。三个子的速度和位置按公式(10)(12)和(13)动态更新。
三个粒子的寻优目标是为矩阵的每个奇异值分配合适的阈值，以提升矩阵补全的精度。假设,X i j 表示子A j (j=1,2,3)中粒子P i j 的位置；评价X i j 优劣的适应度函数如下式所示:
fit(X i j )=∑m
k=1σk μF j (σk |X i j )·σk +μ2
||P Ω(X temp -M)||2F ,
(14)
其中,λ>0,j=1,2,3,F j (σk |X i j )表示其他参数等于
X i j 、自变量x=σk 时,F j (x)的函数值;X temp =∑m
k=1σk (1-F j (σk )/μ)+μk v T k ，且UΛV T 是公式(4)中T k 的奇异值分解形式。F j (x)的参数与X i j 的关系如表2所示:
三个子A 1、A 2和A 3经过若干次迭代之后会
产生适应度函数值最小的全局最优位置，不妨记为Gbest j 且j∈(1,2,3)。根据表1中的参数与粒子位置的
关系，计算出最优阈值:
w i pso =σi F j (σi |Gbest j ),(15)
其中,i=1,2,…,m。利用粒子搜索到的阈值
w i pso 取代公式(6)中的阈值，对待优化矩阵进行阈值化操作，并重构恢复结果，得到问题(4)的最优解
如下:
X=Udiag(Λi,i -w i pso /μ,i=1,2,…,m)。
(16)
上述通过粒子优化阈值决策函数的关键参
数,
然后生成奇异值最优阈值的加权核范数最小化
图2
速度惯性衰减因子Z 的变化曲线
函数名参数1参数2参数3F 1(x)F 2(x)F 3(x)
a=X j=1i,1a=X j=2i,1a=X j=3
i,1
b=X j=1i,1b=X j=2i,2b=X j=3
i,2
无h=X j=2
i,1t=X j=3
i,3
表2阈值决策函数的参数与粒子位置分量的关系
输
入:σ1,σ2,…,σm ;
初始化:N 1,N 2,N 3;X 1
1,…,N ,X 21,…,N ,X 31,…,N ;V 11,…,N ,V 21,…,N ,V 3
1,…,N ,
c 1=c 2=2;α=0.2,β=0.6;A=2;itermax=100;
For ith=1:itermax
UPDATE:V 11,…,N ,V 2
1,…,N ,V 3
1,…,N ：公式(10),(12);UPDATE:X 2
1,…,N ,X 31,…,N ;V 1
1,…,N ：公式(13);
按公式(14)选择适应度函数值最小的X i j ，记为
Gbest j ;
end
w i pso =F j (σi |Gbest j )：表2，公式(7-9);(i=1,2,…,m)。
输
出:w 1pso ,w 2pso ,…,w m pso 。
正则化是结构风险最小化策略的实现
表3PWNNM 算法中COSWPSO 算法优化奇异值阈值的主要步骤
低秩矩阵补全方法，简记为PWNNM 方法。PWNNM 算法中，利用COSWPSO 粒子优化奇异值阈值的主要流程如图3所示。
PWNNM 方法的改进工作主要是如表3所示
的利用COSWPSO 粒子优化算法，智能化搜索奇异值的阈值，替换WNNM 算法中Step3(表1)。改
进方法能够自适应地更换阈值决策函数并为其设置最优参数组合，进而生成恰当的奇异值阈值，具有更好的收敛精度和数据适应能力。3实验结果
本文分别在人造低秩矩阵和图像矩阵上进行低秩矩阵补全的相关实验，并测试PWNNM 算法的收敛精度、算法稳定性等性能。实验采用的对比算法分别为：低秩矩阵拟合算法(LMaFit)[17]
，奇异值
阈值化方法(SVT)[7]以及加权核范数最小化矩阵补
全方法(WNNM)[6]
。各算法收敛精度的评价指标包括重建误差(Error)和峰值信噪比(PSNR)，定义分
别如下所示:
Error=||X rec -I||F ,
(17)PSNR=10log 10
m×n×2552
Error 2
(
)
,
(18)
其中,I∈R
m×n
是不含缺失元素的原始测试矩
阵,m、n 分别是其行数与列数,X rec 是矩阵补全算法的恢复结果矩阵。
PWNNM 算法的主要参数设置如下：三个粒子
的种规模N 1=N 2=N 3=10，最大迭代次数100，粒子最大速度v max =0.1，粒子最小速度v min =-0.
1;c 1=c 2=2,α=0.2,β=0.6;Q=2；其他与WNNM 公同的参数与WNNM 算法的相应参数设置保持一致。LMaFit 算
法、WNNM 算法以及SVT 算法的参数已调整至最优，最大迭代次数均为200。3.1
人造低秩矩阵
实验使用的人工低秩矩阵由公式(19)给出:
I=L ·R+P Ω(θ·randn(m,n)),
(19)M=P Ω(I)
(20)
其中,L 和R 的秩都等于r:L=randn (m,r),R=randn (m,r);I 是原始数据矩阵,M 是含有缺失元素的矩阵,Ω是观测元素的下标集合;θ是噪声干扰的强度，范围为:0<θ<1。一般情况下,θ越大，四种测试算法的收敛精度越低。
令m=300,n=300,r=m ·10%=30，且噪声干扰强度θ从0.1逐步增大到0.9，步长为0.1。在这组参数下，按
公式(19)，公式(20)产生实验使用的低秩矩阵I，然后随机选择50%元素作为观测值，剩余的元素作为缺失值。四种算法,PWNNM、WNNM、LMaFit 以及SVT，在这一组低秩数据上的重建误差如表4所示。
首先，从表4可以看出,SVT 算法和LMaFit 算法的重构误差比WNNM 算法和PWNNM 算法的重建误差大很多。主要原因是,WNNM 和PWNNM 方法能够在每次迭代过程中，动态调整奇异值的阈值。其次,LMaFit 算法的重建误差增长速度比SVT 方法的增长速度快。当θ=0.1、0.2时,LMaFit 方法的重建误差优于SVT 算法的重建误差，然而，随着噪声强度的增大,LMaFit 方法的重建误差明显比SVT 算法的结果大很多。因此,LMaFit 算法的抗干扰性能比SVT 算法略差。与WNNM 算法相比,SVT
算法的抗干扰性要差很多：重建误差的增长速度比WNNM 算法的误差增长速度快。最后，改进PWNNM 算法在噪声强度较小(θ=0.1、0.2)时，恢复精度与WNNM 算法基本持平；而当θ>0.2时,PWNNM 算
法的重建误差却明显比WNNM 算法的重建误差小，也即具有更高的收敛精度。3.2
图像矩阵
对数字图像的存储、编码以及传输，自然成为计算机图像处理的基本任务之一。图像数据在上述处理过程中难免发生数据的编码错误、数据信息部分丢失等情况。
噪声∂LMaFit SVT WNNM PWNNM 0.136.7737.9819.7919.990.264.57
66.2333.6433.820.3119.7996.76
52.3248.310.4159.28118.3961.1557.390.5216.12150.5273.1768.890.6246.68189.8197.26
89.16
0.7263.74217.55120.30112.470.8297.47233.18135.98127.630.9
309.12255.94169.32156.56表4四种方法在人工数据上的重建误差对比表

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。