矩阵补全：从极少观测恢复低秩矩阵

Art. 4 范数与条件数 建立了 nuclear 范数 $\|A\|_* = \sum_i \sigma_i$ 这一关键工具，并揭示了它的本质——秩的凸松弛。当时我们说这个性质是”矩阵补全理论的基石”。现在是兑现这个承诺的时候了。

矩阵补全（matrix completion）问题看起来不可能：一个 $n \times n$ 矩阵有 $n^2$ 个元素，你只看到其中极小一部分（比如 1%），却要恢复全部。这就像拿到一本书的几页随机碎片，要还原整本书。

但如果这个矩阵是低秩的——它的自由度远小于 $n^2$——情况就完全不同了。一个秩为 $r$ 的 $n \times n$ 矩阵只有 $r(2n - r) \leq 2nr$ 个自由度（$U \in \mathbb{R}^{n \times r}$ 和 $V \in \mathbb{R}^{n \times r}$ 的参数减去旋转不变性的冗余）。如果观测数量足够覆盖这些自由度，恢复就有希望。

Candès 和 Recht (2009) 的开创性工作将这个直觉变成了严格定理：在温和的条件下，$O(nr \log^2 n)$ 个随机观测就足以通过一个凸优化问题——nuclear 范数最小化——精确恢复原始矩阵。这个结果连接了压缩感知（compressed sensing）、凸优化和随机矩阵理论，是过去二十年最优美的数学结果之一。

问题设定：Netflix Prize 的数学抽象

从推荐系统到矩阵

2006 年，Netflix 悬赏 100 万美元征集改进其推荐算法的方案。数据是一个用户-电影评分矩阵 $M \in \mathbb{R}^{m \times n}$（约 48 万用户 × 1.8 万电影），其中只有约 1% 的元素被观测到——绝大多数用户只评价了极少数电影。

核心假设：用户的品味可以用少数几个潜在因素（latent factors）描述——比如对”动作片”、“文艺片”、“喜剧”的偏好程度。如果有 $r$ 个潜在因素，那么评分矩阵可以近似表示为：

$M \approx UV^T$

其中 $U \in \mathbb{R}^{m \times r}$ 是用户因子矩阵（每行是一个用户在 $r$ 个因素上的”偏好向量”），$V \in \mathbb{R}^{n \times r}$ 是电影因子矩阵（每行是一部电影在 $r$ 个因素上的”属性向量”）。这意味着 $\text{rank}(M) \leq r$，而 $r$ 远小于 $\min(m, n)$。

形式化问题

给定观测集合 $\Omega \subseteq \{1, \ldots, m\} \times \{1, \ldots, n\}$（已知评分的位置），我们观测到 $M_{ij}$ 对所有 $(i,j) \in \Omega$。矩阵补全的目标是恢复完整的矩阵 $M$。

最自然的形式化是秩最小化：

$\min_{X \in \mathbb{R}^{m \times n}} \text{rank}(X) \quad \text{s.t.} \quad X_{ij} = M_{ij}, \; \forall (i,j) \in \Omega \qquad \text{(1)}$

即：在所有满足观测约束的矩阵中，找秩最小的那个。

问题：$\text{rank}(\cdot)$ 是非凸、不连续的函数（非零奇异值的个数 = 奇异值向量的 $\ell_0$ “范数”），这个优化问题是 NP-hard 的——和稀疏恢复中的 $\ell_0$ 最小化一样困难。

核范数松弛：秩最小化的凸替代

从 $\ell_0$ 到 $\ell_1$ 的类比

在 Art. 4 范数与条件数 中，我们建立了向量稀疏性和矩阵秩之间的精确类比：

向量	矩阵（对奇异值向量 $\boldsymbol{\sigma}$）
$\lVert\boldsymbol{\sigma}\rVert_0 =$ 非零分量个数	$\text{rank}(A) =$ 非零奇异值个数
$\lVert\boldsymbol{\sigma}\rVert_1 = \sum_i \lvert\sigma_i\rvert$	$\lVert A\rVert_* = \sum_i \sigma_i$（nuclear 范数）
$\ell_0$ 最小化（NP-hard）	秩最小化（NP-hard）
$\ell_1$ 最小化（凸，可高效求解）	nuclear 范数最小化（凸，可高效求解）

