Random Laplacian Matrices and Convex Relaxations
Random Laplacian Matrices and Convex Relaxations
复制标题
DOI：
10.1007/s10208-016-9341-9
复制
发表时间：
2018-04-01
影响因子：
3
通讯作者：
Bandeira, Afonso S.
中科院分区：
文献类型：
--
作者：
Bandeira, Afonso S.
矩阵的最大特征值总是大于或等于其最大对角线项。我们证明了对于一类具有独立的非对角线项的随机拉普拉斯矩阵，这个界本质上是紧的：最大本征值，直到更低阶项，通常是最大对角线的大小。进入。除了是获得一类随机拉普拉斯矩阵最大特征值的精确估计的简单工具外，我们的主要结果还解决了一些与某些基于凸松弛的算法的紧性有关的公开问题。它很容易暗示半定松弛方法在同步和随机块模型恢复等问题上的最优性。有趣的是，这一结果很容易地暗示了ERDAS-R，Nyi图的连通性阈值，并表明这三种现象是同一基本原理的表现。主要的工具是van Handel和作者最近对具有独立项的矩阵的谱范数的估计。
The largest eigenvalue of a matrix is always larger or equal than its largest diagonal entry. We show that for a class of random Laplacian matrices with independent off-diagonal entries, this bound is essentially tight: the largest eigenvalue is, up to lower order terms, often the size of the largest diagonal. entry. Besides being a simple tool to obtain precise estimates on the largest eigenvalue of a class of random Laplacian matrices, our main result settles a number of open problems related to the tightness of certain convex relaxation-based algorithms. It easily implies the optimality of the semidefinite relaxation approaches to problems such as Synchronization and stochastic block model recovery. Interestingly, this result readily implies the connectivity threshold for ErdAs-R,nyi graphs and suggests that these three phenomena are manifestations of the same underlying principle. The main tool is a recent estimate on the spectral norm of matrices with independent entries by van Handel and the author.