CMX Lunch Seminar

The non-backtracking operator, an asymmetric matrix constructed from an undirected graph, connects to various aspects of graph theory, including random walks, graph zeta functions, and expander graphs. It has emerged as a powerful tool for analyzing sparse random graphs, leading to new results for sparse random matrices. Additionally, algorithms employing the non-backtracking operator have achieved optimal sample complexity in many low-rank estimation problems. In my talk, I will present my recent work utilizing the non-backtracking operator to design new algorithms through the introduction of asymmetry into data matrices. The discussion will include estimates of the extreme singular values of sparse random matrices and applications in hypergraph community detection and tensor completion.