Orbit recovery under the rigid motions group

Abstract: We study the orbit recovery problem under the rigid-motion group SE(n), where the objective is to reconstruct an unknown signal from multiple noisy observations subjected to unknown rotations and translations. This problem is fundamental in signal processing, computer vision, and structural biology. Our main theoretical contribution is bounding the sample complexity of this problem. We show that if the d-th order moment under the rotation group SO(n) uniquely determines the signal orbit, then orbit recovery under SE(n) is achievable with $N\gtrsim σ^{2d+4}$ samples as the noise variance $σ² \to \infty$. The key technical insight is that the d-th order SO(n) moments can be explicitly recovered from (d+2)-order SE(n) autocorrelations, enabling us to transfer known results from the rotation-only setting to the rigid-motion case. We further harness this result to derive a matching bound to the sample complexity of the multi-target detection model that serves as an abstract framework for electron-microscopy-based technologies in structural biology, such as single-particle cryo-electron microscopy (cryo-EM) and cryo-electron tomography (cryo-ET). Beyond theory, we present a provable computational pipeline for rigid-motion orbit recovery in three dimensions. Starting from rigid-motion autocorrelations, we extract the SO(3) moments and demonstrate successful reconstruction of a 3-D macromolecular structure. Importantly, this algorithmic approach is valid at any noise level, suggesting that even very small macromolecules, long believed to be inaccessible using structural biology electron-microscopy-based technologies, may, in principle, be reconstructed given sufficient data.