目錄

• 引
• 恢復1
  • 核范數與SDP
• 穩定恢復

Candes E J, Plan Y. Matrix Completion With Noise[J]. arXiv: Information Theory, 2010, 98(6): 925-936.

這篇文章，同一個人（團隊？）寫的，遺憾的是，沒怎么看懂。怎么說呢，里面的關于對偶的性質實在不知道從何入手，但想來還是得記一筆。

引

這篇文章，討論的是這樣的一個問題，有一個矩陣\(M \in \mathbb{R}^{n_1 \times n_2}\)，但是因為種種原因，我們只能知曉其中的一部分元素即\(P_{\Omega}(M)\)，那么問題來了，有沒有辦法能夠恢復\(M\)呢，或者說在什么條件下我們能恢復\(M\)呢（實際上，這個問題好像是作者前一篇論文已經給出了答案）？然后，又有新的困難，因為我們的觀測是有誤差的，也就是說我們觀測到的實際上不是\(P_{\Omega}(M)\),而是\(P_{\Omega}(M+Z)\)。
作者總拿Netflix舉例子，類似地，我們可以用網易云來舉例子（雖然估計網易云的推薦方法和這個并沒有啥大關系）。

我們可以這么想，\(M\)的每一行是一個用戶，每一列是一首歌，其中的每一個元素是該用戶給這首歌打的分（當然，這個分可能是通過一些操作的判斷的，比如收藏，評論，下載，是否跳過等等）。顯然，一個用戶不可能聽過里面的所有的歌，一首歌也沒法讓所有人都聽（打分），所以，我們所見識到的是\(P_{\Omega}(M)\),一個稀疏的矩陣。然而，推薦歌曲，關注的就是那些用戶沒有聽過的但可能被打高分的歌，所以我們要做的就是利用\(P_{\Omega}(M)\)恢復出\(M\)。聽起來的確蠻好玩的。

然后問題是，恢復需要什么前提。很顯然，如果一首歌沒有被人聽過，或者該用戶沒有聽過任何歌，肯定沒法把分數恢復出來，因為這跟瞎猜沒分別，所以，假設就是\(M\)低秩，但是每行每列不能全為零。

和之前一樣，作者采用不連貫條件來描述：

恢復1

本來，是應該求解下述問題的：

但是，這個問題很難求解（NP-hard)。

然后\(\mathrm{rank}\)的凸放松是\(\|\cdot\|_*\)核范數，所以：

核范數與SDP

核范數與SDP

然后，作者指出，核范數可以通過對偶，轉換成一個半正定規范問題（看這篇論文最大的收獲吧）。

\[ \|X\|_* \le y \Leftrightarrow 存在對稱矩陣W_1，W_2 使得 M:= \left [ \begin{array}{cc} W_1 & X \\ X^T & W_2 \end{array} \right ] \succeq 0, \mathrm{Tr} W_1 + \mathrm{Tr} W_2 \le 2y \]
先來前推后，只要構造出這么一個\(W_1\)就可以了。假設\(X = U\Sigma V^T, \Sigma \in \mathbb{R}^{r \times r}\)，\(W_1 = U\Sigma U^T,W_2=V\Sigma V^T\)。那么，\(\mathrm{Tr} W_1 + \mathrm{Tr} W_2 \le 2y\)容易證明，第一個條件這么來玩：
\[ [z_1^T, z_2^T] \left [ \begin{array}{cc} W_1 & X \\ X^T & W_2 \end{array} \right ] \left [ \begin{array}{c} z_1\\ z_2 \end{array} \right ] \]
再令\(a = U^Tz_1, b = V^Tz_2\)，可得：
\[ [z_1^T, z_2^T] \left [ \begin{array}{cc} W_1 & X \\ X^T & W_2 \end{array} \right ] \left [ \begin{array}{c} z_1\\ z_2 \end{array} \right ] = (a+b)^T \Sigma (a+b) \ge 0 \]
對于任意的\(z_1, z_2\)成立，所以半正定條件也得證了。

好了，現在來反推：
\(\|X\|_* = \sup \{\mathrm{Tr}(X^TW)|\|W\|\le 1\}\)，其中\(\|\cdot\|\)表示譜范數。
注意\(\|A\|_* \le \mathrm{Tr}(A)\),當\(A\)為半正定矩陣的時候。
所以
\[ \|M\|_* \le \mathrm{Tr}(M)=\mathrm{Tr}(W_1+W_2)\le 2y \]
又\(\|M\|_* = \sup \{\mathrm{Tr}(M^TW)|\|W\|\le 1\}\),所以
\[ \mathrm{Tr}(M^TW) \le 2y \]
又
\[ N := \left [ \begin{array}{cc} U^T & 0 \\ 0 & V^T \end{array} \right ] M \left [ \begin{array}{cc} 0 & I_{n_1 \times n_1} \\ I_{n_2 \times n_2} & 0 \end{array} \right ] \left [ \begin{array}{cc} V & 0\\ 0 & U \end{array} \right ] = \left [ \begin{array}{cc} \Sigma & U^TW_1U \\ V^TW_2V & \Sigma \end{array} \right ] \]
令
\[ W = \left [ \begin{array}{cc} 0 & I_{n_1 \times n_1} \\ I_{n_2 \times n_2} & 0 \end{array} \right ] \left [ \begin{array}{cc} V & 0\\ 0 & U \end{array} \right ] \left [ \begin{array}{cc} U^T & 0 \\ 0 & V^T \end{array} \right ] = \left [ \begin{array}{cc} 0 & UV^T \\ VU^T & 0 \end{array} \right ] \]
容易證明\(\|W\| \le 1\)，所以\(\mathrm{Tr}(N) = \mathrm{Tr}(M^TW)=2\|X\|_*\le 2y\)，故\(\|X\|_* \le y\)得證。但愿沒出錯。。。

然后，論文就給出了第一個定理，關于恢復的：

這個結果貌似是之前的工作，，滿足一定條件，\(M\)就會有很大概率被恢復。

然后呢，論文又提了以下加強版的不連貫條件：

然后有相應的定理2：

然后跳過。

穩定恢復

用戶的評分是不一定正確，不同的場合，不同的天氣可能就會給出不同的分數，如果是機器推斷的分數那就更是如此了。所以，我們觀測的部分數據實際上不一定是\(P_\Omega (M)\)，而是\(P_\Omega (Y) = P_\Omega (M+Z)\)，其中\(Z\)是類似噪聲的存在。
假設，\(\|P_{\Omega}(Z)\|_F \le \delta\),求解下列問題：
\[ \begin{array}{cc} \min & \|X\|_* \\ s.t. & \|P_{\Omega}(X-Y)\|_F \le \delta \end{array} \]
這個問題同樣可以作為SDP求解，假設其解為\(\hat{M}\)。有如下定理：

但是問題是，我們從何知道\(\delta\)呢？而在實際操作的時候，作者是求解下述問題：

\[ \min \quad \frac{1}{2} \|P_{\Omega} (X-Y)\|_F^2 + \mu \|X\|_* \]

作者說，這個問題是上面那個問題的對偶結果，饒了我吧，有點像，但是整不出來。然后，不同的情況，作者也給出了\(\mu\)的一些選擇。

作者還拿上面的結果和下面的神諭問題進行了比較：

這個神諭，就是指，我們已經知道\(X \in T\)里面了，然后用了對偶還是共軛算子？暈了已經。就這樣吧，再看我就得吐了。

轉載于:https://www.cnblogs.com/MTandHJ/p/10738769.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的Matrix Completion with Noise的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。