Abstract : We discuss a class of estimation problems that aim for unknown group elements or a signal affected by group actions. Three prominent examples of such problems are synchronization over groups, multireference alignment, and the recovery problem in single-particle cryo-EM. The talks will cover computational and theoretical aspects, including the sample complexity of the problems, constructing group invariant operators, sparsity, recovery strategies, machine learning-based methods, group-robust metrics, data modeling, autocorrelation analysis, and its acceleration techniques, manifold optimization in cryo-EM, synchronization analysis, and more. This mini-symposium is divided into three sections and will host senior and junior researchers as its speakers.
Organizer(s) : Yuehaw Khoo, Nir Sharon, Amit Singer
Zhizhen Jane Zhao (University of Illinois at Urbana-Champaign)
Anderson Ye Zhang (University of Pennsylvania)
Yoel Shkolnisky (Tel Aviv University)
Joakim Anden (KTH Royal Institute of Technology)
Tamir Bendory (Tel Aviv University)
Oscar Mickelin (Princeton University)
William Leeb (University of Minnesota)
Jose Perea (Northeastern University)
Jeff Donatelli (UC Berkeley and Lawrence Berkeley National Laboratory)
Ozan Oktem (KTH Royal Institute of Technology)
Talks in Minisymposium :
[03118] Optimal Spectral Methods for Synchronization Problems
Author(s) :
Anderson Ye Zhang (University of Pennsylvania)
Abstract : We study the performance of spectral methods for synchronization problems with additive Gaussian noises and incomplete data. Spectral methods refer to algorithms that use the leading eigenvectors of the data matrix followed by a normalization step. (1) For phase synchronization and orthogonal group synchronization, we prove that they achieve the minimax lower bound of the problem with a matching leading constant under a squared $\ell_2$ loss. This shows that the spectral method has the same performance as more sophisticated procedures including MLE, generalized power method, and SDP when consistent parameter estimation is possible. (2) For permutation synchronization, we propose a novel spectral method that overcomes a crucial limitation of existing ones and has improved numerical performance. We further show the proposed method is statistically optimal with an exponentially small error that matches the minimax rate.
[04753] Autocorrelation analysis for cryo-EM with sparsity constraints
Author(s) :
Tamir Bendory (Tel Aviv University)
Yuehaw Khoo (The University of Chicago)
Joe Kileel (UT Austin)
Oscar Mickelin (Princeton University)
Amit Singer (Princeton University)
Abstract : This work presents new results for the method of moments applied to cryo-electron microscopy. We prove that autocorrelations of noisy tomographic projection images can reconstruct molecular structures that are modeled as sparse sums of Gaussians. This significantly reduces the sample complexity of the problem, compared to previous results. Additionally, we detail a practical ab initio reconstruction algorithm using tools adapted from crystallographic phase retrieval.
[04814] The sample complexity of multireference alignment and cryo-EM
Author(s) :
Tamir Bendory (Tel Aviv University)
Abstract : The problem of multi-reference alignment (MRA) involves retrieving a signal from multiple copies that have been corrupted by noise and transformed by a random group element. MRA is of particular interest in the context of single-particle cryo-electron microscopy (cryo-EM), a prominent technique used to reconstruct biological molecular structures. During this talk, I will examine the sample complexity of both the MRA and cryo-EM models using tools from representation theory, sparse coding, and generative models.
[04867] Group-robust metrics
Author(s) :
William Leeb (University of Minnesota, Twin Cities)
Abstract : This talk will describe a family of metrics between functions. These metrics are provably robust to a large class of perturbations of the inputs, including the group of integral-preserving reparameterizations; they are also robust to additive noise, and can be evaluated rapidly. Their theoretical properties will be illustrated by numerical experiments.
[05122] Vector bundles for alignment and dimensionality reduction
Author(s) :
Jose Perea (Northeastern University)
Luis Scoccola (Northeastern University)
Abstract : Vector bundles have rich structure and arise naturally when trying to solve dimensionality reduction and synchronization problems in data science. I will show in this talk how the classical machinery (e.g., classifying maps, characteristic classes, etc) can be adapted to the world of algorithms and noisy data, as well as the insights one can gain.
[05181] Orthogonal Matrix Retrieval with Spatial Consensus for 3D Unknown-View Tomography
Author(s) :
Shuai Huang (Emory University)
Mona Zehni (University of Illinois at Urbana-Champaign)
Ivan Dokmanic (University of Basel)
Zhizhen Zhao (University of Illinois at Urbana Champaign)
Abstract : A line of work starting with Kam (1980) employs the method of moments (MoM) with rotation-invariant features to reconstruct a 3D density map from its 2D tomographic projections at unknown, random orientations, assuming that the orientations are uniformly distributed. This line of work includes the recent orthogonal matrix retrieval approaches. In this talk, we extend the previous approaches and propose to jointly recover the density map and the orthogonal matrices by imposing spatial nonnegativity constraint.