論文の概要: A note on estimating the dimension from a random geometric graph
- arxiv url: http://arxiv.org/abs/2311.13059v1
- Date: Tue, 21 Nov 2023 23:46:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-23 16:44:37.520321
- Title: A note on estimating the dimension from a random geometric graph
- Title（参考訳）: ランダムな幾何学グラフからの次元推定に関する一考察
- Authors: Caelan Atamanchuk and Luc Devroye and Gabor Lugosi
- Abstract要約: グラフの隣接行列にアクセスする際に、基礎空間の次元$d$を推定する問題について検討する。
また、密度の条件がなければ、$d$の一貫した推定子は$n r_nd to infty$と$r_n = o(1)$が存在することを示す。
- 参考スコア（独自算出の注目度）: 2.3020018305241337
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Let $G_n$ be a random geometric graph with vertex set $[n]$ based on $n$
i.i.d.\ random vectors $X_1,\ldots,X_n$ drawn from an unknown density $f$ on
$\R^d$. An edge $(i,j)$ is present when $\|X_i -X_j\| \le r_n$, for a given
threshold $r_n$ possibly depending upon $n$, where $\| \cdot \|$ denotes
Euclidean distance. We study the problem of estimating the dimension $d$ of the
underlying space when we have access to the adjacency matrix of the graph but
do not know $r_n$ or the vectors $X_i$. The main result of the paper is that
there exists an estimator of $d$ that converges to $d$ in probability as $n \to
\infty$ for all densities with $\int f^5 < \infty$ whenever $n^{3/2} r_n^d \to
\infty$ and $r_n = o(1)$. The conditions allow very sparse graphs since when
$n^{3/2} r_n^d \to 0$, the graph contains isolated edges only, with high
probability. We also show that, without any condition on the density, a
consistent estimator of $d$ exists when $n r_n^d \to \infty$ and $r_n = o(1)$.
- Abstract（参考訳）: 頂点集合 $[n]$ を $n$ i.i.d.\ランダムベクトル $X_1,\ldots,X_n$ を未知密度 $f$ on $\R^d$ に基づいてランダムな幾何学グラフとする。
エッジ$(i,j)$は、与えられた閾値$r_n$に対して$\|X_i -X_j\| \le r_n$が存在し、おそらく$n$に依存する。
グラフの隣接行列にアクセスできるが、r_n$ やベクトル $x_i$ を知らない場合、基礎となる空間の次元 $d$ を推定する問題について検討する。
この論文の主な結果は、$n^{3/2} r_n^d \to \infty$と$r_n = o(1)$を持つすべての密度に対して$n \to \infty$として確率的に$d$に収束する$d$の推定子が存在することである。
この条件は、$n^{3/2} r_n^d \to 0$ であるとき、グラフは孤立エッジのみを含み、高い確率で表される。
また、密度の条件がなければ、$n r_n^d \to \infty$ と $r_n = o(1)$ のとき、$d$ の一貫した推定器が存在することを示す。
関連論文リスト
- Improved convergence rate of kNN graph Laplacians [11.93971616098517]
k$NNグラフの一般クラスで、グラフ親和性は$W_ij = epsilon-d/2 である。
制限多様体作用素に対する$k$NNグラフ Laplacian の点収束性を証明する。
論文 参考訳（メタデータ） (2024-10-30T17:01:00Z) - 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) - Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。
我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。
平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文 参考訳（メタデータ） (2023-04-17T10:38:08Z) - A spectral least-squares-type method for heavy-tailed corrupted
regression with unknown covariance \& heterogeneous noise [2.019622939313173]
重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。
本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
論文 参考訳（メタデータ） (2022-09-06T23:37:31Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-10T16:10:41Z) - Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
本稿では, ErdHos--R'enyi グラフに対するグラフマッチングやネットワークアライメントの問題を扱う。
これはグラフ同型問題のうるさい平均ケース版と見なすことができる。
論文 参考訳（メタデータ） (2021-10-11T05:07:50Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z) - The planted matching problem: Sharp threshold and infinite-order phase
transition [25.41713098167692]
ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。
任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
論文 参考訳（メタデータ） (2021-03-17T00:59:33Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳（メタデータ） (2020-11-21T01:33:15Z) - Optimal Coreset for Gaussian Kernel Density Estimation [0.8376091455761259]
点集合 $Psubset mathbbRd$ が与えられたとき、$P$ の核密度推定は [ overlinemathcalG_P(x) = frac1left|Pright|sum_pin Pe-leftlVert x-p rightrVert2 ] for any $xinmathbbRd$ と定義される。
我々は、小さなサブセット$Q$ of $P を構築する方法を研究する。
論文 参考訳（メタデータ） (2020-07-15T22:58:50Z) - Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss [76.02734481158458]
最悪の場合、行列に対する良いランク-$k$近似を得るには、任意に大きい$nOmega(1)$列数が必要であることが知られている。
最小かつ現実的な分布設定では、ほぼ線形な実行時間を持つ$(k/epsilon)$-approximationとpoly$(k/epsilon)+O(klog n)$ columnsが得られる。
これは、エントリワイズで$(k/epsilon)$-approximationを達成するための任意の種類の最初のアルゴリズムである
論文 参考訳（メタデータ） (2020-04-16T22:57:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。