서브메뉴
검색
Joint Clustering and Group Synchronization: Fundamental Limits and Efficient Algorithms
Joint Clustering and Group Synchronization: Fundamental Limits and Efficient Algorithms
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20260209102856
- ISBN
- 9798291574454
- DDC
- 004
- 저자명
- Fan, Yifeng.
- 서명/저자
- Joint Clustering and Group Synchronization: Fundamental Limits and Efficient Algorithms
- 발행사항
- [Sl] : University of Illinois at Urbana-Champaign, 2023
- 발행사항
- Ann Arbor : ProQuest Dissertations & Theses, 2023
- 형태사항
- 217 p
- 주기사항
- Source: Dissertations Abstracts International, Volume: 87-03, Section: A.
- 주기사항
- Advisor: Zhao, Zhizhen.
- 학위논문주기
- Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2023.
- 초록/해제
- 요약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.
- 일반주제명
- Computer science
- 일반주제명
- Electrical engineering
- 일반주제명
- Computer engineering
- 일반주제명
- Information science
- 키워드
- Clustering
- 기타저자
- University of Illinois at Urbana-Champaign Electrical & Computer Eng
- 기본자료저록
- Dissertations Abstracts International. 87-03A.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008260203s2023 us c eng d■001000017365927
■00520260209102856
■006m o d
■007cr#unu||||||||
■020 ▼a9798291574454
■035 ▼a(MiAaPQ)AAI32272146
■035 ▼a(MiAaPQ)httphdlhandlenet2142121940
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a004
■1001 ▼aFan, Yifeng.
■24510▼aJoint Clustering and Group Synchronization: Fundamental Limits and Efficient Algorithms
■260 ▼a[Sl]▼bUniversity of Illinois at Urbana-Champaign▼c2023
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2023
■300 ▼a217 p
■500 ▼aSource: Dissertations Abstracts International, Volume: 87-03, Section: A.
■500 ▼aAdvisor: Zhao, Zhizhen.
■5021 ▼aThesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2023.
■520 ▼aThe 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.
■590 ▼aSchool code: 0090.
■650 4▼aComputer science
■650 4▼aElectrical engineering
■650 4▼aComputer engineering
■650 4▼aInformation science
■653 ▼aClustering
■653 ▼aGroup synchronization
■653 ▼aSignal-to-noise ratio
■653 ▼aMaximum likelihood estimator
■690 ▼a0544
■690 ▼a0984
■690 ▼a0464
■690 ▼a0723
■71020▼aUniversity of Illinois at Urbana-Champaign▼bElectrical & Computer Eng.
■7730 ▼tDissertations Abstracts International▼g87-03A.
■790 ▼a0090
■791 ▼aPh.D.
■792 ▼a2023
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17365927▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
