Lederman, Roy R; Singer, Amit A representation theory perspective on simultaneous alignment and classification Journal Article Applied and Computational Harmonic Analysis, 49 (3), pp. 1001–1024, 2020, ISSN: 1063-5203. Abstract | Links | BibTeX | Tags: Algorithms, Alignment, Classification, cryo-EM, Graph-cut, heterogeneity, Heterogeneous multireference alignment, Representation Theory, Rotation group, SDP, Synchronization @article{lederman_representation_2020, title = {A representation theory perspective on simultaneous alignment and classification}, author = {Roy R Lederman and Amit Singer}, url = {http://www.sciencedirect.com/science/article/pii/S1063520319301034}, doi = {10.1016/j.acha.2019.05.005}, issn = {1063-5203}, year = {2020}, date = {2020-01-01}, urldate = {2021-01-22}, journal = {Applied and Computational Harmonic Analysis}, volume = {49}, number = {3}, pages = {1001--1024}, abstract = {Single particle cryo-electron microscopy (EM) is a method for determining the 3-D structure of macromolecules from many noisy 2-D projection images of individual macromolecules whose orientations and positions are random and unknown. The problem of orientation assignment for the images motivated work on multireference alignment. The recent non-unique games framework provides a representation theoretic approach to alignment over compact groups, and offers a convex relaxation with certificates of global optimality in some cases. One of the great opportunities in cryo-EM is studying heterogeneous samples, containing two or more distinct conformations of molecules. Taking advantage of this opportunity presents an algorithmic challenge: determining both the class and orientation of each particle. We generalize multireference alignment to a problem of alignment and classification, and propose to extend non-unique games to the problem of simultaneous alignment and classification with the goal of simultaneously classifying cryo-EM images and aligning them within their classes.}, keywords = {Algorithms, Alignment, Classification, cryo-EM, Graph-cut, heterogeneity, Heterogeneous multireference alignment, Representation Theory, Rotation group, SDP, Synchronization}, pubstate = {published}, tppubtype = {article} } Single particle cryo-electron microscopy (EM) is a method for determining the 3-D structure of macromolecules from many noisy 2-D projection images of individual macromolecules whose orientations and positions are random and unknown. The problem of orientation assignment for the images motivated work on multireference alignment. The recent non-unique games framework provides a representation theoretic approach to alignment over compact groups, and offers a convex relaxation with certificates of global optimality in some cases. One of the great opportunities in cryo-EM is studying heterogeneous samples, containing two or more distinct conformations of molecules. Taking advantage of this opportunity presents an algorithmic challenge: determining both the class and orientation of each particle. We generalize multireference alignment to a problem of alignment and classification, and propose to extend non-unique games to the problem of simultaneous alignment and classification with the goal of simultaneously classifying cryo-EM images and aligning them within their classes. |

Boumal, N; Bendory, T; Lederman, Roy R; Singer, A Heterogeneous multireference alignment: A single pass approach Inproceedings 2018 52nd Annual Conference on Information Sciences and Systems (CISS), pp. 1–6, 2018. Abstract | Links | BibTeX | Tags: bispectrum, concave programming, cryo-EM, cyclic shifts, Discrete Fourier transforms, estimation theory, expectation-maximization, Gaussian mixture models, heterogeneity, heterogeneous MRA, Heterogeneous multireference alignment, Multireference alignment, Noise measurement, non-convex optimization, nonconvex optimization problem, Optimization, Reliability, signal estimation, signal processing, Signal resolution, Signal to noise ratio, single pass approach, Standards @inproceedings{boumal_heterogeneous_2018, title = {Heterogeneous multireference alignment: A single pass approach}, author = {N Boumal and T Bendory and Roy R Lederman and A Singer}, doi = {10.1109/CISS.2018.8362313}, year = {2018}, date = {2018-01-01}, booktitle = {2018 52nd Annual Conference on Information Sciences and Systems (CISS)}, pages = {1--6}, abstract = {Multireference alignment (MRA) is the problem of estimating a signal from many noisy and cyclically shifted copies of itself. In this paper, we consider an extension called heterogeneous MRA, where K signals must be estimated, and each observation comes from one of those signals, unknown to us. This is a simplified model for the heterogeneity problem notably arising in cryo-electron microscopy. We propose an algorithm which estimates the K signals without estimating either the shifts or the classes of the observations. It requires only one pass over the data and is based on low-order moments that are invariant under cyclic shifts. Given sufficiently many measurements, one can estimate these invariant features averaged over the K signals. We then design a smooth, non-convex optimization problem to compute a set of signals which are consistent with the estimated averaged features. We find that, in many cases, the proposed approach estimates the set of signals accurately despite non-convexity, and conjecture the number of signals K that can be resolved as a function of the signal length L is on the order of √L.}, keywords = {bispectrum, concave programming, cryo-EM, cyclic shifts, Discrete Fourier transforms, estimation theory, expectation-maximization, Gaussian mixture models, heterogeneity, heterogeneous MRA, Heterogeneous multireference alignment, Multireference alignment, Noise measurement, non-convex optimization, nonconvex optimization problem, Optimization, Reliability, signal estimation, signal processing, Signal resolution, Signal to noise ratio, single pass approach, Standards}, pubstate = {published}, tppubtype = {inproceedings} } Multireference alignment (MRA) is the problem of estimating a signal from many noisy and cyclically shifted copies of itself. In this paper, we consider an extension called heterogeneous MRA, where K signals must be estimated, and each observation comes from one of those signals, unknown to us. This is a simplified model for the heterogeneity problem notably arising in cryo-electron microscopy. We propose an algorithm which estimates the K signals without estimating either the shifts or the classes of the observations. It requires only one pass over the data and is based on low-order moments that are invariant under cyclic shifts. Given sufficiently many measurements, one can estimate these invariant features averaged over the K signals. We then design a smooth, non-convex optimization problem to compute a set of signals which are consistent with the estimated averaged features. We find that, in many cases, the proposed approach estimates the set of signals accurately despite non-convexity, and conjecture the number of signals K that can be resolved as a function of the signal length L is on the order of √L. |