論文の概要: Eigen-convergence of Gaussian kernelized graph Laplacian by manifold
heat interpolation
- arxiv url: http://arxiv.org/abs/2101.09875v1
- Date: Mon, 25 Jan 2021 03:22:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2021-03-14 19:15:36.985236
- Title: Eigen-convergence of Gaussian kernelized graph Laplacian by manifold
heat interpolation
- Title（参考訳）: 多様体熱補間によるガウス核化グラフラプラシアンの固有収束
- Authors: Xiuyuan Cheng, Nan Wu
- Abstract要約: グラフラプラシアンのラプラス・ベルトラミ作用素へのスペクトル収束について検討する。
データは$d$次元多様体上で均一にサンプリングされる。
密度補正グラフ Laplacian に対する新しい点和およびディリクレ形式収束率を証明した。
- 参考スコア（独自算出の注目度）: 16.891059233061767
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: This work studies the spectral convergence of graph Laplacian to the
Laplace-Beltrami operator when the graph affinity matrix is constructed from
$N$ random samples on a $d$-dimensional manifold embedded in a possibly high
dimensional space. By analyzing Dirichlet form convergence and constructing
candidate approximate eigenfunctions via convolution with manifold heat kernel,
we prove that, with Gaussian kernel, one can set the kernel bandwidth parameter
$\epsilon \sim (\log N/ N)^{1/(d/2+2)}$ such that the eigenvalue convergence
rate is $N^{-1/(d/2+2)}$ and the eigenvector convergence in 2-norm has rate
$N^{-1/(d+4)}$; When $\epsilon \sim N^{-1/(d/2+3)}$, both eigenvalue and
eigenvector rates are $N^{-1/(d/2+3)}$. These rates are up to a $\log N$ factor
and proved for finitely many low-lying eigenvalues. The result holds for
un-normalized and random-walk graph Laplacians when data are uniformly sampled
on the manifold, as well as the density-corrected graph Laplacian (where the
affinity matrix is normalized by the degree matrix from both sides) with
non-uniformly sampled data. As an intermediate result, we prove new point-wise
and Dirichlet form convergence rates for the density-corrected graph Laplacian.
Numerical results are provided to verify the theory.
- Abstract（参考訳）: 本研究は,ラプラス・ベルトラミ作用素に対するグラフラプラシアンのスペクトル収束を,高次元空間に埋め込まれた$d$次元多様体上の$N$ランダムなサンプルからグラフアフィニティ行列を構築するときの研究である。
ディリクレ形式収束を解析し、ガウス核との畳み込みにより近似固有関数を構成することにより、核帯域幅パラメータ $\epsilon \sim (\log n/n)^{1/(d/2+2)}$ を、固有値収束率 $n^{-1/(d/2+2)}$ とし、2-ノルムにおける固有ベクトル収束率 $n^{-1/(d/2+4)}$; $\epsilon \sim n^{-1/(d/2+3)}$ とすると、固有値と固有ベクトル率は$n^{-1/(d/2+3)}$となる。
これらのレートは最大で$\log n$ factorであり、有限個の低次固有値に対して証明される。
この結果は、データが多様体上で一様にサンプリングされたときに非正規化およびランダムウォークグラフラプラシアンと、非一様サンプリングデータを持つ密度補正グラフラプラシアン(両辺の次数行列によってアフィニティ行列が正規化される)が成り立つ。
中間結果として,密度補正グラフラプラシアンに対する新しい点分割型およびディリクレ型収束率を示す。
理論を検証するために数値的結果が提供される。
関連論文リスト
- Improved convergence rate of kNN graph Laplacians [11.93971616098517]
k$NNグラフの一般クラスで、グラフ親和性は$W_ij = epsilon-d/2 である。
制限多様体作用素に対する$k$NNグラフ Laplacian の点収束性を証明する。
論文 参考訳（メタデータ） (2024-10-30T17:01:00Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳（メタデータ） (2022-08-18T09:19:01Z) - Bi-stochastically normalized graph Laplacian: convergence to manifold Laplacian and robustness to outlier noise [10.418647759223965]
双確率正規化 (bi-stochastic normalization) はグラフベースのデータ解析においてグラフラプラシアンの代替正規化を提供する。
両階層正規化グラフ Laplacian から (重み付き) Laplacian への収束を速度で証明する。
多様体データが外乱ノイズによって破損した場合、理論的にはラプラシア点の整合性を証明する。
論文 参考訳（メタデータ） (2022-06-22T21:08:24Z) - Structure Learning in Graphical Models from Indirect Observations [17.521712510832558]
本稿では、パラメータ法と非パラメトリック法の両方を用いて、Rp$における$p$次元ランダムベクトル$Xのグラフィカル構造を学習する。
温和な条件下では、グラフ構造推定器が正しい構造を得ることができることを示す。
論文 参考訳（メタデータ） (2022-05-06T19:24:44Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - Random Geometric Graphs on Euclidean Balls [2.28438857884398]
ノード $i$ がユークリッド単位球上のランダム潜在点 $X_i$ に関連付けられたランダムグラフに対する潜在空間モデルを考える。
特定のリンク関数に対して、ここで考慮されたモデルは、パワーロー型の分布を持つ尾を持つ次数分布を持つグラフを生成する。
論文 参考訳（メタデータ） (2020-10-26T17:21:57Z) - Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative
GLASSO and Projection [58.5350491065936]
グラフ Laplacian 行列 $L$ 上の構造的仮定を考える。
最初の$K$ eigenvectors of $L$は、例えばドメイン固有の基準に基づいて事前選択される。
本稿では,H_u+$$$$barC$で最も適切なグラフラプラシアン行列$L*を計算するために,効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-10-25T18:12:50Z) - Lipschitz regularity of graph Laplacians on random data clouds [1.2891210250935146]
グラフポアソン方程式の解に対する高確率内部および大域リプシッツ推定を証明した。
我々の結果は、グラフラプラシア固有ベクトルが、高い確率で、本質的には、対応する固有値に明示的に依存する定数を持つリプシッツ正則であることが示せる。
論文 参考訳（メタデータ） (2020-07-13T20:43:19Z) - 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) - A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian
Kernel, a Precise Phase Transition, and the Corresponding Double Descent [85.77233010209368]
本稿では、データサンプルの数が$n$である現実的な環境で、ランダムフーリエ(RFF)回帰の正確さを特徴付けます。
この分析はまた、大きな$n,p,N$のトレーニングとテスト回帰エラーの正確な推定も提供する。
論文 参考訳（メタデータ） (2020-06-09T02:05:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。