第 62 章 矩阵补全问题¶
前置：奇异值分解 (Ch11) · 矩阵范数 (Ch15) · 凸优化 (Ch25)
本章脉络：从缺失数据到低秩恢复 \(\to\) 矩阵补全 (Matrix Completion) 的数学定义 \(\to\) 低秩假设的重要性 \(\to\) 核心挑战：秩最小化的非凸性 \(\to\) 凸松弛技术：核范数 (Nuclear Norm) 最小化 \(\to\) 采样率与可恢复性（相变现象） \(\to\) 算法实现：奇异值阈值化 (SVT) \(\to\) 应用：Netflix 推荐算法、计算机视觉中的图像修复、传感器网络定位
延伸：矩阵补全揭示了高维数据中“信息冗余”的巨大威力；它证明了只要底层结构是低秩的，我们仅需极少量的随机观测即可完美重构全局，是压缩感知理论在二维空间的精彩延伸
在现代数据科学中，我们经常面临不完整的观测。例如，在一个推荐系统中，数百万用户中只有极少数人对少数电影评分。如何根据这些零星的数字猜出整个评分矩阵？这就是矩阵补全问题（Matrix Completion）。利用数据的低秩性（Low-rank），我们可以在数学上证明：在一定条件下，缺失的信息是可以被精确“算”出来的。本章将介绍这一作为大数据智能核心的重构理论。
62.1 矩阵补全的数学定义¶
定义 62.1 (补全问题)
设 \(M\) 为一个未知的 \(m \times n\) 矩阵。我们只观测到其部分元素 \(M_{ij}, (i,j) \in \Omega\)。目标是寻找秩最小的矩阵 \(X\) 满足观测约束： $\(\min \operatorname{rank}(X) \quad \text{s.t. } X_{ij} = M_{ij}, \forall (i,j) \in \Omega\)$
62.2 凸松弛与核范数¶
计算障碍
直接最小化 \(\operatorname{rank}(X)\) 是一个组合爆炸的 NP-难问题。
核范数最小化
由于奇异值之和（核范数 \(\|X\|_*\)）是秩函数的最佳凸包络，我们将原问题松弛为： $\(\min \|X\|_* \quad \text{s.t. } X_{ij} = M_{ij}, \forall (i,j) \in \Omega\)$ 这是一个凸优化问题，可以利用半正定规划 (SDP) 高效求解。
62.3 恢复界限与算法¶
定理 62.1 (精确恢复定理)
若 \(M\) 满足“非相干性”（即能量不集中在少数位置），且其秩为 \(r\)，则当采样数 \(|\Omega| \ge C n r \log^2 n\) 时，通过核范数最小化可以以极高概率精确重构 \(M\)。
练习题¶
1. [基础] 为什么矩阵补全必须假设矩阵是“低秩”的？
参考答案
理由： 1. 一个一般的 \(m \times n\) 矩阵有 \(mn\) 个自由参数。 2. 如果没有结构假设，缺失的每一个位置都可以是任意值，无法进行预测。 3. 低秩性意味着矩阵虽然庞大，但其自由度（独立变量）只有 \(r(m+n-r)\)。 4. 当自由度远小于总元素个数时，信息的冗余性使得通过部分观测还原整体成为可能。
2. [计算] 若 \(M = \mathbf{u}\mathbf{v}^T\) 是一个秩 1 矩阵。观测到 \(M_{11}=1, M_{12}=2, M_{21}=3\)。求 \(M_{22}\)。
参考答案
推导： 1. 秩 1 矩阵满足 \(M_{11}M_{22} = M_{12}M_{21}\)。 2. 代入已知值：\(1 \cdot M_{22} = 2 \cdot 3\)。 3. 解得 \(M_{22} = 6\)。 结论：在低秩假设下，缺失项被唯一的代数约束确定。
3. [范数判定] 计算 \(A = \operatorname{diag}(3, 4, 0)\) 的核范数 \(\|A\|_*\) 和算子范数 \(\|A\|_2\)。
参考答案
计算： 1. 核范数是奇异值之和：\(\|A\|_* = 3 + 4 + 0 = 7\)。 2. 算子范数是最大奇异值：\(\|A\|_2 = 4\)。 对比：核范数起到了类似于 \(L_1\) 范数的作用，倾向于产生稀疏的奇异值分布（即低秩）。
4. [可恢复性] 举出一个无法补全的低秩矩阵例子。
参考答案
例子：极稀疏阵 \(M = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}\)。 原因：该矩阵虽然秩为 1，但其能量完全集中在 (1,1) 位置。如果观测集合 \(\Omega\) 没有采样到该位置，我们永远无法得知该元素是非零的。 这种性质在理论上称为相干性（Coherence）太高。
5. [应用] 简述 Netflix 问题中矩阵补全的应用。
参考答案
Netflix 矩阵的行是用户，列是电影。条目是评分（1-5）。 由于大多数用户只看过极少数电影，矩阵 99% 的条目是缺失的。 通过矩阵补全技术，算法挖掘出隐藏的“品味维度”（低秩空间），预测出用户对未看电影的评分，从而实现精准推荐。
6. [凸松弛] 为什么用核范数代替秩？
参考答案
理由： 1. 秩函数是非连续且非凸的，梯度为 0，无法直接优化。 2. 核范数是秩函数在单位球上的凸包（Convex Envelope）。 3. 它具有将奇异值推向 0 的倾向，类似于 \(L_1\) 范数将向量分量推向 0。这使得我们能用成熟的凸优化算法解决本来属于组合数学的难题。
7. [数值算法] 简述奇异值阈值化 (SVT) 算法的一步迭代过程。
参考答案
步骤： 1. 更新：\(X_{k} = X_{k-1} + \delta \cdot \mathcal{P}_\Omega(M - X_{k-1})\)（在观测位置修正偏差）。 2. 收缩：\(X_{k+1} = \mathcal{D}_\tau(X_k)\)（对 \(X_k\) 做 SVD，将所有奇异值减去阈值 \(\tau\) 并在 0 处截断）。 这一过程通过反复的“数据拟合”与“秩压缩”逼近最优解。
8. [采样率] 随着秩 \(r\) 的增加，重构所需的最小观测比例如何变化？
参考答案
结论：线性增加。 理论界限显示 \(|\Omega|\) 正比于 \(nr\)。这意味着如果系统变得更复杂（秩增加），我们必须收集成比例增加的数据才能维持重构的精确性。
9. [性质] 核范数是否满足三角不等式？
参考答案
是的。 核范数是一个合法的范数（它对应于对偶算子范数）。这意味着 \(\|A+B\|_* \le \|A\|_* + \|B\|_*\)，保证了优化目标的全局凸性。
10. [应用] 矩阵补全如何解决无线传感器网络中的定位问题？
参考答案
在传感器网络中，只能测量距离较近的节点间的距离。 由欧几里得距离组成的平方距离矩阵 \(D\) 具有非常低的秩（通常在 3 维空间中秩为 5）。 通过补全缺失的远距离测度，可以根据部分局部观测精确推算出所有节点的全局坐标。
本章小结¶
矩阵补全理论是数据稀疏性时代的代数奇迹：
- 低维的投影：它揭示了高维表象下的本质简单性，证明了低秩性是跨越数据缺失鸿沟的唯一桥梁。
- 松弛的智慧：核范数的引入将不可逾越的非凸鸿沟转化为可计算的凸优化坦途，确立了现代统计学习的算法范式。
- 重构的哲学：从局部的碎片还原出全局的全貌，矩阵补全不仅是计算工具，更是描述信息结构冗余性与恢复可能性的深刻定律。