低秩分布矩阵补全

# 低秩分布矩阵补全
来源：https://arxiv.org/html/2606.04176

###### 摘要

我们研究矩阵补全问题的一种分布泛化形式，其中目标矩阵的每个条目是一个概率分布而非标量。在该设定下，仅能观察到矩阵的一部分条目，且即使是观测到的条目，其底层分布也无法直接获取；相反，我们只能观测到从这些分布中抽取的有限样本。为表示分布型条目，我们采用核均值嵌入，并为取值于分布的矩阵引入一种 Tucker 秩概念，以捕捉其低秩结构。核嵌入的无穷维性质带来了显著的方法论挑战。为解决这一问题，我们引入函数展开算子，将所提出的分布低秩结构与有限维张量的经典 Tucker 秩关联起来。基于这一框架，我们提出了一种新的分布矩阵补全估计器。我们建立了非渐近误差界来刻画该估计器的统计性能。在合成数据与真实应用上的大量实验验证了所提方法的有效性。

## 1 引言

低秩矩阵补全旨在从部分观测且可能受污染的数据矩阵中恢复缺失条目，其中低秩假设作为关键的结构正则化器，有助于识别。由于灵活有效，低秩矩阵补全广泛应用于推荐系统（Kang 等，2016（https://arxiv.org/html/2606.04176#bib.bib17）；Gurini 等，2018（https://arxiv.org/html/2606.04176#bib.bib14）；Chen 等，2021（https://arxiv.org/html/2606.04176#bib.bib8）；Zhang 等，2021（https://arxiv.org/html/2606.04176#bib.bib40））、信号处理（Weng and Wang，2012（https://arxiv.org/html/2606.04176#bib.bib36）；Zhang and Zhang，2020（https://arxiv.org/html/2606.04176#bib.bib41）；Chen 等，2023（https://arxiv.org/html/2606.04176#bib.bib5）；Yuchi 等，2023（https://arxiv.org/html/2606.04176#bib.bib39））、图像恢复（Changjun 等，2012（https://arxiv.org/html/2606.04176#bib.bib4）；Cao 等，2014（https://arxiv.org/html/2606.04176#bib.bib3）；Zheng 等，2024（https://arxiv.org/html/2606.04176#bib.bib43））及数据插补（Chen 等，2017（https://arxiv.org/html/2606.04176#bib.bib6），2020（https://arxiv.org/html/2606.04176#bib.bib7）；Xu 等，2023（https://arxiv.org/html/2606.04176#bib.bib38））等领域。大量工作致力于矩阵补全的理论与算法发展。然而，大多数现有方法针对标量值矩阵设计，无法直接扩展至条目为非标量的目标矩阵。

在本文中，我们研究条目为概率分布的矩阵补全问题。作为一个激励性例子，考虑建模每日出租车行程数量在起点和终点位置之间的分布（见第 7 节（https://arxiv.org/html/2606.04176#S7）），以捕捉交通流量的总量与变异性。另一个例子来自对上市公司季度盈利预估的分析，目标是研究不同银行和交易员所发布预估的分布。在该设定中，公司索引行，跨多个年度的财政季度索引列；详细讨论见Feitelberg 等（2024（https://arxiv.org/html/2606.04176#bib.bib10））的第 1.1 节。对于观测到的条目，底层分布可从相应样本中推断。然而在实践中，某些条目可能完全缺失。在出租车行程例子中，缺失可能源于行程记录不完整或某些位置 GNSS 覆盖有限。在盈利预估例子中，公司可能不定期发布信息，导致特定季度或时间段的条目缺失。这些挑战凸显了有效插补缺失分布条目的需求。

据我们所知，目前仅有 Feitelberg 等（2024（https://arxiv.org/html/2606.04176#bib.bib10））明确研究了分布矩阵补全问题。在该工作中，作者提出使用基于最近邻的方法来插补缺失条目。具体来说，对于位置 \((i,j)\) 处的缺失条目，利用在重叠列上的平均经验 2- Wasserstein 距离来识别与可用观测相似的列，然后选取这些邻接行在列 j 上对应的分布，并计算其经验 Wasserstein 重心来估计缺失分布。该方法依赖于一个简化的观测设定：列 j 对所有选定的邻接行都是观测的，且每个邻接行在列 j 上的样本数 N 相同。此外，最终估计由从估计分布生成的 N 个合成样本表示，这要求 N 足够大以准确恢复底层分布。此外，由于计算多元分布的 2- Wasserstein 距离及 Wasserstein 重心存在计算挑战，该算法不易推广至多维分布设定。相比之下，我们的方法允许更一般的观测模式：允许不同观测条目的样本数不同，并自然扩展到多维分布数据。

