The group synchronization problem is to estimate unknown group elements at the vertices of a graph when given a set of possibly noisy observations of group differences at the edges. We consider the group synchronization problem on finite graphs with size tending to infinity, and we focus on the question of whether the true edge differences can be exactly recovered from the observations (i.e., strong recovery). We prove two main results, one positive and one negative. In the positive direction, we prove that for a sequence of synchronization problems containing the complete digraph along with a relatively well behaved prior distribution and observation kernel, with high probability we can recover the correct edge labeling. Our negative result provides conditions on a sequence of sparse graphs under which it is impossible to recover the correct edge labeling with high probability.


翻译:组同步问题在于当给出一组对边缘群落差异可能很吵的观测结果时, 在图形的顶端估计未知的群分元素。 我们考虑的是大小趋向无限的定点图形中的群组同步问题, 我们集中研究从观察中能否完全恢复真实的边缘差异( 即强力恢复 ) 。 我们证明了两个主要结果, 一个是正的, 一个是负的。 在正方向上, 我们证明对于包含完整分层的同步问题序列, 以及一个相对良好的先前分布和观察内核, 我们很有可能恢复正确的边缘标签。 我们的负面结果为一个细小的图表序列提供了条件, 使得极有可能恢复正确的边缘标签。

0
下载
关闭预览

相关内容

Group一直是研究计算机支持的合作工作、人机交互、计算机支持的协作学习和社会技术研究的主要场所。该会议将社会科学、计算机科学、工程、设计、价值观以及其他与小组工作相关的多个不同主题的工作结合起来,并进行了广泛的概念化。官网链接:https://group.acm.org/conferences/group20/
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Python计算导论,560页pdf,Introduction to Computing Using Python
专知会员服务
72+阅读 · 2020年5月5日
经济学中的数据科学,Data Science in Economics,附22页pdf
专知会员服务
35+阅读 · 2020年4月1日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
已删除
将门创投
9+阅读 · 2017年7月28日
Entropic Optimal Transport in Random Graphs
Arxiv
0+阅读 · 2022年1月11日
Arxiv
0+阅读 · 2022年1月11日
Arxiv
0+阅读 · 2022年1月6日
Arxiv
0+阅读 · 2022年1月5日
VIP会员
相关资讯
Top
微信扫码咨询专知VIP会员