論文の概要: Exact Limits of Random Projections for Preserving Geometry: Distance Recovery, Nearest-Neighbor Rankings, and Covariance Shape in Gaussian Models

• arxiv url: http://arxiv.org/abs/2609.02155v1
• Date: Wed, 02 Sep 2026 06:12:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-03 17:53:18.102145
• Title: Exact Limits of Random Projections for Preserving Geometry: Distance Recovery, Nearest-Neighbor Rankings, and Covariance Shape in Gaussian Models
• Title（参考訳）: 幾何保存のための厳密なランダム射影の限界:ガウスモデルにおける距離回復、最近傍ランク付け、共分散形状
• Abstract要約: Johnson-Lindenstrauss lemma は、$n$点のランダム射影が$m=O(varepsilon-2log n)$次元であることを保証する。 しかし、高次元では、距離はベースラインの周りに集中し、鍵となる幾何学的情報ははるかに小さなゆらぎにある。 したがって、JL 境界は残留幾何に対して非形式的であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Johnson-Lindenstrauss (JL) lemma guarantees that a random projection of $n$ points to $m=O(\varepsilon^{-2}\log n)$ dimensions preserves pairwise squared distances within relative error $\varepsilon$ with high probability, and this dimension order is asymptotically optimal. In high dimensions, however, distances concentrate around a baseline while key geometric information lies in much smaller fluctuations. We show that the JL bound can therefore be uninformative about retained geometry: an independent Gaussian replacement map can satisfy it even though the replacement cloud is independent of the original data. We then ask how well any decoder can recover a feature $f(D)$ of a squared distance $D$ from a linear sketch. Under squared-error loss, the optimal decoder is conditional expectation, so recovery defines a linear operator whose singular values quantify feature recovery. For isotropic Gaussian data ($Σ=σ^2 I_d$), we diagonalize this operator in closed form. For fixed $k$ with $m,d-m\to\infty$, its $k$th singular value satisfies $\ell_k\approx(m/ d)^{k/2}$. This yields three sharp consequences. A rank-$m$ sketch retains at most an $m/d$ fraction of the variance of any feature of one squared distance. If $m\to\infty$ and $m/d\to0$, the expected Kendall correlation is $\frac{2}π\sqrt{m/d}(1+o(1))$; for fixed $q$, nearest- neighbor agreement tends to $1/q$. Yet one projection can satisfy the JL bound while mean Kendall correlation vanishes when $\log n\ll m\ll d$. After removing scale, Haar-averaged retained covariance-shape information is $(m/d)^2$. Thus JL distance preservation does not quantify the geometry available for comparison or inference.
• Abstract（参考訳）: Johnson-Lindenstrauss (JL) 補題は、$n$点のランダムな射影が$m=O(\varepsilon^{-2}\log n)$次元が相対誤差$\varepsilon$の対角距離を高い確率で保存することを保証する。 しかし、高次元では、距離はベースラインの周りに集中し、鍵となる幾何学的情報ははるかに小さなゆらぎにある。 独立ガウス代入写像は、置換クラウドが元のデータとは独立であるにもかかわらず、それを満足させることができる。 次に、任意のデコーダが、線形スケッチから2乗距離$D$のフィーチャー$f(D)$を回復できるかどうかを尋ねる。 2乗誤差損失の下では、最適デコーダは条件付き期待であるので、リカバリは特異値が特徴回復を定量化する線形演算子を定義する。 等方的ガウスデータ(Σ=σ^2 I_d$)については、この作用素を閉形式で対角化する。 固定$k$と$m,d-m\to\infty$の場合、その$k$th特異値は$\ell_k\approx(m/d)^{k/2}$を満たす。 これは3つの急激な結果をもたらす。 階数-$m$スケッチは、少なくとも1平方距離の任意の特徴のばらつきの$m/d$分を保っている。 m\to\infty$ と $m/d\to0$ とすると、期待されるケンドール相関は $\frac{2}π\sqrt{m/d}(1+o(1))$ となる。 しかし、ある射影は JL 境界を満たすことができ、一方、Kendall の相関は $\log n\ll m\ll d$ のときに消える。 スケールを除去した後、平均的に保持される共分散形情報は$(m/d)^2$である。 したがって、JL距離保存は比較や推論に利用可能な幾何を定量化しない。

関連論文リスト

• Nonparametric MLE for Gaussian Location Mixtures: Certified Computation and Generic Behavior [28.71736321665378]
  一次元のガウス的位置混合に対する非パラメトリック最大度推定器$widehatpi$について検討する。 We provide a algorithm that for small enough $varepsilon>0$ computes a $varepsilon$-approximation of $widehatpi in Wasserstein distance。 また、$k$-atomicと条件付けられた$widehatpi$の分布は、関連する2k-1$次元パラメータ空間上の密度を許容することを示す。
  論文  参考訳（メタデータ） (2025-03-26T03:36:36Z)
• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
  我々は、$ell_p$ノルムや広範なヒンジ様損失関数のクラスから、様々な損失関数の下で、$k$スパース線形回帰の難読スケッチを研究する。 スパース$ell$varepsレグレッションの場合、$Theta(klog(d/k)/varepsilon2)$ rowsでスケッチの上に曖昧な分布が存在し、これは定数要素に固執することを示している。 また、$O(mu2 klog(mun d/varepsilon)/varのスケッチも示します。
  論文  参考訳（メタデータ） (2023-04-05T07:24:19Z)
• Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error [8.615625517708324]
  サンプルから標準ハイパーキューブの未知アフィン変換を学習するためのリアルタイムアルゴリズムを提案する。 本アルゴリズムは,証明書の要求が満たされない場合に,未知アフィン変換の推定を反復的に改善する手法に基づいている。
  論文  参考訳（メタデータ） (2023-02-23T19:13:30Z)
• Mean Estimation in High-Dimensional Binary Markov Gaussian Mixture Models [12.746888269949407]
  2進隠れマルコフモデルに対する高次元平均推定問題を考える。 ほぼ最小限の誤差率(対数係数まで)を $|theta_*|,delta,d,n$ の関数として確立する。
  論文  参考訳（メタデータ） (2022-06-06T09:34:04Z)
• Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
  本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。 近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。 副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
  論文  参考訳（メタデータ） (2022-02-22T04:14:45Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。 線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。 線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
  論文  参考訳（メタデータ） (2021-01-29T18:57:52Z)
• Consistent regression when oblivious outliers overwhelm [8.873449722727026]
  我々の研究に先立ち、ガウスの$X$でさえ、$beta*$ の見積子は、このモデルでは一貫性がないことが知られていた。 ほぼ線形なサンプルサイズと逆ポリノミアル不整分率で一貫した推定が可能であることを示す。 ここで研究したモデルは、最初の瞬間さえも持たない重い尾の雑音の分布も捉えている。
  論文  参考訳（メタデータ） (2020-09-30T16:21:34Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。