我们使用核均值嵌入（KME）表示分布条目，从而将概率分布嵌入到希尔伯特空间中，避免了显式的流形约束。与 Feitelberg 等（2024（https://arxiv.org/html/2606.04176#bib.bib10））的最近邻策略不同，我们的方法基于经验风险最小化框架，并通过精心设计的正则化在分布矩阵上施加全局低秩结构。所提出的低秩结构受张量分析中 Tucker 分解（Tucker，1966（https://arxiv.org/html/2606.04176#bib.bib32））的启发，但在一个更具挑战性的设定下运行，其中一个模态是无穷维的。为应对这一挑战，我们引入展开算子，将分布矩阵映射到两个空间的张量积中（见定义 3.1（https://arxiv.org/html/2606.04176#S3.Thmtheorem1）），并对相应的诱导线性算子施加核范数正则化以促进低秩性。这一建模策略同时能在核均值嵌入的函数分量中鼓励内在降维，并在相关的期望泛函矩阵（定义见（5）（https://arxiv.org/html/2606.04176#S3.E5））中诱导低秩结构。尽管分布表示的无穷维性质带来了优化挑战，但我们证明，通过适当正则化并利用底层核的再生性质，解具有有限维表示。因此，所提出的优化问题可使用凸算法高效求解。

在理论方面，我们建立了跨所有矩阵条目的聚合最大均值差异（MMD）的误差界。我们表明，尽管用函数表示替代标量带来了额外的技术挑战，但所得速率与经典核范数正则化矩阵补全（针对近似低秩矩阵）的速率相匹配。值得注意的是，与 Feitelberg 等（2024（https://arxiv.org/html/2606.04176#bib.bib10））不同，我们的相合性保证并不要求每个观测条目的样本数趋于无穷。

## 2 问题设定

设 \(\mathcal{X} \subseteq \mathbb{R}^d\)，并记 \(\mathcal{P}(\mathcal{X})\) 为取值于 \(\mathcal{X}\) 的随机变量的概率分布的全体。考虑一个取值于分布的矩阵 \(\rho^* \in \mathcal{P}(\mathcal{X})^{m_1 \times m_2}\)，其 \((i,j)\) 条目 \(\rho^*(i,j)\) 是 \(\mathcal{X}\) 上的一个概率分布。本文的目标是从部分且间接的观测中恢复 \(\rho^*\)。具体来说，仅对 \(\rho^*\) 的条目子集有观测，且即使对于这些观测到的条目，其底层分布也无法直接获取。相反，对于每个观测条目 \((i,j)\)，我们收集 i.i.d. 样本 \(X_1^{(ij)},\dots,X_{N_{ij}}^{(ij)} \sim \rho^*(i,j)\)，其中 \(N_{ij}\) 表示条目 \((i,j)\) 的样本量。令 \(T(i,j) \in \{0,1\}\) 为表示分布 \(\rho^*(i,j)\) 是否被观测的指示变量：若从 \(\rho^*(i,j)\) 收集了样本，则 \(T(i,j)=1\)；否则 \(T(i,j)=0\)。因此，观测数据为
\[
\{ X_1^{(ij)},\dots,X_{N_{ij}}^{(ij)} : T(i,j)=1, i=1,\dots,m_1, j=1,\dots,m_2 \}.
\]
在整篇文章中，我们假设集合 \(\{ (T(i,j), X_1^{(ij)},\dots,X_{N_{ij}}^{(ij)}) : i=1,\dots,m_1, j=1,\dots,m_2 \}\) 是相互独立的。

有多种常见方式来表示 \(\mathcal{X}\) 上的一个分布，例如概率质量/密度函数和累积分布函数。然而，这些经典函数表示大多具有流形约束。为了避免流形约束，核均值嵌入（KME）已成为将概率分布嵌入到希尔伯特空间的流行工具。它允许分布被视为再生核希尔伯特空间（RKHS）中的元素（例如 Smola 等，2007（https://arxiv.org/html/2606.04176#bib.bib30）；Muandet 等，2017（https://arxiv.org/html/2606.04176#bib.bib27））。此外，KME 支持从样本的高效经验估计，并具有一种自然度量——最大均值差异（MMD），可在广泛的机器学习任务中促进分布比较与学习（Gretton 等，2012（https://arxiv.org/html/2606.04176#bib.bib13））。更具体地，MMD 定义为
\[
\mathrm{MMD}(\rho_1,\rho_2;\mathcal{H}) := \sup_{\substack{\|f\|_{\mathcal{H}}\le 1}} \left( \mathbb{E}_{X\sim\rho_1}[f(X)] - \mathbb{E}_{Y\sim\rho_2}[f(Y)] \right) = \| \mathbb{E}_{X\sim\rho_1} K(X,\cdot) - \mathbb{E}_{Y\sim\rho_2} K(Y,\cdot) \|_{\mathcal{H}},
\]
其中 \(K:\mathcal{X}\times\mathcal{X}\to\mathbb{R}\) 是再生核，\(\mathcal{H}\) 为关联的 RKHS。

