Unrolled algorithms for group synchronization

• URL: http://arxiv.org/abs/2207.09418v1
• Date: Tue, 19 Jul 2022 17:25:56 GMT
• Title: Unrolled algorithms for group synchronization
• Authors: Noam Janco and Tamir Bendory
• Abstract summary: 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.
• Score: 7.969977930633441
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The group synchronization problem involves estimating a collection of group elements from noisy measurements of their pairwise ratios. This task is a key component in many computational problems, including the molecular reconstruction problem in single-particle cryo-electron microscopy (cryo-EM). The 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, where training data is used to optimize the algorithm. We design unrolled algorithms for several group synchronization instances, including synchronization over the group of 3-D rotations: the synchronization problem in cryo-EM. We also apply a similar approach to the multi-reference alignment problem. We show by numerical experiments that the unrolling strategy outperforms existing synchronization algorithms in a wide variety of scenarios.

Related papers

• Efficient Detection of Long Consistent Cycles and its Application to Distributed Synchronization [16.017134759593333]
  Group synchronization plays a crucial role in global pipelines for Structure from Motion (SfM) Cycle synchronization has been effective in addressing these challenges. We propose an algorithm for group synchronization that leverages information from cycles of lengths from three to six.
  arXiv  Detail & Related papers  (2024-07-05T05:19:53Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• Multi-Frequency Joint Community Detection and Phase Synchronization [22.683901672480353]
  This paper studies the joint community detection and phase synchronization problem on the textitstochastic block model with relative phase We show this problem exhibits a textitmulti-frequency'' structure by closely examining its maximum likelihood estimation (MLE) formulation. Two simple yet efficient algorithms that leverage the MLE formulation and benefit from the information across multiple frequencies are proposed.
  arXiv  Detail & Related papers  (2022-06-16T23:08:27Z)
• 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)
• A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization [20.413250472034143]
  We propose a simple algorithm that consists of a spectral decomposition step followed by a blockwise column pivoted QR factorization (CPQR) The proposed algorithm is efficient and scales linearly with the number of data points. We also leverage the recently developed leave-one-out' technique to establish a near-optimal guarantee for exact recovery of the cluster memberships.
  arXiv  Detail & Related papers  (2021-12-25T07:38:14Z)
• Learning Iterative Robust Transformation Synchronization [71.73273007900717]
  We propose to use graph neural networks (GNNs) to learn transformation synchronization. In this work, we avoid handcrafting robust loss functions, and propose to use graph neural networks (GNNs) to learn transformation synchronization.
  arXiv  Detail & Related papers  (2021-11-01T07:03:14Z)
• 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)
• On the Robustness of Multi-View Rotation Averaging [77.09542018140823]
  We introduce the $epsilon$-cycle consistency term into the solver. We implicitly constrain the negative effect of erroneous measurements by weight reducing. Experiment results demonstrate that our proposed approach outperforms state of the arts on various benchmarks.
  arXiv  Detail & Related papers  (2021-02-09T05:47:37Z)
• Determinantal consensus clustering [77.34726150561087]
  We propose the use of determinantal point processes or DPP for the random restart of clustering algorithms. DPPs favor diversity of the center points within subsets. We show through simulations that, contrary to DPP, this technique fails both to ensure diversity, and to obtain a good coverage of all data facets.
  arXiv  Detail & Related papers  (2021-02-07T23:48:24Z)
• 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)
• Message Passing Least Squares Framework and its Application to Rotation Synchronization [16.650654530240566]
  We first describe our theoretically guaranteed message passing algorithm that estimates the corruption levels of the measured group ratios. We then propose a novel reweighted least squares method to estimate the group elements, where the weights are iteratively updated using the estimated corruption levels. We demonstrate the superior performance of our algorithm over state-of-the-art methods for rotation synchronization using both synthetic and real data.
  arXiv  Detail & Related papers  (2020-07-27T15:39:19Z)

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.