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

• arxiv url: http://arxiv.org/abs/2607.14304v2
• Date: Thu, 23 Jul 2026 05:48:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-24 14:12:06.722861
• Title: Spectral Concentration and Recovery in Sparse High-Dimensional Random Geometric Graphs
• Title（参考訳）: Sparse High-D Random Geometric Graphsにおけるスペクトル集中と回復
• Abstract要約: 高次元球面ベクトルや潜在ベクトルによって生成される幾何学的しきい値ランダムグラフについて検討する。 接続スケール $np=(log n)$ では、球面の隣接行列は高い確率で満足する。 これにより、Liu, Mohanty, Schramm, and Yang (2023) のスペクトル境界は弱い仮定の下で鋭くなり、同質な倉本モデルに対する Abdalla, Bandeira, Invernizzi (2024) のグローバル同期保証を強化する。
• 参考スコア（独自算出の注目度）: 6.217597733532163
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study sparse threshold random geometric graphs generated by high-dimensional spherical or Gaussian latent vectors. Although each edge has marginal probability $p$, shared latent variables make the adjacency entries dependent. At the connectivity scale $np=Ω(\log n)$, the spherical adjacency matrix satisfies, with high probability,$\|A-\mathbb E A\|_{\mathrm{op}}=O\left(\sqrt{np\log n}+npτ\right)$, where $τ$ is the cap threshold; an analogous estimate holds for Gaussian vectors after controlling radial fluctuations. This sharpens the spectral bound in Liu, Mohanty, Schramm, and Yang (2023) under weaker assumptions and strengthens the global-synchronization guarantee of Abdalla, Bandeira, and Invernizzi (2024) for the homogeneous Kuramoto model. The leading eigenspace also estimates the latent geometry. When $np\gg\log n$, vector and relative Gram-matrix errors vanish for$\log(1/p)\ll d\ll np\log(1/p)/\log n$ in the spherical model and $\log^2(1/p)\log n\ll d\ll np\log(1/p)/\log n$ in the Gaussian model, improving the recovery conditions of Li and Schramm (2023). For the Gaussian mixture block model introduced there, a polynomial-time semidefinite program gives, to our knowledge, the first exact-recovery guarantee at the connectivity scale in a moderate-separation regime. At much larger separation, fixed edge density creates isolated vertices and makes exact recovery impossible. Our reusable decoupling and matrix concentration framework avoids trace-moment methods and applies broadly to random graph models with latent vectors.
• Abstract（参考訳）: 本研究では, 高次元球面およびガウス潜在ベクトルによって生成されるスパースしきい値のランダムな幾何グラフについて検討する。 それぞれのエッジに辺りの確率は$p$であるが、共有潜伏変数は隣接エントリを依存させる。 接続スケール $np=Ω(\log n)$ では、球面隣接行列は高い確率で、$\|A-\mathbb E A\|_{\mathrm{op}}=O\left(\sqrt{np\log n}+npτ\right)$ を満たす。 これにより、Liu, Mohanty, Schramm, and Yang (2023) のスペクトル境界は弱い仮定の下で鋭くなり、同質な倉本モデルに対する Abdalla, Bandeira, Invernizzi (2024) のグローバル同期保証を強化する。 主固有空間もまた潜在幾何学を推定する。 np\gg\log n$, vector and relative Gram-matrix errors for$\log(1/p)\ll d\ll np\log(1/p)/\log n$ in the spherical model and $\log^2(1/p)\log n\ll d\ll np\log(1/p)/\log n$ in the Gaussian model, and improve the recovery conditions of Li and Schramm (2023)。 そこで導入されたガウス混合ブロックモデルに対し、多項式時間半定プログラムは、我々の知る限り、中間分離状態における接続スケールにおける最初の正確な回復保証を与える。 より大きな分離では、固定エッジ密度は孤立した頂点を生成し、正確な回復を不可能にする。 我々の再利用可能な疎結合および行列集中フレームワークは、トレースモーメント法を回避し、潜在ベクトルを持つランダムグラフモデルに広く適用する。

関連論文リスト

• 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)

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

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