一種非凸隨機(jī)優(yōu)化框架下的矩陣補(bǔ)全算法研究

摘" 要：矩陣補(bǔ)全問題可轉(zhuǎn)化為非凸優(yōu)化問題進(jìn)行求解，但在高維矩陣或海量數(shù)據(jù)場景下，傳統(tǒng)優(yōu)化方法易受“維數(shù)災(zāi)難”制約而難以有效實施。為提升求解效率，文章提出一種融合方差縮減技術(shù)的非凸隨機(jī)優(yōu)化算法MC_SVR。通過設(shè)計minibatch加速策略，該算法在保持計算精度的同時顯著提升了運算效率。多組數(shù)據(jù)集實驗表明，相較于傳統(tǒng)方法，MC_SVR算法在收斂速度、補(bǔ)全精度等關(guān)鍵指標(biāo)上均展現(xiàn)出顯著優(yōu)勢，尤其在處理大規(guī)模矩陣補(bǔ)全問題時，其平均相對誤差、迭代次數(shù)都有明顯的變化。該研究為高維矩陣補(bǔ)全問題提供了新的解決方案，對推薦系統(tǒng)、圖像修復(fù)等實際應(yīng)用具有重要參考價值。

關(guān)鍵詞：矩陣補(bǔ)全；非凸問題；隨機(jī)優(yōu)化；方差減小

中圖分類號：TP301.6" 文獻(xiàn)標(biāo)識碼：A" 文章編號：2096-4706（2025）04-0103-05

Research on a Matrix Completion Algorithm under the Non-convex Stochastic Optimization Framework

WANG Xuewei1，2

（1.School of Mathematics， Yunnan Normal University， Kunming" 650500， China;

2.Yunnan Key Laboratory of Modern Analytical Mathematics and Applications， Kunming" 650500， China）

Abstract： The matrix completion problem can be solved by transforming into a non-convex optimization problem. However， in high-dimensional matrix or massive data scenarios， traditional optimization methods are easily constrained by “dimension disaster” and they are difficult to implement effectively. In order to improve the efficiency of the solution， this paper proposes a non-convex stochastic optimization algorithm MC_SVR that integrates Variance Reduction technique. By designing the minibatch acceleration strategy， the algorithm significantly improves the computational efficiency while maintaining the computational accuracy. Experiments on multiple sets of datasets show that compared with the traditional method， the MC_SVR algorithm shows significant advantages in key indicators such as convergence speed and completion accuracy. Especially when dealing with large-scale matrix completion problems， the Mean Relative Error and the number of iterations have obvious changes. This study provides a new solution to the problem of high-dimensional matrix completion， and has important reference value for practical applications such as recommendation systems and image inpainting.

Keywords： matrix completion; non-convex problem; random optimization; Variance Reduction

0" 引" 言

隨著計算機(jī)技術(shù)的發(fā)展和大數(shù)據(jù)時代的到來，大規(guī)模優(yōu)化問題日益增多，傳統(tǒng)的優(yōu)化理論和算法每次迭代都要遍歷所有樣本，難以滿足快速求解的需求[1]這促進(jìn)了隨機(jī)優(yōu)化算法的發(fā)展。在機(jī)器學(xué)習(xí)領(lǐng)域，隨機(jī)優(yōu)化算法在處理大規(guī)模數(shù)據(jù)集時顯示出其獨特的優(yōu)勢。比如低秩矩陣恢復(fù)、線性回歸和稀疏字典學(xué)習(xí)等，但是這些問題可能不是凸的，而非凸問題可能包含多個局部最小值，導(dǎo)致非凸優(yōu)化問題很難找出全局最優(yōu)解。這一特性使得非凸優(yōu)化問題比凸優(yōu)化問題更加復(fù)雜和困難。所以在實際的非凸優(yōu)化應(yīng)用中，由于計算資源和時間的限制，通常只能找到一個近似的最優(yōu)解。

