The Sharp Dimension Bound in the Johnson--Lindenstrauss Lemma

技術要約：ジョンソン＝リンデンシュトラウス補題における鋭い次元境界

問題提起
本論文は、計量埋め込み（metric embeddings）の根本的な問題、すなわち、$d$ 次元ユークリッド空間内の任意の $n$ 個の点集合 $X \subseteq \mathbb{R}^d$ を、歪み（distortion）が最大 $1+\varepsilon$ となるように $\mathbb{R}^r$ へ埋め込むための最小の整数 $r$ を決定する問題に取り組んでいる。ジョンソン＝リンデンシュトラウス（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 n$ という項を、$\varepsilon^2 n$ が $n$ に対して相対的に小さい領域において、$\log(2 + \varepsilon^2 n)$ に置き換えることができるかどうかが不明であった。

手法
著者は、目標次元が線形写像によって達成可能であることを示すことで、この予想を解決する。証明は、アルゴリズム的ディスクレパンシー理論（algorithmic discrepancy theory）に根ざした、新しい「ランク半減（rank-halving）」の手法に基づいている。

1. ランク半減ステップ (Theorem 1.2): コアとなる技術的貢献は、以下の補題である。$\mathbb{R}^{2r}$ 内の $m$ 個の単位ベクトルの集合に対して、ランクが最大 $r$ であり、かつ二次形式 $u_\ell^T M u_\ell$ が誤差 $O\left(\sqrt{\frac{\log(2 + m/r^2)}{r}}\right)$ で 1 を近似するような正定値行列 $M$ が存在する。

   • これは、標準的なガウス型ランダム射影がもたらす誤差 $O\left(\sqrt{\frac{\log(2 + m)}{r}}\right)$ を改善している。この改善は、対数の中の $m$ を $m/r^2$ に置き換えたことに由来する。
   • $M$ の構成には、対称行列の空間における適応的ランダムウォーク（ブラウン運動）を用いる。このプロセスは、Spencerの定理で用いられるLovett–Mekaのエッジウォークに類似した「部分彩色（partial-coloring）」の議論によって導かれる。
   • プロセスは、0 から始まる行列 $Q_t$ を進化させる。固有値が $\pm 1$ に達したときに固有方向を固定し、特定の二次形式が障壁 $b$ に達したときにそれらを固定する。これにより、指定された形式の歪みを制御しながらランクを減少させることが保証される。

2. 反復的な削減: メイン定理（Theorem 1.1）は、このランク半減ステップを反復することによって導かれる。点集合のアフィン包（次元 $\min\{d, n-1\}$）から出発し、次元を繰り返し半分に減らしていく。各ステップで導入される誤差は幾何級数的に収束する列を形成するため、総歪みを $1+\varepsilon$ 以下に抑えつつ、目標次元 $r \approx \frac{\log(2 + \varepsilon^2 n)}{\varepsilon^2}$ まで次元を削減することが可能となる。

3. 内積スケッチングへの接続: 本論文は、これらの結果を $\varepsilon$-内積スケッチングの問題にも適用する。線形次元削減と既存の低次元被覆推定を組み合わせることで、内積をスケッチするために必要な最小ビット数に関するAlonとKlartagの予想を解決する。

主要な結果

• Theorem 1.1 (主要結果): 任意の $n, d \ge 2$、$0 < \varepsilon < 1/2$、および $X \subseteq \mathbb{R}^d$ に対して、歪みが最大 $1+\varepsilon$ である線形写像 $L: \mathbb{R}^d \to \mathbb{R}^r$ が存在する。ここで、
  $$r \le C \min \left\{ d, n-1, \frac{\log(2 + \varepsilon^2 n)}{\varepsilon^2} \right\}$$
  これはLarsen–Nelson予想を肯定的に確認するものである。特筆すべきは、この埋め込みが、予想で許容されていた任意の（潜在的に非線形な）写像ではなく、周囲の空間上の線形作用素によって誘導されている点である。

• Theorem 1.3 (内積スケッチング): $D(n, \varepsilon) \le k \le n$（ここで $D(n, \varepsilon) = \varepsilon^{-2}\log(2+\varepsilon^2 n)$）である次元 $k$ の構成において、$\varepsilon$-内積スケッチに必要な最小ビット数 $f(n, k, \varepsilon)$ は $\Theta(n D(n, \varepsilon))$ である。これにより、高次元領域における既知の下界と上界の間のギャップが埋められた。

意義と主張
本論文は、ジョンソン＝リンデンシュトラウス補題における鋭い次元境界に関するLarsen–Nelson予想を解決したと主張している。その意義は主に以下の2点にある：

1. 最適性: 以前知られていた上界 $O(\varepsilon^{-2} \log n)$ が、すべてのパラメータ領域においてタイトではないことを確立した。具体的には、$\varepsilon^2 n \ll \log n$ の場合、要求される次元は $\log n$ ではなく $\log(2 + \varepsilon^2 n)$ にスケールし、大幅に小さくなる。
2. 線形性: この最適な次元が、線形写像によって達成可能であることを証明した。Larsen–NelsonやAlon–Klartagによる以前の下界は、非線形埋め込みに対しても成立していたが、上界については、より弱い $\log n$ の因子を持つ線形写像でのみ既知であった。本論文は、線形性が最適な次元においてペナルティを課さないことを示している。

著者は、行列の構成を（Lovett–Mekaのフレームワークに従って）離散化することで、埋め込み作用素を構築するための効率的なランダム化手順が得られると述べている。また、本研究は内積スケッチングのビット複雑性を完全に特徴付け、AlonとKlartagの予想に決着をつけるものである。