論文の概要: 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であり、有限個の低次固有値に対して証明される。
この結果は、データが多様体上で一様にサンプリングされたときに非正規化およびランダムウォークグラフラプラシアンと、非一様サンプリングデータを持つ密度補正グラフラプラシアン(両辺の次数行列によってアフィニティ行列が正規化される)が成り立つ。
中間結果として,密度補正グラフラプラシアンに対する新しい点分割型およびディリクレ型収束率を示す。
理論を検証するために数値的結果が提供される。
関連論文リスト
- 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 [8.271859911016719]
双構造正規化グラフ Laplacian to manifold (weighted-)Laplacian は Sinkhorn-Knopp (SK) の反復によって効率的に計算できる。
多様体データが外乱ノイズによって破壊されるとき、理論的にはラプラシア点の整合性を証明する。
論文 参考訳（メタデータ） (2022-06-22T21:08:24Z) - Structure Learning in Graphical Models from Indirect Observations [17.521712510832558]
本稿では、パラメータ法と非パラメトリック法の両方を用いて、Rp$における$p$次元ランダムベクトル$Xのグラフィカル構造を学習する。
温和な条件下では、グラフ構造推定器が正しい構造を得ることができることを示す。
論文 参考訳（メタデータ） (2022-05-06T19:24:44Z) - Convergence of Laplacian Eigenmaps and its Rate for Submanifolds with
Singularities [0.0]
我々は、ユークリッド空間の部分多様体上のラプラシアンのスペクトル近似結果を、その部分多様体上のランダムな点から構築された$epsilon$-neighborhood graphによって特異性を持つ。
論文 参考訳（メタデータ） (2021-10-15T15:06: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) - Accelerated Gradient Tracking over Time-varying Graphs for Decentralized
Optimization [77.57736777744934]
この論文は、広く使用されている加速勾配追跡を再検討し、拡張する。
私たちの複雑さは $cal O(frac1epsilon5/7)$ と $cal O(fracLmu)5/7frac1 (1-sigma)1.5logfrac1epsilon)$ で大幅に改善します。
論文 参考訳（メタデータ） (2021-04-06T15:34:14Z) - High-Dimensional Gaussian Process Inference with Derivatives [90.8033626920884]
低データ状態の$ND$では、Gram行列は$mathcalO(N2D + (N2)3)$に推論のコストを下げる方法で分解できることを示す。
最適化や予測勾配を持つハミルトニアンモンテカルロなど、機械学習に関連する様々なタスクでこの可能性を実証する。
論文 参考訳（メタデータ） (2021-02-15T13:24:41Z) - Convergence of Graph Laplacian with kNN Self-tuned Kernels [14.645468999921961]
自己チューニングされたカーネルは、各点に$sigma_i$ を $k$-nearest neighbor (kNN) 距離で適応的に設定する。
本稿では、グラフラプラシアン作用素$L_N$を、kNN自己チューニングカーネルの新しい族に対する多様体(重み付き)ラプラシアンに収束することを証明する。
論文 参考訳（メタデータ） (2020-11-03T04:55:33Z) - 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) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-30T19:10:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。