查看“︁矩阵还原”︁的源代码

[[File:Rank-1-matrix-completion.png|缩略图|440x440像素|对部分显示的5 x 5的秩-1矩阵的矩阵还原。左：观察到的不完整矩阵；右：矩阵还原结果。]]
'''矩阵还原'''是在只有部分观察值时填充矩阵缺失的条目的任务。自然地，各种数据集都以矩阵形式表示。一个例子是电影评级矩阵，如Netflix问题所示：给定一个评级矩阵，其中如果客户<math>i</math>看过电影<math>j</math>那么数据点<math>(i,j)</math>的值代表客户<math>i</math>给电影<math>j</math>的评分，否则会该处没有值，我们希望预测这种没有值的数据点，以便就接下来要看什么向客户提出好的建议。另一个示例是术语文档矩阵：文档集合中使用的单词频率可以表示为矩阵，其中每个数据点对应于相关术语出现在指定文档中的次数。

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

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

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

== 低秩矩阵还原 ==
矩阵还原问题的变体之一是找到最低[[秩 (线性代数)|秩]]矩阵<math>X</math>匹配矩阵<math>M</math> ，我们希望从观测集合<math>E</math>恢复出所有数据点。此问题的数学公式如下：



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

:

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

假设矩阵<math>M</math>已知要恢复矩阵的[[秩 (线性代数)|秩]]<math>r</math>是r， 一个等价的表达，是解<math>X</math>，其中<math>X_{ij} = M_{ij} \;\; \forall i,j \in E</math>

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

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

==== 观察到的条目数量的下限 ====
假设我们正在尝试恢复的<math>m\times n</math>矩阵<math>M</math> （<math>m < n</math> ) 为[[秩 (线性代数)|秩]]-r。 我们应该知道信息理论下界即必须观测到多少数据才能实现对矩阵<math>M</math>的唯一重建。秩小于等于r的<math>m\times n</math>维矩阵的集合是在<math>{\mathbb C}^{m\times n}</math>空间上一个代数变量，其空间维数为<math>(n+m)r - r^2</math>。利用这个结论，可以证明当<math>r \leq n/2</math>时<math> {\mathbb C}^{n \times n} </math>上的矩阵还原问题要有唯一解必须至少要有<math>4nr - 4r^2</math>个数据输入。

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