矩陣補(bǔ)全（matrix completion）的理論基礎(chǔ)主要來源于壓縮感知理論的發(fā)展，由Donoho[2]提出的壓縮感知技術(shù)是信號處理領(lǐng)域的研究熱點，其核心思想是基于信號稀疏性，通過低分辨率、欠Nyquist采樣數(shù)據(jù)的非相關(guān)觀測來實現(xiàn)高維信號的感知。如果將矩陣的低秩性視為矩陣稀疏性，那么向量空間的壓縮感知理論就自然拓展為矩陣空間的矩陣補(bǔ)全理論。現(xiàn)如今，隨著大規(guī)模的數(shù)據(jù)越來越多，研究者們熱衷于對這些大規(guī)模數(shù)據(jù)進(jìn)行處理，在一些特定應(yīng)用的領(lǐng)域，矩陣補(bǔ)全技術(shù)也受到了越來越多關(guān)注，例如在一些特定應(yīng)用的領(lǐng)域，如矩陣補(bǔ)全理論已在壓縮感知[3]、計算機(jī)視覺[4]、機(jī)器學(xué)習(xí)[5]、工程控制[6]、子空間聚類[7]等領(lǐng)域均得到了重要應(yīng)用。為了提高推薦系統(tǒng)的準(zhǔn)確性和效率，在矩陣補(bǔ)全技術(shù)受到了越來越多關(guān)注的同時，也催生了許多關(guān)于低秩矩陣補(bǔ)全的經(jīng)典算法，如SVT[8]，近鄰梯度下降算法[9]（PFBS），加速近鄰梯度算法[10]（Accelerated Proximal Gradient， APG）等。本文使用隨機(jī)梯度下降算法和帶方差縮減技術(shù)的隨機(jī)梯度下降算法以及對應(yīng)的小批量算法在人造數(shù)據(jù)集和真實數(shù)據(jù)集上進(jìn)行求解并對其效果進(jìn)行對比。實驗結(jié)果表明本文提出的算法在矩陣補(bǔ)全問題中，可以適用于大規(guī)模問題求解，可以緩解大規(guī)模問題求解上的受限，并且補(bǔ)全性能更好。

1" 矩陣補(bǔ)全模型

假設(shè)待恢復(fù)的矩陣是低秩矩陣，并且對于這個矩陣假設(shè)我們采樣到它的其中一部分元素，其他一部分或者大部分元素由于各種原因丟失了或無法得到。從觀測到的不完整矩陣最后恢復(fù)出原本的低秩矩陣，標(biāo)準(zhǔn)矩陣補(bǔ)全問題可建模為如下形式的秩最小化約束優(yōu)化模型[11]：

其中Ω為觀測到的集合，也就說X中的元素值與觀測到的元素值相同。由于秩函數(shù)的非凸性和非光滑性，這個問題的求解是一個NP難問題在所有已知的求解算法中，其求解復(fù)雜度均隨著矩陣維數(shù)的增加呈平方倍指數(shù)增長[12]。所以我們將上述問題的目標(biāo)函數(shù)用核范數(shù)來代替，那么上述的這個問題就轉(zhuǎn)化為了如下的凸問題：

2" 矩陣補(bǔ)全的半正定規(guī)劃模型

基于上述模型，已經(jīng)有一些理論結(jié)果很好的算法被提出。但是在實際操作中，面對大規(guī)模數(shù)據(jù)，這些算法效率仍然不是很高[13]。另一方面上述模型的求解涉及復(fù)雜的奇異值分解，求解效率和可擴(kuò)放性受限，不適合用于大規(guī)模問題且核范數(shù)不能緊致地逼近目標(biāo)矩陣的真實秩[12]，所以研究者將問題重寫為SDP[14]。

（1）

其中，，V和W為對稱矩陣，N為觀測值的個數(shù)。

將Z分解為Z=VVT（V∈Rn×r），模型轉(zhuǎn)化為如下無約束非凸問題：

記

（2）

算法1" 隨機(jī)方差縮減的矩陣補(bǔ)全（MC_SVR）算法[15-16]

輸入：外循環(huán)迭代次數(shù)n，內(nèi)循環(huán)次數(shù)m，容許誤差tol以及初始值 ∈Rn×r

輸出：結(jié)束算法時內(nèi)循環(huán)最后一次更新的V m

1）在外循環(huán)中，，k = 0，1，…，n，計算全梯度?g（k）。

2）在內(nèi)循環(huán)中，t = 0，1，…，m-1，Z t=V t（V t）T，V 0=k，隨機(jī)選取it∈{1，2，…，N}，計算。

3）計算參考點 。

4）如果，則轉(zhuǎn)到步驟5），否則k = k+1，返回步驟1）。

5）結(jié)束算法時內(nèi)循環(huán)最后一次更新的V m。

