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

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

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

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

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

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

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

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

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

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

（1）

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

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

記

（2）

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

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

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

1）在外循環(huán)中，，k = 0，1，…，n，計(jì)算全梯度?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}，計(jì)算。

3）計(jì)算參考點(diǎn) 。

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

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

3" 算法1的收斂性分析

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

若，則：

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

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

若，則?k∈?，成立。

4" 實(shí)驗(yàn)與分析

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

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

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

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

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

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

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

4.3" 性能評(píng)價(jià)指標(biāo)

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

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

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

4.4" 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

5" 結(jié)" 論

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

參考文獻(xiàn)：

[1] 朱小輝，陶卿，邵言劍，等.一種減小方差求解非光滑問(wèn)題的隨機(jī)優(yōu)化算法 [J].軟件學(xué)報(bào)，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é)報(bào)，2017，28（6）：1547-1564.

[13] 王川龍，張璐璇.一種求解低秩矩陣補(bǔ)全的修正加速近端梯度算法 [J].忻州師范學(xué)院學(xué)報(bào)，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].長(zhǎng)春：吉林大學(xué)，2022.

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

收稿日期：2024-09-04

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