在压缩感知（compressed sensing）中，Candès、Romberg 和 Tao 以及 Donoho 在 2006 年证明了：在 RIP（restricted isometry property）条件下，$\ell_1$ 最小化可以精确恢复稀疏向量。矩阵补全理论将这个思路推广到矩阵世界。

Nuclear 范数最小化

将问题 (1) 中的 $\text{rank}(X)$ 替换为它的凸松弛 $\|X\|_*$，得到：

$\min_{X \in \mathbb{R}^{m \times n}} \|X\|_* \quad \text{s.t.} \quad X_{ij} = M_{ij}, \; \forall (i,j) \in \Omega \qquad \text{(2)}$

这是一个凸优化问题——更准确地说，它可以表述为一个半正定规划（semidefinite program, SDP）。

为什么 $\|X\|_*$ 是 $\text{rank}(X)$ 的”好”凸松弛？因为 nuclear 范数是秩函数在 spectral 范数单位球 $\{X : \|X\|_2 \leq 1\}$ 上的凸包（convex envelope）——在所有凸函数中，nuclear 范数是对秩函数最紧的下界。形式化地说（见 Candès & Recht, 2009）：

$\|X\|_* = \text{conv}\big(\text{rank}(X)\big) \quad \text{在 } \{X : \|X\|_2 \leq 1\} \text{ 上}$

这意味着在 spectral 范数有界的矩阵集合内，最小化 nuclear 范数与最小化秩”尽可能等价”。

SDP 形式

Nuclear 范数最小化问题 (2) 可以等价地写成半正定规划：

$\min_{X, W_1, W_2} \;\frac{1}{2}\big(\text{tr}(W_1) + \text{tr}(W_2)\big) \quad \text{s.t.} \quad \begin{bmatrix} W_1 & X \\ X^T & W_2 \end{bmatrix} \succeq 0, \; X_{ij} = M_{ij} \; \forall (i,j) \in \Omega$

其中 $W_1 \in \mathbb{R}^{m \times m}$，$W_2 \in \mathbb{R}^{n \times n}$，$\succeq 0$ 表示半正定。这个等价性来自 nuclear 范数的变分表示：

$\|X\|_* = \min_{X = AB^T} \frac{1}{2}\big(\|A\|_F^2 + \|B\|_F^2\big)$

SDP 可以用通用的内点法求解，但对大规模问题（如 Netflix 的 48 万 × 1.8 万矩阵）计算代价过高。实践中使用更高效的专用算法——见本文后半部分。

Incoherence 条件：不是所有矩阵都能补全

为什么需要额外条件

核范数松弛能精确恢复原矩阵吗？答案是：不一定——取决于原矩阵的结构。

考虑一个极端例子：$M = \mathbf{e}_1 \mathbf{e}_1^T$，即只在第 $(1,1)$ 位置为 1、其余全为 0 的秩 1 矩阵。这个矩阵的所有”信息”集中在一个元素上。如果随机采样没有恰好采到 $(1,1)$，我们将完全看不到任何非零信号——恢复不可能成功。

问题的根源是：这个矩阵的能量高度集中在少数行列上。用 SVD 的语言说：$M = \mathbf{e}_1 \mathbf{e}_1^T$ 的左右奇异向量都是标准基向量 $\mathbf{e}_1$——它们与标准基完全”对齐”（coherent）。

相反，如果奇异向量在所有坐标上都比较”均匀”——即与标准基不对齐（incoherent）——那么矩阵的信息均匀分散在各个元素中，随机采样就能有效地捕获信息。

Incoherence 的形式定义

设 $M \in \mathbb{R}^{n \times n}$ 是秩为 $r$ 的矩阵，其紧 SVD（compact SVD）为 $M = U\Sigma V^T$，其中 $U \in \mathbb{R}^{n \times r}$，$V \in \mathbb{R}^{n \times r}$ 的列分别是左右奇异向量。记 $U$ 和 $V$ 的列空间分别张成的子空间的正交投影矩阵为 $P_U = UU^T$ 和 $P_V = VV^T$。

定义（Incoherence，见 Candès & Recht, 2009）。矩阵 $M$ 满足参数为 $\mu_0$ 的 incoherence 条件，如果：

