Reconstruction and subgaussian processes

Dans cette Note, on présente une méthode stochastique pour approcher un vecteur v d'une partie T⊂Rn. Les données sont d'une part T et d'autre part k produits scalaires (〈Xi,v〉)i=1k, où (Xi)i=1k sont des vecteurs aléatoires de Rn, indépendants de type sous-gaussiens, et k≪n. On montre qu'avec une grande probabilité, tout y∈T pour lequel (〈Xi,y〉)i=1k est proche de (〈Xi,v〉)i=1k est une bonne approximation de v avec un degré d'erreur déterminé par un paramètre de la géométrie de T. Cette approche permet de généraliser et d'améliorer des résultats d'un récent travail de Candes et Tao. Pour citer cet article : S. Mendelson et al., C. R. Acad. Sci. Paris, Ser. I 340 (2005).