The sample complexity of multireference alignment
From MaRDI portal
Abstract: The growing role of data-driven approaches to scientific discovery has unveiled a large class of models that involve latent transformations with a rigid algebraic constraint. Three-dimensional molecule reconstruction in Cryo-Electron Microscopy (cryo-EM) is a central problem in this class. Despite decades of algorithmic and software development, there is still little theoretical understanding of the sample complexity of this problem, that is, number of images required for 3-D reconstruction. Here we consider multi-reference alignment (MRA), a simple model that captures fundamental aspects of the statistical and algorithmic challenges arising in cryo-EM and related problems. In MRA, an unknown signal is subject to two types of corruption: a latent cyclic shift and the more traditional additive white noise. The goal is to recover the signal at a certain precision from independent samples. While at high signal-to-noise ratio (SNR), the number of observations needed to recover a generic signal is proportional to , we prove that it rises to a surprising in the low SNR regime. This precise phenomenon was observed empirically more than twenty years ago for cryo-EM but has remained unexplained to date. Furthermore, our techniques can easily be extended to the heterogeneous MRA model where the samples come from a mixture of signals, as is often the case in applications such as cryo-EM, where molecules may have different conformations. This provides a first step towards a statistical theory for heterogeneous cryo-EM.
Recommendations
- Multi-reference alignment in high dimensions: sample complexity and phase transition
- A representation theory perspective on simultaneous alignment and classification
- Super-resolution multi-reference alignment
- Estimation under group actions: recovering orbits from invariants
- Rank-one multi-reference factor analysis
Cites work
- A Decomposition for Three-Way Arrays
- Angular synchronization by eigenvectors and semidefinite programming
- Bispectrum Inversion With Application to Multireference Alignment
- Convergence of estimates under dimensionality restrictions
- Fourier PCA and robust tensor decomposition
- Fundamental Limits in Multi-Image Alignment
- scientific article; zbMATH DE number 1194132 (Why is no real title available?)
- scientific article; zbMATH DE number 775749 (Why is no real title available?)
- Multireference Alignment Is Easier With an Aperiodic Translation Distribution
- Multireference alignment using semidefinite programming
- Noisy dynamic simulations in the presence of symmetry: data alignment and model reduction
- Optimal rates of estimation for multi-reference alignment
- Rapid solution of the cryo-EM reconstruction problem by frequency marching
- Reconstruction from limited single-particle diffraction data via simultaneous determination of state, orientation intensity, and phase
- The bispectrum as a source of phase-sensitive invariants for Fourier descriptors: a group-theoretic approach
Cited in
(45)- Rank-one multi-reference factor analysis
- Iterative algorithm for discrete structure recovery
- Optimal rates of estimation for multi-reference alignment
- Signal recovery from a few linear measurements of its high-order spectra
- Multi-target detection with rotations
- General space-efficient sampling algorithm for suboptimal alignment
- Multi-reference alignment in high dimensions: sample complexity and phase transition
- Method of moments for 3D single particle \textit{ab initio} modeling with non-uniform distribution of viewing angles
- Blind Identification of Stochastic Block Models from Dynamical Observations
- Compactification of the rigid motions group in image processing
- Estimating Higher-Order Moments Using Symmetric Tensor Decomposition
- Multi-target detection with application to cryo-electron microscopy
- Likelihood landscape and maximum likelihood estimation for the discrete orbit recovery model
- Sparse multi-reference alignment: phase retrieval, uniform uncertainty principles and the beltway problem
- Toward Single Particle Reconstruction without Particle Picking: Breaking the Detection Limit
- Max filtering with reflection groups
- Maximum likelihood for high-noise group orbit estimation and single-particle cryo-EM
- Estimation under group actions: recovering orbits from invariants
- Rates of estimation for high-dimensional multireference alignment
- The sample complexity of sparse multi-reference alignment and single-particle cryo-electron microscopy
- Average-case complexity of tensor decomposition for low-degree polynomials
- Degree bounds for fields of rational invariants of \(\mathbb{Z}/p\mathbb{Z}\) and other finite groups
- Deep neural-network prior for orbit recovery from method of moments
- Towards a bilipschitz invariant theory
- Orbit recovery for band-limited functions
- The beltway problem over orthogonal groups
- Method of moments for estimation of noisy curves
- Subspace method of moments for \textit{ab initio} 3-D single particle cryo-EM reconstruction
- The stability of generalized phase retrieval problem over compact groups
- The reflection-invariant bispectrum: signal recovery in the dihedral model
- Robust Detection of Lead-Lag Relationships in Lagged Multi-Factor Models
- Sharp concentration of simple random tensors
- Functions on symmetric matrices and point clouds via lightweight invariant features from Galois theory
- Phase retrieval with semialgebraic and ReLU neural network priors
- Embedding distributional data
- Group-invariant max filtering
- Spectral methods from tensor networks
- Circular trace reconstruction
- Separating polynomial invariants over non-closed fields of finite abelian groups
- Sharp concentration of simple random tensors. II: Asymmetry
- Generic orbits, normal bases, and generation degree for fields of rational invariants
- Functional multireference alignment via deconvolution
- A transversality theorem for semi-algebraic sets with application to signal recovery from the second moment and cryo-EM
- Reconstructing rational functions on finite abelian groups with higher autocorrelations
- Provable orbit recovery over SO(3) from the non-uniform second moment
This page was built for publication: The sample complexity of multireference alignment
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5025787)
