粒子群優(yōu)化的加權(quán)核范數(shù)低秩矩陣補(bǔ)全算法

陳笑笑　任丹丹　劉清

摘 要：針對(duì)加權(quán)核范數(shù)最小化矩陣補(bǔ)全方法存在閾值決策函數(shù)單一、收斂精度不高等問題，提出一種粒子群優(yōu)化的加權(quán)核范數(shù)最小化低秩矩陣補(bǔ)全算法。改進(jìn)算法利用粒子群的啟發(fā)式智能搜索能力，為待恢復(fù)矩陣的奇異值自適應(yīng)地匹配恰當(dāng)?shù)拈撝?，以提升算法的收斂性能。改進(jìn)工作主要包括：（1）設(shè)計(jì)多種奇異值閾值決策函數(shù)，為矩陣提供多種閾值分配策略；（2）改進(jìn)粒子群的速度迭代公式，提出基于余弦函數(shù)的速度慣性調(diào)節(jié)公式以增強(qiáng)粒子群的全局搜索性能；（3）利用改進(jìn)的粒子群優(yōu)化算法為閾值決策函數(shù)搜索最優(yōu)的參數(shù)組合，然后再通過閾值決策函數(shù)生成奇異值的閾值，重構(gòu)恢復(fù)結(jié)果并提升算法的收斂精度。在人工數(shù)據(jù)和圖像數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果表明，與加權(quán)核范數(shù)最小化方法、奇異值閾值化方法以及低秩矩陣擬合方法相比，改進(jìn)方法具有收斂精度更高、恢復(fù)結(jié)果更清晰等優(yōu)勢(shì)。

關(guān)鍵詞：加權(quán)核范數(shù)；粒子群；低秩；矩陣補(bǔ)全

中圖分類號(hào)：O151；TP931? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：1673-260X（2023）05-0022-07

0 引言

低秩矩陣補(bǔ)全是恢復(fù)二維矩陣缺失信息的一種新興技術(shù)[1，2]。該技術(shù)利用缺失信息與觀測(cè)數(shù)據(jù)之間的相關(guān)性，通過優(yōu)化秩最小化模型獲得一個(gè)與原觀測(cè)矩陣近似的低秩矩陣，從而恢復(fù)矩陣中的缺失元素[3]。由于相關(guān)恢復(fù)算法的收斂精度較高，低秩矩陣現(xiàn)已成為機(jī)器學(xué)習(xí)領(lǐng)域的研究熱點(diǎn)之一[4，5]。

加權(quán)核范數(shù)最小化方法（Weighted Nuclear Norm Minimization，WNNM）是Shuhang Gu等人[6]于2017年提出的一種改進(jìn)版本的奇異值閾值化方法。該方法能夠根據(jù)閾值決策函數(shù)動(dòng)態(tài)調(diào)整矩陣奇異值的閾值：奇異值越大，獲得的閾值越小。這種策略能夠更好地保留矩陣中的有效信息并抑制矩陣中的噪聲信息[1]。與奇異值閾值化算法（SVT）[7]等基于核范數(shù)最小化的補(bǔ)全方法相比，WNNM算法具有更高的收斂精度。因此，該算法一經(jīng)提出就受到機(jī)器學(xué)習(xí)[8-10]等領(lǐng)域的廣泛關(guān)注。

然而，WNNM算法因閾值決策函數(shù)單一，導(dǎo)致該算法在不同數(shù)據(jù)矩陣上的恢復(fù)性能不穩(wěn)定的問題也越來越受到許多學(xué)者的重視。為了獲得收斂精度高的恢復(fù)結(jié)果，必須針對(duì)特定的測(cè)試數(shù)據(jù)合理設(shè)置相應(yīng)參數(shù)的取值。這樣，WNNM算法批量化處理大量矩陣數(shù)據(jù)的能力必然受到一定的限制：很難找到統(tǒng)一的參數(shù)設(shè)置使得WNNM算法在不同數(shù)據(jù)上都能獲得較好的收斂效果。

