Bandeira, Afonso S; Chen, Yutong; Lederman, Roy R; Singer, Amit Non-unique games over compact groups and orientation estimation in cryo-EM Journal Article Inverse Problems, 36 (6), pp. 064002, 2020, ISSN: 0266-5611, 1361-6420. Links | BibTeX | Tags: Algorithms, cryo-EM, Non-unique games, Representation Theory @article{bandeira_non-unique_2020, title = {Non-unique games over compact groups and orientation estimation in cryo-EM}, author = {Afonso S Bandeira and Yutong Chen and Roy R Lederman and Amit Singer}, url = {https://iopscience.iop.org/article/10.1088/1361-6420/ab7d2c}, doi = {10.1088/1361-6420/ab7d2c}, issn = {0266-5611, 1361-6420}, year = {2020}, date = {2020-01-01}, urldate = {2020-08-13}, journal = {Inverse Problems}, volume = {36}, number = {6}, pages = {064002}, keywords = {Algorithms, cryo-EM, Non-unique games, Representation Theory}, pubstate = {published}, tppubtype = {article} } |
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. |
Lederman, Roy R; Singer, Amit A Representation Theory Perspective on Simultaneous Alignment and Classification Technical Report (arXiv:1607.03464 [cs, math]), 2016, (arXiv: 1607.03464). Abstract | Links | BibTeX | Tags: Algorithms, Computer Science - Computer Vision and Pattern Recognition, cryo-EM, Mathematics - Optimization and Control, Representation Theory @techreport{lederman_representation_2016, title = {A Representation Theory Perspective on Simultaneous Alignment and Classification}, author = {Roy R Lederman and Amit Singer}, url = {http://arxiv.org/abs/1607.03464}, year = {2016}, date = {2016-07-01}, urldate = {2021-01-22}, number = {arXiv:1607.03464 [cs, math]}, abstract = {One of the difficulties in 3D reconstruction of molecules from images in single particle Cryo-Electron Microscopy (Cryo-EM), in addition to high levels of noise and unknown image orientations, is heterogeneity in samples: in many cases, the samples contain a mixture of molecules, or multiple conformations of one molecule. Many algorithms for the reconstruction of molecules from images in heterogeneous Cryo-EM experiments are based on iterative approximations of the molecules in a non-convex optimization that is prone to reaching suboptimal local minima. Other algorithms require an alignment in order to perform classification, or vice versa. The recently introduced Non-Unique Games framework provides a representation theoretic approach to studying problems of alignment over compact groups, and offers convex relaxations for alignment problems which are formulated as semidefinite programs (SDPs) with certificates of global optimality under certain circumstances. In this manuscript, we 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 respective classes. Our proposed approach can also be extended to the case of continuous heterogeneity.}, note = {arXiv: 1607.03464}, keywords = {Algorithms, Computer Science - Computer Vision and Pattern Recognition, cryo-EM, Mathematics - Optimization and Control, Representation Theory}, pubstate = {published}, tppubtype = {techreport} } One of the difficulties in 3D reconstruction of molecules from images in single particle Cryo-Electron Microscopy (Cryo-EM), in addition to high levels of noise and unknown image orientations, is heterogeneity in samples: in many cases, the samples contain a mixture of molecules, or multiple conformations of one molecule. Many algorithms for the reconstruction of molecules from images in heterogeneous Cryo-EM experiments are based on iterative approximations of the molecules in a non-convex optimization that is prone to reaching suboptimal local minima. Other algorithms require an alignment in order to perform classification, or vice versa. The recently introduced Non-Unique Games framework provides a representation theoretic approach to studying problems of alignment over compact groups, and offers convex relaxations for alignment problems which are formulated as semidefinite programs (SDPs) with certificates of global optimality under certain circumstances. In this manuscript, we 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 respective classes. Our proposed approach can also be extended to the case of continuous heterogeneity. |