論文の概要: The Umeyama algorithm for matching correlated Gaussian geometric models
in the low-dimensional regime
- arxiv url: http://arxiv.org/abs/2402.15095v1
- Date: Fri, 23 Feb 2024 04:58:54 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-26 15:39:55.148081
- Title: The Umeyama algorithm for matching correlated Gaussian geometric models
in the low-dimensional regime
- Title（参考訳）: 低次元状態における相関ガウス幾何モデルと一致する梅山アルゴリズム
- Authors: Shuyang Gong and Zhangsong Li
- Abstract要約: 2つの相関したランダムな幾何グラフのマッチングの問題に触発され、潜在ノード置換によって相関した2つのガウス幾何学モデルのマッチング問題を研究する。
A_i,j=langle X_i,X_j rangle$, $B_i,j=langle Y_i,Y_j rangle$ で与えられるエッジウェイトを持つ2種類の(相関した)重み付き完全グラフを考える。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by the problem of matching two correlated random geometric graphs,
we study the problem of matching two Gaussian geometric models correlated
through a latent node permutation. Specifically, given an unknown permutation
$\pi^*$ on $\{1,\ldots,n\}$ and given $n$ i.i.d. pairs of correlated Gaussian
vectors $\{X_{\pi^*(i)},Y_i\}$ in $\mathbb{R}^d$ with noise parameter $\sigma$,
we consider two types of (correlated) weighted complete graphs with edge
weights given by $A_{i,j}=\langle X_i,X_j \rangle$, $B_{i,j}=\langle Y_i,Y_j
\rangle$. The goal is to recover the hidden vertex correspondence $\pi^*$ based
on the observed matrices $A$ and $B$. For the low-dimensional regime where
$d=O(\log n)$, Wang, Wu, Xu, and Yolou [WWXY22+] established the information
thresholds for exact and almost exact recovery in matching correlated Gaussian
geometric models. They also conducted numerical experiments for the classical
Umeyama algorithm. In our work, we prove that this algorithm achieves exact
recovery of $\pi^*$ when the noise parameter $\sigma=o(d^{-3}n^{-2/d})$, and
almost exact recovery when $\sigma=o(d^{-3}n^{-1/d})$. Our results approach the
information thresholds up to a $\operatorname{poly}(d)$ factor in the
low-dimensional regime.
- Abstract（参考訳）: 2つの相関したランダムな幾何グラフのマッチングの問題に触発され、潜在ノード置換によって相関した2つのガウス幾何学モデルのマッチング問題を研究する。
具体的には、未知の置換である$\pi^*$ on $\{1,\ldots,n\}$ と、相関関係を持つガウスベクトルの対 $n$ i.i.d. が与えられたとき、ノイズパラメータ $\sigma$ とともに$\mathbb{r}^d$ で$\{x_{\pi^*(i)},y_i\}$ in$\sigma{r}^d$ に対して、2種類の(関連する)重み付き完全グラフを、$a_{i,j}=\langle x_i,x_j \rangle$, $b_{i,j}=\langle y_i,y_j \rangle$ で与える。
目標は、観測された行列 $a$ と $b$ に基づいて、隠れた頂点対応 $\pi^*$ を回復することである。
d=O(\log n)$, Wang, Wu, Xu, および Yolou [WWXY22+] が一致するガウス幾何学モデルにおいて, 精度とほぼ正確に回復するための情報しきい値を確立した。
また、古典的梅山アルゴリズムの数値実験も行った。
本研究では,ノイズパラメータ$\sigma=o(d^{-3}n^{-2/d})$の場合に$\pi^*$を,$\sigma=o(d^{-3}n^{-1/d})$の場合にはほぼ正確に回復できることを実証する。
我々の結果は、低次元状態における$\operatorname{poly}(d)$ factorまでの情報しきい値にアプローチする。
関連論文リスト
- Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models [39.33814194788341]
潜在変数モデル学習の課題について検討する。
このような応用により、暗黙のモーメント計算のための一般化されたアルゴリズムを開発した。
一般的なアルゴリズムを利用して, 以下のモデルに対する初等学習者を得る。
論文 参考訳（メタデータ） (2024-11-23T23:13:24Z) - Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
閾値降下を用いた単一ニューロンモデル学習のための近似境界を導出する。
線形回帰問題も研究し、$sigma(mathbfx) = mathbfx$ となる。
論文 参考訳（メタデータ） (2024-09-05T16:59:56Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Seeded graph matching for the correlated Gaussian Wigner model via the projected power method [5.639451539396459]
グラフマッチングアルゴリズムとして,Emphprojected Power Method (PPM) の性能解析を行った。
PPM は定数 $sigma$ の反復でも機能し、(Mao et al. 2023) のスパース相関エルドス・レニー(CER) モデルに対する解析を (dense) CGW モデルに拡張する。
論文 参考訳（メタデータ） (2022-04-08T14:31:26Z) - Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。
近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。
副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
論文 参考訳（メタデータ） (2022-02-22T04:14:45Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - Sharp threshold for alignment of graph databases with Gaussian weights [1.6752182911522522]
重み付きグラフ(行列)データベースアライメントにおける再構成の基本的限界について検討する。
我々は、$pi*$の正確なリカバリには鋭いしきい値が存在することを証明している。
論文 参考訳（メタデータ） (2020-10-30T14:42:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。