A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization

Community detection and synchronization are both fundamental problems in signal processing, machine learning, and computer vision. Recently, there is an increasing interest in their joint problem [27, 8, 44]. That is, in the presence of heterogeneous data where data points associated with random group elements (e.g. the orthogonal group O(d) of dimension d) fall into multiple underlying clusters, the joint problem is to simultaneously recover the cluster structures as well as the group elements. A motivating example is the 2D class averaging process in cryo-electron microscopy single particle reconstruction [30, 58, 68], whose goal is to align (with SO(2) group synchronization) and average projection images of a single particle with similar viewing angles to improve their signal-to-noise ratio (SNR). Another application in computer vision is simultaneous permutation group synchronization and clustering on heterogeneous object collections consisting of 2D images or 3D shapes [8]. In this work, we study the joint problem based on the probabilistic model introduced in [27] which extends the celebrated stochastic block model (SBM) [19, 21, 22, 29, 38, 41, 49, 50, 51, 52] (see Figure 1) for community detection. In particular, we focus on the orthogonal group O(d) that covers a wide range of applications mentioned above.