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

陈笑笑　任丹丹　刘清

摘 要：针对加权核范数最小化矩阵补全方法存在阈值决策函数单一、收敛精度不高等问题，提出一种粒子群优化的加权核范数最小化低秩矩阵补全算法。改进算法利用粒子群的启发式智能搜索能力，为待恢复矩阵的奇异值自适应地匹配恰当的阈值，以提升算法的收敛性能。改进工作主要包括：（1）设计多种奇异值阈值决策函数，为矩阵提供多种阈值分配策略；（2）改进粒子群的速度迭代公式，提出基于余弦函数的速度惯性调节公式以增强粒子群的全局搜索性能；（3）利用改进的粒子群优化算法为阈值决策函数搜索最优的参数组合，然后再通过阈值决策函数生成奇异值的閾值，重构恢复结果并提升算法的收敛精度。在人工数据和图像数据上的实验结果表明，与加权核范数最小化方法、奇异值阈值化方法以及低秩矩阵拟合方法相比，改进方法具有收敛精度更高、恢复结果更清晰等优势。

关键词：加权核范数；粒子群；低秩；矩阵补全

中图分类号：O151；TP931  文献标识码：A  文章编号：1673-260X（2023）05-0022-07

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]等人提出一种泛化的加权核范数最小化方法，也即加权L2，1范数最小化的矩阵补全方法。该方法的最优化模型在理论上能够收敛到加权核范数最小化模型，具有与加权核范数最小化方法类似的收敛精度。2020年，冯伟[12]等人提出一种基于加速近似梯度的加权核范数最小化方法（APGL-WNNM）。该方法利用加速近似梯度搜索方法，优化传统的加权核范数最小化模型。由于APGL-WNNM算法是一种贪婪算法，其算法收敛速度比传统WNNM算法有较大的提升。然而，APGL-WNNM算法与WNNM算法一样，也存在频繁调整关键参数的问题。

综上所述，基于加权核范数最小化的低秩矩阵补全方法，比如WNNM以及截断核范数正则化方法等，都具有较好的算法收敛精度。然而，这些算法都存在阈值决策函数较为单一、算法的数据依赖性较强等问题。因此，开发一种算法稳定性强，参数自适应调整的矩阵补全方法是十分有意义的。

为了进一步提升WNNM算法的收敛精度，提出一种基于粒子群优化的加权核范数最小化方法。粒子群优化算法[13]主要模拟鸟类群体的觅食行为：算法保留粒子的全局学习能力以及个体的记忆能力。因此，粒子群优化算法具有较强的全局收敛能力，并因此受到广泛关注[14-16]。改进方法主要利用粒子群的启发式智能搜索能力，为阈值决策函数匹配最优参数组合，然后为矩阵的每个奇异值自动分配恰当的阈值。由于粒子群算法的全局搜索能力较强，改进方法具有更高的收敛精度以及更好的稳定性。

1 基础知识介绍

1.1 相关定义及其说明

1.2 加权核范数最小化低秩矩阵补全方法（WNNM）

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

针对WNNM算法存在的参数鲁棒性较差，收敛精度不高等问题，提出一种基于粒子群优化的加权核范数低秩矩阵补全算法（Particle Swarm Optimization based Weighted Nuclear Norm Minimization， PWNNM）。PWNNM算法的主要思想为：利用三个子群分别优化三种阈值决策函数的关键参数，选择最优函数并让其生成对应于当前恢复数据的最优阈值，然后进行奇异值的阈值化操作，最后重构结果矩阵。

2.1 三种阈值决策函数

2.2 改进的粒子群优化算法

2.3 粒子群优化的加权核范数最小化方法

3 实验结果

3.1 人造低秩矩阵

3.2 图像矩阵

从图4可以看出，（B1，B2）中LMaFit算法的恢复结果含有较为明显的异常噪声，说明LMaFit算法不能精确地恢复矩阵中的缺失信息。SVT算法的恢复结果（C1，C2）比LMaFit算法的结果更加清晰，但是仍然能够观察到一些不是特别明显的微小噪声干扰。WNNM算法的恢复图像几乎与原图一致，噪声信息很少且图像细节较为清晰。PWNNM算法的恢复结果与WNNM算法的结果一样，几乎找不到明显的噪声信息。因此，各算法恢复结果的视觉效果与表5中的收敛精度是保持一致的。

