低秩矩阵补全（low-rank matrix completion）

什么是低秩矩阵补全

低秩矩阵补全（low-rank matrix completion）研究的是如下估计问题：真实矩阵为 $\mathbf M^\ast\in\mathbb R^{n_1\times n_2}$，但只能观测到索引集合 $\Omega\subset[n_1]\times[n_2]$ 上的条目；若存在噪声，观测模型通常写为 $Y_{ij}=M^\ast_{ij}+\varepsilon_{ij}$，其中 $(i,j)\in\Omega$。采样算子 $\mathcal P_\Omega$ 定义为 $[\mathcal P_\Omega(\mathbf A)]_{ij}=A_{ij}$ 当 $(i,j)\in\Omega$，否则为 $0$。矩阵补全的目标是由 $\mathcal P_\Omega(\mathbf Y)$ 恢复或估计整个 $\mathbf M^\ast$。

若不加入结构约束，该问题通常不可识别：同一组观测条目可以对应无穷多个完整矩阵。低秩假设要求 $\operatorname{rank}(\mathbf M^\ast)=r\ll\min(n_1,n_2)$，等价地，$\mathbf M^\ast$ 可以写成 $\mathbf U^\ast(\mathbf V^\ast)^T$，其中 $\mathbf U^\ast\in\mathbb R^{n_1\times r}$ 且 $\mathbf V^\ast\in\mathbb R^{n_2\times r}$。一个秩为 $r$ 的 $n_1\times n_2$ 矩阵的自由度为 $r(n_1+n_2-r)$，远小于一般矩阵的 $n_1n_2$ 个自由参数，因此低秩结构为从少量观测中恢复整体矩阵提供了可能性。

低秩结构常见于以下情形：第一，行实体与列实体由少数潜在因子（latent factors）驱动，例如推荐系统中的用户偏好与物品属性；第二，行或列之间存在强相关性，数据主要集中在低维子空间中；第三，真实矩阵未必严格低秩，但奇异值快速衰减，此时低秩矩阵可作为有效近似。需要强调的是，矩阵补全不是任意插值，而是在低维结构、采样机制与噪声条件共同约束下的统计估计问题。

原始优化问题及其困难

在无噪声情形下，最直接的数学表述是秩最小化：

$$\min_{\mathbf M}\ \operatorname{rank}(\mathbf M) \qquad \text{s.t.}\qquad \mathcal P_\Omega(\mathbf M)=\mathcal P_\Omega(\mathbf M^\ast).$$

这表示：在所有和观测数据一致（consistent with observations）的矩阵里，选一个秩最小（minimum rank）的。

若考虑噪声，一种自然形式是 $\min_{\mathbf M}\frac12\|\mathcal P_\Omega(\mathbf Y-\mathbf M)\|_F^2+\lambda\operatorname{rank}(\mathbf M)$。该问题的困难不只是技术性的。秩函数是整数值、非凸且非光滑的复杂度度量；在一般线性约束下，秩最小化是 NP-hard 问题。直观上，直接求解需要在可能的低维行空间、列空间或奇异值支撑结构之间进行组合搜索，不能依靠标准凸优化方法保证全局解。矩阵补全的随机采样模型具有特殊结构，但原始秩最小化仍不构成可实施的通用算法，因此需要可计算的替代形式。

核范数松弛（nuclear norm relaxation）

核范数 $\|\mathbf M\|_\ast=\sum_k\sigma_k(\mathbf M)$ 是奇异值向量的 $\ell_1$ 范数，其中 $\sigma_k(\mathbf M)$ 为 $\mathbf M$ 的奇异值。由于 $\operatorname{rank}(\mathbf M)=\|\sigma(\mathbf M)\|_0$，核范数松弛可以看作把奇异值上的 $\ell_0$ 计数替换为 $\ell_1$ 惩罚。更严格地说，在谱范数单位球 $\{\mathbf M:\|\mathbf M\|_2\le1\}$ 上，核范数是秩函数的凸包络（convex envelope）；同时，核范数与谱范数互为对偶，即 $\|\mathbf M\|_\ast=\sup_{\|\mathbf Z\|_2\le1}\langle \mathbf Z,\mathbf M\rangle$。这说明核范数不是任意替代，而是与秩最小化紧密相关的凸复杂度度量。

无噪声情形下，核范数松弛写为

$$\min_{\mathbf M}\ \|\mathbf M\|_\ast \qquad \text{s.t.}\qquad \mathcal P_\Omega(\mathbf M)=\mathcal P_\Omega(\mathbf M^\ast).$$

有噪声时，常用的惩罚形式为 $\min_{\mathbf M}\frac12\|\mathcal P_\Omega(\mathbf Y-\mathbf M)\|_F^2+\lambda\|\mathbf M\|_\ast$。由于目标函数是凸函数，该问题可以用凸优化方法求解，并成为低秩矩阵恢复理论中的基本模型。

需要注意，低秩本身不足以保证可恢复性。如果矩阵的信息集中在极少数坐标上，即使矩阵秩很低，未观测到关键坐标也会导致不可识别。因此，经典核范数理论通常还需要以下条件：观测集合 $\Omega$ 近似均匀随机且规模足够大；真实矩阵的奇异向量不应过度集中；噪声水平受控，正则化参数 $\lambda$ 与噪声尺度匹配。若 $\mathbf M^\ast=\mathbf U^\ast\mathbf\Sigma^\ast(\mathbf V^\ast)^T$，一种典型的不相干性条件为

$$\max_i \|(\mathbf U^\ast)^T \mathbf e_i\|_2^2 \le \frac{\mu r}{n_1}, \qquad \max_j \|(\mathbf V^\ast)^T \mathbf e_j\|_2^2 \le \frac{\mu r}{n_2}.$$

