Skip to content
Title: Generalized Power Methods for Group Synchronization Problems
Speaker: Dr. Man Chung Yue, Assistant Professor, IDS & Department of Industrial and Manufacturing Systems Engineering, HKU
Date: Jul 6, 2023
Time: 10:30am – 11:30am

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

Dr. Man Chung Yue
Assistant Professor @ HKU IDS & Department of IMSE
Dr. Man Chung Yue is an Assistant Professor jointly affiliated with the Musketeers Foundation Institute of Data Science and the Department of Industrial and Manufacturing Systems Engineering at The University of Hong Kong. Prior to joining HKU, he was an Assistant Professor in the Department of Applied Mathematics at The Hong Kong Polytechnic University. From 2017 to 2019, he worked as a Research Associate at Imperial College London. He received his Ph.D. in Systems Engineering and Engineering Management in 2017 and B.Sc. in Mathematics in 2012, both from The Chinese University of Hong Kong. His research focuses on optimization, data science and decision-making under uncertainty.
For full biography of Dr. Yue, please refer to: https://datascience.hku.hk/people/man-chung-yue/

For information, please contact:
Email: datascience@hku.hk