In this work we study the orbit recovery problem, which is a natural abstraction for the problem of recovering a planted signal from noisy measurements under unknown group actions. Many important inverse problems in statistics, engineering and the sciences fit into this framework. Prior work has studied cases when the group is discrete and/or abelian. However fundamentally new techniques are needed in order to handle more complex group actions. Our main result is a quasi-polynomial time algorithm to solve orbit recovery over $SO(3)$ - i.e. the cryo-electron tomography problem which asks to recover the three-dimensional structure of a molecule from noisy measurements of randomly rotated copies of it. We analyze a variant of the frequency marching heuristic in the framework of smoothed analysis. Our approach exploits the layered structure of the invariant polynomials, and simultaneously yields a new class of tensor decomposition algorithms that work in settings when the tensor is not low-rank but rather where the factors are algebraically related to each other by a group action.
翻译:在这项工作中,我们研究了轨道回收问题,这是一个自然的抽象问题,它涉及在未知群体行动下从噪音测量中恢复一个人工信号的问题。统计、工程和科学方面许多重要的反向问题都与这个框架相适应。以前的工作研究过该组是离散和/或无波的个案。然而,为了处理更复杂的群集行动,基本上需要新的技术。我们的主要结果是一个准极代时间算法,以解决轨道回收超过$SO(3)美元的问题,即冷冻电子断层摄影学问题,它要求从随机旋转复制物的噪音测量中恢复分子的三维结构。我们分析了在平滑分析框架内的频率行进超的变异体。我们的方法利用了变异聚合体的分层结构,同时产生了一种在温度不低但因素与群体行动有代数关系的情况下起作用的新型高压脱位算法。