與WNNM類似，同時(shí)期的其他多種類型的加權(quán)核范數(shù)最小化方法則嘗試不同的加權(quán)方式來提升算法的恢復(fù)精度。2016年，胡堯[11]等人提出截?cái)嗪朔稊?shù)正則化低秩矩陣補(bǔ)全方法，強(qiáng)調(diào)矩陣的前幾個(gè)較大的奇異值主要用來恢復(fù)矩陣的有效信息，不對(duì)其進(jìn)行閾值化操作能夠盡可能多的保留矩陣的主體信息；因此，只對(duì)剩余的較小奇異值進(jìn)行優(yōu)化，在一定程度上提升了算法的收斂精度。2019年，Liu[3]等人提出一種泛化的加權(quán)核范數(shù)最小化方法，也即加權(quán)L2，1范數(shù)最小化的矩陣補(bǔ)全方法。該方法的最優(yōu)化模型在理論上能夠收斂到加權(quán)核范數(shù)最小化模型，具有與加權(quán)核范數(shù)最小化方法類似的收斂精度。2020年，馮偉[12]等人提出一種基于加速近似梯度的加權(quán)核范數(shù)最小化方法（APGL-WNNM）。該方法利用加速近似梯度搜索方法，優(yōu)化傳統(tǒng)的加權(quán)核范數(shù)最小化模型。由于APGL-WNNM算法是一種貪婪算法，其算法收斂速度比傳統(tǒng)WNNM算法有較大的提升。然而，APGL-WNNM算法與WNNM算法一樣，也存在頻繁調(diào)整關(guān)鍵參數(shù)的問題。

綜上所述，基于加權(quán)核范數(shù)最小化的低秩矩陣補(bǔ)全方法，比如WNNM以及截?cái)嗪朔稊?shù)正則化方法等，都具有較好的算法收斂精度。然而，這些算法都存在閾值決策函數(shù)較為單一、算法的數(shù)據(jù)依賴性較強(qiáng)等問題。因此，開發(fā)一種算法穩(wěn)定性強(qiáng)，參數(shù)自適應(yīng)調(diào)整的矩陣補(bǔ)全方法是十分有意義的。

為了進(jìn)一步提升WNNM算法的收斂精度，提出一種基于粒子群優(yōu)化的加權(quán)核范數(shù)最小化方法。粒子群優(yōu)化算法[13]主要模擬鳥類群體的覓食行為：算法保留粒子的全局學(xué)習(xí)能力以及個(gè)體的記憶能力。因此，粒子群優(yōu)化算法具有較強(qiáng)的全局收斂能力，并因此受到廣泛關(guān)注[14-16]。改進(jìn)方法主要利用粒子群的啟發(fā)式智能搜索能力，為閾值決策函數(shù)匹配最優(yōu)參數(shù)組合，然后為矩陣的每個(gè)奇異值自動(dòng)分配恰當(dāng)?shù)拈撝?。由于粒子群算法的全局搜索能力較強(qiáng)，改進(jìn)方法具有更高的收斂精度以及更好的穩(wěn)定性。

1 基礎(chǔ)知識(shí)介紹

1.1 相關(guān)定義及其說明

1.2 加權(quán)核范數(shù)最小化低秩矩陣補(bǔ)全方法（WNNM）

2 粒子群優(yōu)化的加權(quán)核范數(shù)低秩矩陣補(bǔ)全算法

針對(duì)WNNM算法存在的參數(shù)魯棒性較差，收斂精度不高等問題，提出一種基于粒子群優(yōu)化的加權(quán)核范數(shù)低秩矩陣補(bǔ)全算法（Particle Swarm Optimization based Weighted Nuclear Norm Minimization， PWNNM）。PWNNM算法的主要思想為：利用三個(gè)子群分別優(yōu)化三種閾值決策函數(shù)的關(guān)鍵參數(shù)，選擇最優(yōu)函數(shù)并讓其生成對(duì)應(yīng)于當(dāng)前恢復(fù)數(shù)據(jù)的最優(yōu)閾值，然后進(jìn)行奇異值的閾值化操作，最后重構(gòu)結(jié)果矩陣。

2.1 三種閾值決策函數(shù)

2.2 改進(jìn)的粒子群優(yōu)化算法

2.3 粒子群優(yōu)化的加權(quán)核范數(shù)最小化方法

3 實(shí)驗(yàn)結(jié)果

3.1 人造低秩矩陣

3.2 圖像矩陣

