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

関連論文リスト

• Structure Learning in Graphical Models from Indirect Observations [17.521712510832558]
  本稿では、パラメータ法と非パラメトリック法の両方を用いて、Rp$における$p$次元ランダムベクトル$Xのグラフィカル構造を学習する。 温和な条件下では、グラフ構造推定器が正しい構造を得ることができることを示す。
  論文  参考訳（メタデータ） (2022-05-06T19:24:44Z)
• Perturbation Analysis of Randomized SVD and its Applications to High-dimensional Statistics [8.90202564665576]
  一般の「信号+雑音」の枠組みによるRSVDの統計特性について検討する。 3つの統計的推論問題に適用した場合、RSVDのほぼ最適性能保証を導出する。
  論文  参考訳（メタデータ） (2022-03-19T07:26:45Z)
• 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)
• 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)
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization [49.090785356633695]
  非対称な低ランク分解問題: [mathbbRm min d , mathbfU$ および MathV$ について検討する。
  論文  参考訳（メタデータ） (2021-06-27T17:25:24Z)
• Parameter-free Statistically Consistent Interpolation: Dimension-independent Convergence Rates for Hilbert kernel regression [0.0]
  最近提案された重み付き補間近接補間法 (wiNN) はこのクラスに属する。 プラグインの余剰リスクは 2|f(x)-1/2|1-1-varepsilon) sigma(x)((n))-frac2$ 以下の任意の$に対して、$f$ は回帰関数 $xmapstomathbbE[yx]$ であることを示す。
  論文  参考訳（メタデータ） (2021-06-07T05:50:02Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)
• 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)

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

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