矩阵填充
- 提出者
- Emmanuel Candès & Benjamin Recht
- 年份
- 2009
- 类型
- Convex low-rank recovery
- 类别
- Missing data
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
矩阵填充是一种从其少量、可能随机的条目子集中恢复低秩矩阵的技术。该技术由 Emmanuel Candès 和 Benjamin Recht 于 2009 年提出,它将问题重新表述为核范数最小化——这是秩最小化的凸松弛——并提供了理论保证,即当条目均匀随机观测且矩阵满足不相干条件时,可以实现精确恢复。
方法背后的直觉
设想一个部分填写的用户-电影评分电子表格,其中大部分单元格为空。如果底层数据具有简单的结构——例如,品味可以通过少数几个潜在因素来解释,如类型偏好和时代——那么即使只知道一小部分评分也足以自信地填补其余部分。矩阵填充利用了这种隐藏的低维结构,就像在知道拼图只有几种不同形状的情况下完成拼图一样。
历史学
矩阵填充源于压缩感知文献。Candès 和 Recht (2009) 通过核范数最小化建立了第一个精确恢复定理,随后 Candès 和 Tao 的关于不相干性的研究也紧随其后。该方法通过 Netflix Prize 竞赛获得了广泛的公众关注,其中低秩协同过滤方法在推荐准确性方面达到了最先进水平。Recht、Fazel 和 Parrilo 后续的工作将核范数最小化与机器学习中的迹范数正则化联系起来。
何时使用
当数据可以组织成具有系统性缺失条目的矩阵,并且有理由相信真实信号具有低秩时(例如,在推荐系统、基因组学、社交网络分析和图像恢复中),请使用矩阵填充。关键假设是条目是随机缺失的,并且矩阵满足不相干条件。它不适用于具有结构性或非随机缺失、秩非常高或低秩假设不成立的矩阵。替代方法包括用于一般缺失数据的 MICE 插补以及在需要非负性时的 NMF。
局限与注意事项
- 半定规划的计算成本随矩阵维数的增加而呈不良比例增长
- 不相干假设在具有结构性缺失或异常值的真实数据集中可能失效
- 当真实秩远小于矩阵维数时,性能会下降
- 核范数最小化可能对噪声敏感;鲁棒变体增加了额外的复杂性
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 在温和条件下,通过多项式时间凸规划可证明精确恢复
- 当矩阵确实是低秩时,可处理非常高的缺失率
- 不需要预先了解秩;核范数最小化会隐式地找到它
- 强大的理论保证植根于随机矩阵理论和凸分析
应用
- 协同过滤和推荐系统(预测用户-项目评分)
- 基因组学和生物信息学(恢复具有缺失测量的基因表达矩阵)
- 计算机视觉(图像修复和视频背景减除)
- 传感器网络定位(从部分距离测量中恢复位置矩阵)
- 神经科学(从部分 fMRI 观测中完成功能连接矩阵)
使用方式
使用方式
算法从一个条目仅在索引集 Omega 上可观测的矩阵 M 开始。这些可观测值构成了恢复问题的约束。假设稀疏模式是均匀随机采样的,这是建立精确恢复保证的理论环境。
公式
\text{Given } M \in \mathbb{R}^{n_1 \times n_2},\; \text{observe entries } \{M_{ij}\}_{(i,j)\in\Omega}由于直接最小化矩阵的秩是 NP-难的,Candès 和 Recht 提出最小化核范数——奇异值之和——作为凸松弛。核范数在矩阵中的作用与 L1 范数在压缩感知中的向量作用相同:它在保持问题可通过半定规划处理的同时,促进低秩解。
公式
\min_{X} \|X\|_* \quad \text{subject to} \quad X_{ij} = M_{ij},\; \forall (i,j)\in\Omega为了实现恢复,真实矩阵的奇异向量不能与标准基过于对齐,这由不相干参数 mu 量化。能量集中在少数行或列中的矩阵是不相干的;高度局部化的矩阵违反了此条件,并且无法从随机样本中恢复,因为过多的信息被编码在未观测的条目中。
公式
\max_{i} \|U^\top e_i\|^2 \leq \frac{\mu r}{n_1},\quad \max_{j} \|V^\top e_j\|^2 \leq \frac{\mu r}{n_2}当观测到的条目数超过与 mu 乘以秩 r 乘以 n log n 成比例的阈值时,核范数问题的最小化器会以高概率精确恢复真实矩阵。该结果表明,所需的样本量仅比秩 r 矩阵的内在自由度大对数多项式倍,使得该方法在信息论上接近最优。
公式
\text{If } |\Omega| \geq C \cdot \mu r n \log n,\; \text{then } \hat{X} = M \text{ with high probability}常见陷阱
- 假设均匀随机缺失,而实际观测是用户选择的或有偏的(例如,只对评分高的项目进行评分),这违反了理论采样模型
- 忽略检查不相干条件,即使有足够的观测值也会导致恢复效果不佳
- 在噪声环境下使用核范数最小化而未进行缩放或正则化,此时精确恢复公式不适用
- 将矩阵填充与矩阵分解启发式方法混淆:交替最小二乘法可能会收敛到局部最小值,并且缺乏核范数最小化的恢复保证
常见问题
核范数最小化是解决矩阵填充的唯一方法吗?
不是。交替最小二乘法 (ALS) 和分解形式上的梯度下降(例如,对 UV^T ≈ M 的 U 和 V 进行 SGD)在实践中因其可扩展性而被广泛使用。然而,这些非凸方法缺乏核范数最小化的精确恢复保证,并且在没有仔细初始化的情况下可能收敛到局部最小值。
需要多少数据才能精确恢复?
Candès 和 Recht 表明,对于不相干参数为 mu 的 n×n 秩为 r 的矩阵,大约 C·mu·r·n·log(n) 个观测到的条目就足够了。在实践中,这意味着一个低秩矩阵通常可以从仅是其内在自由度(对于 n×n 矩阵,其内在自由度为 r(2n−r))的几倍的样本中恢复出来。
什么是“不相干条件”以及为什么它很重要?
不相干性衡量奇异向量在坐标基上的分散程度。奇异向量集中的矩阵——例如,仅在一个行中非零的秩 1 矩阵——将其大部分信息存储在一小组条目中。如果这些条目碰巧未被观测到,无论其他条目有多少已知,都无法恢复。
相关方法
参考文献
Candès, E. J., & Recht, B. (2009). Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6), 717–772.
打开 DOI 文献已复制。