论文标题
有关恢复保证的角度同步
On recovery guarantees for angular synchronization
论文作者
论文摘要
在各种应用中，从其已知的噪声成对差异中估算一组未知角度的角度同步问题。它可以在涉及图Laplacian矩阵的图表上重新构成优化问题。我们考虑了这个问题的一般加权版本，其中噪声的影响在不同的条目对之间和某些差异之间被完全消除。这个版本是在Ptychography中产生的。我们研究了解决此问题的两种常见方法，即特征向量弛豫和半决赛凸松弛。尽管两种方法都可以使用某些恢复保证，但它们的性能要么不满意，要么仅限于未加权图。我们缩小了这一差距，从而获得了与未加权版本完全类似的加权问题的恢复保证。
The angular synchronization problem of estimating a set of unknown angles from their known noisy pairwise differences arises in various applications. It can be reformulated as a optimization problem on graphs involving the graph Laplacian matrix. We consider a general, weighted version of this problem, where the impact of the noise differs between different pairs of entries and some of the differences are erased completely; this version arises for example in ptychography. We study two common approaches for solving this problem, namely eigenvector relaxation and semidefinite convex relaxation. Although some recovery guarantees are available for both methods, their performance is either unsatisfying or restricted to the unweighted graphs. We close this gap, deriving recovery guarantees for the weighted problem that are completely analogous to the unweighted version.