從圖4可以看出，（B1，B2）中LMaFit算法的恢復(fù)結(jié)果含有較為明顯的異常噪聲，說明LMaFit算法不能精確地恢復(fù)矩陣中的缺失信息。SVT算法的恢復(fù)結(jié)果（C1，C2）比LMaFit算法的結(jié)果更加清晰，但是仍然能夠觀察到一些不是特別明顯的微小噪聲干擾。WNNM算法的恢復(fù)圖像幾乎與原圖一致，噪聲信息很少且圖像細(xì)節(jié)較為清晰。PWNNM算法的恢復(fù)結(jié)果與WNNM算法的結(jié)果一樣，幾乎找不到明顯的噪聲信息。因此，各算法恢復(fù)結(jié)果的視覺效果與表5中的收斂精度是保持一致的。

4 結(jié)論

為了克服加權(quán)核范數(shù)最小化低秩矩陣補(bǔ)全方法WNNM存在的閾值決策函數(shù)單一，算法收斂精度不高等問題，提出了一種基于粒子群優(yōu)化的加權(quán)核范數(shù)最小化矩陣補(bǔ)全方法，簡(jiǎn)記為PWNNM。首先，提出三種凹凸性不同的閾值決策函數(shù)，作為生成奇異值閾值的備選函數(shù)；其次，提出一種余弦函數(shù)調(diào)節(jié)速度慣性因子的粒子群優(yōu)化算法；最后，使用改進(jìn)的粒子群優(yōu)化算法優(yōu)化三種閾值決策函數(shù)的參數(shù)，選出最優(yōu)決策函數(shù)并生成奇異值的最優(yōu)閾值。由于改進(jìn)的PWNNM算法能夠利用粒子群的全局搜索性能，在較為廣闊的參數(shù)空間內(nèi)為每個(gè)閾值決策函數(shù)匹配合適的參數(shù)組合，PWNNM算法在收斂精度、參數(shù)設(shè)置等方面都具有良好的性能。在人工數(shù)據(jù)以及圖像數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果表明，改進(jìn)的PWNNM算法比WNNM算法、SVT算法以及LMaFit算法具有更高的收斂精度。

參考文獻(xiàn)：

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

〔2〕劉清.基于加權(quán)殘差和矩陣分解的快速低秩矩陣補(bǔ)全方法[D].南京理工大學(xué)博士學(xué)位論文，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〕曾德宇，梁澤逍，吳宗澤.基于加權(quán)核范數(shù)和L2，1范數(shù)的最優(yōu)均值線性分類器[J].電子與信息學(xué)報(bào)，2022，44（05）：1602-1609.

〔5〕袁安富，施徐凱，邱勝峰.基于低秩矩陣的自適應(yīng)邊緣檢測(cè)算法[J].組合機(jī)床與自動(dòng)化加工技術(shù)，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〕郝才研.基于張量分解和加權(quán)核范數(shù)的圖像修復(fù)[D].山東大學(xué)碩士學(xué)位論文，2020.6.

〔9〕李璠，張紹泉，曹晶晶，梁炳堃，李軍.高光譜數(shù)據(jù)截?cái)嗉訖?quán)核范數(shù)稀疏解混[J].遙感學(xué)報(bào)，2022，26（06）：1067-1082.

〔10〕張嘉旭，王駿等.基于低秩約束的熵加權(quán)多視角模糊聚類算法.自動(dòng)化學(xué)報(bào)，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〕馮偉，謝冬秀.基于加權(quán)核范數(shù)的低秩矩陣近似及其應(yīng)用[J].計(jì)算機(jī)應(yīng)用，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〕白曉蘭，周文全，張振朋，袁錚.基于啟發(fā)式粒子群算法的機(jī)器人平滑路徑規(guī)劃[J].組合機(jī)床與自動(dòng)化加工技術(shù)，2022，8（08）：44-52.

〔15〕陳震，王亞茹，陳璐，李曉克.基于學(xué)習(xí)因子優(yōu)化的粒子群算法識(shí)別結(jié)構(gòu)損傷[J].華北水利水電大學(xué)學(xué)報(bào)，2022，43（04）：43-47.

〔16〕潘紅麗.基于改進(jìn)粒子群算法的垃圾清運(yùn)車輛低碳路徑規(guī)劃[D].南京信息工程大學(xué)碩士學(xué)位論文，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.