CTMS Adventures In Theory Lectures Seminar
Tuesday, October 25, 2016, 4:30pm, 119 Physics
Lenka Zdeborova (IPhT, CEA Saclay)
The spectral redemption comes from no backtracking

Abstract:

A number of computational problems on graphs can be solved using algorithms based on the spectrum of a matrix associated with the graph. On very sparse graphs the traditionally-considered matrices develop spurious large eigenvalues associated with localized eigenvectors that harm the algorithmic performance. Inspired by the theory of spin glasses, we introduce the non-backtracking operator that is able to mitigate this problem. We discuss properties of this operator, as well as its applications to several algorithmic problems such as clustering of networks, percolation, matrix completion or inference from pairwise comparisons. [video]

---

Generated at 9:17pm Friday, April 19, 2024 by Mcal.   Top * Reload * Login