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

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

VL - 66

SP - 1037

EP - 1050

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

SN - 1053-587X

IS - 4

M1 - 8115200

ER -