矩陣補全（matrix completion）的經典演算法有哪些？目前比較流行的演算法是什麼？

01-04

請教一下，矩陣補全的經典演算法有哪些？目前比較流行的矩陣補全演算法是什麼？打算往這方面研究下，還沒任何頭緒，也沒代碼。

簡單科普一下這個問題，最早這個問題火起來是因為Netflix公司的公開挑戰：懸賞100萬美金給予能夠improve公司現行的matrix completion演算法10%以上的最優勝隊伍。最後的結果是09年9月BellKor』s
Pragmatic拿走了獎金。當時比賽的網址：Netflix Prize: Home

獲勝者的演算法paper http://www.stat.osu.edu/~dmsl/GrandPrize2009_BPC_BellKor.pdf

我們先看看什麼是matrix completion問題，就用Netflix的dataset來說明。簡單來說就是在一個豆瓣電影評分系統做inference，要根據非常稀疏的現有數據集（一個用戶可能就只rate了幾十部電影）來推斷整個用戶群對不同電影的評分。見下圖，480000 x 18000規模的matrix completion（各位可以算算光存儲這個矩陣就需要多少GB）。

這個問題在推薦系統、圖像處理等方面都有廣泛的運用。接著，這類問題一般來說都有隱含的假設即最終的矩陣應該是低秩（low rank）的。這其實也很好理解，因為我們一般會覺得：1、不同用戶對於電影的偏好可以分成聚落（cliques），即最多也就是這麼幾大類的用戶，比如按照年齡：年輕人，中年人，老年人...，而電影因為也可以分成不同的題材（genres），戰爭片，魔幻片，言情片...所以會有low rank的特性。簡單來說，就是這個矩陣的行和列會有「合作」的特性，這也是這個問題的別名collaborative filtering得名的原因。另外，low rank限制下的matrix completion也會比較實用，因為一般人都會喜歡稀疏（sparse）的解，這樣利於存儲且有更好的詮釋性。最後則是理論上的意義，更利於reconstruction，這點先隱去不表（下圖有幾篇paper可以refer）。當然我們注意到，data是會有noise的（有些用戶可能會亂填rating...）。這段總結如下圖。

好了，那麼這個問題的數學形式其實非常簡潔。Z是我們要complete的矩陣，X則是現有的data（大部分缺失）。我們希望找到一個和X不缺失部分差距盡量小的rank最小的矩陣。

然而問題來了：1、這個問題是非凸的，所以可能有一大堆local minimum因此沒有什麼現成的efficient的辦法（NP-hard, of course）。2、這種問題一般的應用規模都非常大（比如上述的netflix問題規模是10^5 x 10^4），需要考慮很多數值方面的trick才能讓演算法比較實際。

最早人們用一些啟發式演算法如下圖。即局部讓user對item做迭代（vote）最後演算法收斂到一個局部最優解。

矩陣P就是最後的ouput。至於裡面那個weight就是見仁見智了，如下圖可以取各種，反正是啟發式演算法...

顯然，這些演算法雖然很容易實現，但沒有理論上的收斂性保證，也沒有對rank的考慮，也絕無可能滿足像Netflix這種公司對解的精度的需求（對那種規模的問題這些演算法的表現可能會驚人的差）。所以，我們需要一些更好的方法。這裡我不詳述BellKor的解法，因為他的解法實質上是一堆解法的組合。只是指出，他們的方法主要是基於matrix factorization，如下圖。

核心想法是把Z作low rank factorization（有一些比較有效的演算法，比如regularized SVD，但具體implementation detail水其實很深）然後解這個reformulate之後的優化問題。

另外一種方法是對原問題作convex relaxation，即把原問題的目標函數rank(Z)換成Z的nuclear norm（定義不清楚的可查Matrix norm），這個在里有介紹。見下圖：

(http://arxiv.org/pdf/0810.3286.pdf

http://www.jmlr.org/papers/v12/recht11a.html)

不過我們發現這兩種reformulation仍然有太過於rigid或者無法控制noise的缺陷，所以最後簡單介紹一下這篇工作：http://www.jmlr.org/papers/v11/mazumder10a.html 思路是把那個constraint dualize來做。

為了快速解這個問題我們也需要考慮合理利用每步的SVD做很多fast subroutine，具體也不展開。哦對了，以上這些圖大多是我research advisor課件里的，最後一篇是他當phd時候的一篇很不錯的paper...

樓上已經講了 trace-norm ，這個方法應該是 Maryam Fazel 的論文裡面的結果。

因為我們希望復原的矩陣是low-rank 的，所以第一個optimization 是：

$min_{X} rank(X)\ s.t. ||X_{Omega} - Y_{Omega}||_{F} leq delta \ where Omega : collection of observed entries$

這個最優化問題因為目標函數不是凸函數，所以沒辦法保證全局最優，並且計算很複雜，所以想到需要把目標函數換成convex的。 Fazel 在她的phd thesis 裡面證明了， trace-norm 這個函數是 rank這個函數的 convex envelope。convex envelope 就是說 trace-norm 是所有convex function裡面對rank 函數 point-wise approximation 最好的。於是上面的問題就可以通過解以下凸優化問題來得到一個近似。

$min_{X} ||X||_{*}\ s.t. ||X_{omega} - Y_{Omega}||_{F} leq delta \ where Omega is the collection of observed entries.$

看上去很好，但是理論上只有當observed entries 是 uniformly sampled（所有matrix entries 有相同的概率被採樣）的時候， trace-norm是最好的convex relaxation。但這在現實中並不成立。以 Netflix 這個問題來說，有的用戶可能會評價很多部電影，有的可能只評價很少的幾部。有的電影比較熱門可能會有很多的評價，有的比較冷門而沒有多少評價。所以為了避免這個問題，Srebro 和 Salakhutdinov 提出了一個新的formulation。

$min_{X} ||X||_{max}\ s.t. ||X_{Omega}-Y_{Omega}||_{F} leq delta\ where Omega is the observed entries$

$||X||_{max} = min_{X=UV^{T}}(max_i U_i)*(max_j V_j)\ where i and j are rows of U, V$

$||X||_{*} = min_{X=UV^{T}}||U||_{Fro}||V||_{Fro}=min_{X=UV^{T}} frac{1}{2}(||U||^2_{Fro}+||V||^2_{Fro})$

所以可以看出 max-norm是通過 mapping user 和 item 到一個 r-維的空間（r = rank）形成一個hard margin separation problem。

semi-definite programming formulation：（知乎不支持 bmatrix？？)

