2024Bendory Complexity: Difference between revisions
Created page with "== Citation == T. Bendory and D. Edidin, “The Sample Complexity of Sparse Multireference Alignment and Single-Particle Cryo-Electron Microscopy,” SIAM J. on Mathematics of Data Science, vol. 6, no. 2, pp. 254–282, 2024. == Abstract == Multireference 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 ha..." |
No edit summary |
||
| Line 7: | Line 7: | ||
Multireference 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 | Multireference 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 | ||
, where | , where | ||
is the number of observations, | |||
is the variance of the noise, and | |||
is the lowest-order moment of the observations that uniquely determines the signal. In particular, it was shown that, in many cases, | |||
for generic signals, and thus, the sample complexity is | |||
. 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 | . 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 | ||
. Notably, we show that the sample complexity of cryo-EM is | . Notably, we show that the sample complexity of cryo-EM is | ||
if at most one-third of the coefficients representing the molecular structure are nonzero; 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. | |||
== Keywords == | == Keywords == | ||
Latest revision as of 20:04, 23 December 2024
Citation
T. Bendory and D. Edidin, “The Sample Complexity of Sparse Multireference Alignment and Single-Particle Cryo-Electron Microscopy,” SIAM J. on Mathematics of Data Science, vol. 6, no. 2, pp. 254–282, 2024.
Abstract
Multireference 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 , where is the number of observations, is the variance of the noise, and is the lowest-order moment of the observations that uniquely determines the signal. In particular, it was shown that, in many cases, for generic signals, and thus, the sample complexity is . 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 . Notably, we show that the sample complexity of cryo-EM is if at most one-third of the coefficients representing the molecular structure are nonzero; 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.
Keywords
Links
https://epubs.siam.org/doi/abs/10.1137/23M155685X