The Sharp Dimension Bound in the Johnson--Lindenstrauss Lemma

技术摘要：Johnson–Lindenstrauss 引理中的锐利维度界限

问题陈述
本文探讨了度量嵌入（metric embeddings）中的基本问题：确定最小整数 $r$，使得任何位于 $d$ 维欧几里得空间中的 $n$ 个点集 $X \subseteq \mathbb{R}^d$，都能以最多 $1+\varepsilon$ 的失真嵌入到 $\mathbb{R}^r$ 中。Johnson–Lindenstrauss (JL) 引理确立了一个上界 $r = O(\varepsilon^{-2} \log n)$。然而，在全参数范围 $n, d, \varepsilon$ 内，最优目标维度的研究一直是一个悬而未决的问题。

Larsen 和 Nelson 曾提出一个猜想，认为最优维度为：
$$\Theta\left( \min \left\{ d, n-1, \frac{\log(2 + \varepsilon^2 n)}{\varepsilon^2} \right\} \right)$$
虽然 Alon 和 Klartag 最近已经确立了该猜想的下界，但其上界仍未得到证明。具体而言，目前尚不清楚在 JL 界限中，是否可以用 $\log(2 + \varepsilon^2 n)$ 替换标准的 $\log n$，特别是在 $\varepsilon^2 n$ 相对于 $n$ 较小的情形下。

方法论
作者通过证明该上界解决了这一猜想，并证明该目标维度可以通过一个线性映射来实现。该证明依赖于一种根植于算法差异理论（algorithmic discrepancy theory）的新型秩减半（rank-halving）技术。

1. 秩减半步骤（定理 1.2）： 核心技术贡献是一个引理，该引理指出：对于 $\mathbb{R}^{2r}$ 中的任意 $m$ 个单位向量，存在一个秩至多为 $r$ 的正定矩阵 $M$，使得二次型 $u_\ell^T M u_\ell$ 近似于 1，且误差由 $O\left(\sqrt{\frac{\log(2 + m/r^2)}{r}}\right)$ 限制。

   • 这改进了标准的随机高斯投影，后者的误差为 $O\left(\sqrt{\frac{\log(2 + m)}{r}}\right)$。改进之处在于将对数内部的 $m$ 替换为了 $m/r^2$。
   • $M$ 的构造利用了对称矩阵空间中的自适应随机游走（布朗运动）。这一过程受到类似于 Spencer 定理中 Lovett–Meka 边行进（edge-walk）的“部分着色”（partial-coloring）论证的引导。
   • 该过程演化一个从 0 开始的矩阵 $Q_t$。当特征值达到 $\pm 1$ 时，冻结特征方向；当特定的二次型达到障碍 $b$ 时，冻结这些二次型。这确保了在控制预设形式失真的同时，降低矩阵的秩。

2. 迭代缩减： 主定理（定理 1.1）是通过迭代秩减半步骤推导出来的。从点集的仿射扩张（维度为 $\min\{d, n-1\}$）开始，不断将维度减半。每一步引入的误差构成一个几何级数可求和的序列，从而使得总失真被控制在 $1+\varepsilon$ 以内，同时将维度降低到目标 $r \approx \frac{\log(2 + \varepsilon^2 n)}{\varepsilon^2}$。

3. 与内积草图（Inner Product Sketching）的联系： 本文还将这些结果应用于 $\varepsilon$-内积草图问题。通过将线性降维与现有的低维覆盖估计相结合，作者解决了 Alon 和 Klartag 关于草图内积所需最少比特数的猜想。

关键结果

• 定理 1.1（主要结果）： 对于任何 $n, d \ge 2$，$0 < \varepsilon < 1/2$ 以及 $X \subseteq \mathbb{R}^d$，存在一个线性映射 $L: \mathbb{R}^d \to \mathbb{R}^r$，其失真至多为 $1+\varepsilon$，其中：
  $$r \le C \min \left\{ d, n-1, \frac{\log(2 + \varepsilon^2 n)}{\varepsilon^2} \right\}$$
  这肯定地证实了 Larsen–Nelson 猜想。值得注意的是，该嵌入是由作用于环境空间的线性算子诱导的，这比猜想中所允许的任意（可能非线性）映射是一个更强的条件。

• 定理 1.3（内积草图）： 对于维度为 $k$ 且满足 $D(n, \varepsilon) \le k \le n$ 的配置（其中 $D(n, \varepsilon) = \varepsilon^{-2}\log(2+\varepsilon^2 n)$），实现 $\varepsilon$-内积草图所需的最小比特数 $f(n, k, \varepsilon)$ 为 $\Theta(n D(n, \varepsilon))$。这填补了高维情形下已知下界与上界之间的差距。

意义与主张
本文声称解决了关于 Johnson–Lindenstrauss 引理锐利维度界的 Larsen–Nelson 猜想。其意义主要体现在两个方面：

1. 最优性： 它确立了此前已知的 $O(\varepsilon^{-2} \log n)$ 上界在所有参数范围内并非都是紧致的。具体而言，当 $\varepsilon^2 n \ll \log n$ 时，所需的维度明显更小，其规模随 $\log(2 + \varepsilon^2 n)$ 而变化，而非 $\log n$。
2. 线性： 该结果证明了这一最优维度可以通过线性映射来实现。此前的 Larsen–Nelson 和 Alon–Klartag 的下界对于非线性嵌入也成立，但之前的上界仅已知可以通过具有较弱 $\log n$ 因子的线性映射来实现。本文表明，线性并不在最优维度上带来惩罚。

作者指出，可以对矩阵构造进行离散化（遵循 Lovett–Meka 框架），从而产生一种高效的随机化程序来构建嵌入算子。这项工作还对内积草图的比特复杂度进行了完整的表征，解决了 Alon 和 Klartag 的一个猜想。