- June 19, 2023
- Events, Gallery
- HKU IDS Scholar Seminar Series
Mode: Hybrid. Seats for on-site participants are limited. A confirmation email will be sent to participants who have successfully registered.
Abstract
Group synchronization problems (GSPs) aim at recovering a collection of group elements based on their noisy pairwise comparisons and find a wide range of applications in areas such as machine learning, molecular biology, robotics and computer vision. Existing approaches to GSPs are designed only for a specific subgroup, do not scale well and/or lack theoretical guarantees. In this talk, we present a unified approach to the important sub-class of GSPs associated with any closed subgroup of the orthogonal group, which consists of a suitable initialization and an iterative refinement step based on the generalized power method. Theoretically, we show that our approach enjoys a strong guarantee on the estimation error under certain conditions on the group, measurement graph, noise and initialization. We also show that the group condition is satisfied for the orthogonal group, the special orthogonal group, the permutation group and the cyclic group, which are all practically relevant subgroups of the orthogonal group. We then verify the conditions on the measurement graph and noise for standard random graph and random matrix models. Finally, based on the classical notion of metric entropy, we develop a novel spectral-type estimator for GSPs, which can be used as the initialization of our approach.
Speaker
For information, please contact:
Email: datascience@hku.hk