论文标题
相同步和正交组同步中光谱方法的精确最小值
Exact Minimax Optimality of Spectral Methods in Phase Synchronization and Orthogonal Group Synchronization
论文作者
论文摘要
我们研究了与添加剂高斯噪声和数据不完整的相同步问题的光谱方法的性能。光谱方法利用数据矩阵的领先特征向量，然后是归一化步骤。我们证明，它可以通过平方$ \ ell_2 $损失的匹配领先常数实现了问题的最小值。这表明光谱方法具有与更复杂的过程相同的性能，包括一致的参数估计，包括最大似然估计，广义能力法和半趋势编程。为了建立我们的结果，我们首先可以选择人口特征向量，这使我们能够在没有添加剂噪声时确定光谱方法的精确恢复。然后，我们为领先的特征向量开发了一个新的扰动分析工具包，并证明它可以通过其一阶近似和小$ \ ell_2 $误差来很好地对其进行评估。我们进一步扩展了分析，以建立正交组同步光谱方法的确切最小值最佳性。
We study the performance of the spectral method for the phase synchronization problem with additive Gaussian noises and incomplete data. The spectral method utilizes the leading eigenvector of the data matrix followed by a normalization step. We prove that it achieves the minimax lower bound of the problem with a matching leading constant under a squared $\ell_2$ loss. This shows that the spectral method has the same performance as more sophisticated procedures including maximum likelihood estimation, generalized power method, and semidefinite programming, as long as consistent parameter estimation is possible. To establish our result, we first have a novel choice of the population eigenvector, which enables us to establish the exact recovery of the spectral method when there is no additive noise. We then develop a new perturbation analysis toolkit for the leading eigenvector and show it can be well-approximated by its first-order approximation with a small $\ell_2$ error. We further extend our analysis to establish the exact minimax optimality of the spectral method for the orthogonal group synchronization.
