# Algorithms from Invariants: Smoothed Analysis of Orbit Recovery over SO(3)

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 34 references that are in the map.
- First posted on arXiv 4 Jun 2021.

## Builds on (most cited first, 10 of 10)

- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Non-asymptotic Identification of LTI Systems from a Single Trajectory](https://mlsanity.com/paper/1806.05722/) (2018)
- [Learning Mixtures of Gaussians in High Dimensions](https://mlsanity.com/paper/1503.00424/) (2015)
- [Smoothed Analysis of Tensor Decompositions](https://mlsanity.com/paper/1311.3651/) (2013)
- [Estimation under group actions: recovering orbits from invariants](https://mlsanity.com/paper/1712.10163/) (2017)
- [Minimal Realization Problems for Hidden Markov Models](https://mlsanity.com/paper/1411.3698/) (2014)
- [Fundamental Limits in Multi-image Alignment](https://mlsanity.com/paper/1602.01541/) (2016)
- [Spectral Methods from Tensor Networks](https://mlsanity.com/paper/1811.00944/) (2018)
- [Algorithmic Foundations for the Diffraction Limit](https://mlsanity.com/paper/2004.07659/) (2020)

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

- [Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials](https://mlsanity.com/paper/2211.05274/) (2022)
- [Deep Invertible Approximation of Topologically Rich Maps between Manifolds](https://mlsanity.com/paper/2210.00577/) (2022)

## Abstract (arXiv)

In this work we study orbit recovery over SO(3), where the goal is to recover a function on the sphere from noisy, randomly rotated copies of it. We assume that the function is a linear combination of low-degree spherical harmonics. This is a natural abstraction for the problem of recovering the three-dimensional structure of a molecule through cryo-electron tomography. For provably learning the parameters of a generative model, the method of moments is the standard workhorse of theoretical machine learning. It turns out that there is a natural incarnation of the method of moments for orbit recovery based on invariant theory. Bandeira et al. [BBSK+18] used invariant theory to give tight bounds on the sample complexity in terms of the noise level. However many of the key challenges remain: Can we prove bounds on the sample complexity that are polynomial in n, the dimension of the signal? The bounds in [BBSK+18] hide constants that have an unspecified dependence on n and only hold in the limit as σ2 rightarrow ∞ where σ2 is the variance of the noise. Moreover can we give efficient algorithms? We revisit these challenges from the perspective of smoothed analysis, where we assume that the coefficients of the signal, in the basis of spherical harmonics, are subject to small random perturbations. Our main result is a quasi-polynomial time algorithm for orbit recovery over SO(3) in this model. Our approach is based on frequency marching, which sequentially solves linear systems to find higher degree coefficients. Our main technical contribution is to show that these linear systems have unique solutions, are well-conditioned, and that the error can be made to compound over at most a logarithmic number of rounds. We believe that our work takes an important first step towards uncovering the algorithmic implications of invariant theory.