（trace-norm）soft-margin 的 SDP formulation， S ： observed entries

這個問題的對偶問題是：

可以得到一個sparse的psd matrix。而且滿足 slater『s condition，沒有 duality gap，同時問題矩陣是sparse的，並且constraint數量等於observed entries的數量，所以計算比較方便。

（max-norm）soft-margin 的 SDP formulation，和對偶形式

max-norm 雖然可以通過positive semi-definite 問題求解，不過一般的方法像interior point 無法解決大型的問題。最近我老闆在review一篇論文講的是max-norm 和trace-norm 混合使用，不過還沒發表，所以就不在這寫了。。

謝邀。

參考：稀疏矩陣中的空缺元素是怎樣通過機器學習填補的？ - li Eta 的回答

一些代碼:

http://perception.csl.illinois.edu/matrix-rank/sample_code.html

http://cvxr.com/tfocs/demos/matrixcompletion/

Matrix Completion.m

Matrix Completion via Thresholding

https://bamdevmishra.com/codes/qgeommc/

GitHub - alaa-saade/macbeth_matlab: Matrix Completion with the Bethe Hessian : matlab demo

Matlab codes for linearized Bregman algorithms

http://users.ece.gatech.edu/~mdavenport/software/1BMC-1.2.zip

RTRMC - A Riemannian Trust-Region method for low-rank Matrix
Completion

Inductive Matrix Completion

Matrix Completion

LINKS OF SOFTWARE / CODES

GitHub - adrtod/hasi: Hierarchical Adaptive Soft Impute

http://perso.telecom-paristech.fr/~lafond/downloads/code.tar.gz

可以參考一下我寫的一個project report，裡面總結了matrix completion的主要理論結果以及演算法，有code。

pdf：

https://staff.ie.cuhk.edu.hk/~zbyang/projects/matrix_completion/manu_mtxcomp.pdf

code：

https://staff.ie.cuhk.edu.hk/~zbyang/projects/matrix_completion/codes.zip

svd lda word2vec

以下內容有可能有謬誤，如果發現有問題麻煩告訴我，非常感謝！

該方向目前最為完整的理論是candes Recht把壓縮感知中對正交基的假設（incoherence）擴展到矩陣補全問題的論文, exact matrix completion via convex optimazation, 以及第二年candes和陶哲軒提升bound的論文(the power of convex relaxation: near optimal xxx)。該方法提供了目前最好的bound O(nr log n), r=rank(X).

鑒於個人數學水平有限這兩篇論文都有一部分內容沒看懂……

求解目標函數目前最精確、理論分析最完整的解法是使用SDP，收斂速度非常快（參見boyd關於SDP的tutorial），缺點是每輪計算複雜度非常不可接受，也就是非常不實用。recht他們有一篇singular value thresholding(SVT)的演算法，該演算法可以認為是求解有約束優化問題的一種通用方法，這種思路類似於對拉格朗日函數加入平方項，對矩陣補全問題效果很不錯。特此指出，這種方法是有bad case的，有些優化問題用這種方法求解效果會很糟糕。對於這類方法的分析可以參考ALM和ALM出現之前的一些工作。

從10年開始，幾乎每年都有從矩陣分解角度方向來做bound的，該類方法優勢在於計算速度會快很多，但是bound基於eigen gap。由於本人方向所限，我閱讀的這類論文大都發表在EECS會議和期刊上，不排除數學期刊上有這類論文我沒有讀到，如果有的話麻煩私信或留言告訴我，非常感謝。這類論文另一問題在於我看過的有很大一部分證明多多少少有點瑕疵.

沒有bound的方法很多，在此不表。

The field of matrix completion is overly crowded with all those TCS, Stats, Opt, ML, DM researchers. Too hard to make large impact.

樓上回答的大神們，給你們跪了。【真跪】

棒，大神

最近又有聚類與矩陣補全相結合的工作，見"high-rank-matrix-completion-and-clustering-under-self-expressive-models","A Structured Sparse Plus Structured Low-Rank Framework for Subspace Clustering and Completion"