論文の概要: Lipschitz regularity of graph Laplacians on random data clouds
- arxiv url: http://arxiv.org/abs/2007.06679v2
- Date: Wed, 20 Oct 2021 22:18:57 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-10 23:50:51.102217
- Title: Lipschitz regularity of graph Laplacians on random data clouds
- Title（参考訳）: ランダムデータ雲上のグラフラプラシアンのリプシッツ正則性
- Authors: Jeff Calder and Nicolas Garcia Trillos and Marta Lewicka
- Abstract要約: グラフポアソン方程式の解に対する高確率内部および大域リプシッツ推定を証明した。
我々の結果は、グラフラプラシア固有ベクトルが、高い確率で、本質的には、対応する固有値に明示的に依存する定数を持つリプシッツ正則であることが示せる。
- 参考スコア（独自算出の注目度）: 1.2891210250935146
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we study Lipschitz regularity of elliptic PDEs on geometric
graphs, constructed from random data points. The data points are sampled from a
distribution supported on a smooth manifold. The family of equations that we
study arises in data analysis in the context of graph-based learning and
contains, as important examples, the equations satisfied by graph Laplacian
eigenvectors. In particular, we prove high probability interior and global
Lipschitz estimates for solutions of graph Poisson equations. Our results can
be used to show that graph Laplacian eigenvectors are, with high probability,
essentially Lipschitz regular with constants depending explicitly on their
corresponding eigenvalues. Our analysis relies on a probabilistic coupling
argument of suitable random walks at the continuum level, and an interpolation
method for extending functions on random point clouds to the continuum
manifold. As a byproduct of our general regularity results, we obtain high
probability $L^\infty$ and approximate $\mathcal{C}^{0,1}$ convergence rates
for the convergence of graph Laplacian eigenvectors towards eigenfunctions of
the corresponding weighted Laplace-Beltrami operators. The convergence rates we
obtain scale like the $L^2$-convergence rates established by two of the authors
in previous work.
- Abstract（参考訳）: 本稿では,ランダムデータ点から構築した幾何グラフ上の楕円型pdesのリプシッツ正則性について検討する。
データポイントは滑らかな多様体上に支持された分布からサンプリングされる。
グラフベース学習の文脈におけるデータ解析で生じる方程式の族は、グラフラプラシアン固有ベクトルによって満たされる方程式を含む重要な例である。
特に、グラフポアソン方程式の解に対する高確率内部および大域リプシッツ推定を証明している。
この結果は、グラフラプラシアン固有ベクトルが、その固有値に明示的に依存する定数を持つ本質的にリプシッツ正則であることを示すために用いられる。
本解析は,連続体レベルでの適切なランダムウォークの確率的結合引数と,ランダム点雲上の関数を連続体多様体に拡張するための補間法に依存する。
一般正規性結果の副産物として、対応する重み付きラプラス・ベルトラミ作用素の固有関数に対するグラフラプラシアン固有ベクトルの収束に対する高い確率 $l^\infty$ と近似 $\mathcal{c}^{0,1}$ が得られる。
収束率は、以前の2人の著者によって確立された$l^2$-convergence rateのようにスケールする。
関連論文リスト
- Convergence rates for Poisson learning to a Poisson equation with measure data [2.7961972519572447]
グラフに基づく半教師付き学習アルゴリズムであるPoisson Learningに対して,連続収束率を離散的に証明する。
グラフ熱核によるモリフィケーションによるグラフポアソン方程式の正則化法を示す。
我々は、一般的なデータ分布に$O(varepsilonfrac1d+2)$、均一に分散したデータに$O(varepsilonfrac2-sigmad+4)$などの対数因子にスケールする収束率を得る。
論文 参考訳（メタデータ） (2024-07-09T11:54:34Z) - 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) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳（メタデータ） (2021-12-29T18:46:52Z) - Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov
Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。
三角凸分解はその上部に対応する変換によって保証されることを示す。
論文 参考訳（メタデータ） (2021-09-17T17:46:12Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。
次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文 参考訳（メタデータ） (2021-05-03T16:36:27Z) - Eigen-convergence of Gaussian kernelized graph Laplacian by manifold
heat interpolation [16.891059233061767]
グラフラプラシアンのラプラス・ベルトラミ作用素へのスペクトル収束について検討する。
データは$d$次元多様体上で均一にサンプリングされる。
密度補正グラフ Laplacian に対する新しい点和およびディリクレ形式収束率を証明した。
論文 参考訳（メタデータ） (2021-01-25T03:22:18Z) - Random Geometric Graphs on Euclidean Balls [2.28438857884398]
ノード $i$ がユークリッド単位球上のランダム潜在点 $X_i$ に関連付けられたランダムグラフに対する潜在空間モデルを考える。
特定のリンク関数に対して、ここで考慮されたモデルは、パワーロー型の分布を持つ尾を持つ次数分布を持つグラフを生成する。
論文 参考訳（メタデータ） (2020-10-26T17:21:57Z) - Tight Nonparametric Convergence Rates for Stochastic Gradient Descent
under the Noiseless Linear Model [0.0]
このモデルに基づく最小二乗リスクに対する1パス, 固定段差勾配勾配の収束度を解析した。
特殊な場合として、ランダムなサンプリング点における値のノイズのない観測から単位区間上の実関数を推定するオンラインアルゴリズムを解析する。
論文 参考訳（メタデータ） (2020-06-15T08:25:50Z) - 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) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。