Multireference Alignment Is Easier With an Aperiodic Translation Distribution

DOI10.1109/TIT.2018.2889674zbMATH Open1432.94018arXiv1710.02793OpenAlexW2962988788WikidataQ128613429 ScholiaQ128613429MaRDI QIDQ5224017FDOQ5224017

Authors: Emmanuel Abbe, Tamir Bendory, William Leeb, João M. Pereira, Nir Sharon, A. Singer 

Publication date: 19 July 2019

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: 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 (the signal energy divided by the noise variance) in order to drive the mean-square error (MSE) 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 $omega(1/ext{SNR}^3)$. In this work, using a generalization of the Chapman--Robbins bound for orbits and expansions of the $ch{i}^2$ divergence at low SNR, we show that in the same regime the sample complexity for any aperiodic translation distribution scales as $omega(1/ext{SNR}^2)$. 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.

Full work available at URL: https://arxiv.org/abs/1710.02793

zbMATH Keywords

signal-to-noise ratiosample complexityrecovering of signal's orbitsignal observation by action of random circular translation and addition of Gaussian noise

Mathematics Subject Classification ID

Estimation in multivariate analysis (62H12) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cited In (17)

• Deep neural-network prior for orbit recovery from method of moments
• Multi-target detection with application to cryo-electron microscopy
• Maximum likelihood for high-noise group orbit estimation and single-particle cryo-EM
• The sample complexity of multireference alignment
• Orbit recovery for band-limited functions
• Likelihood landscape and maximum likelihood estimation for the discrete orbit recovery model
• Rank-one multi-reference factor analysis
• Power spectrum unbiasing for dilation-invariant multi-reference alignment
• Multi-reference alignment in high dimensions: sample complexity and phase transition
• Method of moments for 3D single particle \textit{ab initio} modeling with non-uniform distribution of viewing angles
• Rates of estimation for high-dimensional multireference alignment
• Sparse multi-reference alignment: phase retrieval, uniform uncertainty principles and the beltway problem
• Optimal rates of estimation for multi-reference alignment
• Toward Single Particle Reconstruction without Particle Picking: Breaking the Detection Limit
• Signal recovery from a few linear measurements of its high-order spectra
• Multi-target detection with rotations
• Iterative algorithm for discrete structure recovery

This page was built for publication: Multireference Alignment Is Easier With an Aperiodic Translation Distribution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5224017)