【综述】矩阵补全问题

前言最近接触到这个问题，看了一些相关的资料，觉得维基百科的介绍是最为精炼详实的，以这篇笔记翻译了一下，也供自己查阅所用。矩阵补全顾名思义，矩阵补全就是指将一个部分元素已知的矩阵的缺失值补全的问题。这个问题的著名背景是美国的视频公司Netflix提出了这样的问题，给出一个矩阵，其每行代表一个用户，每列则代表用户所看过的电影。这样一个矩阵的维度是非常庞大的，因此Netflix公司希望

B417科研笔记

8354人浏览 · 2020-11-02 16:49:04

B417科研笔记 · 2020-11-02 16:49:04 发布

前言

最近接触到这个问题，看了一些相关的资料，觉得维基百科的介绍是最为精炼详实的，以这篇笔记翻译了一下，也供自己查阅所用。

矩阵补全

顾名思义，矩阵补全就是指将一个部分元素已知的矩阵的缺失值补全的问题。这个问题的著名背景是美国的视频公司Netflix提出了这样的问题，给出一个矩阵，其每行代表一个用户，每列则代表用户所看过的电影。这样一个矩阵的维度是非常庞大的，因此Netflix公司希望可以只储存其中的个别值，就能将矩阵进行补全，算是一种信息的压缩。

如果没有任何其他的辅助限制的话，这个问题其实有无数组解——除了被观测到的元素之外，其他矩阵元素可以是任意值。因此，矩阵补全往往要求补全的矩阵的秩最小。或者，假设已知了原始矩阵的秩 $r$ ，我们就是补全一个秩为 $r$ 的矩阵。

在这里插入图片描述
上图展示了一个例子。左边的是缺失的矩阵，我们希望将其补全。如果已知矩阵的秩为1，那么就能很轻松的知道，每一行都必须和第三行是一样的（否则秩不为1）。

低秩矩阵补全

常见的矩阵补全问题可以表示如下：

$\begin{array}{lc} \min _{X} & \operatorname{rank}(X) \\ \text { subject to } & X_{i j}=M_{i j} \forall i, j \in E \end{array}$
求解这个问题的时候，我们需要保证足够多的矩阵采样数（即已知元素的个数）来确保这个问题不是欠定的，能求得一个唯一解。

均匀采样

为了使分析更为简便，我们往往假设观测的元素是在 $E$ 中均匀采样所得。一种更特殊的假设是考虑伯努利采样（ Bernoulli sampling），即每个矩阵元素都有 $p$ 的概率被观测到。我们令 $\frac{N}{mn}$ ，其中 $N$ 为总的期望采样元素数，m,n为矩阵的维度。

最少的观测数量

假设我们现在要恢复一个秩为 $r$ 的 $m\times n$ 的矩阵 $M$ 。【3】中证明了，当 $\le \frac{n}{2}$ 时，至少需要 $4nr - 4r^2$ 个观测元素，可以确保该矩阵补全问题有唯一解。

同时，每一行和每一列都必须要被采样到。
这个也很容易证明：我们可以把矩阵M奇异值分解为： $U\Sigma V^H$
比如 $M$ 的第一行没有被采样到，由矩阵相乘我们可知， $U$ 的第一行只参与了构建 $M$ 的第一行，那么当 $M$ 的第一行是任意的时候，我们可以任意的设置 $U$ 的第一行。同理，如果第一列没有被采样到，我们可以任意的设置 $V^H$ 的第一列。如果考虑伯努利采样的话，已被证明需要 $\log n)$ 个元素被观测才能确保大概率每一行和每一列都被观测到了。

综合这两点考虑，我们认为所需的观测元素数的下界为 $\mathrm{log}n$ 。

Incoherence

并不是所有的矩阵都能很好的补全。事实上，我们希望被补全的矩阵不要太稀疏。尽可能的在每个奇异值方向上都有分量的矩阵是较为容易补全的。反例是这样的一个矩阵 $\left[\begin{array}{cccc}1 & 0 & \cdots & 0 \\ \vdots & & \vdots & \\ 0 & 0 & 0 & 0\end{array}\right]$ 几乎只能通过观测所有元素才能确定。

噪声情况下

在实际中，我们的观测可能还存在噪声：

$Y_{i j}=M_{i j}+Z_{i j},(i, j) \in \Omega$

$Z$ 代表观测的噪声。最后观测到的矩阵可以写为：
$P_{\Omega}(Y)=P_{\Omega}(M)+P_{\Omega}(Z)$
那么，我们可以把问题建模为：
$\begin{array}{lr} \min _{X} & \|X\|_{*} \\ \text { subject to } & \left\|P_{\Omega}(X-Y)\right\|_{F} \leq \delta \end{array}$
$X\|_{*}$ 代表 $X$ 的核范数，等于奇异值之和。可以近似的将最小化核范数看做最小化秩，原理就和将 $l_0$ 范数近似为 $l_1$ 范数类似。

算法

凸优化

上面的最小化核函数的问题，可以看做是一个凸松弛，将一个NP-hard问题放松成了凸问题。他可以改写为下式：
$\begin{array}{ll} \min _{W_{1}, W_{2}} & \operatorname{trace}\left(W_{1}\right)+\operatorname{trace}\left(W_{2}\right) \\ \text { subject to } & X_{i j}=M_{i j} \forall i, j \in E \\ & {\left[\begin{array}{cc} W_{1} & X \\ X^{T} & W_{2} \end{array}\right] \succeq 0} \end{array}$
这个经典的半正定规划（SDP）问题。可以用凸优化算法进行求解。