TY - JOUR
T1 - Bispectrum Inversion with Application to Multireference Alignment
AU - Bendory, Tamir
AU - Boumal, Nicolas
AU - Ma, Chao
AU - Zhao, Zhizhen
AU - Singer, Amit
N1 - Funding Information:
Manuscript received May 16, 2017; revised October 6, 2017; accepted November 6, 2017. Date of publication November 20, 2017; date of current version January 16, 2018. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Antti Tolli. The authors were supported in part by the National Institute of General Medical Sciences under Award Number R01GM090200, in part by the Air Force Office of Scientific Research under Grant FA9550-17-1-0291, in part by Simons Investigator Award and Simons Collaboration on Algorithms and Geometry from Simons Foundation, and in part by the Moore Foundation Data-Driven Discovery Investigator Award. The work of N. Boumal was supported by the National Science Foundation under Grant DMS-1719558. The work of Z. Zhao was supported in part by the National Center for Supercomputing Applications Faculty Fellowship and in part by the University of Illinois at Urbana-Champaign College of Engineering Strategic Research Initiative. (T. Bendory and N. Boumal contributed equally to this work.) (Corresponding author: Tamir Bendory.) T. Bendory, N. Boumal, C. Ma, and A. Singer are with the Program in Applied and Computational Mathematics and the Mathematics Department, Princeton University, Princeton, NJ 08544 USA (e-mail: tamir.bendory@princeton.edu; nboumal@math.princeton.edu; chaom@princeton.edu; amits@math.princeton. edu).
Publisher Copyright:
© 1991-2012 IEEE.
PY - 2018/2/15
Y1 - 2018/2/15
N2 - We consider the problem of estimating a signal from noisy circularly translated versions of itself, called multireference alignment (MRA). One natural approach to MRA could be to estimate the shifts of the observations first, and infer the signal by aligning and averaging the data. In contrast, we consider a method based on estimating the signal directly, using features of the signal that are invariant under translations. Specifically, we estimate the power spectrum and the bispectrum of the signal from the observations. Under mild assumptions, these invariant features contain enough information to infer the signal. In particular, the bispectrum can be used to estimate the Fourier phases. To this end, we propose and analyze a few algorithms. Our main methods consist of nonconvex optimization over the smooth manifold of phases. Empirically, in the absence of noise, these nonconvex algorithms appear to converge to the target signal with random initialization. The algorithms are also robust to noise. We then suggest three additional methods. These methods are based on frequency marching, semidefinite relaxation, and integer programming. The first two methods provably recover the phases exactly in the absence of noise. In the high noise level regime, the invariant features approach for MRA results in stable estimation if the number of measurements scales like the cube of the noise variance, which is the information-Theoretic rate. Additionally, it requires only one pass over the data, which is important at low signal-To-noise ratio when the number of observations must be large.
AB - We consider the problem of estimating a signal from noisy circularly translated versions of itself, called multireference alignment (MRA). One natural approach to MRA could be to estimate the shifts of the observations first, and infer the signal by aligning and averaging the data. In contrast, we consider a method based on estimating the signal directly, using features of the signal that are invariant under translations. Specifically, we estimate the power spectrum and the bispectrum of the signal from the observations. Under mild assumptions, these invariant features contain enough information to infer the signal. In particular, the bispectrum can be used to estimate the Fourier phases. To this end, we propose and analyze a few algorithms. Our main methods consist of nonconvex optimization over the smooth manifold of phases. Empirically, in the absence of noise, these nonconvex algorithms appear to converge to the target signal with random initialization. The algorithms are also robust to noise. We then suggest three additional methods. These methods are based on frequency marching, semidefinite relaxation, and integer programming. The first two methods provably recover the phases exactly in the absence of noise. In the high noise level regime, the invariant features approach for MRA results in stable estimation if the number of measurements scales like the cube of the noise variance, which is the information-Theoretic rate. Additionally, it requires only one pass over the data, which is important at low signal-To-noise ratio when the number of observations must be large.
KW - Bispectrum
KW - cryo-EM
KW - frequency marching
KW - integer programming
KW - multireference alignment
KW - non-convex optimization
KW - optimization on manifolds
KW - phase retrieval
KW - phase synchronization
KW - semidefinite relaxation
UR - http://www.scopus.com/inward/record.url?scp=85035782980&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85035782980&partnerID=8YFLogxK
U2 - 10.1109/TSP.2017.2775591
DO - 10.1109/TSP.2017.2775591
M3 - Article
C2 - 29805244
AN - SCOPUS:85035782980
SN - 1053-587X
VL - 66
SP - 1037
EP - 1050
JO - IEEE Transactions on Signal Processing
JF - IEEE Transactions on Signal Processing
IS - 4
M1 - 8115200
ER -