Generalized Power Methods for Group Synchronization Problems
Event details
| Date | 09.03.2023 |
| Hour | 15:00 › 16:00 |
| Speaker |
Professor Man-Chung Yue, University of Hong Kong
Biography Dr. Man-Chung Yue is currently an Assistant Professor at the Musketeers Foundation Institute of Data Science and the Department of Industrial and Manufacturing Systems Engineering, The University of Hong Kong. He received his B.Sc. degree in Mathematics and Ph.D. degree in Systems Engineering and Engineering Management, both from The Chinese University of Hong Kong. Before joining The University of Hong Kong, he worked in The Hong Kong Polytechnic University as an Assistant Professor and Imperial College London as a Research Associate. His research focuses on continuous optimization and its interplay with decision-making under uncertainty, signal processing, machine learning and operations research. |
| Location | |
| Category | Conferences - Seminars |
| Event Language | English |
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.
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.
Practical information
- Informed public
- Registration required
Organizer
- Professor Daniel Kuhn, EPFL CDM MTEI RAO
Contact
- Angela Devenoge