Title: Thresholds for inverse problems on random graphs
Speaker: Emmanuel Abbe, Princeton University
Date: Tuesday, April 15, 2014 2:00pm
Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ
We consider inverse problems on random graphs, where vertex-variables are to be recovered from dependent edge-variables. In particular, we consider the linear inverse problem Y=I(G)X+Z, where I(G) is the incidence matrix of an Erdos-Rényi random graph, X is the vector of vertex-variables assumed to be Boolean, and Z is an iid noise vector. In the absence of noise, X can be fully recovered if and only if G is connected, with a sharp threshold at log(n)/n, and X can be partially recovered (more than 50%) if and only if G has a giant component, with a sharp threshold at 1/n. We will show how these thresholds are rescaled in order to cope with the noise. Concentration results and recovery algorithms will be discussed. Based on joint works with A. Bandeira, A. Bracher, A. Singer, and A. Montanari.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math