Skip to content
返回搜索结果

矩阵填充

提出者
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 观测中完成功能连接矩阵)

使用方式

使用方式

1

算法从一个条目仅在索引集 Omega 上可观测的矩阵 M 开始。这些可观测值构成了恢复问题的约束。假设稀疏模式是均匀随机采样的,这是建立精确恢复保证的理论环境。

公式
\text{Given } M \in \mathbb{R}^{n_1 \times n_2},\; \text{observe entries } \{M_{ij}\}_{(i,j)\in\Omega}
2

由于直接最小化矩阵的秩是 NP-难的,Candès 和 Recht 提出最小化核范数——奇异值之和——作为凸松弛。核范数在矩阵中的作用与 L1 范数在压缩感知中的向量作用相同:它在保持问题可通过半定规划处理的同时,促进低秩解。

公式
\min_{X} \|X\|_* \quad \text{subject to} \quad X_{ij} = M_{ij},\; \forall (i,j)\in\Omega
3

为了实现恢复,真实矩阵的奇异向量不能与标准基过于对齐,这由不相干参数 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}
4

当观测到的条目数超过与 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 矩阵——将其大部分信息存储在一小组条目中。如果这些条目碰巧未被观测到,无论其他条目有多少已知,都无法恢复。

相关方法

参考文献

  1. Candès, E. J., & Recht, B. (2009). Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6), 717–772.

    打开 DOI 文献
    已复制。