3" 算法1的收斂性分析

定理（算法1的線性收斂）：設(shè)為算法1生成的序列，假設(shè)1-3均成立且ηk∈（0，ηmax），則以下兩點成立：

若，則：

1）是單調(diào)遞減的。

2）（線性收斂）對于?k≥1，有以下不等式成立：

若，則?k∈?，成立。

4" 實驗與分析

在本節(jié)中，我們將比較隨機(jī)梯度下降算法和帶方差縮減技術(shù)的隨機(jī)梯度下降算法以及對應(yīng)的小批量算法，所有實驗均在MATLAB中運行。

4.1" 人工數(shù)據(jù)集及參數(shù)初始設(shè)置

我們首先對人工數(shù)據(jù)進(jìn)行實驗，我們從矩陣中隨機(jī)抽取7%的元素作為觀察到的結(jié)果，得到的顯式評分矩陣的稀疏度為7%。其中部分用于訓(xùn)練，其余未觀察到的元素將用于測試，實驗重復(fù)運行10次以獲得結(jié)果。在不同的算法中，統(tǒng)一參數(shù)設(shè)置如下：最大迭代次數(shù)為950，容許誤差為10-8。對于SGD minibatch和MC_SVR minibatch兩個算法設(shè)置的小批量值為7。

這些人工數(shù)據(jù)由MATLAB生成。矩陣中觀測到的元素是從{1，2，3，4，5}中隨機(jī)采樣，用于模擬用戶打分，未觀測到的元素由0填充。

4.2" 真實數(shù)據(jù)集選取及參數(shù)初始設(shè)置

然后在公開MovieLens數(shù)據(jù)集上運行我們的實驗，我們將觀測到的部分?jǐn)?shù)據(jù)用于訓(xùn)練，其余用來測試，并且將實驗重復(fù)運行10次得到結(jié)果。

我們選擇的真實數(shù)據(jù)集通常被用在推薦系統(tǒng)中[17]，這兩個數(shù)據(jù)集來自（https：//grouplens.org/data sets/movielens/）。將MovieLens上的兩個不同大小的數(shù)據(jù)集的信息整理如表1所示。

4.3" 性能評價指標(biāo)

在實驗中，最終迭代結(jié)果的目標(biāo)函數(shù)值越低，表明對原問題的求解效果越好。

均方根誤差（Root Mean Square Error， RMSE）是一種常用的衡量預(yù)測模型在連續(xù)性數(shù)據(jù)上的預(yù)測精度的指標(biāo)。它通過計算預(yù)測值與真實值之間的差異的平方和，然后取平均值的平方根來得出，均方根誤差的定義如：

其中，yi為第i個觀測點的預(yù)測值，bi為第i個觀測點的真實值，N為觀測點的數(shù)量。RMSE的值越小，表示模型的預(yù)測越準(zhǔn)確，效果越好。

4.4" 實驗結(jié)果分析

在三個不同大小的人工數(shù)據(jù)集上運行隨機(jī)梯度下降算法（SGD）、方差縮減算法（MC_SVR）以及對應(yīng)的小批量算法，由圖1可得，方差縮減算法迭代次數(shù)更少達(dá)到跳出準(zhǔn)則，并且小批量的方差縮減算法（MC_SVR minbatch）能在更少的迭代次數(shù)下，目標(biāo)函數(shù)值下降到最低，并且RMSE最小，如表2所示。

在兩個不同大小的真實數(shù)據(jù)集上運行隨機(jī)算法，由圖2可得，方差縮減算法迭代次數(shù)更少達(dá)到跳出準(zhǔn)則，并且小批量的方差縮減算法（MC_SVR minbatch）能在更少的迭代次數(shù)下，目標(biāo)函數(shù)值下降到最低，并且RMSE最小。

從表2可以看出，兩種帶有方差縮減的隨機(jī)算法的測試均方根誤差比SGD和SGD minbatch SGD這兩種算法的更小，其中帶有小批量MC_SVR算法又更優(yōu)于SVRG算法。

同樣的，從表3可以看出，兩種帶有方差縮減的隨機(jī)算法的測試均方根誤差比SGD和SGD minbatch這兩種算法的更小，其中帶有小批量MC_SVR算法又更優(yōu)于SVRG算法。

5" 結(jié)" 論

