TY - JOUR
T1 - Multireference Alignment Is Easier with an Aperiodic Translation Distribution
AU - Abbe, Emmanuel
AU - Bendory, Tamir
AU - Leeb, William
AU - Pereira, João M.
AU - Sharon, Nir
AU - Singer, Amit
N1 - Funding Information:
Manuscript received February 13, 2018; revised October 30, 2018; accepted December 5, 2018. Date of publication December 27, 2018; date of current version May 20, 2019. E. Abbe was supported in part by the Bell Labs Prize, in part by the NSF CAREER Award under Grant CCF–1552131, in part by ARO under Grant W911NF–16–1–0051, in part by the NSF Center for the Science of Information under Grant CCF–0939370, and in part by the Google Faculty Research Award. T. Bendory, W. Leeb, J. M. Pereira, N. Sharon, and A. Singer were supported in part by NIGMS under Award R01GM090200, in part by the Simons Foundation Investigator Award and Simons Collaboration on Algorithms and Geometry, in part by the Moore Foundation Data-Driven Discovery Investigator Award, in part by AFOSR under Grant FA9550-17-1-0291, and in part by NSF BIGDATA under Award IIS-1837992.
Publisher Copyright:
© 1963-2012 IEEE.
PY - 2019/6
Y1 - 2019/6
N2 - In the multireference alignment model, a signal is observed by the action of a random circular translation and the addition of Gaussian noise. The goal is to recover the signal's orbit by accessing multiple independent observations. Of particular interest is the sample complexity, i.e., the number of observations/samples needed in terms of the signal-to-noise ratio (SNR) (the signal energy divided by the noise variance) in order to drive the mean-square error to zero. Previous work showed that if the translations are drawn from the uniform distribution, then, in the low SNR regime, the sample complexity of the problem scales as ω (1/ SNR3). In this paper, using a generalization of the Chapman-Robbins bound for orbits and expansions of the χ2 divergence at low SNR, we show that in the same regime the sample complexity for any aperiodic translation distribution scales as ω (1/ SNR2). This rate is achieved by a simple spectral algorithm. We propose two additional algorithms based on non-convex optimization and expectation-maximization. We also draw a connection between the multireference alignment problem and the spiked covariance model.
AB - In the multireference alignment model, a signal is observed by the action of a random circular translation and the addition of Gaussian noise. The goal is to recover the signal's orbit by accessing multiple independent observations. Of particular interest is the sample complexity, i.e., the number of observations/samples needed in terms of the signal-to-noise ratio (SNR) (the signal energy divided by the noise variance) in order to drive the mean-square error to zero. Previous work showed that if the translations are drawn from the uniform distribution, then, in the low SNR regime, the sample complexity of the problem scales as ω (1/ SNR3). In this paper, using a generalization of the Chapman-Robbins bound for orbits and expansions of the χ2 divergence at low SNR, we show that in the same regime the sample complexity for any aperiodic translation distribution scales as ω (1/ SNR2). This rate is achieved by a simple spectral algorithm. We propose two additional algorithms based on non-convex optimization and expectation-maximization. We also draw a connection between the multireference alignment problem and the spiked covariance model.
KW - Multireference alignment
KW - cryo-EM
KW - expectation-maximization
KW - method of moments
KW - non-convex optimization
KW - spectral algorithm
KW - spiked covariance model
UR - http://www.scopus.com/inward/record.url?scp=85059266992&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85059266992&partnerID=8YFLogxK
U2 - 10.1109/TIT.2018.2889674
DO - 10.1109/TIT.2018.2889674
M3 - Article
AN - SCOPUS:85059266992
SN - 0018-9448
VL - 65
SP - 3565
EP - 3584
JO - IRE Professional Group on Information Theory
JF - IRE Professional Group on Information Theory
IS - 6
M1 - 8590822
ER -