一種非凸隨機優化框架下的矩陣補全算法研究

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

關鍵詞：矩陣補全；非凸問題；隨機優化；方差減小

中圖分類號：TP301.6" 文獻標識碼：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" 引" 言

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

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

1" 矩陣補全模型

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

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

2" 矩陣補全的半正定規劃模型

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

（1）

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

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

記

（2）

算法1" 隨機方差縮減的矩陣補全（MC_SVR）算法[15-16]

輸入：外循環迭代次數n，內循環次數m，容許誤差tol以及初始值 ∈Rn×r

輸出：結束算法時內循環最后一次更新的V m

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

2）在內循環中，t = 0，1，…，m-1，Z t=V t（V t）T，V 0=k，隨機選取it∈{1，2，…，N}，計算。

3）計算參考點 。

4）如果，則轉到步驟5），否則k = k+1，返回步驟1）。

5）結束算法時內循環最后一次更新的V m。

3" 算法1的收斂性分析

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

若，則：

1）是單調遞減的。

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

若，則?k∈?，成立。

4" 實驗與分析

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

4.1" 人工數據集及參數初始設置

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

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

4.2" 真實數據集選取及參數初始設置

然后在公開MovieLens數據集上運行我們的實驗，我們將觀測到的部分數據用于訓練，其余用來測試，并且將實驗重復運行10次得到結果。

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

4.3" 性能評價指標

在實驗中，最終迭代結果的目標函數值越低，表明對原問題的求解效果越好。

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

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

4.4" 實驗結果分析

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

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

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

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

5" 結" 論

將矩陣補全的標準問題形式轉化為非凸優化問題，將隨機優化算法運用在對應的問題形式中，在不同的數據集上運行實驗，實驗結果表明小批量的方差縮減算法相比于其他算法在訓練集和測試集上具有更小的均方根誤差和更小的目標函數值，所以本文所提出的MC_SVR、MC_SVR minibatch算法具有更明顯的優勢。

參考文獻：

[1] 朱小輝，陶卿，邵言劍，等.一種減小方差求解非光滑問題的隨機優化算法 [J].軟件學報，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，FELIX 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] 陳蕾，陳松燦.矩陣補全模型及其算法研究綜述 [J].軟件學報，2017，28（6）：1547-1564.

[13] 王川龍，張璐璇.一種求解低秩矩陣補全的修正加速近端梯度算法 [J].忻州師范學院學報，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] 劉浩洋，戶將，李勇鋒，等.最優化：建模，算法與理論 [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] 吳浩萌.推薦系統中的深度矩陣分解方法研究及應用 [D].長春：吉林大學，2022.

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

收稿日期：2024-09-04

基金項目：云南省現代分析數學及其應用重點實驗室基金資助（202302AN360007）；國家自然科學基金項目（62266055）