矩陣還原

矩陣還原是在只有部分觀察值時填充矩陣缺失的條目的任務。自然地，各種數據集都以矩陣形式表示。一個例子是電影評級矩陣，如Netflix問題所示：給定一個評級矩陣，其中如果客戶 $i$ 看過電影 $j$ 那麼數據點 $(i,j)$ 的值代表客戶 $i$ 給電影 $j$ 的評分，否則會該處沒有值，我們希望預測這種沒有值的數據點，以便就接下來要看什麼向客戶提出好的建議。另一個示例是術語文檔矩陣：文檔集合中使用的單詞頻率可以表示為矩陣，其中每個數據點對應於相關術語出現在指定文檔中的次數。

對還原後矩陣中的自由度數沒有任何限制，這個問題是不確定的，因為可以為隱藏的數據點分配任意值。因此，我們需要對矩陣進行一些假設來創建一個適定問題，比如假設它具有最大行列式，是正定的，或者是低秩的。

例如，可以假設矩陣具有低秩結構，接下來試圖找到最低秩的矩陣，或者，如果還原後的矩陣的秩是已知的，那麼一個秩-r的矩陣會與已知數據點匹配。該圖顯示，可以在零錯誤（右側）的條件下還原部分顯示的秩1矩陣（左側），因為所有缺少數據點的行都應與第三行相同。在Netflix問題的情況下，由於用戶偏好通常可以通過少數因素來描述，例如電影類型和發行時間，因此評分矩陣會是低秩的。其他應用包括計算機成像，需要重建圖像中丟失的像素，從局部距離信息中檢測傳感器在網絡中的全局位置，以及多類學習。矩陣完成問題通常是NP-難問題，但是在其他假設下，有一些有效的算法可以以很高的概率實現精確的重構。

從統計學習的角度來看，矩陣還原問題是矩陣正則化的一種應用，矩陣正則化是向量正則化的推廣。例如，在低秩矩陣還原問題中，可以應用核範數形式的正則化懲罰 $R(X)=\lambda \|X\|_{*}$

低秩矩陣還原

矩陣還原問題的變體之一是找到最低秩矩陣 $X$ 匹配矩陣 $M$ ，我們希望從觀測集合 $E$ 恢復出所有數據點。此問題的數學公式如下：

${\begin{aligned}&{\underset {X}{\text{min}}}&{\text{rank}}(X)\\&{\text{subject to}}&X_{ij}=M_{ij}&\;\;\forall i,j\in E\\\end{aligned}}$

Candès 和 Recht 證明，假設對觀察數據的採樣和足夠多的採樣數據，這個問題具有高概率的唯一解決方案。

假設矩陣 $M$ 已知要恢復矩陣的秩 $r$ 是r，一個等價的表達，是解 $X$ ，其中 $X_{ij}=M_{ij}\;\;\forall i,j\in E$

假設

經常對觀察到的數據抽樣和抽樣數據的數量做出許多假設，以簡化分析並確保問題不是欠定的。

觀察條目的均勻採樣

為了使分析易於處理，通常假設集合 $E$ 有固定基數 $|E|$ 並且觀察到的數據是從數據的所有子集的集合中隨機均勻採樣。為了進一步簡化分析，假設 $E$ 由伯努利採樣構造，即每個數據都以概率 $p$ 被觀察到。如果 $p$ 設為 ${\frac {N}{mn}}$ ，其中 $N$ 是 $E$ 的期望基數， $m,\;n$ 是矩陣的維數（不失一般性，使 $m<n$ ）， ~~$|E|$~~ 隨 $N$ 有高概率上界 $O(n\log n)$ ，因此伯努利採樣是均勻採樣的一個很好的近似。另一種簡化是假設數據是獨立採樣的並且帶有替換。

觀察到的條目數量的下限

假設我們正在嘗試恢復的 $m\times n$ 矩陣 $M$ （ $m<n$ ) 為秩-r。我們應該知道信息理論下界即必須觀測到多少數據才能實現對矩陣 $M$ 的唯一重建。秩小於等於r的 $m\times n$ 維矩陣的集合是在 ${\mathbb {C} }^{m\times n}$ 空間上一個代數變量，其空間維數為 $(n+m)r-r^{2}$ 。利用這個結論，可以證明當 $r\leq n/2$ 時 ${\mathbb {C} }^{n\times n}$ 上的矩陣還原問題要有唯一解必須至少要有 $4nr-4r^{2}$ 個數據輸入。

第二，矩陣 $M$ 的每一行每一列必須至少有一個觀察值。矩陣 $M$ 的奇異值分解為 $U\Sigma V^{\dagger }$ 。如果第 ${i}$ 行未被觀察，容易看到矩陣 $M$ 的第 ${i}$ 個右奇異向量 $v_{i}$ 可以改變為任意值並且仍然從可以觀測數據中得到一個匹配的矩陣 $M$ 。同理，如果第 ${j}$ 列未被觀察，矩陣 $M$ 的第 ${j}$ 個左奇異向量 $u_{j}$ 可以是任意的。