余宏偉 蔣軼

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

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

中圖分類號： TN92

文獻標志碼： A

文章編號：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?引言

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

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

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

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

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

1.1?問題描述

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

1.2?經(jīng)典算法

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

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

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

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

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

2?最小二乘法矩陣恢復

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

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

本節(jié)將通過仿真驗證上述算法的恢復性能。

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

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

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

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

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

4?總結

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

參考文獻

[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）