$\max_{1 \leq i \leq n} \|P_U \mathbf{e}_i\|_2^2 \leq \frac{\mu_0 r}{n}, \qquad \max_{1 \leq j \leq n} \|P_V \mathbf{e}_j\|_2^2 \leq \frac{\mu_0 r}{n} \qquad \text{(3)}$

其中 $\mathbf{e}_i$ 是第 $i$ 个标准基向量。

逐项理解：

• $\|P_U \mathbf{e}_i\|_2^2 = \sum_{k=1}^{r} U_{ik}^2$：这是 $U$ 的第 $i$ 行的平方范数，衡量第 $i$ 个标准基向量在 $U$ 的列空间中的”投影长度”
• $\frac{\mu_0 r}{n}$ 是上界：由于 $U$ 有 $r$ 列且列正交归一，$\sum_{i=1}^n \|P_U \mathbf{e}_i\|_2^2 = \text{tr}(UU^T) = r$，所以”平均”值恰好是 $r/n$。Incoherence 条件要求没有哪一行的投影远大于平均值
• 参数 $\mu_0 \geq 1$ 衡量”不均匀”的程度。$\mu_0 = 1$ 是最优情况（完全均匀），$\mu_0 = n/r$ 是最坏情况（如 $M = \mathbf{e}_1 \mathbf{e}_1^T$）

Candès 和 Recht 还引入了第二个条件：

$\|UV^T\|_\infty \leq \sqrt{\frac{\mu_1 r}{n^2}} \qquad \text{(4)}$

其中 $\|UV^T\|_\infty = \max_{i,j} |(UV^T)_{ij}|$。这个条件要求 $U$ 和 $V$ 的行之间的内积也是均匀的，防止某个特定 $(i,j)$ 位置承载过多信息。

直觉：为什么随机缺失比结构性缺失好

Incoherence 条件的直觉可以这样理解：

• Incoherent 矩阵（$\mu_0$ 小）：信息均匀分散在所有元素中。每个元素都携带了关于低秩结构的少量信息。随机采样就像”均匀品尝”，很快就能收集到足够的信息。
• Coherent 矩阵（$\mu_0$ 大）：信息集中在少数行列中。必须”恰好”采到这些关键位置才能获取信息。随机采样很可能错过关键元素。

一个有用的类比：incoherent 矩阵就像一篇信息均匀分布的文章——随机读几段就能把握大意。Coherent 矩阵就像密码学文本——关键信息隐藏在特定位置，漏掉一个字符就可能丢失全部含义。

好消息：许多实际应用中的低秩矩阵天然满足 incoherence 条件。例如，推荐系统中的用户-物品矩阵：如果用户偏好由少数潜在因素驱动，而这些因素在用户群体中的分布是相对均匀的（没有某个因素只被极少数用户拥有），那么对应的奇异向量就是 incoherent 的。

Candès & Recht (2009) 主定理

现在我们可以陈述 Candès 和 Recht 的核心结果。以下是他们论文中 Theorem 1.1 的严格陈述。

定理（Candès & Recht, 2009, Theorem 1.1）。设 $M \in \mathbb{R}^{n \times n}$ 是秩为 $r$ 的矩阵，满足 incoherence 条件 (3) 和 (4)，参数分别为 $\mu_0$ 和 $\mu_1$。设 $\Omega$ 是大小为 $m = |\Omega|$ 的观测集合，其中每个 $(i,j) \in \Omega$ 独立均匀随机从 $\{1, \ldots, n\} \times \{1, \ldots, n\}$ 中采样。如果

$m \geq C \, \mu^2 \, n \, r \, (\log n)^2 \qquad \text{(5)}$

其中 $\mu = \max(\mu_0, \mu_1)$，$C > 0$ 是一个数值常数，那么 nuclear 范数最小化问题 (2) 的唯一解就是 $M$ 本身——即 $\hat{X} = M$——的概率至少为 $1 - n^{-3}$。

逐项理解这个定理：

• $m \geq C \mu^2 n r (\log n)^2$：所需的观测数量。秩 $r$ 和维度 $n$ 的矩阵有 $2nr - r^2$ 个自由度，定理要求观测数量是自由度的 $O(\log^2 n)$ 倍——只比信息论下界多一个对数因子。
• 独立均匀随机采样：观测位置的随机性至关重要。如果观测位置是对抗性选择的（比如只看某几行），定理不成立。
• 概率 $\geq 1 - n^{-3}$：以压倒性的概率成功。对于 $n = 10000$，失败概率小于 $10^{-12}$。
• 精确恢复：$\hat{X} = M$，没有任何误差。这不是近似——是精确等式。
• 唯一解：不仅 $M$ 是可行解，而且是 nuclear 范数最小化的唯一最优解。

