矩阵还原

矩阵还原是在只有部分观察值时填充矩阵缺失的条目的任务。自然地，各种数据集都以矩阵形式表示。一个例子是电影评级矩阵，如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}$ 可以是任意的。