低秩半正定矩陣最小二乘恢復(fù)算法

余宏偉 蔣軼

摘 要： 多年來(lái)矩陣恢復(fù)一直是學(xué)術(shù)界的一個(gè)熱門研究課題，它被廣泛應(yīng)用于多個(gè)技術(shù)領(lǐng)域，如計(jì)算機(jī)視覺、圖像恢復(fù)以及推薦系統(tǒng)等。考慮其中一種特殊且十分重要的矩陣恢復(fù)，即半正定矩陣恢復(fù)。通過(guò)將此類矩陣恢復(fù)問(wèn)題與基于測(cè)距的網(wǎng)絡(luò)定位問(wèn)題類比，構(gòu)造了基于最小二乘的優(yōu)化模型，運(yùn)用順序凸規(guī)劃（sequential convex programming/SCP）算法，可以高效并精確地求解此問(wèn)題，從而將缺失矩陣較為精準(zhǔn)地還原為全矩陣。仿真結(jié)果證明相比于目前文獻(xiàn)中已有矩陣恢復(fù)算法，提出的算法具有更好的恢復(fù)性能。

關(guān)鍵詞： 低秩矩陣;半正定矩陣;核范數(shù)最小化;最小二乘法;順序凸規(guī)劃

中圖分類號(hào)： TN92

文獻(xiàn)標(biāo)志碼： A

文章編號(hào)：1007-757X（2019）06-0001-03

Abstract： Matrix completion has been an active topic for more than a decade in academic research due to its widely applications in many fields， such as computer vision， image recovery and recommendation system. In this paper， we study a special and important case， low-rank positive semi-definite （PSD） matrix completion. By linking the matrix completion problem to a network localization problem， we propose an optimization model based on the least square criterion. Using the sequential solution programming （SCP） algorithm， we can efficiently reconstruct the PSD matrix with high precision. Simulation results show that the proposed method has more superior performance than the state-of-art algorithms.

Key words： Low-rank matrix; PSD matrix; Nuclear norm minimization; Least square; Sequential solution programming

0?引言

矩陣恢復(fù)技術(shù)要求能夠從部分甚至是受到噪聲污染的矩陣元素觀測(cè)中精確地還原整個(gè)矩陣。在具有里程碑意義的論文[1]中，Candes等人證明，如果某矩陣是一個(gè)低秩矩陣，且其中被觀測(cè)到的元素集合滿足一定的條件，那么通過(guò)一個(gè)簡(jiǎn)單的凸規(guī)劃，就可以以較高的概率將其恢復(fù)。矩陣恢復(fù)的應(yīng)用范圍非常廣泛，如計(jì)算機(jī)視覺、圖像恢復(fù)、定位[2]、推薦系統(tǒng)（Netflix）等等。

Candes等人提出通過(guò)最小化核范數(shù)的方法來(lái)恢復(fù)整個(gè)矩陣[1、3]。特別地，在滿足一定非相干條件的情況下，最小化核范數(shù)法可以逼近最優(yōu)解[4]。[1]中應(yīng)用半正定規(guī)劃解算器SDPT3求解核范數(shù)最小化問(wèn)題，該計(jì)算正如SeDuMi一樣都是基于內(nèi)點(diǎn)法，當(dāng)矩陣規(guī)模很大時(shí)需要求解一個(gè)巨大的線性方程組計(jì)算牛頓方向，一般來(lái)說(shuō)當(dāng)矩陣維度大于100時(shí)，SDPT就無(wú)能為力了[5]。后來(lái)的很多學(xué)者針對(duì)此優(yōu)化問(wèn)題的求解進(jìn)行了大量的工作。如[5]中提出了Singular Value Thresholding（SVT）算法，該算法在迭代求解過(guò)程中產(chǎn)生一組矩陣序列{Xk，Yk}，每一步迭代只需Yk對(duì)進(jìn)行SVD分解并對(duì)奇異值作閾值化操作，最終{Xk}會(huì)收斂逼近核范數(shù)最小化問(wèn)題的解。針對(duì)存在觀測(cè)噪聲情形下的半正定矩陣恢復(fù)，論文[6]提出了一種基于Alternating Direction Method of Multipliers （ADMM）的算法，引入了一個(gè)與待恢復(fù)矩陣X相等的矩陣變量Y，每次迭代更新X，Y，更新值都存在閉式表達(dá)，求解過(guò)程簡(jiǎn)潔高效。類似的工作還有很多[7、8、9]，但研究重點(diǎn)大都是集中在如何更高效的求解Candes所提出的核范數(shù)最小化模型，鮮有矩陣恢復(fù)性能上的提升。

