The sample complexity of sparse multi-reference alignment and single-particle cryo-electron microscopy

DOI10.1137/23M155685XMaRDI QIDQ6415353zbMATH OpenOpenAlexWikidataFDO

Authors Tamir Bendory, Dan Edidin

Publication date 27 October 2022

Full work available at URL https://doi.org/10.1137/23m155685x

Mathematics Subject Classification ID

Applications of group representations to physics and other areas of science (20C35) Computing methodologies for image processing (68U10) Crystalline structure (74E15) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: Multi-reference alignment (MRA) is the problem of recovering a signal from its multiple noisy copies, each acted upon by a random group element. MRA is mainly motivated by single-particle cryo-electron microscopy (cryo-EM) that has recently joined X-ray crystallography as one of the two leading technologies to reconstruct biological molecular structures. Previous papers have shown that in the high noise regime, the sample complexity of MRA and cryo-EM is $n=omega(sigm{a}^{2d})$, where $n$ is the number of observations, $sigm{a}^2$ is the variance of the noise, and $d$ is the lowest-order moment of the observations that uniquely determines the signal. In particular, it was shown that in many cases, $d=3$ for generic signals, and thus the sample complexity is $n=omega(sigm{a}^6)$. In this paper, we analyze the second moment of the MRA and cryo-EM models. First, we show that in both models the second moment determines the signal up to a set of unitary matrices, whose dimension is governed by the decomposition of the space of signals into irreducible representations of the group. Second, we derive sparsity conditions under which a signal can be recovered from the second moment, implying sample complexity of $n=omega(sigm{a}^4)$. Notably, we show that the sample complexity of cryo-EM is $n=omega(sigm{a}^4)$ if at most one third of the coefficients representing the molecular structure are non-zero; this bound is near-optimal. The analysis is based on tools from representation theory and algebraic geometry. We also derive bounds on recovering a sparse signal from its power spectrum, which is the main computational problem of X-ray crystallography.

Recommendations

• The sample complexity of multireference alignment
• Multi-reference alignment in high dimensions: sample complexity and phase transition
• Estimation under group actions: recovering orbits from invariants
• A representation theory perspective on simultaneous alignment and classification

Cited in

(14)

• Maximum likelihood for high-noise group orbit estimation and single-particle cryo-EM
• Rates of estimation for high-dimensional multireference alignment
• Orbit recovery for band-limited functions
• The beltway problem over orthogonal groups
• 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
• Recovering a group from few orbits
• Functions on symmetric matrices and point clouds via lightweight invariant features from Galois theory
• Phase retrieval with semialgebraic and ReLU neural network priors
• The generic crystallographic phase retrieval problem
• Two datasets are better than one: method of double moments for 3D reconstruction in cryo-EM
• Sample complexity analysis of multi-target detection via Markovian and hard-core multi-reference alignment
• Functional multireference alignment via deconvolution
• A transversality theorem for semi-algebraic sets with application to signal recovery from the second moment and cryo-EM

This page was built for publication: The sample complexity of sparse multi-reference alignment and single-particle cryo-electron microscopy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6415353)