技术摘要：通过平方和方法与改进的聚类算法实现非球形混合模型的降维

1. 问题陈述

本文解决了对具有任意协方差（非球形）的高维高斯混合模型（GMM）进行聚类的问题。具体而言，给定来自 $k$ 个 $d$ 维高斯分布的 $i.i.d.$ 样本 $P = \sum_{i=1}^k w_i \mathcal{N}(\mu_i, \Sigma_i)$，其中 $k \ll d$，目标是将数据进行划分，使得误分类点的比例很小（至多为 1%）。

假设这些分量在全变差（Total Variation, TV）距离下是“充分分离”的，即 $d_{TV}(\mathcal{N}(\mu_i, \Sigma_i), \mathcal{N}(\mu_j, \Sigma_j)) \ge 1 - f(w_{\min})$，其中 $w_{\min}$ 是最小混合权重。作者专注于两种特定的设定：

1. 中心化混合（Centered Mixtures）： 所有分量的均值为零（$\mu_i = 0$），但具有任意协方差 $\Sigma_i$。
2. 等协方差混合（Identical-Covariance Mixtures）： 所有分量共享同一个未知的协方差 $\Sigma$，但具有不同的均值 $\mu_i$。

在此项工作之前，针对非球形混合模型的现有最先进算法在样本和时间复杂度上需要 $d^{\Omega(k)}$，即使是在这些结构化设定下也是如此。这与可以实现 $d^{O(1)}$ 时间复杂度的球形混合模型形成了鲜明对比。$d^{\Omega(k)}$ 的障碍得到了统计查询（Statistical Query, SQ）和平方和（Sum-of-Squares, SoS）下界 [DKS17, DKPP24] 的支持，这些下界表明，对于一般的非球形混合模型，此类成本是必要的。

zeta 2. 方法论与核心技术思想

其核心贡献是一种基于平方和（SoS）方法的全新降维子程序。该子程序能够识别输入数据的低维投影，该投影能够保留至少一对分量之间的分离度，从而允许算法进行部分聚类并进行迭代。

2.1 前期工作的瓶颈

以往的方法（例如 [BK20, DHKK20]）依赖于证明数据在所有方向上的“反集中”（anti-concentration）性质以区分不同分量。对于非球形混合模型，这种认证需要匹配 $\Omega(k)$ 阶矩，从而导致了 $d^{\Omega(k)}$ 的复杂度。作者观察到，对于中心化分量或等协方差这些特定设定，用于证明下界的“硬实例”（即平行饼干/parallel pancakes 构建）并不适用，因为这些构建依赖于非零均值和指数级小的权重。

2.2 SoS 降维方法

作者开发了一种技术，可以在不需要匹配高阶矩的情况下找到“分离方向”。该方法包括：

1. 构建约束条件： 在单位向量 $v$ 上构建一个多项式不等式系统 $A(v)$，用以刻画“球形方向”（即方差接近 1 的方向）或正交于分离方向的方向。

   • 对于中心化混合： 作者利用了四阶矩张量。他们观察到，虽然对称化的四阶矩张量是高秩且难以直接分解的，但向量 $v$ 为“球形”的条件（即对于所有 $i$， $v^\top \Sigma_i v \approx 1$）可以通过涉及四阶矩形式的海森矩阵（Hessian）的系统来捕捉。具体而言，如果 $\langle M_4, v^{\otimes 4} \rangle \approx 0$ 且 $\nabla^2_v \langle M_4, v^{\otimes 4} \rangle \approx 0$，则 $v$ 接近于偏差矩阵 $(\Sigma_i - I)$ 的核（kernel）。
   • 对于等协方差混合： 作者利用了 [BS23] 的结果，该结果表明具有相同协方差的混合模型无法匹配标准高斯的头 $O(\log k)$ 阶矩。他们基于前 $O(\log k)$ 阶矩构建约束，以识别方差接近 1 的方向。

