Joint Community Detection and Rotational Synchronization via Semidefinite Programming

In the presence of heterogeneous data, where randomly rotated objects fall into multiple underlying categories, it is challenging to simultaneously synchronize the objects and classify them into clusters. A motivating example is the 2D class averaging in cryo-electron microscopy single particle reconstruction [17, 41, 49]. It aims to cluster images taken from similar viewing directions, rotationally align and average those images in order to denoise the experimental data. Joint clustering and synchronization is an emerging area that connects community detection [1, 16, 32, 2, 19, 20] and synchronization [39, 7, 18]. Recently, several works discussed simultaneous classification and mapping (alignment) [4, 24] and proposed different models and algorithms. In [4], the authors addressed simultaneous permutation group synchronization and clustering via a spectral method with rounding and used the consistency of the mapping for clustering. In [24], the authors noticed that both rotational alignment and classification are problems over compact groups and proposed a harmonic analysis and semidefinite programming based approach for solving alignment and classification simultaneously. In this paper, we consider joint community detection and rotational synchronization under a specific probabilistic model, which extends the celebrated stochastic block model (SBM) [9, 10, 11, 15, 21, 22, 28, 29, 30, 31] to incorporate both the community structure and pairwise rotations. In particular, we inherit the G(n, p, q)-SBM setting [26, 19, 2, 20] for the graph connection as shown in Figure 1.