論文の概要: Dynamic angular synchronization under smoothness constraints
- arxiv url: http://arxiv.org/abs/2406.04071v1
- Date: Thu, 6 Jun 2024 13:36:41 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-07 14:49:58.791656
- Title: Dynamic angular synchronization under smoothness constraints
- Title(参考訳): 滑らか性制約下における動的角同期
- Authors: Ernesto Araya, Mihai Cucuringu, Hemant Tyagi,
- Abstract要約: 統計モデルにより平均二乗誤差(MSE)の漸近的回復を保証する。
MSE が 0 に収束するのは、静的条件よりも穏やかな条件で$T$ が増加するためである。
- 参考スコア(独自算出の注目度): 9.196539011582361
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given an undirected measurement graph $\mathcal{H} = ([n], \mathcal{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 all $\{i,j\} \in \mathcal{E}$. This problem arises in a variety of applications, including computer vision, time synchronization of distributed networks, and ranking from pairwise comparisons. In this paper, we consider a dynamic version of this problem where the angles, and also the measurement graphs evolve over $T$ time points. Assuming a smoothness condition on the evolution of the latent angles, we derive three algorithms for joint estimation of the angles over all time points. Moreover, for one of the algorithms, we establish non-asymptotic recovery guarantees for the mean-squared error (MSE) under different statistical models. In particular, we show that the MSE converges to zero as $T$ increases under milder conditions than in the static setting. This includes the setting where the measurement graphs are highly sparse and disconnected, and also when the measurement noise is large and can potentially increase with $T$. We complement our theoretical results with experiments on synthetic data.
- Abstract(参考訳): 非方向測度グラフ $\mathcal{H} = ([n], \mathcal{E})$ が与えられたとき、古典的な角同期問題は未知の角度 $\theta_1^*,\dots,\theta_n^*$ を $(\theta_i^* - \theta_j^*) \mod 2\pi$, for all $\{i,j\} \in \mathcal{E}$ という形の雑音の対数測定の集合から回復する。
この問題は、コンピュータビジョン、分散ネットワークの時間同期、ペア比較からのランキングなど、様々なアプリケーションで発生する。
本稿では、この問題の動的バージョンとして、角度と測定グラフが時間点$T$以上で進化する点について考察する。
潜角の進化に関する滑らかさ条件を仮定すると、全点にわたる角度の合同推定のための3つのアルゴリズムを導出する。
さらに,アルゴリズムの1つとして,平均二乗誤差(MSE)の漸近的回復保証を,異なる統計モデルの下で確立する。
特に、MSE が 0 に収束すると、静的条件よりも穏やかな条件で$T$ が増加することが示される。
これには、測定グラフが非常に疎結合で切断されている設定や、測定ノイズが大きくて、潜在的に$T$で増加する可能性がある設定が含まれる。
我々は、理論結果を合成データの実験で補完する。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-11-01T17:59:53Z) - Self-Ensembling Gaussian Splatting for Few-Shot Novel View Synthesis [55.561961365113554]
3D Gaussian Splatting (3DGS) は新規ビュー合成(NVS)に顕著な効果を示した
しかし、3DGSモデルはスパースポーズビューで訓練すると過度に適合する傾向にあり、その一般化能力は新規ビューに制限される。
オーバーフィッティング問題を緩和するために,Self-Ensembling Gaussian Splatting (SE-GS) アプローチを提案する。
提案手法は,NVSの品質向上に寄与し,既存の最先端手法よりも優れる。
論文 参考訳(メタデータ) (2024-10-31T18:43:48Z) - Joint Learning of Linear Dynamical Systems under Smoothness Constraints [5.2395896768723045]
複数の線形力学系の連立学習の問題点を考察する。
特に,平均二乗誤差が平均二乗誤差(MSE)に収束する条件を示す。
論文 参考訳(メタデータ) (2024-06-03T08:29:42Z) - 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) - 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) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳(メタデータ) (2022-06-16T17:10:57Z) - 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) - An extension of the angular synchronization problem to the heterogeneous
setting [8.391320712953553]
角度 $theta_l,1, dots,theta_l,n$ の $k$ 未知群が $l=1,dots,k$ に対して存在する設定への一般化を見つける。
この問題は、コンピュータビジョン、分散ネットワークの時間同期、設定関係からのランキングなど、さまざまなアプリケーションで発生します。
論文 参考訳(メタデータ) (2020-12-29T20:29:10Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳(メタデータ) (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。