Linear inverse problems on Erdős-Rényi graphs: Information-theoretic limits and efficient recovery

Abstract—This paper considers the linear inverse problem Y = AX ⊕ Z, where A is the incidence matrix of an Erdős-Rényi graph, Z is an i.i.d. noise vector, and X is the vector of unknown variables, assumed to be Boolean. This model is motivated by coding, synchronization, and community detection problems. Without noise, exact recovery is possible if and only the graph is connected, with a sharp threshold at the edge probability log(n)/n. The goal of this paper is to determine how the edge probability p needs to scale in order to cope with the noise. Defining the rate parameter r = log(n)/np, it is shown that for an error probability of ε close to half, exact recovery is possible if and only if r is below D(1/2||ε). In other words, D(1/2||ε) provides 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 up to half the threshold. I