# Estimation under group actions: recovering orbits from invariants

arXiv: https://arxiv.org/abs/1712.10163 · HTML: https://mlsanity.com/paper/1712.10163/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Dec 2017.

## Built on by (most cited first, 14 of 14)

- [Group-invariant max filtering](https://mlsanity.com/paper/2205.14039/) (2022)
- [Tensor Moments of Gaussian Mixture Models: Theory and Applications](https://mlsanity.com/paper/2202.06930/) (2022)
- [Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials](https://mlsanity.com/paper/2211.05274/) (2022)
- [Algorithms from Invariants: Smoothed Analysis of Orbit Recovery over SO(3)](https://mlsanity.com/paper/2106.02680/) (2021)
- [Orthogonal Matrix Retrieval with Spatial Consensus for 3D Unknown-View Tomography](https://mlsanity.com/paper/2207.02985/) (2022)
- [Multi-target detection with rotations](https://mlsanity.com/paper/2101.07709/) (2021)
- [An accelerated expectation-maximization algorithm for multi-reference alignment](https://mlsanity.com/paper/2105.07372/) (2021)
- [Unrolled algorithms for group synchronization](https://mlsanity.com/paper/2207.09418/) (2022)
- [Dictionary Learning under Symmetries via Group Representations](https://mlsanity.com/paper/2305.19557/) (2023)
- [Reconstructing Rational Functions on Finite Abelian Groups with Higher Autocorrelations](https://mlsanity.com/paper/2503.21022/) (2025)
- [If you can distinguish, you can express: Galois theory, Stone--Weierstrass, machine learning, and linguistics](https://mlsanity.com/paper/2510.09902/) (2025)
- [A Probabilistic Approach to Pose Synchronization for Multi-Reference Alignment with Applications to MIMO Wireless Communication Systems](https://mlsanity.com/paper/2511.03280/) (2025)
- [Two Datasets Are Better Than One: Method of Double Moments for 3-D Reconstruction in Cryo-EM](https://mlsanity.com/paper/2511.07438/) (2025)
- [Group-invariant Coresets for Data-efficient Active Learning](https://mlsanity.com/paper/2607.01089/) (2026)

## Abstract (arXiv)

We study a class of orbit recovery problems in which we observe independent copies of an unknown element of ℝp, each linearly acted upon by a random element of some group (such as mathbbZ/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.