4 結论

为了克服加权核范数最小化低秩矩阵补全方法WNNM存在的阈值决策函数单一，算法收敛精度不高等问题，提出了一种基于粒子群优化的加权核范数最小化矩阵补全方法，简记为PWNNM。首先，提出三种凹凸性不同的阈值决策函数，作为生成奇异值阈值的备选函数；其次，提出一种余弦函数调节速度惯性因子的粒子群优化算法；最后，使用改进的粒子群优化算法优化三种阈值决策函数的参数，选出最优决策函数并生成奇异值的最优阈值。由于改进的PWNNM算法能够利用粒子群的全局搜索性能，在较为广阔的参数空间内为每个阈值决策函数匹配合适的参数组合，PWNNM算法在收敛精度、参数设置等方面都具有良好的性能。在人工数据以及图像数据上的实验结果表明，改进的PWNNM算法比WNNM算法、SVT算法以及LMaFit算法具有更高的收敛精度。

参考文献：

〔1〕M. Fazel. Matrix Rank Minimization with Applications[M]. PhD thesis， Stanford Univ. 2002.

〔2〕刘清.基于加权残差和矩阵分解的快速低秩矩阵补全方法[D].南京理工大学博士学位论文，2017.6.

〔3〕Q. Liu， Franck Davoine， Jian Yang， Ying Cui， Zhong Jin and Fei Han. A Fast and Accurate Matrix Completion Method Based on QR Decomposition and L2，1-Norm Minimization[J]. IEEE Trans. On Neural Networks And Learning Systems， 2019， 30（03）： 803-817.

〔4〕曾德宇，梁泽逍，吴宗泽.基于加权核范数和L2，1范数的最优均值线性分类器[J].电子与信息学报，2022，44（05）：1602-1609.

〔5〕袁安富，施徐凯，邱胜峰.基于低秩矩阵的自适应边缘检测算法[J].组合机床与自动化加工技术，2020，1（01）：116-119.

〔6〕S. Gu， Q. Xie etal. Weighted Nuclear Norm Minimization and Its Applications to Low Level Vision[J]. International Journal of Computer Vision ，2017.183-208.

〔7〕J. F. Cai， E. J. Candes， and Z. Shen. A singular value thresholding algorithm for matrix completion[J]. SIAM Journal on Optimization， 2010， 20（04）：1956-1982.

〔8〕郝才研.基于张量分解和加权核范数的图像修复[D].山东大学硕士学位论文，2020.6.

〔9〕李璠，张绍泉，曹晶晶，梁炳堃，李军.高光谱数据截断加权核范数稀疏解混[J].遥感学报，2022，26（06）：1067-1082.

〔10〕张嘉旭，王骏等.基于低秩约束的熵加权多视角模糊聚类算法.自动化学报，2022，48（07）：1760-1770.

〔11〕Y. Hu， D. Zhang J. Ye， X. Li， X. He. Fast and accurate matrix completion via truncated nuclear norm regularization [J]. IEEE Trans. on Pattern Analysis and Machine Intelligence， 2013， 35（09）： 2117-2130.

〔12〕冯伟，谢冬秀.基于加权核范数的低秩矩阵近似及其应用[J].计算机应用，2020，40（S1）：128-131.

〔13〕Y. Shi， R. C. Eberhart. A modified particle swarm optimizer [C]. In proceedings of IEEE Congress on Evolutionary Computation. Piscataway， USA： IEEE， 1998： 69-73.

〔14〕白晓兰，周文全，张振朋，袁铮.基于启发式粒子群算法的机器人平滑路径规划[J].组合机床与自动化加工技术，2022，8（08）：44-52.

〔15〕陈震，王亚茹，陈璐，李晓克.基于学习因子优化的粒子群算法识别结构损伤[J].华北水利水电大学学报，2022，43（04）：43-47.

〔16〕潘红丽.基于改进粒子群算法的垃圾清运车辆低碳路径规划[D].南京信息工程大学硕士学位论文，2022.6.

〔17〕Z. Wen， W. Yin， Y. Zhang. Solving a low-rank factorization model for matrix completion by a nonlinear successive over relaxation [J]. Math. Prog. Comp. 2012， 4（04）： 333-361.