Yizhe Zhu: Non-backtracking methods for sparse random matrices

Abstract:

The non-backtracking operator is a non-Hermitian matrix associated with an undirected graph. It has become a powerful tool in the spectral analysis of random graphs. Recently, many new results for sparse Hermitian random matrices have been proved using the corresponding non-backtracking operator through the Ihara-Bass formula. In another direction, efficient algorithms based on the non-backtracking matrix have successfully reached optimal sample complexity in many sparse low-rank estimation problems. I will talk about my recent work with the help of the non-backtracking operator. This includes a Bai-Yin law for sparse random rectangular matrices and a spectral algorithm for hypergraph community detection. Based on Joint work with Ioana Dumitriu and Ludovic Stephan.