WikiSysop: Created page with "== Citation == Bendory, Tamir / Mickelin, Oscar / Singer, Amit. Sparse multi-reference alignment: Sample complexity and computational hardness. 2022. ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), p. 8977-8981 == Abstract == Motivated by the problem of determining the atomic structure of macromolecules using single-particle cryo-electron microscopy (cryo-EM), we study the sample and computational complexities of th..."

2024-09-04T06:41:44Z

Created page with "== Citation == Bendory, Tamir / Mickelin, Oscar / Singer, Amit. Sparse multi-reference alignment: Sample complexity and computational hardness. 2022. ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), p. 8977-8981 == Abstract == Motivated by the problem of determining the atomic structure of macromolecules using single-particle cryo-electron microscopy (cryo-EM), we study the sample and computational complexities of th..."

New page

== Citation ==

Bendory, Tamir / Mickelin, Oscar / Singer, Amit. Sparse multi-reference alignment: Sample complexity and computational hardness. 2022. ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), p. 8977-8981

== Abstract ==

Motivated by the problem of determining the atomic structure of
macromolecules using single-particle cryo-electron microscopy
(cryo-EM), we study the sample and computational complexities
of the sparse multi-reference alignment (MRA) model: the problem
of estimating a sparse signal from its noisy, circularly shifted
copies. Based on its tight connection to the crystallographic phase
retrieval problem, we establish that if the number of observations
is proportional to the square of the variance of the noise, then the
sparse MRA problem is statistically feasible for sufficiently sparse
signals. To investigate its computational hardness, we consider
three types of computational frameworks: projection-based algorithms,
bispectrum inversion, and convex relaxations. We show that
a state-of-the-art projection-based algorithm achieves the optimal
estimation rate, but its computational complexity is exponential in
the sparsity level. The bispectrum framework provides a statisticalcomputational
trade-off: it requires more observations (so its estimation
rate is suboptimal), but its computational load is provably
polynomial in the signal’s length. The convex relaxation approach
provides polynomial-time algorithms (with a large exponent) that
recover sufficiently sparse signals at the optimal estimation rate. We
conclude the paper by discussing potential statistical and algorithmic
implications for cryo-EM.

== Keywords ==

== Links ==

https://ieeexplore.ieee.org/abstract/document/9746298

== Related software ==

== Related methods ==

== Comments ==

2022Bendory Complexity - Revision history