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