WikiSysop at 20:04, 23 December 2024

2024-12-23T20:04:13Z

← Older revision		Revision as of 20:04, 23 December 2024
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 number of observations,
	is the variance of the noise, and		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,		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		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.		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 ==

WikiSysop: 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..."

2024-12-23T20:03:26Z

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..."

New page

== 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

== Related software ==

== Related methods ==

== Comments ==

2024Bendory Complexity - Revision history

WikiSysop at 20:04, 23 December 2024