在本文中，我们用对应的 KME 表示目标分布值矩阵 \(\rho^* \in \mathcal{P}(\mathcal{X})^{m_1 \times m_2}\) 的条目。具体地，对每个 \((i,j)\)，定义
\[
\mu^*(i,j,\cdot) = \mathbb{E}_{X\sim\rho^*(i,j)} K(X,\cdot) \in \mathcal{H}. \tag{1}
\]
当核 \(K\) 是特征性的（例如高斯核和拉普拉斯核）时，KME 是单射的，这意味着底层分布 \(\rho^*(i,j)\) 由 \(\mu^*(i,j,\cdot)\) 唯一确定（Sriperumbudur 等，2010（https://arxiv.org/html/2606.04176#bib.bib31））。因此，恢复取值分布的矩阵 \(\rho^*\) 等价于恢复其 KME 矩阵 \(\mu^*\)。在后续中，我们专注于完成 KME 矩阵 \(\mu^* \in \mathcal{H}^{m_1 \times m_2}\) 的问题。

## 3 低秩建模

遵循经典噪声矩阵补全文献（例如 Klopp，2014（https://arxiv.org/html/2606.04176#bib.bib18）；Candes and Plan，2010（https://arxiv.org/html/2606.04176#bib.bib2）），我们旨在对 \(\mu^*\) 施加合适的“低秩”结构假设，以从部分观测中促进恢复。我们首先观察到，KME 矩阵 \(\mu^*\) 可自然视为一个三阶张量，取值于张量积空间 \(\mathbb{R}^{m_1} \otimes \mathbb{R}^{m_2} \otimes \mathcal{H}\)。我们的目标是在 Tucker 意义上对 \(\mu^*\) 施加低秩结构。注意，与标准张量学习设定不同，最后一个空间 \(\mathcal{H}\) 通常是无穷维的，从而得到一个部分无穷维的张量：前两个模态具有有限边际维数，而最后一个模态具有无穷边际维数。为了处理这类张量，我们需要更复杂的数学构造来研究多重线性秩。

受函数展开算子概念的启发（Wang 等，2022（https://arxiv.org/html/2606.04176#bib.bib35）），我们定义了三个展开算子，将 \(\mu^*\) 映射到两个空间的张量积中，从而诱导出秩可表征的线性算子。注意，张量积空间 \(\mathbb{R}^{m_1} \times \mathbb{R}^{m_2} \times \mathcal{H}\) 是所有形如 \(a_1 \otimes a_2 \otimes h\) 的初等张量在内积
\[
\langle a_1 \otimes a_2 \otimes h, a_1' \otimes a_2' \otimes h' \rangle_{\mathbb{R}^{m_1} \times \mathbb{R}^{m_2} \times \mathcal{H}} = (a_1^\intercal a_1')(a_2^\intercal a_2')\langle h, h' \rangle_{\mathcal{H}}
\]
下的线性张成的完备化，其中 \(a_1,a_1' \in \mathbb{R}^{m_1}\)，\(a_2,a_2' \in \mathbb{R}^{m_2}\)，\(h,h' \in \mathcal{H}\)。

###### 定义 3.1.
展开算子 \(\mathcal{U}_j\)，\(j=1,2,3\)，对任意初等张量 \(a_1 \otimes a_2 \otimes h\) 定义如下：
\[
\begin{aligned}
\mathcal{U}_1 &: \mathbb{R}^{m_1} \otimes \mathbb{R}^{m_2} \otimes \mathcal{H} \to \mathbb{R}^{m_1} \otimes (\mathbb{R}^{m_2} \otimes \mathcal{H}), \\
\mathcal{U}_1(a_1 \otimes a_2 \otimes h) &= a_1 \otimes (a_2 \otimes h); \\
\mathcal{U}_2 &: \mathbb{R}^{m_1} \otimes \mathbb{R}^{m_2} \otimes \mathcal{H} \to \mathbb{R}^{m_2} \otimes (\mathbb{R}^{m_1} \otimes \mathcal{H}), \\
\mathcal{U}_2(a_1 \otimes a_2 \otimes h) &= a_2 \otimes (a_1 \otimes h); \\
\mathcal{U}_3 &: \mathbb{R}^{m_1} \otimes \mathbb{R}^{m_2} \otimes \mathcal{H} \to \mathcal{H} \otimes (\mathbb{R}^{m_1} \otimes \mathbb{R}^{m_2}), \\
\mathcal{U}_3(a_1 \otimes a_2 \otimes h) &= h \otimes (a_1 \otimes a_2).
\end{aligned}
\]