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 $\sigma^2 \rightarrow \infty$ where $\sigma^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.
翻译:在此工作中,我们研究轨道回收 $SO(3) $(美元) 的轨道回收, 目标是从杂音和随机旋转的复制件中恢复球体上的函数。 我们假设该函数是低度球球调调调调的线性组合。 这是通过冷冻- 电子摄像学恢复分子三维结构的问题自然抽象。 可以理解的是, 要学习基因化模型的参数, 瞬间的方法是理论机器学习的标准工作马匹。 事实证明, 根据变幻理论, 轨道恢复的时间方法是自然的。 Bandeira 等人。 [BBBSK+18] 该函数是低度球球调调调调调调调调调的线性组合。 这是自然的抽象。 然而, 许多关键挑战依然存在: 我们能否证明样本复杂性的界限是 美元, 信号的维度? 我们的模型体系的边际链条系对美元有不明确的依赖度, 并且只能以美元为极限。 我们的直线性平流运算法是我们的主要轨道的直径比 。