Bispectrum Inversion With Application to Multireference Alignment

DOI10.1109/TSP.2017.2775591MaRDI QIDQ4621616zbMATH OpenWikidataFDO

Authors Tamir Bendory, Nicolas Boumal, Chao Ma, Zhizhen Zhao, A. Singer

Publication date 12 February 2019

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: 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 non-convex optimization over the smooth manifold of phases. Empirically, in the absence of noise, these non-convex 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.

Cited in

(36)

• Rank-one multi-reference factor analysis
• Iterative algorithm for discrete structure recovery
• On signal reconstruction from FROG measurements
• Signal recovery from a few linear measurements of its high-order spectra
• Multi-target detection with rotations
• Bearing estimation in the bispectrum domain
• 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
• The sample complexity of multireference alignment
• Compactification of the rigid motions group in image processing
• Optimized response function estimation for spherical deconvolution
• Multi-target detection with application to cryo-electron microscopy
• Benchmark problems for phase retrieval
• Likelihood Maximization and Moment Matching in Low <scp>SNR</scp> Gaussian Mixture Models
• Likelihood landscape and maximum likelihood estimation for the discrete orbit recovery model
• Sparse multi-reference alignment: phase retrieval, uniform uncertainty principles and the beltway problem
• A unified approach to synchronization problems over subgroups of the orthogonal group
• Maximum likelihood for high-noise group orbit estimation and single-particle cryo-EM
• Estimation under group actions: recovering orbits from invariants
• Power spectrum unbiasing for dilation-invariant multi-reference alignment
• Rates of estimation for high-dimensional multireference alignment
• Average-case complexity of tensor decomposition for low-degree polynomials
• Deep neural-network prior for orbit recovery from method of moments
• Towards a bilipschitz invariant theory
• Orbit recovery for band-limited functions
• The beltway problem over orthogonal groups
• The stability of generalized phase retrieval problem over compact groups
• The reflection-invariant bispectrum: signal recovery in the dihedral model
• Phase retrieval with semialgebraic and ReLU neural network priors
• Spectral methods from tensor networks
• Separating polynomial invariants over non-closed fields of finite abelian groups
• Unitary invariants of the finite Heisenberg group
• Sample complexity analysis of multi-target detection via Markovian and hard-core multi-reference alignment
• Functional multireference alignment via deconvolution
• A transversality theorem for semi-algebraic sets with application to signal recovery from the second moment and cryo-EM
• Provable orbit recovery over SO(3) from the non-uniform second moment

This page was built for publication: Bispectrum Inversion With Application to Multireference Alignment

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