A few weeks ago, Nicolas, Amit, and myself uploaded our new paper entitled “Tightness of the maximum likelihood semidefinite relaxation for angular synchronization”. I am quite excited about this one as it is the first instance for which we were able to establish a rank recovery type of result! I will briefly explain the main result, its motivation, and describe some of the main ideas behind the proof.
Continue reading Tightness of the Angular Synchronization SDP relaxation and rank recovery
Advertisements
be an even positive integer. Given two sets of 
nodes consider the following random graph 
: For each pair 
of nodes, 
if 
and 
are in the same set and 
if they are in different sets. Each edge is drawn independently and 
.
standard Wigner matrix, a symmetric matrix with iid standard gaussian entries. As each entry of the matrix is essentially of constant order the spectral norm of such a matrix can go up to 
, however, due to a concentration phenomenon, it is almost always roughly 
. Unfortunately, random matrix in many applications do not correspond to this simple model.
be a gaussian random vector in 
with a known covariance matrix 
and 
. Now, for any orthonormal basis 
of 
norm of the largest projection of 
elements of the basis 