論文の概要: Bi-stochastically normalized graph Laplacian: convergence to manifold Laplacian and robustness to outlier noise
- arxiv url: http://arxiv.org/abs/2206.11386v3
- Date: Wed, 17 Jul 2024 22:24:56 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-20 00:38:23.364741
- Title: Bi-stochastically normalized graph Laplacian: convergence to manifold Laplacian and robustness to outlier noise
- Title（参考訳）: 双構造正規化グラフ Laplacian: 多様体 Laplacian への収束と外部雑音へのロバスト性
- Authors: Xiuyuan Cheng, Boris Landa,
- Abstract要約: 双確率正規化 (bi-stochastic normalization) はグラフベースのデータ解析においてグラフラプラシアンの代替正規化を提供する。
両階層正規化グラフ Laplacian から (重み付き) Laplacian への収束を速度で証明する。
多様体データが外乱ノイズによって破損した場合、理論的にはラプラシア点の整合性を証明する。
- 参考スコア（独自算出の注目度）: 10.418647759223965
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bi-stochastic normalization provides an alternative normalization of graph Laplacians in graph-based data analysis and can be computed efficiently by Sinkhorn-Knopp (SK) iterations. This paper proves the convergence of 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 plus an additional term proportional to the boundedness of the inner-products of the noise vectors among themselves and with data vectors. Motivated by our analysis, which suggests that not exact bi-stochastic normalization but an approximate one will achieve the same consistency rate, we propose an approximate and constrained matrix scaling problem that can be solved by SK iterations with early termination. Numerical experiments support our theoretical results and show the robustness of bi-stochastically normalized graph Laplacian to high-dimensional outlier noise.
- Abstract（参考訳）: 双確率正規化(bi-stochastic normalization)はグラフベースのデータ解析においてグラフラプラシアンの代替正規化を提供し、シンクホーン・ノック(SK)反復によって効率的に計算できる。
この論文は、高次元空間に埋め込まれた一般の$d$次元多様体から、$n$のデータ点が i.d.d.d.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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。