TY - GEN
T1 - Linear inverse problems on Erdos-Rényi graphs
T2 - 2014 IEEE International Symposium on Information Theory, ISIT 2014
AU - Abbe, Emmanuel
AU - Bandeira, Afonso S.
AU - Bracher, Annina
AU - Singer, Amit
PY - 2014
Y1 - 2014
N2 - This paper considers the inverse problem with observed variables Y = B GX +Z, where BG is the incidence matrix of a graph G, X is the vector of unknown vertex variables with a uniform prior, and Z is a noise vector with Bernoulli(ε) i.i.d. entries. All variables and operations are Boolean. This model is motivated by coding, synchronization, and community detection problems. In particular, it corresponds to a stochastic block model or a correlation clustering problem with two communities and censored edges. Without noise, exact recovery of X is possible if and only the graph G is connected, with a sharp threshold at the edge probability log(n)=n for Erdos-Rényi random graphs. The first goal of this paper is to determine how the edge probability p needs to scale to allow exact recovery in the presence of noise. Defining the degree (oversampling) rate of the graph by α = np= log(n), it is shown that exact recovery is possible if and only if α > 2/(1-2ε)2+o(1/(1-2ε)2). In other words, 2/(1-2ε)2 is the information theoretic threshold for exact recovery at low-SNR. In addition, an efficient recovery algorithm based on semidefinite programming is proposed and shown to succeed in the threshold regime up to twice the optimal rate. Full version available in [1].
AB - This paper considers the inverse problem with observed variables Y = B GX +Z, where BG is the incidence matrix of a graph G, X is the vector of unknown vertex variables with a uniform prior, and Z is a noise vector with Bernoulli(ε) i.i.d. entries. All variables and operations are Boolean. This model is motivated by coding, synchronization, and community detection problems. In particular, it corresponds to a stochastic block model or a correlation clustering problem with two communities and censored edges. Without noise, exact recovery of X is possible if and only the graph G is connected, with a sharp threshold at the edge probability log(n)=n for Erdos-Rényi random graphs. The first goal of this paper is to determine how the edge probability p needs to scale to allow exact recovery in the presence of noise. Defining the degree (oversampling) rate of the graph by α = np= log(n), it is shown that exact recovery is possible if and only if α > 2/(1-2ε)2+o(1/(1-2ε)2). In other words, 2/(1-2ε)2 is the information theoretic threshold for exact recovery at low-SNR. In addition, an efficient recovery algorithm based on semidefinite programming is proposed and shown to succeed in the threshold regime up to twice the optimal rate. Full version available in [1].
UR - http://www.scopus.com/inward/record.url?scp=84906545974&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84906545974&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2014.6875033
DO - 10.1109/ISIT.2014.6875033
M3 - Conference contribution
AN - SCOPUS:84906545974
SN - 9781479951864
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 1251
EP - 1255
BT - 2014 IEEE International Symposium on Information Theory, ISIT 2014
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 29 June 2014 through 4 July 2014
ER -