2. SoS 舍入（Rounding）： 该约束系统 $A(v)$ 定义了一组向量。作者使用 SoS 舍入算法（定理 4.1 和 4.2）来恢复一个包含 $A(v)$ 解（或与它们正交）的低维子空间。

   • 至关重要的是，所需的 SoS 证明阶数对于中心化混合是常数阶，对于等协方差混合是 $O(\log k)$ 阶。这种低阶特性使得算法的运行时间为 $d$ 的多项式时间（具体为 $d^{O(1)}$ 或 $d^{O(\log k)}$），而不是 $d^{\Omega(k)}$。

3. 迭代聚类： 一旦找到了包含分离方向的低维子空间，算法会将数据投影，执行简单的阈值处理以将混合模型拆分为两部分（部分聚类），然后在生成的子集上进行递归。

3. 主要结果

论文提出了两个主要定理，为上述两种设定提供了高效算法。

定理 1.1：中心化高斯混合

对于具有最小权重 $w_{\min}$ 且满足两两 TV 分离的 $k$ 个中心化高斯混合模型，存在一个算法可以实现：

• 样本复杂度： $n \ge \text{poly}(d) \cdot f(w_{\min}^{-1})$。
• 时间复杂度： $\text{poly}(d) \cdot f(w_{\min}^{-1})$。
• 保证： 输出的聚类具有 $O(k w_{\min}^{-1} \max\{\epsilon, k^{-k}\})$ 的误分类误差，其中 $\epsilon$ 是离群点比例。
• 意义： 对维度 $d$ 的依赖是一个固定的多项式，完全独立于 $k$。这打破了此前认为必须存在的 $d^{\Omega(k)}$ 障碍。

定理 1.2：等协方差高斯混合

对于具有 $k$ 个高斯分量、相同的未知协方差 $\Sigma$、最小权重 $w_{\min}$ 且满足两两 TV 分离的混合模型：

• 样本复杂度： $n \ge d^{O(\log w_{\min}^{-1})} \cdot f(w_{\min}^{-1})$。
• 时间复杂度： $d^{O(\log^2 w_{\min}^{-1})} \cdot f(w_{\min}^{-1})$。
• 保证： 与中心化情况类似的误分类界限。
• 意义： 虽然对 $d$ 的依赖（$d^{\text{polylog}(k)}$）比中心化情况略高，但仍比之前的 $d^{\Omega(k)}$ 界限有了指数级的提升。

推论：子空间聚类

作为直接应用，作者提供了一个针对高斯子空间聚类（其中各分量支撑在不同的子空间上）的离群点鲁棒算法，其时间与样本复杂度为 $\text{poly}(d) \cdot f(w_{\min}^{-1})$。

4. 意义与主张

作者声称，在现有硬度结果的背景下，他们的结果是令人惊讶的。针对非球形混合模型的 $d^{\Omega(k)}$ 下界 [DKS17, DKPP24] 是基于涉及非零均值和指数级小权重的“平行饼干”构建。通过将问题限制在中心化分量或等协方差范围内，作者展示了可以绕过这些硬度障碍。

• 打破障碍： 本工作表明，对于一类“极其广泛的”非球形混合模型（中心化或等协方差），聚类的成本可以从 $d^{\Omega(k)}$ 降低到 $d^{O(1)}$ 或 $d^{\text{polylog}(k)}$。
• 方法论进步： 本文引入了一种新的基于 SoS 的降维技术，避免了对高阶矩匹配的需求。它不再试图通过高阶张量恢复完整的结构，而是利用低阶 SoS 证明来识别与分离相关的特定子空间。
• 鲁棒性： 这些算法自然地扩展到可以容忍与维度无关的任意比例的离群点。

作者承认了 [DKK+25] 最近的一个下界（晚于本预印本），该结果显示在等协方差情况下存在 $d^{\Omega(\log k)}$ 的 SQ 下界。这证实了虽然 $d^{\Omega(k)}$ 障碍已被打破，但等协方差情况下的 $d^{O(1)}$ 障碍在 SQ 模型下无法被改进到 $d^{O(1)}$，这突显了中心化设定与等协方差设定之间的差异。

总之，本文提供了第一类针对具有零均值或等协方差的非球形高斯混合模型的有效聚类算法，其运行时间相对于维度 $d$ 是多项式级别的（具有常数或多对数幂次），显著改进了此前 $d^{\Omega(k)}$ 的最先进水平。