Fugu-MT 論文翻訳(概要): Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation

論文の概要: 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であり、有限個の低次固有値に対して証明される。この結果は、データが多様体上で一様にサンプリングされたときに非正規化およびランダムウォークグラフラプラシアンと、非一様サンプリングデータを持つ密度補正グラフラプラシアン(両辺の次数行列によってアフィニティ行列が正規化される)が成り立つ。中間結果として,密度補正グラフラプラシアンに対する新しい点分割型およびディリクレ型収束率を示す。理論を検証するために数値的結果が提供される。