This Note presents a randomized method to approximate any vector v from some set  . The data one is given is the set T, and k scalar products  , where   are i.i.d. isotropic subgaussian random vectors in  , and  . We show that with high probability any   for which   is close to the data vector   will be a good approximation of v, and that the degree of approximation is determined by a natural geometric parameter associated with the set T. This extends and improves recent results by Candes and Tao. To cite this article: S. Mendelson et al., C. R. Acad. Sci. Paris, Ser. I 340 (2005).

Dans cette Note, on présente une méthode stochastique pour approcher un vecteur v dʼune partie  . Les données sont dʼune part T et dʼautre part k produits scalaires  , où   sont des vecteurs aléatoires de  , indépendants de type sous-gaussiens, et  . On montre quʼavec une grande probabilité, tout   pour lequel   est proche de   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).