### Abstract

This paper considers the inverse problem with observed variables Y = B _{G}X +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(ε) 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].

Original language | English (US) |
---|---|

Title of host publication | 2014 IEEE International Symposium on Information Theory, ISIT 2014 |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 1251-1255 |

Number of pages | 5 |

ISBN (Print) | 9781479951864 |

DOIs | |

State | Published - 2014 |

Event | 2014 IEEE International Symposium on Information Theory, ISIT 2014 - Honolulu, HI, United States Duration: Jun 29 2014 → Jul 4 2014 |

### Publication series

Name | IEEE International Symposium on Information Theory - Proceedings |
---|---|

ISSN (Print) | 2157-8095 |

### Other

Other | 2014 IEEE International Symposium on Information Theory, ISIT 2014 |
---|---|

Country | United States |

City | Honolulu, HI |

Period | 6/29/14 → 7/4/14 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Information Systems
- Modeling and Simulation
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Linear inverse problems on Erdos-Rényi graphs: Information-theoretic limits and efficient recovery'. Together they form a unique fingerprint.

## Cite this

*2014 IEEE International Symposium on Information Theory, ISIT 2014*(pp. 1251-1255). [6875033] (IEEE International Symposium on Information Theory - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2014.6875033