Joint clustering and group synchronization: fundamental limits and efficient algorithms

Fan, Yifeng

Permalink

https://hdl.handle.net/2142/121940 Copy

Description

Title

Joint clustering and group synchronization: fundamental limits and efficient algorithms

Author(s)

Fan, Yifeng

Issue Date

2023-09-05

Director of Research (if dissertation) or Advisor (if thesis)

Khoo, Yuehaw

Doctoral Committee Chair(s)

Zhao, Zhizhen

Committee Member(s)

• Hajek, Bruce
• Milenkovic, Olgica
• Shomorony, Ilan

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

Clustering, Group synchronization

Abstract

The explosion of data in recent decades poses a formidable obstacle in data analysis due to its extensive volume and the low signal-to-noise ratio (SNR). Specifically, clustering and synchronization emerge as two fundamental problems that find applications across various scientific disciplines. In this thesis, we delve into a scenario where these two problems converge such that in the presence of heterogeneous data, each sample not only falls onto an underlying category or cluster but also associates with an unknown group element, giving rise to a joint problem that aims to recover the cluster structures and the group elements simultaneously. A motivating example is the 2D class averaging problem for cryo-electron microscopy single particle analysis, whose objective revolves around aligning and averaging projection images of a single particle that share similar viewing angles, thereby amplifying their SNR. Our study on the joint problem is based on a statistical model that integrates the stochastic block model for clustering and the random rewiring model for synchronization. In essence, the model generates a random data networks with community structures, where nodes within the same community are densely connected, as apposed to nodes across different communities that are sparsely connected. Furthermore, group transformations are observed on edges, resulting in clear observations for edges within the same cluster, while the transformations for connections across clusters are completely noisy. The first half of this thesis focuses on the development of efficient algorithms to solve the joint problem within the proposed model. Initially, we derive the maximum likelihood estimator (MLE) for recovery in the model. However, due to the non-convex nature and computational complexity of the MLE, we introduce an alternative formulation that allows for convex relaxations. This formulation serves as the foundation for the development of two efficient algorithms based on semidefinite relaxation and spectral relaxation, respectively. Remarkably, both methods achieve exact recovery of the cluster structures and the group elements, subject to mild conditions on the model parameters. In addition, we establish a performance guarantee for each algorithm, which sharply characterizes the empirical phase transition threshold for achieving exact recovery. The second part centers on the fundamental limits for creating an algorithm that achieves the exact recovery on the proposed model. In particular, we investigate the performance of the MLE, which represents the optimal estimator in terms of the recovery accuracy under a uniform prior. Through our analysis, we establish a sharp phase transition threshold for exact recovery by the MLE. Above the threshold, the exact recovery is achieved with high probability, while the MLE fails to recover with high probability below the threshold, indicating that no algorithms can succeed in such regime. Moreover, by comparing these limits with the performance of the proposed algorithms, we demonstrate a significant performance gap between the MLE and those efficient algorithms, suggesting that there is substantial room for improving the existing algorithms.

Graduation Semester

2023-12

Type of Resource

Thesis

Copyright and License Information

Copyright 2023 Yifeng Fan

Owning Collections