Estimation under group actions: Recovering orbits from invariants

Afonso S. Bandeira, Ben Blum-Smith, Joe Kileel, Jonathan Niles-Weed, Amelia Perry, Alexander S. Wein

Research output: Contribution to journalArticlepeer-review


We study a class of orbit recovery problems in which we observe independent copies of an unknown element of Rp, each linearly acted upon by a random element of some group (such as Z/p or 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 σ2, the number of images required to recover the molecule structure scales as σ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.

Original languageEnglish (US)
Pages (from-to)236-319
Number of pages84
JournalApplied and Computational Harmonic Analysis
StatePublished - Sep 2023


  • Applications of commutative algebra
  • Applications of invariant theory
  • Applications of lie groups
  • Biomedical imaging
  • Signal processing
  • Statistical aspects of information theory

ASJC Scopus subject areas

  • Applied Mathematics


Dive into the research topics of 'Estimation under group actions: Recovering orbits from invariants'. Together they form a unique fingerprint.

Cite this