論文の概要: Spectral Concentration and Recovery in Sparse High-Dimensional Random Geometric Graphs

• arxiv url: http://arxiv.org/abs/2607.14304v1
• Date: Wed, 15 Jul 2026 19:09:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-17 17:01:32.892795
• Title: Spectral Concentration and Recovery in Sparse High-Dimensional Random Geometric Graphs
• Title（参考訳）: Sparse High-D Random Geometric Graphsにおけるスペクトル集中と回復
• Abstract要約: 本研究では,内積がしきい値を超える高次元ベクトルの対を連結したランダムな幾何グラフについて検討する。 球面モデルの場合、接続スケール $np=(log n)$ で、$|A-mathbb E A|=Oleft(sqrtnplog n+npright)$ を高い確率で証明する。
• 参考スコア（独自算出の注目度）: 6.217597733532163
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study sparse random geometric graphs generated by connecting pairs of high-dimensional vectors whose inner product exceeds a threshold. The latent vectors are sampled either uniformly from the sphere or from a standard Gaussian distribution. Although every edge appears with probability $p$, the edges are dependent through their shared latent vectors. For the spherical model, at the connectivity scale $np=Ω(\log n)$, we prove $\|A-\mathbb E A\|=O\left(\sqrt{np\log n}+npτ\right)$, with high probability, where $τ$ is the cap threshold. This sharpens the spectral norm bound of Liu, Mohanty, Schramm, and Yang (2023) under weaker assumptions. An analogous result holds for the Gaussian model after removing the fluctuations of the vector norms, yielding improved global synchronization guarantees for the homogeneous Kuramoto model. We then recover the latent geometry from the leading eigenspace. When $np\gg\log n$, both the latent vector and relative Gram matrix errors vanish provided $d\ll np\log(1/p)/\log n$. The required lower dimension is only $d\gg\log(1/p)$ for the spherical model and $d\gg\log^2(1/p)\log n$ for the Gaussian model, improving the recovery guarantees of Li and Schramm (2023). Finally, we prove the first exact recovery result for the Gaussian mixture block model of Li and Schramm (2023). At the optimal connectivity scale $np=Ω(\log n)$, a polynomial-time semidefinite program exactly recovers all labels in a moderate-separation regime, whereas larger separation makes exact recovery impossible because isolated vertices appear with high probability. Our proofs combine orthogonal polynomial expansions, decoupling, and matrix concentration, avoiding the trace-moment arguments used in previous work.
• Abstract（参考訳）: 本研究では,内積がしきい値を超える高次元ベクトルの対を連結したスパースランダムな幾何グラフについて検討した。 潜在ベクトルは球面から一様にサンプリングされるか、標準ガウス分布からサンプリングされる。 すべてのエッジは確率$p$で現れるが、エッジは共有潜在ベクトルを介して依存する。 球面モデルに対しては、接続スケール $np=Ω(\log n)$ において、$τ$ が上限閾値であるような高い確率で $\|A-\mathbb E A\|=O\left(\sqrt{np\log n}+npτ\right)$ を証明する。 これは、より弱い仮定の下で、Liu, Mohanty, Schramm, Yang (2023) のスペクトルノルム境界を鋭くする。 類似の結果は、ベクトルノルムのゆらぎを除去した後、ガウスモデルに対して成り立ち、同質な倉本モデルに対する大域的同期保証が向上する。 次に、先行固有空間から潜在幾何学を復元する。 np\gg\log n$ のとき、潜在ベクトルと相対的なグラム行列の誤差が消えると、$d\ll np\log(1/p)/\log n$ が得られる。 必要最低次元は球面モデルの$d\gg\log(1/p)$とガウスモデルの$d\gg\log^2(1/p)\log n$のみであり、Li と Schramm (2023) の回復保証を改善する。 最後に、Li と Schramm (2023) のガウス混合ブロックモデルに対する最初の正確な回復結果を証明した。 最適接続スケール $np=Ω(\log n)$ では、多項式時間半定プログラムは、中間分離状態の全てのラベルを正確に復元するが、より大きい分離は、分離された頂点が高い確率で現れるため、正確な回復を不可能にする。 我々の証明は直交多項式展開、デカップリング、行列濃度を組み合わせ、以前の研究で使われたトレースモーメントの議論を避ける。

関連論文リスト

• Spectral partitioning for $k$-block averaging kernels of finite Markov chains [2.9399121155604875]
  我々は,有限でエルゴード的で可逆なマルコフ連鎖に対する平均化カーネルを定義する状態空間分割を選択するアルゴリズムを開発した。 制御スペクトルグラフ,平均場イジングモデル,ベイズ変分選択実験は収束率と統計的推定において顕著に改善された。
  論文  参考訳（メタデータ） (2026-08-21T02:53:38Z)
• Recovery of latent inner products from an anisotropic Gaussian random geometric graph [10.573657119155916]
  異方性ガウス潜在点を持つランダムな幾何グラフから潜在内積を復元する問題について検討する。 潜在点の異方性によって増幅される望ましくない次数変動に対処するために、グラフの二重中心隣接行列を考える。
  論文  参考訳（メタデータ） (2026-07-26T15:39:14Z)
• Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs [8.162867143465382]
  我々はこの手法を利用して、平均ケースの複雑さにおいて広く信じられている予想の下で、いくつかの正準高次元統計モデルに対して、還元に基づく計算下界を確立する。 ガウス雑音を持つスパイクテンソルPCAの計算下界は、クラス内の他のガウス雑音分布にまで拡張可能であることを示す。
  論文  参考訳（メタデータ） (2025-10-08T17:16:36Z)
• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。 我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。 我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
  論文  参考訳（メタデータ） (2022-08-19T18:00:34Z)
• Structure Learning in Graphical Models from Indirect Observations [17.521712510832558]
  本稿では、パラメータ法と非パラメトリック法の両方を用いて、Rp$における$p$次元ランダムベクトル$Xのグラフィカル構造を学習する。 温和な条件下では、グラフ構造推定器が正しい構造を得ることができることを示す。
  論文  参考訳（メタデータ） (2022-05-06T19:24:44Z)
• Random Geometric Graphs on Euclidean Balls [2.28438857884398]
  ノード $i$ がユークリッド単位球上のランダム潜在点 $X_i$ に関連付けられたランダムグラフに対する潜在空間モデルを考える。 特定のリンク関数に対して、ここで考慮されたモデルは、パワーロー型の分布を持つ尾を持つ次数分布を持つグラフを生成する。
  論文  参考訳（メタデータ） (2020-10-26T17:21:57Z)
• Estimating Stochastic Linear Combination of Non-linear Regressions Efficiently and Scalably [23.372021234032363]
  サブサンプルサイズが大きくなると、推定誤差が過度に犠牲になることを示す。 私たちの知る限りでは、線形テキスト+確率モデルが保証される最初の研究です。
  論文  参考訳（メタデータ） (2020-10-19T07:15:38Z)
• 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)
• Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
  エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。 代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
  論文  参考訳（メタデータ） (2020-06-12T10:21:40Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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