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)美元的问题,即冷冻电子断层摄影学问题,它要求从随机旋转复制物的噪音测量中恢复分子的三维结构。我们分析了在平滑分析框架内的频率行进超的变异体。我们的方法利用了变异聚合体的分层结构,同时产生了一种在温度不低但因素与群体行动有代数关系的情况下起作用的新型高压脱位算法。

0
下载
关闭预览

相关内容

Group一直是研究计算机支持的合作工作、人机交互、计算机支持的协作学习和社会技术研究的主要场所。该会议将社会科学、计算机科学、工程、设计、价值观以及其他与小组工作相关的多个不同主题的工作结合起来,并进行了广泛的概念化。官网链接:https://group.acm.org/conferences/group20/
【如何做研究】How to research ,22页ppt
专知会员服务
108+阅读 · 2021年4月17日
【干货书】面向计算科学和工程的Python导论,167页pdf
专知会员服务
41+阅读 · 2021年4月7日
抢鲜看!13篇CVPR2020论文链接/开源代码/解读
专知会员服务
49+阅读 · 2020年2月26日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
On the Merge of k-NN Graph
Arxiv
0+阅读 · 2021年7月29日
Arxiv
5+阅读 · 2021年2月15日
Arxiv
17+阅读 · 2019年3月28日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
相关论文
On the Merge of k-NN Graph
Arxiv
0+阅读 · 2021年7月29日
Arxiv
5+阅读 · 2021年2月15日
Arxiv
17+阅读 · 2019年3月28日
Top
微信扫码咨询专知VIP会员