論文の概要: A Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Group

• arxiv url: http://arxiv.org/abs/2009.07514v4
• Date: Fri, 16 Jun 2023 05:50:54 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-19 18:43:26.132127
• Title: A Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Group
• Title（参考訳）: 直交群の部分群上の同期問題への統一的アプローチ
• Authors: Huikang Liu, Man-Chung Yue, Anthony Man-Cho So
• Abstract要約: 群が閉部分群である同期問題のクラスを考える。 このような問題を解くための統一的なアプローチを提案する。 私たちのアプローチは既存のアプローチよりも優れています。
• 参考スコア（独自算出の注目度）: 29.714239628405515
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The problem of synchronization over a group $\mathcal{G}$ aims to estimate a collection of group elements $G^*_1, \dots, G^*_n \in \mathcal{G}$ based on noisy observations of a subset of all pairwise ratios of the form $G^*_i {G^*_j}^{-1}$. Such a problem has gained much attention recently and finds many applications across a wide range of scientific and engineering areas. In this paper, we consider the class of synchronization problems in which the group is a closed subgroup of the orthogonal group. This class covers many group synchronization problems that arise in practice. Our contribution is fivefold. First, we propose a unified approach for solving this class of group synchronization problems, which consists of a suitable initialization step and an iterative refinement step based on the generalized power method, and show that it enjoys a strong theoretical guarantee on the estimation error under certain assumptions on the group, measurement graph, noise, and initialization. Second, we formulate two geometric conditions that are required by our approach and show that they hold for various practically relevant subgroups of the orthogonal group. The conditions are closely related to the error-bound geometry of the subgroup -- an important notion in optimization. Third, we verify the assumptions on the measurement graph and noise for standard random graph and random matrix models. Fourth, based on the classic notion of metric entropy, we develop and analyze a novel spectral-type estimator. Finally, we show via extensive numerical experiments that our proposed non-convex approach outperforms existing approaches in terms of computational speed, scalability, and/or estimation error.
• Abstract（参考訳）: 群 $\mathcal{G}$ 上の同期問題は、群要素の集合 $G^*_1, \dots, G^*_n \in \mathcal{G}$ を、形式 $G^*_i {G^*_j}^{-1}$ の任意の対比の集合の雑音的な観測に基づいて推定することを目的としている。 このような問題は近年注目を集め、幅広い科学や工学分野に応用されている。 本稿では、群が直交群の閉部分群である同期問題のクラスを考える。 このクラスは、実際に発生する多くのグループ同期問題をカバーする。 私たちの貢献は5倍です。 まず,一般化パワー法に基づく適切な初期化ステップと反復的改良ステップからなる群同期問題に対する統一的な解法を提案し,群,測定グラフ,雑音,初期化における推定誤差の強い理論的保証を享受することを示す。 第二に、我々のアプローチで要求される2つの幾何学的条件を定式化し、それらが直交群の様々な実用的な部分群に対して成り立つことを示す。 条件は部分群の誤差有界幾何と密接に関連しており、最適化の重要な概念である。 第3に、標準ランダムグラフとランダム行列モデルに対する測定グラフとノイズの仮定を検証する。 第4に、古典的な距離エントロピーの概念に基づいて、新しいスペクトル型推定器を開発し分析する。 最後に,提案手法が計算速度,スケーラビリティ,推定誤差の点で既存の手法よりも優れていることを示す。

関連論文リスト

• HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
  HeNClerは、Heterophilous Node Clusteringの新しいアプローチである。 HeNClerは異種グラフコンテキストにおけるノードクラスタリングタスクの性能を大幅に向上させることを示す。
  論文  参考訳（メタデータ） (2024-05-27T11:04:05Z)
• An SDP-based Branch-and-Cut Algorithm for Biclustering [0.0]
  本稿では,二クラスタリング問題に対する分枝切断アルゴリズムを提案する。 提案アルゴリズムは汎用的な解法よりも20倍大きな解法を解くことができることを示す。
  論文  参考訳（メタデータ） (2024-03-17T21:43:19Z)
• Clustered Orienteering Problem with Subgroups [6.961946145048321]
  サブグループによるクラスター配向問題(COPS) 我々の新しい定式化は、以前の2つのよく知られた変種をモデル化し、解決する能力を持っていることを示す。
  論文  参考訳（メタデータ） (2023-12-26T18:28:25Z)
• ALEXR: An Optimal Single-Loop Algorithm for Convex Finite-Sum Coupled Compositional Stochastic Optimization [53.14532968909759]
  ALEXRと呼ばれる,効率的な単ループプリマルデュアルブロックコーディネートアルゴリズムを提案する。 本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。 本稿では,ALEXRの収束速度が,検討されたcFCCO問題に対する1次ブロック座標アルゴリズムの中で最適であることを示すために,より低い複雑性境界を示す。
  論文  参考訳（メタデータ） (2023-12-04T19:00:07Z)
• Unrolled algorithms for group synchronization [7.969977930633441]
  群同期問題は、そのペア比のノイズ測定から群要素の集合を推定することを含む。 群要素を推定する標準的な方法は、線形および非線形作用素を反復的に適用することに基づいている。 深層ニューラルネットワークと構造的類似性により、我々はアルゴリズムのアンロールの概念を採用した。
  論文  参考訳（メタデータ） (2022-07-19T17:25:56Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。 我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。 これらのアルゴリズムに対する漸近的理論的保証を提供する。
  論文  参考訳（メタデータ） (2022-04-07T00:11:05Z)
• Gradient Based Clustering [72.15857783681658]
  本稿では,クラスタリングの品質を計測するコスト関数の勾配を用いて,距離に基づくクラスタリングの一般的な手法を提案する。 アプローチは反復的な2段階の手順(クラスタ割り当てとクラスタセンターのアップデートの代替)であり、幅広い機能に適用できる。
  論文  参考訳（メタデータ） (2022-02-01T19:31:15Z)
• Orthogonal Group Synchronization with Incomplete Measurements: Error Bounds and Linear Convergence of the Generalized Power Method [22.901235010786287]
  群同期とは、雑音の対の測度から群要素の集合を推定することを指す。 本稿では,不完全な測定条件下での一般付加音モデルを用いたグループ同期問題に焦点をあてる。
  論文  参考訳（メタデータ） (2021-12-13T10:57:09Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Near-Optimal Performance Bounds for Orthogonal and Permutation Group Synchronization via Spectral Methods [0.7614628596146599]
  グループ同期は、それぞれの測定値からグループ要素を復元することを要求する。 スペクトル法は 効率と利便性で 大人気でした ランダムな乱れの下での置換群同期では、広く使われている2段階の手順がすべての群要素を正確に復元できることが示される。
  論文  参考訳（メタデータ） (2020-08-12T14:20:16Z)
• Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
  直交群 $O(d)$ 上の幾何駆動最適化アルゴリズムの新しいクラスを示す。 提案手法は,深層,畳み込み,反復的なニューラルネットワーク,強化学習,フロー,メトリック学習など,機械学習のさまざまな分野に適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-03-30T15:37:50Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。