本文研究一種極為特殊和重要的矩陣，即半正定矩陣的恢復(fù)問(wèn)題。我們將此類矩陣恢復(fù)問(wèn)題與基于測(cè)距的網(wǎng)絡(luò)定位問(wèn)題[10]類比。從網(wǎng)絡(luò)定位的視角出發(fā)，本文構(gòu)造了基于最小二乘的半正定矩陣恢復(fù)優(yōu)化模型，憑借我們提出的SCP算法，該優(yōu)化問(wèn)題可以被高效精確求解，從而高精度恢復(fù)整個(gè)半正定矩陣。

本文符號(hào)表示說(shuō)明如下。粗體小寫和大寫字母分別表示向量和矩陣。A，A分別表示矩陣A的Frobenius范數(shù)和核范數(shù)。A⊙B表示矩陣A、B的哈達(dá)瑪積，即對(duì)應(yīng)元素相乘。vec（X）表示對(duì)矩陣X按列向量化。

1?問(wèn)題描述與經(jīng)典算法

1.1?問(wèn)題描述

矩陣恢復(fù)問(wèn)題是將整個(gè)矩陣從它的部分觀測(cè)元素集恢復(fù)出來(lái)。定義A∈Rm×n為待恢復(fù)的矩陣。Ω[m]×[n]代表觀測(cè)到的矩陣A的元素集合，其中[m]表示集合{1，2，…，m}. W∈Rm×n表示掩模矩陣如式（1）。

1.2?經(jīng)典算法

矩陣恢復(fù)的一種經(jīng)典思路就是從最小化矩陣的秩角度考慮，此時(shí)如果并不考慮噪聲，那么就形成了以下優(yōu)化問(wèn)題，如式（2）。

眾所周知，上式優(yōu)化問(wèn)題是一個(gè)NP-hard問(wèn)題。為了求解此問(wèn)題，Candes將其放松成一個(gè)最小化矩陣核范數(shù)的凸優(yōu)化問(wèn)題[1]，如式（3）。

此優(yōu)化模型較為容易求解，且能夠較為精確的從部分無(wú)噪聲觀測(cè)集中恢復(fù)出整個(gè)矩陣A。而且，此模型也可以實(shí)現(xiàn)噪聲環(huán)境下的矩陣恢復(fù)，只需稍作改動(dòng)[1][2]，如式（4）。

如果待恢復(fù)矩陣是半正定矩陣，只需要增加一項(xiàng)半正定約束：A≥0，而A*=trace（A）。有很多學(xué)者在此基礎(chǔ)上進(jìn)行了大量的工作，但著力點(diǎn)大都只在于如何更高效地求解式（3）中的優(yōu)化問(wèn)題，而鮮有恢復(fù)性能上的提升。

本文研究一種在通信等應(yīng)用中極為重要的矩陣，即半正定矩陣的恢復(fù)問(wèn)題。接下來(lái)我們將展示我們的方法較經(jīng)典核范數(shù)方法在恢復(fù)性能方面有明顯的突破。

2?最小二乘法矩陣恢復(fù)

如何求解式（5）也是一個(gè)具有挑戰(zhàn)性的問(wèn)題。我們?cè)谡撐腫10]中提出了運(yùn)用順序凸規(guī)劃（SCP）算法求解網(wǎng)絡(luò)定位問(wèn)題。優(yōu)化問(wèn)題[4]實(shí)際就是一個(gè)類似的定位問(wèn)題，同樣可以用SCP算法求解。該算法需要一組初始值啟動(dòng)牛頓迭代。此處我們直接利用核范數(shù)最小化算法的結(jié)果構(gòu)造初始值，在此基礎(chǔ)上，可以顯著提高矩陣恢復(fù)性能。具體構(gòu)造方法如下。

將式（6）和（7）帶入SCP算法，式（5）可以被精確且高效求解。進(jìn)而可以重構(gòu)待恢復(fù)的半正定矩陣。為了表述清晰和完整性，我們將整個(gè)矩陣恢復(fù)算法的具體步驟總結(jié)在算法1中。值得注意的是，由于（5）不是一個(gè)關(guān)于X的凸函數(shù)，2f可能存在負(fù)特征值。因此，我們將海森矩陣的逆（2f）-1用（2f）-代替，即將前者中的負(fù)數(shù)特征值用0替換而得到的新矩陣。這是SCP算法的核心技巧。

本節(jié)將通過(guò)仿真驗(yàn)證上述算法的恢復(fù)性能。

此處，A∈R20，rank（A）=4。這些虛擬的節(jié)點(diǎn)坐落在20×20×20×20的空間中。觀測(cè)噪聲服從高斯分布N（0，1）。本仿真比較在刪除不同對(duì)數(shù)矩陣元素的情形下，矩陣恢復(fù)的性能。注意元素刪除都是成對(duì)刪除的，即如果Aij缺失，那么Aji也一定缺失。對(duì)于每一種情形，我們都進(jìn)行了500次蒙特卡羅仿真，每次從N+（N-1）+…+1=210對(duì)元素隨機(jī)選取指定對(duì)數(shù)的矩陣元素刪除。參考論文[2]中的做法，我們也定義矩陣恢復(fù)誤差為A^-AFAF，并且如果該誤差小于1%就認(rèn)為這是一次成功的矩陣恢復(fù)。

