矩阵还原

矩阵还原是在只有部分观察值时填充矩阵缺失的条目的任务。自然地，各种数据集都以矩阵形式表示。一个例子是电影评级矩阵，如Netflix问题所示：给定一个评级矩阵，其中如果客户i看过电影j那么数据点(i,j)的值代表客户i给电影j的评分，否则会该处没有值，我们希望预测这种没有值的数据点，以便就接下来要看什么向客户提出好的建议。另一个示例是术语文档矩阵：文档集合中使用的单词频率可以表示为矩阵，其中每个数据点对应于相关术语出现在指定文档中的次数。

对还原后矩阵中的自由度数没有任何限制，这个问题是不确定的，因为可以为隐藏的数据点分配任意值。因此，我们需要对矩阵进行一些假设来创建一个适定问题，比如假设它具有最大行列式，是正定的，或者是低秩的。

例如，可以假设矩阵具有低秩结构，接下来试图找到最低秩的矩阵，或者，如果还原后的矩阵的秩是已知的，那么一个秩-r的矩阵会与已知数据点匹配。该图显示，可以在零错误（右侧）的条件下还原部分显示的秩1矩阵（左侧），因为所有缺少数据点的行都应与第三行相同。在Netflix问题的情况下，由于用户偏好通常可以通过少数因素来描述，例如电影类型和发行时间，因此评分矩阵会是低秩的。其他应用包括计算机成像，需要重建图像中丢失的像素，从局部距离信息中检测传感器在网络中的全局位置，以及多类学习。矩阵完成问题通常是NP-难问题，但是在其他假设下，有一些有效的算法可以以很高的概率实现精确的重构。

从统计学习的角度来看，矩阵还原问题是矩阵正则化的一种应用，矩阵正则化是向量正则化的推广。例如，在低秩矩阵还原问题中，可以应用核范数形式的正则化惩罚R(X) = \lambda\|X\|_*

低秩矩阵还原
矩阵还原问题的变体之一是找到最低秩矩阵X匹配矩阵M ，我们希望从观测集合E恢复出所有数据点。此问题的数学公式如下：

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

:

Candès 和 Recht 证明，假设对观察数据的采样和足够多的采样数据，这个问题具有高概率的唯一解决方案。

假设矩阵M已知要恢复矩阵的秩r是r， 一个等价的表达，是解X，其中X_{ij} = M_{ij} \;\; \forall i,j \in E

假设
经常对观察到的数据抽样和抽样数据的数量做出许多假设，以简化分析并确保问题不是欠定的。

观察条目的均匀采样
为了使分析易于处理，通常假设集合E有固定并且观察到的数据是从数据的所有子集的集合中随机均匀采样 。为了进一步简化分析，假设E由伯努利采样构造，即每个数据都以概率 p 被观察到。如果p设为\frac{N}{mn}，其中N是E的期望基数，m,\;n是矩阵的维数（不失一般性，使m ）， |E|随N有高概率上界O(n \log n)，因此伯努利采样是均匀采样的一个很好的近似。 另一种简化是假设数据是独立采样的并且带有替换。

观察到的条目数量的下限
假设我们正在尝试恢复的m\times n矩阵M （m ) 为秩-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可以是任意的。