Eigenvalues of very sparse graphs and matrix reconstruction from O(n) entries

vendredi 28 février 2020, 9h30

Salle du conseil, espace Turing

Let P be a low-rank square matrix with size n. Each one of its n^2 entries is then independently revealed with probability d/n, where d is fixed. The resulting random sparse matrix A, which is the adjacency matrix of a directed Erdös-Rényi graph weighted with P, has complex spectrum. We show a new threshold phenomenon : suitably normalized, all the eigenvalues of A are confined in a disk with radius r, except a few ones which are close to the greatest eigenvalues of P. The radius r is completely explicit and only depends on P and d. We apply this theorem to the problem of matrix reconstruction from O(n) samples and show that weak reconstruction is indeed feasible in this regime. This is based on joint work with Charles Bordenave and Raj Rao Nadakuditi.