粒子群优化的加权核范数低秩矩阵补全算法.pdf

0引言低秩矩阵补全是恢复二维矩阵缺失信息的一种新兴技术1,2遥 该技术利用缺失信息与观测数据之间的相关性袁通过优化秩最小化模型获得一个与原观测矩阵近似的低秩矩阵袁从而恢复矩阵中的缺失元素3遥由于相关恢复算法的收敛精度较高袁低秩矩阵现已成为机器学习领域的研究热点之一4,5遥加权核范数最小化方法(Weighted NuclearNorm Minimization袁WNNM)是 Shuhang Gu 等人6于 2017 年提出的一种改进版本的奇异值阈值化方法遥该方法能够根据阈值决策函数动态调整矩阵奇异值的阈值院奇异值越大袁获得的阈值越小遥这种策略能够更好地保留矩阵中的有效信息并抑制矩阵中的噪声信息1遥 与奇异值阈值化算法渊SVT冤7等基于核范数最小化的补全方法相比袁WNNM 算法具有更高的收敛精度遥 因此袁该算法一经提出就受到机器学习8-10等领域的广泛关注遥然而袁WNNM 算法因阈值决策函数单一袁导致该算法在不同数据矩阵上的恢复性能不稳定的问题也越来越受到许多学者的重视遥为了获得收敛精度高的恢复结果袁必须针对特定的测试数据合理设置相应参数的取值遥 这样袁WNNM 算法批量化处理大量矩阵数据的能力必然受到一定的限制院很难找到统一的参数设置使得 WNNM 算法在不同数据上都能获得较好的收敛效果遥与 WNNM 类似袁 同时期的其他多种类型的加权核范数最小化方法则尝试不同的加权方式来提升算法的恢复精度遥 2016 年袁胡尧11等人提出截断核范数正则化低秩矩阵补全方法袁强调矩阵的前几个较大的奇异值主要用来恢复矩阵的有效信息袁不对其进行阈值化操作能够尽可能多的保留矩阵的主体信息曰因此袁只对剩余的较小奇异值进行优化袁在一定程度上提升了算法的收敛精度遥2019 年袁Liu3等人提出一种泛化的加权核范数最小化方法袁也即加权 L2,1范数最小化的矩阵补全方法遥 该方法的最优化模型在理论上能够收敛到加权核范数最小化模型袁具有与加权核范数最小化方法类似的收敛精度遥 2020 年袁冯伟12等人提出一种基于加速近似梯度的加权核范数最小化方法渊APGL-WNNM冤遥该方法利用加速近似梯度搜索方法袁优化传统的加权核粒子群优化的加权核范数低秩矩阵补全算法陈笑笑袁 任丹丹袁 刘清渊安徽理工大学数学与大数据学院袁 安徽淮南232001冤摘要院针对加权核范数最小化矩阵补全方法存在阈值决策函数单一尧收敛精度不高等问题袁提出一种粒子群优化的加权核范数最小化低秩矩阵补全算法遥 改进算法利用粒子群的启发式智能搜索能力袁为待恢复矩阵的奇异值自适应地匹配恰当的阈值袁以提升算法的收敛性能遥 改进工作主要包括院渊1冤设计多种奇异值阈值决策函数袁为矩阵提供多种阈值分配策略曰渊2冤改进粒子群的速度迭代公式袁提出基于余弦函数的速度惯性调节公式以增强粒子群的全局搜索性能曰渊3冤利用改进的粒子群优化算法为阈值决策函数搜索最优的参数组合袁然后再通过阈值决策函数生成奇异值的阈值袁重构恢复结果并提升算法的收敛精度遥 在人工数据和图像数据上的实验结果表明袁与加权核范数最小化方法尧奇异值阈值化方法以及低秩矩阵拟合方法相比袁改进方法具有收敛精度更高尧恢复结果更清晰等优势遥关键词院加权核范数曰粒子群曰低秩曰矩阵补全中图分类号院O151曰TP931文献标识码院A文章编号院1673-260X渊2023冤05-0022-07Vol.39 No.5May 2023赤 峰 学 院 学 报 渊 自 然 科 学 版 冤Journal of Chifeng University(Natural Science Edition)第 39 卷第 5 期2023 年 5 月收稿日期院2023-03-05通讯作者院任丹丹袁女袁安徽淮北人袁博士袁副教授袁研究方向院图像处理尧最优化理论与算法研究袁E-mail:rdd_遥基金项目院国家自然科学基金渊11801008袁62102002冤曰安徽省自然科学基金渊2008085QF291冤22-范数最小化模型遥 由于 APGL-WNNM 算法是一种贪婪算法袁 其算法收敛速度比传统 WNNM 算法有较大的提升遥 然而袁APGL-WNNM 算法与 WNNM算法一样袁也存在频繁调整关键参数的问题遥综上所述袁基于加权核范数最小化的低秩矩阵补全方法袁 比如 WNNM 以及截断核范数正则化方法等袁都具有较好的算法收敛精度遥然而袁这些算法都存在阈值决策函数较为单一尧算法的数据依赖性较强等问题遥因此袁开发一种算法稳定性强袁参数自适应调整的矩阵补全方法是十分有意义的遥为了进一步提升 WNNM 算法的收敛精度袁提出一种基于粒子群优化的加权核范数最小化方法遥粒子群优化算法13主要模拟鸟类群体的觅食行为院算法保留粒子的全局学习能力以及个体的记忆能力遥 因此袁粒子群优化算法具有较强的全局收敛能力袁并因此受到广泛关注14-16遥改进方法主要利用粒子群的启发式智能搜索能力袁为阈值决策函数匹配最优参数组合袁然后为矩阵的每个奇异值自动分配恰当的阈值遥 由于粒子群算法的全局搜索能力较强袁改进方法具有更高的收敛精度以及更好的稳定性遥1基础知识介绍1.1 相关定义及其说明假设袁M(M沂Rm伊n)是一个只有部分元素已知的含有缺失信息的矩阵袁且 0m臆n遥若 Mi,j是 M 中的观测元素袁其下标(i,j)的集合用 赘 表示遥 低秩矩阵补全的目的就是找到一个低秩矩阵 X 近似逼近矩阵 M遥 核范数最小化算法在优化过程中袁都需要使用矩阵 X 的奇异值分解(SVD)袁其定义如下院X=U撰VT袁(1)其中袁撰沂Rm伊n是一个对角矩阵袁其对角线元素撰i,i=滓i(X)是 X 第 i 个奇异值曰矩阵的核范数院|X|=移mi=1滓i(X)遥(2)一般假定 滓i(X)按非增次序排列院滓i(X)逸滓j(X),(ij)曰U沂Rm伊m袁V沂Rn伊m分别是矩阵 X 的左右奇异矩阵遥1.2加权核范数最小化低秩矩阵补全方法 渊WN鄄NM冤WNNM 算法是 Gu6于 2017 年提出的一种加权核范数低秩矩阵补全方法袁其优化模型如下院minx|X|w,*,s.t.P赘(X+E)=M,P赘(E)=0,(3)其中袁|X|w,*是加权核范数院|X|w,*=移mi=1wi滓i(X)且 wi按非减次序排列院wi臆wj(i0 是一个平衡系数袁Tk沂Rm伊n是一个中间变量曰Tk=Ek+1-Y-1滋kLk袁 其中袁Y 是观测数据矩阵袁Lk是 Lagrange 乘子系数矩阵袁Ek+1是稀疏的噪声矩阵遥 由加权核范数阈值化算子6可知袁问题渊4冤的最优解如下院X=Udiang(撰i,i-wi/滋,i=1,2,噎,m)+VT,(5)其中袁(x)+=max(x,0)袁x 为任意实数曰U撰VT是 Tk的奇异值分解形式遥WNNM 算法的权值设定方法如下院wi=c/(滓i(Tk)+着),(6)其中袁c0袁 是一个正则化参数袁着0 是一个值很小的实数袁其作用是避免出现分母为零的情况出现遥 WNNM 算法的主要步骤如表 1 所示院实际上袁对于给定的一组权值(w1,w2,噎,wn)袁问题渊4冤的最优解一定是公式渊5冤给出的解遥 然而袁影响算法最终收敛精度的关键在于如何选择合适的权值(w1,w2,噎,wn)遥2粒子群优化的加权核范数低秩矩阵补全算法初始化院滋c尧籽尧着0袁k=0袁Xk=Y=M袁Lk=zeros(m,n)曰输入院 观测矩阵 M袁已知元素位置集合 赘袁阈值向量 W曰Repeat院Step1:Ek+1=argminEY+1滋kLk-Xk-E2F袁s.t.|P赘(E)|2F=0曰Step2:U,撰,V=SVDEk+1-Y-1滋kLk蓸蔀曰Step3:UPDATE(w1,噎,wm):公式渊6冤曰Step4:UPDATE Xk+1公式渊5冤曰Step5:Lk+1=Lk+滋k(Y-Xk+1-Ek+1)曰滋k+1=籽 窑 滋k曰k=k+1曰Until院|V-Xk+1-Ek+1|F|Y|F着输出院X=Xk+1遥表 1加权核范数最小化算法 WNNM 的主要步骤数理研究23-针对 WNNM 算法存在的参数鲁棒性较差袁收敛精度不高等问题袁提出一种基于粒子群优化的加权核范数低秩矩阵补全算法渊Particle Swarm Opti鄄mization based Weighted Nuclear Norm Minimiza鄄tion,PWNNM冤遥 PWNNM 算法的主要思想为院利用三个子群分别优化三种阈值决策函数的关键参数袁选择最优函数并让其生成对应于当前恢复数据的最优阈值袁然后进行奇异值的阈值化操作袁最后重构结果矩阵遥2.1三种阈值决策函数现有研究表明奇异值的阈值应当按递减次序排列袁即奇异值越大袁则其阈值越小遥 然而袁阈值决策函数应当以何种方式递减是最优的袁目前尚无统一的定论遥因此袁提出三种阈值决策函数袁其表达式如下院F1(x)=1,ifxax-ba-b,ifa臆xb0,ifx逸b扇墒设设设设设设设缮设设设设设设设袁(7)F2(x)=1,ifxa(x-b)h(a-b)h,ifa臆xb0,ifx逸b扇墒设设设设设设设缮设设设设设设设袁(8)F3(x)=1,ifxasint(x-b)sint(a-b),ifa臆xb0,ifx逸b扇墒设设设设设设设缮设设设设设设设袁(9)其中袁a尧b尧h 和 t 是三个函数的参数袁 且 0ab1 且 0t1曰h 的大小直接决定 F2(x)下凸的程度曰t 的取值决定 F2(x)下凹的程度遥由公式渊7冤渊8冤和渊9冤可知院渊1冤当 0 xa 时院F1(x)=F2(x)=F3(x)=1曰这样袁小的奇异值可以被赋予最大的阈值袁 从而过滤噪声信息曰渊2冤当 a臆xb 时院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 次迭代中袁 每个粒子 Pi的速度 Vi按如下公式迭代进化院Vi=ZkVi+c1r1(Pi_best-Xi)+c2r2(Gbest-Xi)(10)其中袁c1和 c2分别是社会学习因子与个体历史学习因子袁一般设置为大于零的实数袁在迭代过程中保持不变曰r1和 r2是渊0袁1冤范围内的随机数曰Xi是粒子 Pi的位置袁Pi_best表示粒子 Pi所经历的历史最优位置袁i=1,2,噎,N,N 是粒子群的种群规模袁也即粒子的总数曰Gbest 表示粒子群已经搜索到的全局最优位置遥 Zith是在第 ith 次迭代中袁粒子 Pi的速度衰减因子遥 传统线性权重粒子群优化算法(WPSO)采用如下方式调整速度衰减因子 Zk院(A)F1(x)的图像(B)F2(x)的图像(C)F3(x)的图像图 1三种阈值决策函数的示例图袁其中袁a=0.2袁b=0.8数理研究24-Zith=Zmax-ith 窑(Zma