定理的意义

这个定理的惊人之处在于效率。一个秩为 $r$ 的 $n \times n$ 矩阵有 $n^2$ 个元素，但只需要观测 $O(nr \log^2 n)$ 个——当 $r \ll n$ 时，这远少于 $n^2$。例如，对于 $n = 10000$、$r = 10$ 的矩阵：

• 总元素数：$n^2 = 10^8$
• 自由度：$\approx 2nr = 2 \times 10^5$
• 所需观测：$O(nr \log^2 n) \approx 10^5 \times (\log 10^4)^2 \approx 10^5 \times 85 \approx 8.5 \times 10^6$
• 观测比例：$\approx 8.5\%$

也就是说，观测不到 10% 的元素就能精确恢复整个矩阵。

后续改进

Candès 和 Recht (2009) 的原始结果中 $(\log n)^2$ 因子稍大。后续工作改进了这个界：

• Candès 和 Tao (2010)：将样本复杂度改进为 $m \geq C \mu_0 n r \log^6 n$，去掉了对 $\mu_1$ 条件的依赖
• Recht (2011)：给出了更简洁的证明，样本复杂度为 $m \geq C \mu_0^2 n r \log^2 n$
• Gross (2011)：利用量子信息论工具进一步简化证明

这些改进的核心信息是一致的：$O(nr \, \text{polylog}(n))$ 个观测就足以精确恢复。

信息论下界

上面的定理告诉我们 $O(nr \log^2 n)$ 个观测足够。一个自然的问题是：最少需要多少观测？

自由度计数

秩为 $r$ 的 $n \times n$ 矩阵的自由度是：

$d = r(2n - r)$

这是因为紧 SVD $M = U \Sigma V^T$ 中，$U \in \mathbb{R}^{n \times r}$ 在 Stiefel 流形上有 $nr - \binom{r}{2}$ 个自由度，$\Sigma$ 有 $r$ 个，$V$ 同理，但 $U$ 和 $V$ 之间有 $r$ 个符号的旋转冗余需要扣除。总计 $r(2n - r)$。

因此，至少需要 $m \geq r(2n - r) \approx 2nr$ 个观测来确定矩阵——否则问题是欠定的（方程数少于未知数）。

信息论下界的严格形式

仅仅自由度计数还不够：它只给出了代数约束，没有考虑随机采样带来的信息损失。

一个更精细的信息论论证（见 Candès & Tao, 2010 的讨论）表明：对于满足 incoherence 条件的秩 $r$ 矩阵类，任何补全算法（不仅是 nuclear 范数最小化）都至少需要

$m = \Omega(nr \log n)$

个观测才能以常数概率成功恢复。这里的 $\log n$ 因子来自coupon collector 问题的类比：要覆盖矩阵的所有行和列，$nr$ 个纯随机采样平均需要”再多 $\log n$ 轮”。

这意味着 Candès 和 Recht 的 $O(nr \log^2 n)$ 上界与 $\Omega(nr \log n)$ 下界之间只差一个 $\log n$ 因子——定理给出的采样数量几乎是最优的。

交互演示：观测比例与恢复质量

下面的交互组件演示了矩阵补全的核心现象。我们生成一个秩 2 的 $8 \times 8$ 矩阵，使用交替最小化算法（ALS）从部分观测中恢复它。拖动滑块改变观测比例，观察恢复质量如何变化。

矩阵补全交互演示

从部分观测恢复低秩矩阵

观测比例:50%重新采样

原始矩阵 (秩 2)

观测掩码

恢复结果

逐元素误差

已观测

30 / 64

‖M̂ − M‖_F / ‖M‖_F

3.1328

 

恢复困难

提示：观测比例低于约 30% 时，恢复质量急剧下降——这正是 Candès & Recht 定理中 O(nr log² n) 下界的直观体现。

观察要点：

