Low rank matrix completion(1)

什么是低秩矩阵补全

低秩矩阵补全（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 的原始秩优化以及大规模计算约束。

References

E. J. Candès and B. Recht, Exact Matrix Completion via Convex Optimization, Foundations of Computational Mathematics, 2009.
B. Recht, M. Fazel, and P. A. Parrilo, Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization, SIAM Review, 2010.
E. J. Candès and T. Tao, The Power of Convex Relaxation: Near-Optimal Matrix Completion, IEEE Transactions on Information Theory, 2010.
J.-F. Cai, E. J. Candès, and Z. Shen, A Singular Value Thresholding Algorithm for Matrix Completion, SIAM Journal on Optimization, 2010. 这是 SVT 算法的经典引用。
R. Mazumder, T. Hastie, and R. Tibshirani, Spectral Regularization Algorithms for Learning Large Incomplete Matrices, Journal of Machine Learning Research, 2010. 这是 Soft-Impute / 谱正则化路线的重要算法参考。
Z. Lin, M. Chen, L. Wu, and Y. Ma, The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices, arXiv, 2010. 这是 ALM / ADMM 类核范数低秩恢复算法的重要参考。
Y. Koren, R. Bell, and C. Volinsky, Matrix Factorization Techniques for Recommender Systems, Computer, 2009. 这是推荐系统中矩阵分解方法的经典综述。
P. Jain, P. Netrapalli, and S. Sanghavi, Low-Rank Matrix Completion using Alternating Minimization, STOC, 2013. 这是 ALS / alternating minimization 理论分析的重要参考。
B. Vandereycken, Low-Rank Matrix Completion by Riemannian Optimization, SIAM Journal on Optimization, 2013. 这是黎曼优化方法处理矩阵补全的经典参考。