粒子群優化的加權核范數低秩矩陣補全算法

陳笑笑　任丹丹　劉清

摘 要：針對加權核范數最小化矩陣補全方法存在閾值決策函數單一、收斂精度不高等問題，提出一種粒子群優化的加權核范數最小化低秩矩陣補全算法。改進算法利用粒子群的啟發式智能搜索能力，為待恢復矩陣的奇異值自適應地匹配恰當的閾值，以提升算法的收斂性能。改進工作主要包括：（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.