論文の概要: Bi-stochastically normalized graph Laplacian: convergence to manifold
Laplacian and robustness to outlier noise
- arxiv url: http://arxiv.org/abs/2206.11386v1
- Date: Wed, 22 Jun 2022 21:08:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-25 01:42:40.252840
- Title: Bi-stochastically normalized graph Laplacian: convergence to manifold
Laplacian and robustness to outlier noise
- Title（参考訳）: 双構造正規化グラフ Laplacian: 多様体 Laplacian への収束と外部雑音へのロバスト性
- Authors: Xiuyuan Cheng, Boris Landa
- Abstract要約: 双構造正規化グラフ Laplacian to manifold (weighted-)Laplacian は Sinkhorn-Knopp (SK) の反復によって効率的に計算できる。
多様体データが外乱ノイズによって破壊されるとき、理論的にはラプラシア点の整合性を証明する。
- 参考スコア（独自算出の注目度）: 8.271859911016719
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Bi-stochastic normalization of kernelized graph affinity matrix provides an
alternative normalization scheme for graph Laplacian methods in graph-based
data analysis and can be computed efficiently by Sinkhorn-Knopp (SK) iterations
in practice. This paper proves the convergence of the bi-stochastically
normalized graph Laplacian to manifold (weighted-)Laplacian with rates when $n$
data points are i.i.d. sampled from a general $d$-dimensional manifold embedded
in a possibly high-dimensional space. Under certain joint limit of $n \to
\infty$ and kernel bandwidth $\epsilon \to 0$, the point-wise convergence rate
of the graph Laplacian operator (under 2-norm) is proved to be $ O(
n^{-1/(d/2+3)})$ at finite large $n$ up to log factors, achieved at the scaling
of $\epsilon \sim n^{-1/(d/2+3)} $. When the manifold data are corrupted by
outlier noise, we theoretically prove the graph Laplacian point-wise
consistency which matches the rate for clean manifold data up to an additional
error term proportional to the boundedness of mutual inner-products of the
noise vectors. Our analysis suggests that, under the setting being considered
in this paper, not exact bi-stochastic normalization but an approximate one
will achieve the same consistency rate. Motivated by the analysis, we propose
an approximate and constrained matrix scaling problem that can be solved by SK
iterations with early termination, and apply to simulated manifold data both
clean and with outlier noise. Numerical experiments support our theoretical
results and show the robustness of bi-stochastically normalized graph Laplacian
to outlier noise.
- Abstract（参考訳）: 核化されたグラフ親和性行列の双確率正規化はグラフベースデータ解析におけるグラフラプラシアン法に対する代替正規化スキームを提供し、実際にシンクホーンknopp(sk)反復によって効率的に計算できる。
本稿では、n$のデータポイントが高次元空間に埋め込まれた一般の$d$次元多様体からサンプリングされた場合のレートで、二項正規化グラフラプラシアンを多様体(重み付き)ラプラシアンに収束することを示す。
ある結合極限$n \to \infty$とカーネル帯域$\epsilon \to 0$の下では、グラフラプラシアン作用素の点収束速度は、(2-ノルムの下で)$ O(n^{-1/(d/2+3)} と証明され、有限大の$n$は、$\epsilon \sim n^{-1/(d/2+3)} のスケーリングで達成される。
マニホールドデータが外れたノイズによって腐敗すると、理論上は、クリーンマニホールドデータのレートとノイズベクトルの相互内積の有界性に比例する追加の誤差項に一致するグラフラプラシアン点方向の一貫性が証明される。
本論文では, この条件下では, 両確率正規化ではなく, 近似的に同じ整合性が得られることが示唆されている。
解析に動機づけられ,sk反復により早期に解くことができる近似的および制約付き行列スケーリング問題を提案し,クリーンかつ異常ノイズを伴う模擬多様体データに適用する。
数値実験は、我々の理論結果を支持し、二階層正規化グラフラプラシアンの外周雑音に対する堅牢性を示す。
関連論文リスト
- High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
重み付き雑音の存在下でのストリーミングデータにおける学習の精度保証について検討した。
解析的に、与えられた問題に対する設定の選択に$ta$を使うことができることを実証する。
論文 参考訳（メタデータ） (2023-10-28T18:53:41Z) - Rates of Convergence for Regression with the Graph Poly-Laplacian [3.222802562733786]
より高次規則性は、ラプラシア正規化器をポリラプラシア正規化器に置き換えることで得られる。
完全教師付き、非パラメトリック、ノイズ劣化、回帰問題におけるグラフポリラプラシア正規化を考察する。
論文 参考訳（メタデータ） (2022-09-06T08:59:15Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - 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) - Convergence Rates of Stochastic Gradient Descent under Infinite Noise
Variance [14.06947898164194]
ヘビーテールは様々なシナリオで勾配降下 (sgd) で現れる。
SGDの収束保証は、潜在的に無限のばらつきを持つ状態依存性および重尾ノイズ下で提供します。
その結果,SGDは無限に分散した重尾雑音下であっても,地球最適値に収束できることが示された。
論文 参考訳（メタデータ） (2021-02-20T13:45:11Z) - Eigen-convergence of Gaussian kernelized graph Laplacian by manifold
heat interpolation [16.891059233061767]
グラフラプラシアンのラプラス・ベルトラミ作用素へのスペクトル収束について検討する。
データは$d$次元多様体上で均一にサンプリングされる。
密度補正グラフ Laplacian に対する新しい点和およびディリクレ形式収束率を証明した。
論文 参考訳（メタデータ） (2021-01-25T03:22:18Z) - Testing correlation of unlabeled random graphs [18.08210501570919]
ラベルなしノードを持つ2つのランダムグラフ間のエッジ相関を検出する問題について検討する。
これは仮説テスト問題として定式化され、ヌル仮説の下では、2つのグラフは独立に生成される。
代替として、2つのグラフは、ある潜在ノード対応の下ではエッジ関連であるが、ヌルと同じ辺分布を持つ。
論文 参考訳（メタデータ） (2020-08-23T19:19:45Z) - Does the $\ell_1$-norm Learn a Sparse Graph under Laplacian Constrained
Graphical Models? [13.572602792770288]
ラプラシアン制約ガウス図形モデルの下でグラフを学習する問題を考察する。
我々は、大きな正規化パラメータが驚くほど完全なグラフ、すなわちエッジで接続されたすべてのエッジにつながることを示した。
論文 参考訳（メタデータ） (2020-06-26T12:06:10Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。