矩阵还原

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

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

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

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

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

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

假设矩阵已知要恢复矩阵的秩是r， 一个等价的表达，是解，其中

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

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

 观察到的条目数量的下限 
假设我们正在尝试恢复的矩阵 （ ) 为秩-r。 我们应该知道信息理论下界即必须观测到多少数据才能实现对矩阵的唯一重建。秩小于等于r的维矩阵的集合是在空间上一个代数变量，其空间维数为。利用这个结论，可以证明当时上的矩阵还原问题要有唯一解必须至少要有个数据输入。

第二，矩阵的每一行每一列必须至少有一个观察值。矩阵的奇异值分解为。如果第行未被观察，容易看到矩阵的第个右奇异向量可以改变为任意值并且仍然从可以观测数据中得到一个匹配的矩阵。同理，如果第列未被观察，矩阵的第个左奇异向量可以是任意的。
Category:矩陣論