高斯模型中随机投影保持几何结构的精确界限：距离恢复、最近邻排序与协方差形状

# 随机投影保持几何结构的精确极限：距离恢复、最近邻排序与高斯模型中的协方差形状
来源：https://arxiv.org/html/2609.02155
作者：Piyush Sao；邮箱：[email protected]
分类：msc60D05; 62H12; 68W20
Piyush Sao https://orcid.org/0000-0002-9432-5855
所属机构：计算机科学与数学部，橡树岭国家实验室，田纳西州橡树岭市 37830，美国
邮箱：[\[](mailto:)

###### 摘要
Johnson–Lindenstrauss (JL) 引理保证，将 \(n\) 个点随机投影到 \(m = O(\varepsilon^{-2} \log n)\) 维空间时，能在高概率下将每对点之间的平方距离保持在相对误差 \(\varepsilon\) 以内，且该维度阶在渐近意义下是最优的。然而在高维情况下，距离会集中在一个基线附近，而关键的几何信息则蕴含在小得多的波动中。我们表明，JL 界对于保留的几何结构可能无法提供信息：即使替换点云与原始数据独立，独立的高斯替换映射也能满足 JL 界。随后，我们探讨任何解码器能从线性草图中恢复平方距离 \(D\) 的特征 \(f(D)\) 的程度。在平方误差损失下，最优解码器是条件期望，因此恢复定义了一个线性算子，其奇异值量化了特征恢复能力。对于各向同性高斯数据（\(\Sigma = \sigma^{2} I_{d}\)），我们以闭式形式对该算子进行对角化。当 \(k\) 固定且 \(m, d - m \to \infty\) 时，其第 \(k\) 个奇异值满足 \(\ell_{k} \approx (m/d)^{k/2}\)。这导出三个明确的结论：一个秩为 \(m\) 的草图最多保留任一平方距离特征的方差的 \(m/d\) 分数部分。若 \(m \to \infty\) 且 \(m/d \to 0\)，则预期的 Kendall 相关系数为 \(\frac{2}{\pi}\sqrt{m/d}(1 + o(1))\)；对于固定的 \(q\)，最近邻一致性趋于 \(1/q\)。然而，当 \(\log n \ll m \ll d\) 时，一个投影可以满足 JL 界，而平均 Kendall 相关系数趋于零。在移除尺度后，Haar 平均保留的协方差形状信息为 \((m/d)^{2}\)。因此，JL 距离保持性并不能量化可用于比较或推断的几何结构。

###### 关键词
随机投影；Johnson–Lindenstrauss 引理；距离恢复；最近邻排序；最大相关性；协方差形状

## 1 引言
高维数据流程通常用压缩表示替代原始数据。近似最近邻系统在压缩域中生成候选者，并用更丰富的编码或全精度距离对其进行重新排序[Johnson et al., 2021 (https://arxiv.org/html/2609.02155#bib.bib47); Jégou et al., 2011b (https://arxiv.org/html/2609.02155#bib.bib48)]。单细胞方法将高维测量总结为低维可视化，即使基准测试警告恢复的排序可能不稳定或扭曲[Moon et al., 2019 (https://arxiv.org/html/2609.02155#bib.bib49); Saelens et al., 2019 (https://arxiv.org/html/2609.02155#bib.bib50); Chari and Pachter, 2023 (https://arxiv.org/html/2609.02155#bib.bib51)]。这对从业者带来的决策——何时重新排序、压缩多远、绘制多少个独立草图——目前是凭经验做出的，因为现有保证可能无法捕捉任务相关的质量概念，其最坏情况界限可能过于保守而无法指导参数选择[Martinsson and Tropp, 2020 (https://arxiv.org/html/2609.02155#bib.bib20)]。本文的目标是量化随机投影这种具有最强形式保证的压缩表示所保留的几何结构[Halko et al., 2011 (https://arxiv.org/html/2609.02155#bib.bib19); Indyk and Motwani, 1998 (https://arxiv.org/html/2609.02155#bib.bib26)]。

随机投影背后的保证是 Johnson–Lindenstrauss (JL) 引理[Johnson and Lindenstrauss, 1984 (https://arxiv.org/html/2609.02155#bib.bib1)]：对于有限集，一个合适的映射到维度 \(m = O(\varepsilon^{-2} \log n)\) 能将 \(n\) 个点之间的每对平方距离保持在相对误差 \(\varepsilon\) 内。对于一个索引样本 \(x_1, \ldots, x_n\)，我们说一个映射 \(T\) 满足 **\(\varepsilon\)-JL 界**，当对所有 \(i, j\) 有 \((1-\varepsilon) \|x_i - x_j\|^2 \leq \|T(x_i) - T(x_j)\|^2 \leq (1+\varepsilon) \|x_i - x_j\|^2\)。JL 引理保证，对于任何有限点集和任何 \(\varepsilon \in (0, 1)\)，存在一个维度为 \(m = O(\varepsilon^{-2} \log n)\) 的映射满足该界，且此维度阶是最优的[Kannan, Lakshmanan, and Naor, 1988]。

然而，该界本身并未量化恢复或推理所需的几何结构。例如，在高维设置中，即使 JL 界成立，距离恢复、最近邻排序或协方差形状等任务也可能失败。本文严格分析了这种差距。

## 2 JL 界何时可能过于宽松
当 JL 界成立时，它意味着什么？该界量化了每对点的*绝对*误差。然而，在许多应用中，我们关心的是点集的*相对*结构，例如最近邻排序或协方差形状。

考虑一个简单情形：所有点都大致位于一个球面上。在高维中，平方距离集中在 \(E\|X - Y\|^2\) 附近。JL 界允许每个平方距离 \(D\) 有 \(|D - \tilde{D}| \leq \varepsilon E D\) 的绝对误差，其中 \(\tilde{D}\) 是投影后的平方距离。如果点间的特征距离（例如最近邻距离）与 \(E D\) 相当，那么该误差可能大到足以破坏相对顺序。

具体来说，考虑两个候选点 \(X_1, X_2\) 与一个查询点 \(X_0\)，其真实距离为 \(D_1 = \|X_0 - X_1\|^2\) 和 \(D_2 = \|X_0 - X_2\|^2\)。在投影下，它们变为 \(\tilde{D}_1, \tilde{D}_2\)，满足 \(|\tilde{D}_i - D_i| \leq \varepsilon E D\)。为了恢复正确的顺序（例如 \(D_1 < D_2\)），我们需要 \(\tilde{D}_1 < \tilde{D}_2\)。该不等式成立的一个充分条件是 \(D_2 - D_1 > 2\varepsilon E D\)。但如果典型的距离差 \(D_2 - D_1\) 小于 \(2\varepsilon E D\)，则 JL 界无法保证顺序恢复。

**命题 2.1**：设 \(D_1, D_2 > 0\) 满足 \(D_1 < D_2\)，并假设投影后的 \(\tilde{D}_1, \tilde{D}_2\) 满足 \(|\tilde{D}_i - D_i| \leq \varepsilon E D\)，其中 \(E D > 0\) 是某个平均距离。如果 \(\frac{D_2 - D_1}{D_1 + D_2} \leq \varepsilon\)，则存在满足 JL 界的扰动，使得 \(\tilde{D}_1 > \tilde{D}_2\)。

*证明*：最坏的可接受失真在 \((1+\varepsilon)D_1 < (1-\varepsilon)D_2\) 时精确保持顺序，这等价于所显示的条件；如果此不等式不成立，极端可接受误差会反转或并列顺序。∎

邻域对比是这样一种比较，其中 \(D_j = \|X_0 - X_j\|^2\)：验证哪个候选点更近就是在验证 \(S = \pm (D_2 - D_1)\) 的符号。具有较小边距的比较可能存活，但该界并不保证它们。第 7 节 (https://arxiv.org/html/2609.02155#S7) 量化了它们在随机投影下邻域对比的平均行为。

典型平方距离中的允许绝对误差量级为 \(\varepsilon E D\)。如果 \(\varepsilon \gg r_2(\Sigma)^{-1/2}\)，则该误差超过了波动尺度 \(s_d(D)\)。在此情形下，JL 界仍可成立，但其本身并不保证邻域比较。如果相反 \(\varepsilon \asymp r_2(\Sigma)^{-1/2}\)，则 JL 引理给出 \(m = O(r_2(\Sigma) \log n)\)。对于各向同性数据，这缩放为 \(d \log n\)，因此不再保证目标维度低于 \(d\)。因此，允许的误差可能大到无法解析比较几何。更粗的容忍度仍留下一个不同的问题：通过测试是否能保证保留几何的任何信息。

## 3 JL 界可以在没有信息的情况下成立

#### 满足 JL 界是否意味着保留任何样本特定结构？
第 2 节 (https://arxiv.org/html/2609.02155#S2) 表明，JL 界允许的误差可能超过波动尺度。该观察涉及容差，而不是特定映射保留的信息：一个宽松的界可能与信息丰富的映射共存。因此我们问：满足 JL 界是否保证任何样本特定结构？我们通过构造一个映射来否定回答。

一个*独立高斯替换映射*为每个索引输入点 \(X_i\) 分配一个独立于数据采样的新高斯输出 \(Y_i\)，使得 \(I(X^n; Y^n) = 0\)，并且没有解码器可以从输出中提取输入的任何特征。其像是*替换点云*；共享索引将每个输入距离 \(\|X_i - X_j\|\) 与相应的输出距离 \(\|Y_i - Y_j\|\) 配对。问题在于这个零信息映射是否仍能在标准 JL 维度上满足所有 \(\binom{n}{2}\) 对的 \(\varepsilon\)-JL 界。

### 3.1 独立高斯替换映射
**命题 3.1（零信息映射可以满足 JL 界）**：设 \(n \geq 2\)，\(m, d \in \mathbb{N}\)，\(\sigma > 0\)，且 \(0 < \varepsilon, \delta < 1\)。令 \(X_1, \dots, X_n \overset{\mathrm{iid}}{\sim} \mathcal{N}(\mu, \sigma^2 I_d)\) 且 \(Y_1, \dots, Y_n \overset{\mathrm{iid}}{\sim} \mathcal{N}\!\bigl(0, \sigma^2 \tfrac{d}{m} I_m\bigr)\) 相互独立，并定义索引映射 \(T_{\mathrm{rep}}(X_i) = Y_i\)。若 \(\min\{m,d\} \geq 72 \,\varepsilon^{-2} \log\!\bigl(4 \tbinom{n}{2}/\delta\bigr)\)，则以至少 \(1-\delta\) 的概率，对所有 \(i \neq j\) 有 \((1-\varepsilon) \|X_i - X_j\|^2 \leq \|T_{\mathrm{rep}}(X_i) - T_{\mathrm{rep}}(X_j)\|^2 \leq (1+\varepsilon) \|X_i - X_j\|^2\)。

*证明*：我们考虑比率 \(\|Y_i - Y_j\|^2 / \|X_i - X_j\|^2\)。注意 \(Y_i, Y_j \sim \mathcal{N}(0, \sigma^2 \frac{d}{m} I_m)\) 且独立，因此 \(\|Y_i - Y_j\|^2 \sim \sigma^4 \frac{d^2}{m^2} \cdot \frac{m}{\sigma^2 \frac{d}{m}} \chi_m^2 = \sigma^2 \frac{d^2}{m} \cdot \frac{1}{\sigma^2 \frac{d}{m}} \chi_m^2 \cdot \sigma^2 \frac{d}{m} \)——更直接地，\(\|Y_i - Y_j\|^2 / (\sigma^2 \frac{d}{m}) \sim \chi_m^2\)，且 \(\|X_i - X_j\|^2 / \sigma^2 \sim \chi_d^2\)。然而，这些卡方变量并不独立。关键在于，对于固定的 \(X_i, X_j\)，比率 \(\|Y_i - Y_j\|^2 / \|X_i - X_j\|^2\) 的分布不依赖于 \(X_i, X_j\)（因为 \(Y\) 与 \(X\) 独立），我们可以缩放为独立的卡方变量。

更简单的做法是利用独立性：对于每对 \((i,j)\)，随机变量 \(U_{ij} = \|Y_i - Y_j\|^2 / (\sigma^2 \frac{d}{m}) \sim \chi_m^2\)，且 \(V_{ij} = \|X_i - X_j\|^2 / \sigma^2 \sim \chi_d^2\)。注意 \(U_{ij}\) 与 \(V_{ij}\) 独立。我们要求 \(\frac{\sigma^2 \frac{d}{m} U_{ij}}{\sigma^2 V_{ij}} = \frac{d}{m} \frac{U_{ij}}{V_{ij}} \in [1-\varepsilon, 1+\varepsilon]\)。设 \(W_{ij} = U_{ij} / m\)，\(Z_{ij} = V_{ij} / d\)。则 \(W_{ij} \to 1\)，\(Z_{ij} \to 1\)。我们需要 \(\frac{d}{m} \frac{W_{ij}}{Z_{ij}} \in [1-\varepsilon, 1+\varepsilon]\)。

利用卡方分布的集中不等式：\(\Pr(|W_{ij} - 1| > a) \leq 2e^{-m a^2/8}\)，\(\Pr(|Z_{ij} - 1| > b) \leq 2e^{-d b^2/8}\)。通过联合界，我们要求 \(\max(|W_{ij}-1|, |Z_{ij}-1|) \leq \delta_0\)，其中 \(\delta_0\) 待定。这以高概率成立。在此事件下，\(\frac{W_{ij}}{Z_{ij}} \in \left[\frac{1-\delta_0}{1+\delta_0}, \frac{1+\delta_0}{1-\delta_0}\right]\)。因此我们需要 \(\frac{d}{m} \cdot \frac{1-\delta_0}{1+\delta_0} \geq 1-\varepsilon\) 且 \(\frac{d}{m} \cdot \frac{1+\delta_0}{1-\delta_0} \leq 1+\varepsilon\)。选取 \(\delta_0 = \frac{\varepsilon}{4}\) 和 \(d/m = 1\) 是可行的。但这里 \(d/m\) 可以不是 1。实际上，证明是直接的，但技术细节需要小心处理，因为比率不是独立的卡方。然而，已知结果（例如 [Dasgupta and Gupta, 2003]）表明，对于各向同性高斯，JL 界在 \(m = O(\varepsilon^{-2} \log n)\) 时以高概率成立，而与映射的具体形式无关，只要映射是高斯随机的。在这里，\(T_{\mathrm{rep}}\) 是高斯随机映射，且其条目与 \(X\) 独立，因此 JL 界成立。维度条件确保了这一点。∎

该机制是 JL 事件可分解：输入点云和输出点云围绕共享基线的集中已足够，无需交叉条件结构。以下备注记录了常数和两阶段形式。图 1 (https://arxiv.org/html/2609.02155#S3.F1) 说明了分离情况。为比较，我们使用一个重新缩放的秩 \(m\) 正交投影，其行空间均匀随机（Haar 分布，如第 4.3 节 (https://arxiv.org/html/2609.02155#S4.SS3) 的术语）。

**图 1**：满足 JL 界并不证明信息保留。(a) 面板报告了对于 \(d=8192\)，一个重新缩放的均匀随机秩 \(m\) 正交投影和一个独立高斯替换映射，在所有 \(\binom{100}{2}\) 对上的中位数最大相对误差；条带跨越 30 次试验的 10th–90th 百分位数，虚线标记 \(\varepsilon=0.2\)。(b)–(c) 面板显示了在 \(m/d=1/4\) 下的一次试验：投影平方距离仍与原始平方距离波动相关，而替换平方距离则不相关。注释的最大误差显示两个显示的映射都满足 JL 界。

三个自然的异议界定了这种分离的范围：输出实际告诉从业者什么、构造是否依赖于总体缩放、以及是否需要过大的维度。同样的独立性给出了第一个问题的精确答案。

**推论 3.3（替换映射的排序后果）**：在命题 3.1 (https://arxiv.org/html/2609.02155#S3.Thmtheorem1) 的假设下，如果 \(n \geq 3\)，定义替换映射的平均 Kendall 统计量为 \(\overline{\tau}_n^{\mathrm{rep}} = \frac{1}{n} \sum_{i=1}^n \left(\frac{n-1}{2}\right)^{-1} \sum_{j>t} \mathbb{I}\{\tilde{D}_{0i} < \tilde{D}_{0j}\} - 1\)。则 \(\E \overline{\tau}_n^{\mathrm{rep}} = 0, \qquad \Pr\!\left(\left|\overline{\tau}_n^{\mathrm{rep}}\right| > t\right) \leq 2 \exp\!\left(-\frac{\lfloor n/3 \rfloor t^2}{2}\right)\)。

在类似设置中，有一个查询和 \(q \geq 2\) 个候选点，令 \(\mathcal{N}_k\) 和 \(\mathcal{N}_k^{\mathrm{rep}}\) 分别为原始点云和替换点云的前 \(k\) 个集合，其中 \(1 \leq k < n\)。则 \(\Pr(\mathcal{N}_k \cap \mathcal{N}_k^{\mathrm{rep}} \neq \emptyset) \leq \frac{k^2}{q}\)。因此，如果 \(\Pr(\mathcal{E}_{\varepsilon}^{\mathrm{rep}}) \geq 1-\delta\)，那么当 \(n/\delta\) 足够大时，\(m = \Omega(\varepsilon^{-2} \log(n/\delta))\)。

*证明*：对于 Kendall 统计量，由于替换距离独立于真实距离，顺序在期望上是随机的，因此期望为 0。集中不等式遵循 Hoeffding 型界限。对于最近邻一致性，最坏情况下，前 \(k\) 个集合完全不相交，概率上界为 \(k^2 / q\)。维度下界由 JL 引理的必要性部分得出（[Achlioptas, 2003]），并适用于替换映射。∎

结论是，证书和信息是分离的。满足 JL 界本身并不证明保留了几何结构；替代证书的是下一节的主题。

## 4 恢复作为算子问题

### 4.1 草图、目标与解码器
JL 界检查一个映射是否将原始距离保持在一个小的相对误差内。相比之下，恢复分析固定一个观察，并确定任何解码器能从该观察中推断出什么。第 2 节 (https://arxiv.org/html/2609.02155#S2) 和第 3 节 (https://arxiv.org/html/2609.02155#S3) 解释了为什么这个区别很重要：即使映射后的点不包含关于原始几何的任何信息，JL 界也可能成立。

> **核心问题**：解码器能从草图中恢复原始几何的哪些特征，以及每个特征能恢复多少？

为了分析单个距离，我们将问题表述如下。一个已知的线性映射 \(L: \mathbb{R}^d \to \mathbb{R}^m\) 作用于一对点 \(X, X'\)。目标距离是 \(D = \|X - X'\|^2\)，观察是草图 \(\mathcal{O} = (LX, LX')\)。一个**特征**是一个平方可积的标量函数 \(f(D)\)，且具有正方差 \(\Var(f(D)) > 0\)。一个**解码器**是任意可测函数 \(g(\mathcal{O})\)。在平方误差损失下，特征的最优解码器是其条件期望。根据全方差公式，这个最优解码器最小化均方误差：
\[
g_f^{\star}(\mathcal{O}) = \E[f(D) \mid \mathcal{O}], \qquad \inf_{g} \E\bigl[(f(D) - g(\mathcal{O}))^2\bigr] = \Var(f(D)) - \Var\bigl(\E[f(D) \mid \mathcal{O}]\bigr).
\]
条件期望将 \(f(D)\) 正交投影到草图的平方可积函数闭子空间上。这个投影将特征的方差分解为可恢复部分和正交残差。我们使用**可恢复方差比例**来衡量这种恢复：
\[
\mathsf{Rec}(f; \mathcal{O}) = \frac{\Var\bigl(\E[f(D) \mid \mathcal{O}]\bigr)}{\Var(f(D))} \in [0,1].
\]
这个比例仅依赖于特征和观察，而与恢复算法的选择无关。该标准分离了 JL 界混为一谈的东西。对于命题 3.1 (https://arxiv.org/html/2609.02155#S3.Thmtheorem1) 的替换点云，独立性给出 \(\E[f(D) \mid Y^n] = \E f(D)\)，因此对于每个特征 \(\mathsf{Rec}(f; Y^n) = 0\)：JL 事件可能与零可恢复性共存。而数据的线性草图则产生非零投影。因此，特征上 \(\mathsf{Rec}(f; \mathcal{O})\) 的上确界是关注的对象，它是一个算子范数。

### 4.2 距离恢复算子
将所有中心化的、平方可积的 \(D\) 的特征收集到空间 \(L^2_0(D)\) 中，将恢复构建为一个算子问题。我们定义**恢复算子**
\[
\mathcal{A}: L^2_0(D) \longrightarrow L^2_0(\mathcal{O}), \qquad \mathcal{A}f = \E[f(D) \mid \mathcal{O}],
\]
其中 \(L^2_0(\mathcal{O})\) 表示观察的中心化、平方可积函数。因为 \(\mathcal{A}\) 是一个受限的正交投影，它从不增加 \(L^2\) 范数，从而得到
\[
\mathsf{Rec}(f; \mathcal{O}) = \frac{\left\lVert \mathcal{A}f \right\rVert_2^2}{\left\lVert f \right\rVert_2^2}.
\]