矩陣填充理論及其研究進展

王會敏

(紹興文理學院 數(shù)學系,浙江 紹興312000)

矩陣填充問題是新近出現(xiàn)的一個研究方向，主要討論如何從已知的部分元素恢復該矩陣.著名的Netflix問題是矩陣填充的一個典型例子.Netflix公司是一個提供影碟租賃的公司，該公司讓用戶在觀看影碟后對電影打分，然后Netflix公司根據(jù)用戶的打分推測用戶的喜好，給用戶推薦影碟.如果將用戶看成一個矩陣的行，電影看成矩陣的列，用戶對電影的打分是矩陣的元素，由于一個用戶看過的電影是有限的，因此矩陣中僅有少量元素是已知的.要預測用戶的喜好，就是要通過這些已知的矩陣元素，推測空白的矩陣元素,這是一個矩陣填充問題.由于影響用戶喜好的因素往往只有少數(shù)幾個，因此這是一個低秩矩陣.Netfilx公司舉辦了一個比賽，參賽隊伍根據(jù)Netflix公司提供的用戶打分數(shù)據(jù)對用戶喜好進行預測，設計新的預測方法，并與Netflix公司的預測軟件結果進行比較，能將預測準確度提高10%的隊伍將獲得100萬美元大獎.矩陣填充在量子理論、人臉識別、在線推薦系統(tǒng)等很多實際問題中都有非常重要的應用.

如果沒有任何限制條件，矩陣填充問題的解是無窮多的，是不可解的,但是在實際問題中，很多時候我們遇到的矩陣都是低秩矩陣或者漸進低秩矩陣.對于低秩矩陣，研究表明,可以通過合適的方法準確恢復出原來的矩陣.

1 數(shù)學模型

為了簡便起見，設M∈n×n是要恢復的矩陣.rank(M)=r，r?n.{Mij,(i,j)∈Ω}是M中已知的矩陣元素的集合.盡管M中有n2個元素，但是M的自由度僅為2nr-2r2.當r比較小時，2nr-2r2?n2.那么，是否有可能在已知矩陣部分元素的情形下，恢復全部的n2個元素呢？一般來講，不是所有的矩陣都可以從部分元素準確恢復其全部元素,比如下面的矩陣：

這個矩陣在右上角有一個元素1，而其余元素都為0.顯然，除非正好采樣包含元素1，否則，沒有辦法從全為0的采樣元素中猜出這是一個非零矩陣.

盡管不可能從部分已知元素中恢復所有的低秩矩陣，但是可以期望恢復其中的絕大多數(shù)矩陣.要恢復一個低秩矩陣，可以先將其轉化為求解下面的矩陣秩最小化問題：

(1)

這里rank(X)是矩陣X的秩.設PΩ是一個投影映射，

則式(1)可以記為

由于矩陣的秩是一個非凸函數(shù)，一般來講，矩陣秩最小化問題是一個NP難問題，求解所需時間隨著矩陣規(guī)模的增加成指數(shù)增長.因此對于大規(guī)模的矩陣，秩最小化方法幾乎是不可解的.受到壓縮感知理論的啟發(fā)，F(xiàn)azel在文獻[1]中提出了核范數(shù)最小化方法恢復低秩矩陣，并且引入了矩陣限制等距性質，對核范數(shù)最小化算法的表現(xiàn)進行了分析.Candes和Recht等在文獻[2]中將核范數(shù)最小化算法應用于矩陣填充問題.令‖X‖*表示矩陣的核范數(shù)，等于矩陣的奇異值之和.核范數(shù)最小化問題用于求解如下優(yōu)化問題：

(2)

注意到‖X‖*是凸函數(shù)，因此這是一個凸優(yōu)化問題，有現(xiàn)成的多項式時間算法可以求解.

2 研究進展

一個重要的理論問題是式(2)的解是不是所要求的最低秩解？由于矩陣填充問題不滿足限制等距性質，因此需要提出新的方法來討論這個問題.Candes和Recht在文獻[2]中進行了一些理論分析，首先提出了一個相干性條件來保證要恢復的低秩矩陣不過分稀疏,并假定已知元素的位置是隨機獲取的，同時討論了幾個不同的隨機模型,指出如果已知元素個數(shù)p≥Cn1.2rlogn,則以接近1的概率,通過求解式(2)可以恢復絕大多數(shù)秩不超過r的矩陣，這里C是一個僅與矩陣維數(shù)有關的常數(shù)，n=min{n1,n2}，r=rank(M).由于秩為r的矩陣的自由度是2nr-2r2，因此，文獻[3]中的結果并不是最優(yōu)的.隨后，Candes和Tao在文獻[4]中將這個結果改進為p≥Cnrlogn，但是證明非常復雜.Gross在文獻[3]中推廣了標準的矩陣填充問題，討論了已知一個低秩矩陣在任意一組標準正交基下的部分系數(shù),恢復原來低秩矩陣的問題.在這篇文章中，作者引入了新的證明技巧，得到了與文獻[4]中類似的結果.Recht在文獻[5]中應用文獻[3]的技巧，簡化了文獻[4]中復雜的證明,并給出了常數(shù)C的具體值.Keshavan等在文獻[3]中提出了一個OptSpace算法來解決矩陣填充問題，并對算法表現(xiàn)進行分析，得到了與文獻[4]類似的結果.

