Quicklists
Javascript must be enabled

Lenka Zdeborova : The spectral redemption comes from no backtracking

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.

Add to Favorites

Please select playlist name from following

Create new playlist

Report Video

Please select the category that most closely reflects your concern about the video, so that we can review it and determine whether it violates our Community Guidelines or isn’t appropriate for all viewers. Abusing this feature is also a violation of the Community Guidelines, so don’t do it.

0 Comments

Comments Disabled For This Video