其中 $\mu$ 是不相干性参数。该条件排除了奇异向量几乎对准标准基方向的尖峰矩阵。通常而言，当 $|\Omega|$ 至少达到自由度 $r(n_1+n_2-r)$ 的量级并乘以必要的对数因子时，核范数方法才可能给出精确恢复或稳定恢复结论；具体常数与概率界依赖于采样模型、噪声模型和不相干性强度。

算法

一、凸松弛：核范数最小化

凸松弛方法直接求解核范数最小化或核范数正则化问题。其核心计算通常是奇异值软阈值化：若 $\mathbf X=\mathbf U\operatorname{diag}(\sigma_k)\mathbf V^T$，则 $\mathcal D_\tau(\mathbf X)=\mathbf U\operatorname{diag}((\sigma_k-\tau)_+)\mathbf V^T$ 是核范数的近端算子。

• 奇异值阈值化（singular value thresholding, SVT）：SVT 可理解为对数据拟合项做梯度步，再对奇异值做软阈值。例如对正则化问题，可用近端梯度迭代 $\mathbf M^{t+1}=\mathcal D_{\eta\lambda}(\mathbf M^t-\eta\mathcal P_\Omega(\mathbf M^t-\mathbf Y))$。其优点是形式清晰、理论分析直接；主要成本在于每步需要计算 SVD，尤其是大规模矩阵时需要截断 SVD。
• 增广拉格朗日法（augmented Lagrangian method, ALM）：对约束问题 $\min\|\mathbf M\|_\ast$ 且 $\mathcal P_\Omega(\mathbf M)=\mathcal P_\Omega(\mathbf Y)$，ALM 将约束违反项加入拉格朗日函数，例如加入乘子项与二次罚项 $\frac{\rho}{2}\|\mathcal P_\Omega(\mathbf M-\mathbf Y)\|_F^2$，再交替更新原变量与乘子。实际实现常与变量分裂或 ADMM 结合，使核范数近端步仍由奇异值软阈值化完成。相较简单 SVT，ALM 通常约束满足更稳定，但单步计算和参数调节更复杂。

二、非凸分解法：低秩矩阵分解

非凸分解法直接设 $\mathbf M=\mathbf U\mathbf V^T$，其中 $\mathbf U\in\mathbb R^{n_1\times r}$ 且 $\mathbf V\in\mathbb R^{n_2\times r}$，并求解

$$\min_{\mathbf U,\mathbf V} \frac12\|\mathcal P_\Omega(\mathbf Y-\mathbf U\mathbf V^T)\|_F^2 + \frac{\lambda}{2}\bigl(\|\mathbf U\|_F^2+\|\mathbf V\|_F^2\bigr).$$

该目标关于 $(\mathbf U,\mathbf V)$ 非联合凸，但参数量约为 $r(n_1+n_2)$，适合大规模稀疏观测场景。在适当初始化、采样和不相干性条件下，许多非凸方法也可获得收敛与统计保证。

• 交替最小二乘（alternating least squares, ALS）：固定 $\mathbf U$ 时，关于 $\mathbf V$ 的问题分解为若干最小二乘子问题；固定 $\mathbf V$ 时同理更新 $\mathbf U$。ALS 实现简单、可利用稀疏观测结构，但依赖秩 $r$、正则化强度和初始化，且一般只能保证收敛到驻点。
• 黎曼梯度下降（Riemannian gradient descent）：将固定秩矩阵集合视为光滑流形，在当前点计算欧氏梯度后投影到切空间，再通过 retraction 回到秩为 $r$ 的矩阵集合。该方法直接在低秩流形上优化，减少冗余参数化带来的尺度不唯一性，适合分析固定秩约束下的几何结构。
• 非凸梯度法与随机梯度法：直接对 $\mathbf U,\mathbf V$ 做梯度或随机梯度更新，计算成本低，适合在线或超大规模推荐系统。其主要问题是步长、初始化和正则化需要谨慎处理，以避免不稳定的尺度增长或较差驻点。

概括地说，核范数方法提供凸优化与恢复理论的标准基准；非凸分解方法牺牲凸性，但显著降低变量维度和单步计算成本，是大规模实现中的常用选择。

它和 PCA / SVD 是什么关系

若矩阵完整观测，问题 $\min_{\operatorname{rank}(\mathbf M)\le r}\|\mathbf Y-\mathbf M\|_F^2$ 的解由截断 SVD 给出，这是 Eckart-Young 定理的内容。矩阵补全可以看作该问题的缺失观测版本：目标函数只在 $\Omega$ 上计算误差，而不是在所有坐标上计算误差。

因此，不能简单地把缺失值填为 $0$ 后直接做 SVD。这样的处理把“未观测”误当成“观测值为零”，会改变目标函数并引入系统性偏差。

几个容易混淆的点

• 低秩是假设，不是结论。若真实矩阵没有足够强的低维结构，补全结果只能解释为模型近似。
• 可恢复性依赖采样机制。低秩但高度尖峰的矩阵，或严重非随机的缺失机制，都可能导致不可识别。
• 精确恢复与预测性能不同。推荐系统中常关心未观测条目的预测误差，而理论矩阵补全常讨论对 $\mathbf M^\ast$ 的精确或稳定恢复。
• 凸方法与非凸方法的差异主要在计算与理论取舍。凸方法更便于给出全局最优与恢复定理；非凸方法更适合大规模问题，但分析通常需要额外条件。

一句话总结

低秩矩阵补全的核心是：在低秩结构、适当采样与可控噪声条件下，用秩最小化的可计算替代或低秩分解方法，由部分观测估计完整矩阵；其关键困难同时来自统计可识别性、NP-hard 的原始秩优化以及大规模计算约束。