論文の概要: An extension of the angular synchronization problem to the heterogeneous
setting
- arxiv url: http://arxiv.org/abs/2012.14932v2
- Date: Mon, 4 Jan 2021 21:26:11 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-18 20:41:22.494859
- Title: An extension of the angular synchronization problem to the heterogeneous
setting
- Title（参考訳）: 角度同期問題の不均一な設定への拡張
- Authors: Mihai Cucuringu and Hemant Tyagi
- Abstract要約: 角度 $theta_l,1, dots,theta_l,n$ の $k$ 未知群が $l=1,dots,k$ に対して存在する設定への一般化を見つける。
この問題は、コンピュータビジョン、分散ネットワークの時間同期、設定関係からのランキングなど、さまざまなアプリケーションで発生します。
- 参考スコア（独自算出の注目度）: 8.391320712953553
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given an undirected measurement graph $G = ([n], E)$, the classical angular
synchronization problem consists of recovering unknown angles
$\theta_1,\dots,\theta_n$ from a collection of noisy pairwise measurements of
the form $(\theta_i - \theta_j) \mod 2\pi$, for each $\{i,j\} \in E$. This
problem arises in a variety of applications, including computer vision, time
synchronization of distributed networks, and ranking from preference
relationships. In this paper, we consider a generalization to the setting where
there exist $k$ unknown groups of angles $\theta_{l,1}, \dots,\theta_{l,n}$,
for $l=1,\dots,k$. For each $ \{i,j\} \in E$, we are given noisy pairwise
measurements of the form $\theta_{\ell,i} - \theta_{\ell,j}$ for an unknown
$\ell \in \{1,2,\ldots,k\}$. This can be thought of as a natural extension of
the angular synchronization problem to the heterogeneous setting of multiple
groups of angles, where the measurement graph has an unknown edge-disjoint
decomposition $G = G_1 \cup G_2 \ldots \cup G_k$, where the $G_i$'s denote the
subgraphs of edges corresponding to each group. We propose a probabilistic
generative model for this problem, along with a spectral algorithm for which we
provide a detailed theoretical analysis in terms of robustness against both
sampling sparsity and noise. The theoretical findings are complemented by a
comprehensive set of numerical experiments, showcasing the efficacy of our
algorithm under various parameter regimes. Finally, we consider an application
of bi-synchronization to the graph realization problem, and provide along the
way an iterative graph disentangling procedure that uncovers the subgraphs
$G_i$, $i=1,\ldots,k$ which is of independent interest, as it is shown to
improve the final recovery accuracy across all the experiments considered.
- Abstract（参考訳）: G = ([n], E)$ が与えられたとき、古典的な角度同期問題は未知のアングル $\theta_1,\dots,\theta_n$ を $(\theta_i - \theta_j) \mod 2\pi$ という形のノイズの多い対の値の集まりから、それぞれ $\{i,j\} \in E$ を復元する。
この問題は、コンピュータビジョン、分散ネットワークの時間同期、選好関係からのランキングなど、さまざまなアプリケーションで発生します。
本稿では、$k$未知の角度群$\theta_{l,1}, \dots,\theta_{l,n}$, for $l=1,\dots,k$ の集合への一般化を考える。
それぞれの ${i,j\} \in E$ に対して、未知の $\ell \in \{1,2,\ldots,k\}$ に対して $\theta_{\ell,i} - \theta_{\ell,j}$ という形のノイズ対の測定が与えられる。
これは角同期問題から多角群の不均一な設定への自然な拡張と見なすことができ、そこでの測定グラフは未知のエッジ分離分解$G = G_1 \cup G_2 \ldots \cup G_k$, ここでは、$G_i$'sは各群に対応するエッジの部分グラフを表す。
本稿では, この問題に対する確率的生成モデルと, サンプリング間隔と雑音の両方に対する堅牢性の観点から, 詳細な理論的解析を行うスペクトルアルゴリズムを提案する。
理論的知見は,様々なパラメータ条件下でのアルゴリズムの有効性を示す,総合的な数値実験によって補完される。
最後に,グラフ実現問題に対するバイ同期化の適用について考察し,検討したすべての実験において最終的な回復精度を向上させることが示されるように,グラフのサブグラフである $G_i$, $i=1,\ldots,k$ を探索する反復グラフ解離手順を提案する。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。
本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
論文 参考訳（メタデータ） (2024-08-10T04:26:19Z) - Dynamic angular synchronization under smoothness constraints [9.196539011582361]
統計モデルにより平均二乗誤差(MSE)の漸近的回復を保証する。
MSE が 0 に収束するのは、静的条件よりも穏やかな条件で$T$ が増加するためである。
論文 参考訳（メタデータ） (2024-06-06T13:36:41Z) - The Umeyama algorithm for matching correlated Gaussian geometric models
in the low-dimensional regime [0.0]
2つの相関したランダムな幾何グラフのマッチングの問題に触発され、潜在ノード置換によって相関した2つのガウス幾何学モデルのマッチング問題を研究する。
A_i,j=langle X_i,X_j rangle$, $B_i,j=langle Y_i,Y_j rangle$ で与えられるエッジウェイトを持つ2種類の(相関した)重み付き完全グラフを考える。
論文 参考訳（メタデータ） (2024-02-23T04:58:54Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - Dynamic Ranking and Translation Synchronization [3.946250592943285]
本研究では, エン翻訳同期問題の動的設定への拡張について検討する。
そこで我々は,2つの推定器を提案し,その1つはスムーズネスの最小二乗法に基づくものであり,もう1つは適切な滑らかさ演算子の低周波固有空間への射影に基づくものである。
論文 参考訳（メタデータ） (2022-07-04T14:45:12Z) - Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。
近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。
副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
論文 参考訳（メタデータ） (2022-02-22T04:14:45Z) - Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。
我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
論文 参考訳（メタデータ） (2021-04-06T15:34:14Z) - Sharp threshold for alignment of graph databases with Gaussian weights [1.6752182911522522]
重み付きグラフ(行列)データベースアライメントにおける再構成の基本的限界について検討する。
我々は、$pi*$の正確なリカバリには鋭いしきい値が存在することを証明している。
論文 参考訳（メタデータ） (2020-10-30T14:42:17Z) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳（メタデータ） (2020-06-02T16:38:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。