• 当观测比例 $\gtrsim 50\%$ 时，恢复几乎完美（相对误差接近 0）
• 当观测比例降到 $\sim 30\%$ 以下时，恢复质量急剧下降
• 多次点击”重新采样”可以看到：即使在同一观测比例下，不同的采样模式也会导致不同的恢复质量——这正是随机性的影响
• 对于 $8 \times 8$、秩 2 的矩阵，自由度 $= 2 \times (2 \times 8 - 2) = 28$，总元素 $= 64$，理论上约 $28/64 \approx 44\%$ 的观测应该足以恢复

证明的核心思想（梗概）

Candès 和 Recht 的证明技术精深，完整展开需要几十页。这里我们概述证明的核心思路，不追求完整性，而是传达关键洞察。

最优性条件

Nuclear 范数最小化问题 (2) 的解 $\hat{X} = M$ 当且仅当存在一个对偶证书（dual certificate）$\Lambda \in \mathbb{R}^{n \times n}$，使得：

1. $\Lambda$ 在观测集合 $\Omega$ 上有支撑：$\Lambda_{ij} = 0$ 对所有 $(i,j) \notin \Omega$
2. $P_T(\Lambda) = UV^T$（投影到 $M$ 的切空间上等于 $UV^T$）
3. $\|P_{T^\perp}(\Lambda)\|_2 < 1$（在正交补空间上的 spectral 范数严格小于 1）

其中 $T$ 是秩 $r$ 矩阵在 $M$ 处的切空间，$P_T$ 和 $P_{T^\perp}$ 分别是向 $T$ 和 $T^\perp$ 的正交投影。$UV^T$ 是 nuclear 范数 $\|M\|_*$ 的次梯度（subgradient）。

直觉：对偶证书的作用是”证明”$M$ 是最优解。条件 2 保证在 $M$ 附近沿切空间方向不可能降低 nuclear 范数，条件 3 保证沿法空间方向也不行。条件 1 保证证书与观测数据一致。

构造对偶证书

证明的核心困难是在随机采样集 $\Omega$ 上构造满足上述三个条件的 $\Lambda$。Candès 和 Recht 使用了 golfing scheme（高尔夫方案，Gross, 2011 命名）的思想：

1. 将观测集 $\Omega$ 随机划分为 $\Omega_1, \ldots, \Omega_L$ 若干组
2. 迭代地修正证书：$\Lambda^{(0)} = 0$，$\Lambda^{(l)} = \Lambda^{(l-1)} +$ 在 $\Omega_l$ 上的修正项
3. 每步修正减少”残差” $UV^T - P_T(\Lambda^{(l)})$ 的大小

类比高尔夫球的过程：第一杆粗略地打向目标（大幅减少残差），后续几杆精细调整，最终把球打入洞中（残差趋于零）。

每步修正的成功依赖于随机矩阵理论的集中不等式（concentration inequalities），而 incoherence 条件保证了这些不等式成立。

含噪声情形

实际应用中，观测值通常包含噪声。设观测模型为：

$Y_{ij} = M_{ij} + Z_{ij}, \quad (i,j) \in \Omega$

其中 $Z_{ij}$ 是噪声。此时精确恢复不再可能，我们转而最小化带正则化的目标：

$\min_{X} \; \frac{1}{2} \sum_{(i,j) \in \Omega} (X_{ij} - Y_{ij})^2 + \lambda \|X\|_* \qquad \text{(6)}$

这里 $\lambda > 0$ 是正则化参数，平衡数据拟合和低秩惩罚。Negahban 和 Wainwright (2012) 证明了在适当条件下，这个估计器的误差上界为：

$\frac{\|\hat{X} - M\|_F^2}{n^2} \leq C \cdot \frac{r \, \sigma^2 \log n}{m}$

其中 $\sigma^2$ 是噪声方差，$m$ 是观测数。他们还证明了这个界本质上是最优的——没有算法能在同类矩阵上做得本质更好。

实践中的算法

Nuclear 范数最小化的 SDP 形式虽然理论上优美，但对大规模问题不实用。以下是实践中常用的高效算法。

奇异值阈值化（Singular Value Thresholding, SVT）

Cai、Candès 和 Shen (2010) 提出的 SVT 算法是求解 nuclear 范数正则化问题 (6) 的近端梯度方法。核心操作是软阈值化奇异值：

$\text{SVT}_\tau(X) = U \, \text{diag}\big((\sigma_i - \tau)_+\big) \, V^T$