比較了無(wú)觀測(cè)噪聲和有觀測(cè)噪聲情況下的半正定矩陣恢復(fù)成功率高低，如圖1和圖2所示。

在有觀測(cè)噪聲情況下，直到60對(duì)（約29%）元素刪除，兩種方法都能完全恢復(fù)出原矩陣。當(dāng)80對(duì)（約38%）元素刪除時(shí)，本文提出的最小二乘算法仍能幾乎100%恢復(fù)，而核范數(shù)最小化算法已經(jīng)出現(xiàn)了明顯的失敗率，等到刪除100對(duì)（約48%）時(shí)，該方法成功率只剩約60%，已經(jīng)不太可靠了。而我們的方法依然保持約95%以上成功率，即使是刪除120對(duì)（約57%）仍然有約60%成功率，此時(shí)，核范數(shù)最小化算法已經(jīng)完全失效了。從圖1中可以看出，在無(wú)噪聲情況下，兩種方法恢復(fù)性能較有噪聲情形性能都有所提升，且最小二乘法依然明顯優(yōu)于核范數(shù)最小化算法。本文的方法在刪除140對(duì)元素時(shí)也無(wú)法實(shí)現(xiàn)矩陣恢復(fù)，原因如下：半正定矩陣A的自由度是N+（N-1）+…+（N-r+1）=74，要想恢復(fù)A，它的210對(duì)矩陣元素至多能刪除210-74=136對(duì)元素。

比較了在無(wú)噪聲和有噪聲情形下半正定矩陣恢復(fù)的平均誤差，如圖3和圖4所示。

從圖中可以看出，隨著刪除的矩陣元素對(duì)數(shù)增加，矩陣恢復(fù)性能逐漸下降，但是可以看出無(wú)論有無(wú)噪聲，最小二乘法的平均恢復(fù)誤差始終顯著低于核范數(shù)最小化算法的平均誤差。

4?總結(jié)

本文主要研究低秩半正定矩陣恢復(fù)問(wèn)題，我們從 “測(cè)距”網(wǎng)絡(luò)定位的視角出發(fā)，構(gòu)造出基于最小二乘的優(yōu)化模型，然后應(yīng)用順序凸規(guī)劃（SCP）算法，可以精確求解并重構(gòu)待恢復(fù)矩陣。仿真試驗(yàn)表明，該方法無(wú)論是在無(wú)觀測(cè)噪聲還是存在觀測(cè)噪聲情形下都能較為精確的恢復(fù)目標(biāo)矩陣，在核范數(shù)最小化算法的基礎(chǔ)上獲得性能的顯著提升。

參考文獻(xiàn)

[1]?Candes Emmanuel J， Recht Benjamin. Exact matrix completion via convex optimization[J]. Foundations of Computational mathematics， 2009（6）： 717-773.

[2]?Dokmanic Ivan， Parhizkar Reza， Ranieri Juri， et al. Euclidean distance matrices： essential theory， algorithms， and applications[J]. IEEE Signal Processing Magazine， 2015，32（6）： 12-30.

[3]?Candes Emmanuel J， Plan Yaniv. Matrix completion with noise[J]. Proceedings of the IEEE， 2010，98（6）： 925-936.

[4]?Candes Emmanuel J， Tao Terence. The power of convex relaxation： Near-optimal matrix completion[J]. IEEE Transactions on Information Theory， 2010， 56（5）：2053-2080.

[5]?Cai Jian-Feng， Candes Emmanuel J， Shen Zuowei. A singular value thresholding algorithm for matrix completion[J]. SIAM Journal on Optimization， 2010， 20（ 4）： 1956-1982.

[6]?Xu， Fangfang and Pan， Peng， "A New Algorithm for Positive Semidefinite Matrix Completion，" Journal of Applied Mathematics， vol. 3， pp. 1-5， 2016.

[7]?Ma S， Goldfarb D， Chen L. Fixed point and Bregman iterative methods for matrix rank minimization[J]. Mathematical Programming， 2011， 128（1-2）： 321-353.

[8]?Fornasier Massimo， Rauhut Holger， Ward Rachel. Low-rank matrix recovery via iteratively reweighted least squares minimization[J]. SIAM Journal on Optimization， 2011， 21（4）： 1614-1640.

[9]?Chen Caihua， He Bingsheng， Yuan Xiaoming. Matrix completion via an alternating direction method[J]. IMA Journal of Numerical Analysis， 2012， 3（1）：227-245.

[10]?Yu， Hongwei and Jiang， Yi， "Maximum likelihood network localization using range estimation and GPS measurements，" 2017 9th International Conference on Wireless Communications and Signal Processing （WCSP）， Nanjing， 2017. Oct， pp. 1-6.

（收稿日期： 2018.12.27）