Séminaire de Daniel Spielman (Yale University) Partager ce post

La conférence COLT 2015 (Conference on Learning Theory) a lieu à Paris du 3 au 6 juillet 2015. Le LTCI est partenaire de la conférence à travers la chaire Machine Learning for Big Data.

Dans ce cadre a lieu le jeudi 2 juillet à 17h un séminaire exceptionnel de Dan Spielman, Sparsification of Graphs and Matrices, à Télécom ParisTech, 37 rue Dareau, en salle DA 108.

Daniel Spielman est Professeur à l’Université de Yale depuis 2005. Il est titulaire d’une thèse du MIT en mathématiques appliquées (1995). Il a enseigné au département de mathématiques appliquées du MIT jusqu’en 2005. Il a reçu de nombreuses distinctions, dont le Information Theory Paper Award (IEEE 2002), le Prix Gödel 2008 et 2015, le Prix Fulkerson 2009, le Prix Nevanlinna 2010… Ses principaux domaines de recherche concernent le design et l’analyse d’algorithmes, la science des réseaux, le machine learning, les communications numériques et les sciences numériques.

Abstract

We introduce a notion of what it means for one graph to be a good spectral approximation of another, and prove that every graph can be well-approximated by a graph with few edges.

Random graphs and expander graphs are sparse spectral approximations of complete graphs, with Ramanujan expanders providing the best possible approximations. We prove that every graph can be approximated by a sparse graph almost as well as complete graphs are approximated by the Ramanujan expanders: our approximations employ at most twice as many edges to achieve the same approximation factor.

We also present an efficient randomized algorithm for constructing sparse approximations that only uses a logarithmic factor more edges than optimal.

Our algorithms follow from the solution of a problem in linear algebra. Given any expression of a rank-n symmetric matrix A as a sum of rank-1 symmetric matrices, we show that A can be well approximated by a weighted sum of only O(n) of those rank-1 matrices.

Partager ce post