其中 $X = U \, \text{diag}(\sigma_1, \ldots, \sigma_p) \, V^T$ 是 $X$ 的 SVD，$(x)_+ = \max(x, 0)$，$\tau > 0$ 是阈值参数。

逐项理解：

• 计算 $X$ 的 SVD
• 将每个奇异值 $\sigma_i$ 减去 $\tau$，如果结果为负则置为 0
• 用修改后的奇异值重构矩阵

直觉：$\text{SVT}_\tau$ 是 nuclear 范数的近端算子（proximal operator），类似于 $\ell_1$ 范数的软阈值化促进向量稀疏性，SVT 通过缩减小奇异值促进矩阵的低秩性。

SVT 算法的迭代格式为：

$X^{(t+1)} = \text{SVT}_\tau \big(X^{(t)} + \delta \, P_\Omega(M - X^{(t)})\big)$

其中 $P_\Omega$ 是对 $\Omega$ 的采样算子（保留 $\Omega$ 中的元素，其余置零），$\delta > 0$ 是步长。每次迭代先沿数据拟合方向走一步，再用 SVT 促进低秩。

交替最小化（Alternating Minimization, ALS）

交替最小化直接在因子空间中优化。假设 $M \approx UV^T$，其中 $U \in \mathbb{R}^{n \times r}$，$V \in \mathbb{R}^{n \times r}$，交替地：

1. 固定 $V$，解 $U$：对每一行 $i$，$U$ 的第 $i$ 行 $\mathbf{u}_i^T$ 由如下最小二乘问题确定：

$\mathbf{u}_i = \arg\min_{\mathbf{u}} \sum_{j: (i,j) \in \Omega} (M_{ij} - \mathbf{u}^T \mathbf{v}_j)^2$

2. 固定 $U$，解 $V$：类似地更新 $V$ 的每一行。

每一步都是小规模最小二乘问题（$r \times r$ 线性方程组），计算非常高效。

Jain、Netrapalli 和 Sanghavi (2013) 给出了 ALS 收敛的理论保证：在 incoherence 条件下，ALS 以几何速率（即线性收敛）收敛到真实矩阵 $M$，且所需的样本复杂度为 $O(\mu^4 n r^5 \log^3 n)$——虽然常数比 nuclear 范数最小化差，但计算复杂度远低。

梯度下降方法

将补全问题参数化为 $M \approx UV^T$ 后，可以直接对 $U$ 和 $V$ 做梯度下降：

$\min_{U \in \mathbb{R}^{n \times r},\, V \in \mathbb{R}^{n \times r}} \sum_{(i,j) \in \Omega} \big(M_{ij} - (UV^T)_{ij}\big)^2$

这是非凸问题（$U$ 和 $V$ 的乘积使目标函数非凸），但在实践中随机梯度下降（SGD）往往能找到全局最优解。近年的理论工作（如 Ge et al., 2016）表明：在 incoherence 条件下，这个非凸问题没有”坏的”局部极小值——所有局部极小值都是全局极小值。

算法比较

算法	优化形式	每步复杂度	理论保证	实践表现
SDP 内点法	凸 (SDP)	$O(n^{6.5})$	最优	仅限小规模
SVT	凸 (proximal)	$O(n^2 r)$ per SVD	最优	中等规模
ALS	非凸 (bilinear)	$O(\lvert\Omega\rvert r)$	几何收敛	大规模首选
SGD	非凸 (bilinear)	$O(\lvert\Omega\rvert)$	渐近收敛	极大规模

实践中，ALS 和 SGD 因其可扩展性而成为推荐系统中的标准选择。Netflix Prize 的获胜方案正是基于矩阵分解 + ALS/SGD 的变体。

数值例子

用一个小例子手算验证核心概念。取 $n = 4$，$r = 1$，矩阵：

$M = \begin{bmatrix} 2 \\ 1 \\ 3 \\ 2 \end{bmatrix} \begin{bmatrix} 1 & 3 & 2 & 1 \end{bmatrix} = \begin{bmatrix} 2 & 6 & 4 & 2 \\ 1 & 3 & 2 & 1 \\ 3 & 9 & 6 & 3 \\ 2 & 6 & 4 & 2 \end{bmatrix}$

这是一个秩 1 矩阵，$M = \mathbf{u}\mathbf{v}^T$，其中 $\mathbf{u} = (2,1,3,2)^T$，$\mathbf{v} = (1,3,2,1)^T$。

