# Linear inverse problems on Erdos-Renyi graphs: Information-theoretic limits and efficient recovery

## Author(s): Abbe, Emmanuel A; Bandeira, Afonso S; Bracher, Annina; Singer, Amit

DownloadTo refer to this page use:

`http://arks.princeton.edu/ark:/88435/pr1cb24`

Abstract: | This paper considers the inverse problem with observed variables Y = BGX circle plus Z, where B-G 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 (epsilon) 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-Renyi 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 alpha = np/log(n), it is shown that exact recovery is possible if and only if alpha > 2/(1 - 2 epsilon)(2) + o(1/(1 - 2 epsilon)(2)). In other words, 2/(1 - 2 epsilon)(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]. |

Publication Date: | 2014 |

Electronic Publication Date: | 11-Aug-2014 |

Citation: | Abbe, Emmanuel, Bandeira, Afonso S, Bracher, Annina, Singer, Amit. (2014). Linear inverse problems on Erdos-Renyi graphs: Information-theoretic limits and efficient recovery. 2014 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), 1251 - 1255 |

Pages: | 1251 - 1255 |

Type of Material: | Conference Article |

Journal/Proceeding Title: | 2014 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT) |

Version: | Author's manuscript |

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.