Angular Synchronization by Eigenvectors and Semidefinite Programming.
Angular Synchronization by Eigenvectors and Semidefinite Programming.
复制标题
DOI：
10.1016/j.acha.2010.02.001
复制
发表时间：
2011-01-30
影响因子：
2.5
通讯作者：
Singer, A.
中科院分区：
文献类型：
--
作者：
Singer, A.
角度同步问题是从对一组未知角度θ1，…，θn的偏移量θi − θj mod 2π的m次含噪测量中获得对这些角度的精确估计（精确到一个常数相加相位）。特别令人感兴趣的是在存在许多异常值测量的情况下恢复角度，这些异常值在[0, 2π)上均匀分布，并且不包含关于真实偏移量的任何信息。我们引入一种高效的恢复算法，从一个特别设计的厄米特矩阵的顶部特征向量中恢复未知角度。该特征向量方法极其稳定，即使异常值的数量非常大时也能成功。例如，我们在一台商用笔记本电脑上，在不到一秒的时间内，从一整套偏移量测量中成功估计出n = 400个角度，其中90%是异常值。我们使用随机矩阵理论和信息理论分析了该方法的性能。我们讨论了同步问题与组合优化问题Max - 2 - Lin mod L的关系，并提出了一种用于角度恢复的半定松弛方法，与用于寻找加权图中最大割的Goemans - Williamson算法有相似之处。我们还介绍了特征向量方法对涉及不同群结构的其他同步问题及其应用的扩展，例如分布式网络中的时间同步问题以及计算机视觉和光学中的表面重建问题。
The angular synchronization problem is to obtain an accurate estimation (up to a constant additive phase) for a set of unknown angles θ1, …, θn from m noisy measurements of their offsets θi − θj mod 2π. Of particular interest is angle recovery in the presence of many outlier measurements that are uniformly distributed in [0, 2π) and carry no information on the true offsets. We introduce an efficient recovery algorithm for the unknown angles from the top eigenvector of a specially designed Hermitian matrix. The eigenvector method is extremely stable and succeeds even when the number of outliers is exceedingly large. For example, we successfully estimate n = 400 angles from a full set of offset measurements of which 90% are outliers in less than a second on a commercial laptop. The performance of the method is analyzed using random matrix theory and information theory. We discuss the relation of the synchronization problem to the combinatorial optimization problem Max-2-Lin mod L and present a semidefinite relaxation for angle recovery, drawing similarities with the Goemans-Williamson algorithm for finding the maximum cut in a weighted graph. We present extensions of the eigenvector method to other synchronization problems that involve different group structures and their applications, such as the time synchronization problem in distributed networks and the surface reconstruction problems in computer vision and optics.
登录
查看更多内容
影响因子：
1.1
作者：
Frieze, A;Jerrum, M
通讯作者：
Jerrum, M
影响因子：
1.2
作者：
Rubinstein, J;Wolansky, G
通讯作者：
Wolansky, G
DOI：
10.1109/34.3909
发表时间：
1988-07-01
影响因子：
23.6
作者：
FRANKOT, RT;CHELLAPPA, R
通讯作者：
CHELLAPPA, R
影响因子：
1.2
作者：
Khorunzhy, A
通讯作者：
Khorunzhy, A
DOI：
10.1109/tase.2006.877401
发表时间：
2006-10-01
影响因子：
5.6
作者：
Biswas, Pratik;Liang, Tzu-Chen;Wang, Ta-Chung
通讯作者：
Wang, Ta-Chung