- Date de réalisation : 1 Juillet 2019
- Lieu de réalisation : École Normale Supérieure, Paris.
- Durée du programme : 59 min
- Classification Dewey : Probabilités, Statistiques mathématiques, Mathématiques appliquées
- Auteur(s) : Tropp Joel
- producteur : Boyer Claire, Chafaï Djalil, Lehec Joseph
Dans la même collectionTropp 9/9 - Random matrix theory and computational linear algebra Tropp 8/9 - Random matrix theory and computational linear algebra Carpentier - Introduction to some problems of composite and minimax hypothesis testing Tropp 7/9 - Random matrix theory and computational linear algebra Tropp 6/9 - Random matrix theory and computational linear algebra Bubeck 9/9 - Some geometric aspects of randomized online decision making
Tropp 1/9 - Random matrix theory and computational linear algebra
This course treats some contemporary algorithms from computational linear algebra that involve random matrices. Rather than surveying the entire field, we focus on a few algorithms that are both simple and practically useful. We begin with an introduction to matrix concentration inequalities, which are a powerful tool for analyzing structured random matrices. We use these ideas to study matrix approximations constructed via randomized sampling, such as the random features method. As a more sophisticated application, we present a complete treatment of a recent algorithm for solving graph Laplacian linear systems in near-linear time. Some references : 1. Tropp, "An introduction to matrix concentration inequalities," Found. Trends. Mach. Learning, 2015. 2. Kyng, "Approximate Gaussian elimination," PhD Thesis, Yale, 2017. 3. Tropp, "Matrix concentration and computational linear algebra," ACM technical report 2019-01, Caltech, Pasadena, 2019.