矩阵还原

对部分显示的5 x 5的秩-1矩阵的矩阵还原。左：观察到的不完整矩阵；右：矩阵还原结果。

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

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

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

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

低秩矩阵还原

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

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

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

假设矩阵$M$已知要恢复矩阵的秩$r$是r， 一个等价的表达，是解$X$，其中$X_{ij}=M_{ij}\mathrm{\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$维矩阵的集合是在${ℂ}^{m\times n}$空间上一个代数变量，其空间维数为$(n+m)r-r^2$。利用这个结论，可以证明当$r\le n/2$时${ℂ}^{n\times n}$上的矩阵还原问题要有唯一解必须至少要有$4nr-4r^2$个数据输入。

第二，矩阵$M$的每一行每一列必须至少有一个观察值。矩阵$M$的奇异值分解为$U\mathrm{\Sigma }{V}^{†}$。如果第$i$行未被观察，容易看到矩阵$M$的第$i$个右奇异向量$v_i$可以改变为任意值并且仍然从可以观测数据中得到一个匹配的矩阵$M$。同理，如果第$j$列未被观察，矩阵$M$的第$j$个左奇异向量$u_j$可以是任意的。