Orthogonal Group Synchronization with Incomplete Measurements: Error Bounds and Linear Convergence of the Generalized Power Method

• URL: http://arxiv.org/abs/2112.06556v1
• Date: Mon, 13 Dec 2021 10:57:09 GMT
• Title: Orthogonal Group Synchronization with Incomplete Measurements: Error Bounds and Linear Convergence of the Generalized Power Method
• Authors: Linglingzhi Zhu, Jinxin Wang, Anthony Man-Cho So
• Abstract summary: 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.
• Score: 22.901235010786287
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Group synchronization refers to estimating a collection of group elements from the noisy pairwise measurements. Such a nonconvex problem has received much attention from numerous scientific fields including computer vision, robotics, and cryo-electron microscopy. In this paper, we focus on the orthogonal group synchronization problem with general additive noise models under incomplete measurements, which is much more general than the commonly considered setting of complete measurements. Characterizations of the orthogonal group synchronization problem are given from perspectives of optimality conditions as well as fixed points of the projected gradient ascent method which is also known as the generalized power method (GPM). It is well worth noting that these results still hold even without generative models. In the meantime, we derive the local error bound property for the orthogonal group synchronization problem which is useful for the convergence rate analysis of different algorithms and can be of independent interest. Finally, we prove the linear convergence result of the GPM to a global maximizer under a general additive noise model based on the established local error bound property. Our theoretical convergence result holds under several deterministic conditions which can cover certain cases with adversarial noise, and as an example we specialize it to the setting of the Erd\"os-R\'enyi measurement graph and Gaussian noise.

Related papers

• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  We provide the first proof of convergence for normalized error feedback algorithms across a wide range of machine learning problems. We show that due to their larger allowable stepsizes, our new normalized error feedback algorithms outperform their non-normalized counterparts on various tasks.
  arXiv  Detail & Related papers  (2024-10-22T10:19:27Z)
• 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)
• On the Estimation Performance of Generalized Power Method for Heteroscedastic Probabilistic PCA [21.9585534723895]
  We show that, given a suitable iterate between the GPMs generated by at least geometrically bound to some threshold, the GPMs decrease to some threshold with the residual part of certain "-resi decomposition" In this paper, we demonstrate the superior performance with sub-Gaussian noise settings using the PCA technique.
  arXiv  Detail & Related papers  (2023-12-06T11:41:17Z)
• Variational Microcanonical Estimator [0.0]
  We propose a variational quantum algorithm for estimating microcanonical expectation values in models obeying the eigenstate thermalization hypothesis. An ensemble of variational states is then used to estimate microcanonical averages of local operators.
  arXiv  Detail & Related papers  (2023-01-10T18:53:24Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  We develop effective Monte Carlo algorithms to approximate the optimal bounds from an arbitrary combination of observational and experimental data. Our algorithms are validated extensively on synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2021-10-12T02:21:30Z)
• Spatially relaxed inference on high-dimensional linear models [48.989769153211995]
  We study the properties of ensembled clustered inference algorithms which combine spatially constrained clustering, statistical inference, and ensembling to aggregate several clustered inference solutions. We show that ensembled clustered inference algorithms control the $delta$-FWER under standard assumptions for $delta$ equal to the largest cluster diameter.
  arXiv  Detail & Related papers  (2021-06-04T16:37:19Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• The Connection between Discrete- and Continuous-Time Descriptions of Gaussian Continuous Processes [60.35125735474386]
  We show that discretizations yielding consistent estimators have the property of invariance under coarse-graining' This result explains why combining differencing schemes for derivatives reconstruction and local-in-time inference approaches does not work for time series analysis of second or higher order differential equations.
  arXiv  Detail & Related papers  (2021-01-16T17:11:02Z)
• A Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Group [29.714239628405515]
  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.
  arXiv  Detail & Related papers  (2020-09-16T07:25:50Z)
• 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)
• Synchronizing Probability Measures on Rotations via Optimal Transport [26.110033098056334]
  We introduce a new paradigm,textitmeasure synchronization$, for synchronizing graphs with measure-valued uncertainties. In particular, we aim estimating absolute orientations of absolute rotations on a graph on-on-manis.
  arXiv  Detail & Related papers  (2020-04-01T18:44:18Z)

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.