SMF

Exposé Bourbaki 1033 : Formes quadratiques creuses et leurs applications géométriques d'après Batson, Spielman et Srivastava

Exposé Bourbaki 1033 : Sparse quadratic forms and their geometric applications

Assaf NAOR
Exposé Bourbaki 1033 : Formes quadratiques creuses et leurs applications géométriques d'après Batson, Spielman et Srivastava
  • Consulter un extrait
  •  
                
  • Année : 2012
  • Tome : 348
  • Format : Électronique
  • Langue de l'ouvrage :
    Anglais
  • Class. Math. : 65F50, 15A63, 46B85, 52A23, 46B07
  • Pages : 189-217

Soit  $(a_{ij})$ une matrice symétrique à coefficients positifs. Batson, Spielman et Srivastava ont montré que pour tout  $\epsilon>0$ il existe  $c=c(\epsilon)>0$ et une matrice symétrique  $(b_{ij})$ dont les coefficients sont positifs et telle qu'au plus $cn$ d'entre eux soient non nuls, de sorte que pour tout $(x_1,...,x_n)\in \mathbb{R}^n$ on ait  $$ \sum_{i,j=1}^n a_{ij}(x_i-x_j)^2\le \sum_{i,j=1}^n b_{ij}(x_i-x_j)^2\le (1+\epsilon)\sum_{i,j=1}^n a_{ij}(x_i-x_j)^2. $$ Nous exposons la démonstration magnifique de ce théorème, ainsi que certaines de ses applications géométriques, dont en particulier une nouvelle preuve du phénom\`ene d'inversibilité  restreinte de Bourgain-Tzafriri,
une amélioration des décompositions de John approchées pour les convexes, et une réduction dimensionnelle dans les espaces $L_p$.

 

Let $(a_{ij})$ be a symmetric matrix with nonnegative entries. Batson, Spielman and Srivastava proved that for every $\epsilon>0$ there exists $c=c(\epsilon)>0$ and a symmetric matrix $(b_{ij})$ whose entries are nonnegative and at most $cn$ of them are nonzero, such that for all $(x_1,...,x_n)\in \mathbb{R}^n$ we have $$ \sum_{i,j=1}^n
a_{ij}(x_i-x_j)^2\le \sum_{i,j=1}^n b_{ij}(x_i-x_j)^2\le (1+\epsilon)\sum_{i,j=1}^n a_{ij}(x_i-x_j)^2. $$ We describe the beautiful proof of this theorem, as well as some of its geometric applications, including a new proof of the Bourgain-Tzafriri restricted invertibility phenomenon, improved approximate John decompositions for convex bodies, and dimensionality reduction in $L_p$ spaces.

Creusage spectral, décomposition de John approchée, réduction dimensionnelle, inversibilité restreinte
Spectral sparsification, approximate John decomposition, dimensionality reduction, restricted invertibility

Électronique
Electronic
Prix public Public price 10.00 €
Prix membre Member price 7.00 €
Quantité
Quantity
- +