自由度

秩 1 的 $4 \times 4$ 矩阵自由度 $= 1 \times (2 \times 4 - 1) = 7$。总元素 $= 16$。所以至少需要 7 个观测。

检验 incoherence

$M$ 的 SVD 为 $M = \sigma_1 \hat{\mathbf{u}} \hat{\mathbf{v}}^T$，其中归一化的奇异向量为：

$\hat{\mathbf{u}} = \frac{1}{\sqrt{18}} \begin{bmatrix} 2 \\ 1 \\ 3 \\ 2 \end{bmatrix}, \quad \hat{\mathbf{v}} = \frac{1}{\sqrt{15}} \begin{bmatrix} 1 \\ 3 \\ 2 \\ 1 \end{bmatrix}$

Incoherence 条件 (3) 要求 $\max_i \hat{u}_i^2 \leq \mu_0 r / n = \mu_0 / 4$。

$\max_i \hat{u}_i^2 = \frac{9}{18} = \frac{1}{2}$

所以 $\mu_0 \geq 2$。这是一个 incoherent 程度适中的矩阵（$\mu_0 = 2$，不算太大）。对比 $\mathbf{e}_1 \mathbf{e}_1^T$ 的情况：$\max_i \hat{u}_i^2 = 1$，需要 $\mu_0 \geq n/r = 4$，是最差情况。

恢复演示

假设观测 8 个元素（50% 观测率）：

$\Omega = \{(1,1),(1,3),(2,2),(2,4),(3,1),(3,3),(4,2),(4,4)\}$

观测值：$M_{11}=2, M_{13}=4, M_{22}=3, M_{24}=1, M_{31}=3, M_{33}=6, M_{42}=6, M_{44}=2$。

在秩 1 的假设下，$M_{ij} = u_i v_j$。从观测中：

$\frac{M_{11}}{M_{31}} = \frac{u_1}{u_3} = \frac{2}{3}, \quad \frac{M_{22}}{M_{42}} = \frac{u_2}{u_4} = \frac{3}{6} = \frac{1}{2}$

$\frac{M_{11}}{M_{13}} = \frac{v_1}{v_3} = \frac{2}{4} = \frac{1}{2}, \quad \frac{M_{22}}{M_{24}} = \frac{v_2}{v_4} = \frac{3}{1} = 3$

从这些比值，加上归一化条件，可以恢复 $\mathbf{u}$ 和 $\mathbf{v}$（进而恢复全部 $M$）。这个小例子直观地展示了低秩结构如何使”方程数少于未知数”的系统变得可解。

总结与展望

本文深入探讨了矩阵补全理论——从极少观测恢复低秩矩阵的数学框架。回顾关键要点：

• 问题：从观测集 $\Omega$ 中的 $m$ 个元素恢复秩 $r$ 的 $n \times n$ 矩阵 $M$
• 秩最小化 → nuclear 范数松弛：$\text{rank}(X)$ 是 NP-hard 的，$\|X\|_*$ 是其在 spectral 范数单位球上的凸包，可高效求解
• Incoherence 条件：奇异向量与标准基不对齐（$\max_i \|P_U \mathbf{e}_i\|^2 \leq \mu_0 r/n$），保证信息均匀分散
• Candès-Recht 定理：在 incoherence 条件下，$m \geq C \mu^2 n r \log^2 n$ 个随机观测足以通过 nuclear 范数最小化精确恢复 $M$，概率 $\geq 1 - n^{-3}$
• 信息论下界：$\Omega(nr \log n)$，与上界只差一个 $\log n$ 因子
• 实践算法：SVT（凸但需 SVD）、ALS（高效、几何收敛）、SGD（可扩展到极大规模）

这篇文章是 nuclear 范数理论的直接应用：Art. 4 范数与条件数 建立了”nuclear 范数 = 秩的凸松弛”，本篇将其付诸实践。矩阵补全也是 Art. 3 SVD 中 SVD 低秩近似思想的自然延伸——从”已知全部元素时的最佳低秩近似”到”只知道部分元素时的精确低秩恢复”。

下一篇我们将看到另一种约束下的矩阵分解——非负矩阵分解（NMF）：当因子矩阵的所有元素必须非负时，分解会自然产生”parts-based”的表示，揭示数据中有意义的局部结构。