Estimation under group actions: recovering orbits from invariants

Abstract

We study a class of orbit recovery problems in which we observe independent copies of an unknown element of ${\mathbb{R}}^p$, each linearly acted upon by a random element of some group (such as $\mathbb{Z}/p$ or $\mathrm{SO}(3)$) and then corrupted by additive Gaussian noise. We prove matching upper and lower bounds on the number of samples required to approximately recover the group orbit of this unknown element with high probability. These bounds, based on quantitative techniques in invariant theory, give a precise correspondence between the statistical difficulty of the estimation problem and algebraic properties of the group. Furthermore, we give computer-assisted procedures to certify these properties that are computationally efficient in many cases of interest. The model is motivated by geometric problems in signal processing, computer vision, and structural biology, and applies to the reconstruction problem in cryo-electron microscopy (cryo-EM), a problem of significant practical interest. Our results allow us to verify (for a given problem size) that if cryo-EM images are corrupted by noise with variance ${\sigma }^2$, the number of images required to recover the molecule structure scales as ${\sigma }^6$. We match this bound with a novel (albeit computationally expensive) algorithm for ab initio reconstruction in cryo-EM, based on invariant features of degree at most 3. We further discuss how to recover multiple molecular structures from mixed (or heterogeneous) cryo-EM samples.

arXiv comment81 pages. Minor revisions since previous version, reflecting peer review feedback. To be published in Applied and Computational Harmonic Analysis

References in corpus (20)

• Bispectrum Inversion with Application to Multireference Alignment
• An algorithm for generic and low-rank specific identifiability of complex tensors
• Testing composite hypotheses, Hermite polynomials and optimal estimation of a nonsmooth functional
• Message-passing algorithms for synchronization problems over compact groups
• On generic identifiability of symmetric tensors of subgeneric rank
• Fundamental Limits in Multi-image Alignment
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• Separating algebras and finite reflection groups
• A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time
• Multi-reference alignment in high dimensions: sample complexity and phase transition
• Degree bounds for separating invariants
• Spontaneous Symmetry Breaking in SO(3) Gauge Theory to Discrete Subgroups
• A Spectral Method for Stable Bispectrum Inversion with Application to Multireference Alignment
• Continuously heterogeneous hyper-objects in cryo-EM and 3-D movies of many temporal dimensions
• The generalized orthogonal Procrustes problem in the high noise regime
• Rational invariants of even ternary forms under the orthogonal group
• Zero-separating invariants for finite groups
• On the generalized Davenport constant and the Noether number
• Likelihood Maximization and Moment Matching in Low SNR Gaussian Mixture Models
• Rates of estimation for high-dimensional multi-reference alignment

Cited by in corpus (10)

• The generalized method of moments for multi-reference alignment
• Multi-target Detection with an Arbitrary Spacing Distribution
• Two-dimensional multi-target detection: an autocorrelation analysis approach
• Degree bounds for fields of rational invariants of $\mathbb{Z}/p\mathbb{Z}$ and other finite groups
• Multi-reference factor analysis: low-rank covariance estimation under unknown translations
• Maximum likelihood for high-noise group orbit estimation and single-particle cryo-EM
• Computational Methods for Single-Particle Cryo-EM
• Some observations on the ambivalent role of symmetries in Bayesian inference problems
• Toward a mathematical theory of the crystallographic phase retrieval problem
• Expanding the reach of quantum optimization with fermionic embeddings