在實際問題中，已知的數(shù)據(jù)往往并不是完全準確的，而是帶有各種噪聲.因此討論恢復算法在噪聲影響下的穩(wěn)定性也是一個很重要的研究內(nèi)容.假定已知的元素

Yij=Mij+Zij, (i,j)∈Ω

其中{Zij:(i,j)∈Ω}是隨機或者確定的噪聲項.記PΩ是投影映射，僅保留矩陣Ω位置上元素的值，其他位置的元素變?yōu)榱?求解下面的優(yōu)化問題：

(3)

Candes和Plan在文獻[6]中討論了高斯隨機噪聲和有界噪聲情形下的矩陣填充問題，指出當已知元素個數(shù)p≥Cnrlog6n時，以接近1的概率，通過求解式(3)可以穩(wěn)定恢復絕大多數(shù)秩不超過r的矩陣.

除了高斯隨機噪聲和有界噪聲之外，稀疏噪聲也是經(jīng)常遇到的噪聲.將一個矩陣分解為一個低秩矩陣和一個稀疏矩陣的和的問題就是經(jīng)典的主分量分析問題.Candes等在文獻[7]中提出了新的恢復算法求解下面的最優(yōu)化問題：

雖然求解核范數(shù)最小化問題已經(jīng)有成熟的算法，但是這些算法復雜度較高，處理高維矩陣填充問題所需時間較長，因此研究快速有效的矩陣填充算法也是一個研究的熱點.目前已經(jīng)出現(xiàn)了很多的快速算法，最早的是Cai等提出的SVT算法[8]，這個算法受到壓縮感知中Bregman迭代算法的啟發(fā),在迭代過程中對矩陣進行奇異值分解，然后將較小的奇異值設為0，生成新的矩陣進行迭代.該算法運算速度快，對于高維低秩矩陣的恢復非常有效.Ma等提出了FPCA算法[9]，該算法也用到了矩陣的奇異值分解，并且在迭代過程中進行不動點連續(xù)處理.FPAC算法對于秩適中的矩陣也有較好的恢復效果.在此之后，又出現(xiàn)了很多關于矩陣填充的快速算法.

3 總結與展望

目前矩陣填充理論與算法方面的研究已經(jīng)取得了極大的進展，但是仍然有很多問題需要解決.比如在一些實際問題中需要恢復的低秩矩陣的核范數(shù)是固定的，這時應用核范數(shù)最小化方法求解就失去意義.對于這樣的問題，需要提出新的算法.另外，矩陣填充在很多領域的應用也是一個重要的研究方向.Candes等將矩陣填充的思想應用于相位恢復問題，提出了相位提升算法，取得了很好的效果.

參考文獻：

[1] Recht B,Fazel M,Parrilo P.Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization[J].SIAM Rev,2010,52(3):471-501.

[2] Candes E J,Recht B.Exact matrix completion via convex optimization[J].Foundation of Computational Mathematics,2008(9):717-772.

[3] Gross D.Recovering low rank matrices from few coe±cients in any basis[J].IEEE Transactions on Information Theory,2011,3:1548-1566.

[4] Candes E J,Tao T.The power of convex relaxation: Near-optimal matrix completion[J].IEEE Transactions on Information Theory,2009,56(5):2053-2080.

[5] Recht B.A Simpler Approach to Matrix Completion[J].Journal of Machine Learning Research,2011,12:3413-3430.

[6] Candes E J,Plan Y.Matrix completion with noise[J].Proceedings of the IEEE,2009,98(6):925-936.

[7] Candes E J,Li X,Ma Y,et al.Robust Principal Component Analysis?[J].Journal of ACM,2009,58(1):1-37.

[8] Cai J F,Candes E J,Shen Z W.A singular value thresholding algorithm for matrix completion[J].SIAM Journal on Optimization,2010,20(4):1956-1982.

[9] Ma S,Goldfarb D,Chen L.Fixed point and Bregman iterative methods for matrix rank minimization[D].Technical report,2008.