將矩陣補(bǔ)全的標(biāo)準(zhǔn)問題形式轉(zhuǎn)化為非凸優(yōu)化問題，將隨機(jī)優(yōu)化算法運用在對應(yīng)的問題形式中，在不同的數(shù)據(jù)集上運行實驗，實驗結(jié)果表明小批量的方差縮減算法相比于其他算法在訓(xùn)練集和測試集上具有更小的均方根誤差和更小的目標(biāo)函數(shù)值，所以本文所提出的MC_SVR、MC_SVR minibatch算法具有更明顯的優(yōu)勢。

參考文獻(xiàn)：

[1] 朱小輝，陶卿，邵言劍，等.一種減小方差求解非光滑問題的隨機(jī)優(yōu)化算法 [J].軟件學(xué)報，2015，26（11）：2752-2761.

[2] DONOHO D L. Compressed Sensing [J].IEEE Transactions Information Theory，2006，52（4）：1289-1306.

[3] LUO Z P，MA J S，SU P，et al. Digital Holographic Phase Imaging Based on Phase Iteratively Enhanced Compressive Sensing [J].Optics letters，2019，44（6）：1395-1398.

[4] NEUS G，F(xiàn)ELIX P，TOBIAS G，et al. Combining Dielectrophoresis and Computer Vision for Precise and Fully Automated Single-Cell Handling and Analysis [J].Lab on a chip，2019，19（24）：4016-4020.

[5] WOLFF P，RíOS S A，GONZáLES C. Machine Learning Methods for Predicting Adverse Drug Reactions in Hospitalized Patients [J].Procedia Computer Science，2023，225：22-31.

[6] LEI Z C，ZHOU H，HU W S. Combining MOOL with MOOC to Promote Control Engineering Education： Experience with NCSLab [J].IFAC PapersOnLine，2019，52（9）：236-241.

[7] PENG X，TANG H J，ZHANG L，et al. A Unified Framework for Representation-Based Subspace Clustering of Out-of-Sample and Large-Scale Data [J].IEEE transactions on neural networks and learning systems，2016，27（12）：2499-2512.

[8] CAI J F，CANDèS E J，SHEN Z W. A Singular Value Thresholding Algorithm for Matrix Completion [J].SIAM Journal on Optimization，2010，20（4）：1956-1982.

[9] COMBETTES L P，WAJS R V. Signal Recovery by Proximal Forward-Backward Splitting [J].Multiscale Modeling amp; Simulation，2006，4（4）：1168-1200.

[10] BECK A，TEBOULLE M. A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems [J].SIAM Journal on Imaging Sciences，2009，2（1）：183-202.

[11] CANDèS J E，RECHT B. Exact Matrix Completion Via Convex Optimization [J].Foundations of Computational Mathematics，2009，9（6）：717-772.

[12] 陳蕾，陳松燦.矩陣補(bǔ)全模型及其算法研究綜述 [J].軟件學(xué)報，2017，28（6）：1547-1564.

[13] 王川龍，張璐璇.一種求解低秩矩陣補(bǔ)全的修正加速近端梯度算法 [J].忻州師范學(xué)院學(xué)報，2024，40（2）：1-4.

[14] HU E L，KWOK J T. Low-rank Matrix Learning Using Biconvex Surrogate Minimization [J].IEEE Transactions on Neural Networks and Learning Systems，2019，30（11）：3517-3527.

[15] 劉浩洋，戶將，李勇鋒，等.最優(yōu)化：建模，算法與理論 [M].北京：高等教育出版社，2020.

[16] ZENG J S，MA K，YAO Y. Finding Global Optima in Nonconvex Stochastic Semidefinite Optimization with Variance Reduction [J/OL].arXiv：1802.06232 [math.OC].[2024-08-16].https：//arxiv.org/abs/1802.06232.

[17] 吳浩萌.推薦系統(tǒng)中的深度矩陣分解方法研究及應(yīng)用 [D].長春：吉林大學(xué)，2022.

作者簡介：王學(xué)偉（2000—），男，漢族，四川南充人，碩士在讀，研究方向：機(jī)器學(xué)習(xí)方面的研究。

收稿日期：2024-09-04

基金項目：云南省現(xiàn)代分析數(shù)學(xué)及其應(yīng)用重點實驗室基金資助（202302AN360007）；國家自然科學(xué)基金項目（62266055）