A Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Group

• URL: http://arxiv.org/abs/2009.07514v4
• Date: Fri, 16 Jun 2023 05:50:54 GMT
• Title: A Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Group
• Authors: Huikang Liu, Man-Chung Yue, Anthony Man-Cho So
• Abstract summary: We consider the class of synchronization problems which the group is a closed subgroup. We propose a unified approach for solving this class of problems. We show that our approach outperforms existing approaches.
• Score: 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.

Related papers

• HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
  HeNCler is a novel approach for Heterophilous Node Clustering. We show that HeNCler significantly enhances performance in node clustering tasks within heterophilous graph contexts.
  arXiv  Detail & Related papers  (2024-05-27T11:04:05Z)
• An SDP-based Branch-and-Cut Algorithm for Biclustering [0.0]
  We present a tailored branch-and-cut algorithm for biclustering problems. We show that the proposed algorithm can solve instances 20 times larger than those handled by general-purpose solvers.
  arXiv  Detail & Related papers  (2024-03-17T21:43:19Z)
• Clustered Orienteering Problem with Subgroups [6.961946145048321]
  Clustered Orienteering Problem with Subgroups (COPS) We show that our new formulation has the ability to model and solve two previous well-known variants.
  arXiv  Detail & Related papers  (2023-12-26T18:28:25Z)
• ALEXR: An Optimal Single-Loop Algorithm for Convex Finite-Sum Coupled Compositional Stochastic Optimization [53.14532968909759]
  We introduce an efficient single-loop primal-dual block-coordinate algorithm, dubbed ALEXR. We establish the convergence rates of ALEXR in both convex and strongly convex cases under smoothness and non-smoothness conditions. We present lower complexity bounds to demonstrate that the convergence rates of ALEXR are optimal among first-order block-coordinate algorithms for the considered class of cFCCO problems.
  arXiv  Detail & Related papers  (2023-12-04T19:00:07Z)
• Unrolled algorithms for group synchronization [7.969977930633441]
  Group synchronization problem involves estimating a collection of group elements from noisy measurements of their pairwise ratios. Standard methods to estimate the group elements are based on iteratively applying linear and non-linear operators. Motivated by the structural similarity to deep neural networks, we adopt the concept of algorithm unrolling.
  arXiv  Detail & Related papers  (2022-07-19T17:25:56Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  We consider the problem of computing an equilibrium in a class of nonlinear generalized Nash equilibrium problems (NGNEPs) Our contribution is to provide two simple first-order algorithmic frameworks based on the quadratic penalty method and the augmented Lagrangian method. We provide nonasymptotic theoretical guarantees for these algorithms.
  arXiv  Detail & Related papers  (2022-04-07T00:11:05Z)
• Gradient Based Clustering [72.15857783681658]
  We propose a general approach for distance based clustering, using the gradient of the cost function that measures clustering quality. The approach is an iterative two step procedure (alternating between cluster assignment and cluster center updates) and is applicable to a wide range of functions.
  arXiv  Detail & Related papers  (2022-02-01T19:31:15Z)
• Orthogonal Group Synchronization with Incomplete Measurements: Error Bounds and Linear Convergence of the Generalized Power Method [22.901235010786287]
  Group synchronization refers to estimating a collection of group elements from the noisy pairwise measurements. In this paper, we focus on the group synchronization problem with general additive noise models under incomplete measurements.
  arXiv  Detail & Related papers  (2021-12-13T10:57:09Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Near-Optimal Performance Bounds for Orthogonal and Permutation Group Synchronization via Spectral Methods [0.7614628596146599]
  Group synchronization asks to recover group elements from their pairwise measurements. spectral methods have enjoyed great popularity due to their efficiency and convenience. For permutation group synchronization under random corruption, we show that the widely-used two-step procedure can recover all the group elements exactly.
  arXiv  Detail & Related papers  (2020-08-12T14:20:16Z)
• Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
  We present a new class of geometrically-driven optimization algorithms on the orthogonal group $O(d)$. We show that our methods can be applied in various fields of machine learning including deep, convolutional and recurrent neural networks, reinforcement learning, flows and metric learning.
  arXiv  Detail & Related papers  (2020-03-30T15:37:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.