Reconstruction and subgaussian processes

Mendelson, Shahar; Pajor, Alain; Tomczak-Jaegermann, Nicole

doi:10.1016/j.crma.2005.04.032

Functional Analysis

Reconstruction and subgaussian processes
[Reconstruction et processus sous-gaussiens]

Présenté par : Gilles Pisier

Mendelson, Shahar ¹ ; Pajor, Alain ² ; Tomczak-Jaegermann, Nicole ³

¹ Centre for Mathematics and its Applications, The Australian National University, Canberra, ACT 0200, Australia
² Équipe d'analyse et mathématiques appliquées, université de Marne-la-Vallée, 5, boulevard Descartes, Champs sur Marne, 77454 Marne-la-Vallee cedex 2, France
³ Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Alberta, Canada T6G 2G1

Comptes Rendus. Mathématique, Tome 340 (2005) no. 12, pp. 885-888.

Résumé
Abstract

Dans cette Note, on présente une méthode stochastique pour approcher un vecteur v d'une partie $T \subset R^{n}$ . Les données sont d'une part T et d'autre part k produits scalaires ${(〈 X_{i}, v 〉)}_{i = 1}^{k}$ , où ${(X_{i})}_{i = 1}^{k}$ sont des vecteurs aléatoires de $R^{n}$ , indépendants de type sous-gaussiens, et $k ≪ n$ . On montre qu'avec une grande probabilité, tout $y \in T$ pour lequel ${(〈 X_{i}, y 〉)}_{i = 1}^{k}$ est proche de ${(〈 X_{i}, v 〉)}_{i = 1}^{k}$ 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.

This Note presents a randomized method to approximate any vector v from some set $T \subset R^{n}$ . The data one is given is the set T, and k scalar products ${(〈 X_{i}, v 〉)}_{i = 1}^{k}$ , where ${(X_{i})}_{i = 1}^{k}$ are i.i.d. isotropic subgaussian random vectors in $R^{n}$ , and $k ≪ n$ . We show that with high probability any $y \in T$ for which ${(〈 X_{i}, y 〉)}_{i = 1}^{k}$ is close to the data vector ${(〈 X_{i}, v 〉)}_{i = 1}^{k}$ 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.

Reçu le : 2005-04-03
Accepté le : 2005-04-27
Publié le : 2005-05-31

DOI : 10.1016/j.crma.2005.04.032

Affiliations des auteurs :

Mendelson, Shahar ¹ ; Pajor, Alain ² ; Tomczak-Jaegermann, Nicole ³

@article{CRMATH_2005__340_12_885_0,
     author = {Mendelson, Shahar and Pajor, Alain and Tomczak-Jaegermann, Nicole},
     title = {Reconstruction and subgaussian processes},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {885--888},
     publisher = {Elsevier},
     volume = {340},
     number = {12},
     year = {2005},
     doi = {10.1016/j.crma.2005.04.032},
     language = {en},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2005.04.032/}
}

TY  - JOUR
AU  - Mendelson, Shahar
AU  - Pajor, Alain
AU  - Tomczak-Jaegermann, Nicole
TI  - Reconstruction and subgaussian processes
JO  - Comptes Rendus. Mathématique
PY  - 2005
SP  - 885
EP  - 888
VL  - 340
IS  - 12
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2005.04.032/
DO  - 10.1016/j.crma.2005.04.032
LA  - en
ID  - CRMATH_2005__340_12_885_0
ER  -

%0 Journal Article
%A Mendelson, Shahar
%A Pajor, Alain
%A Tomczak-Jaegermann, Nicole
%T Reconstruction and subgaussian processes
%J Comptes Rendus. Mathématique
%D 2005
%P 885-888
%V 340
%N 12
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2005.04.032/
%R 10.1016/j.crma.2005.04.032
%G en
%F CRMATH_2005__340_12_885_0

Mendelson, Shahar; Pajor, Alain; Tomczak-Jaegermann, Nicole. Reconstruction and subgaussian processes. Comptes Rendus. Mathématique, Tome 340 (2005) no. 12, pp. 885-888. doi : 10.1016/j.crma.2005.04.032. http://www.numdam.org/articles/10.1016/j.crma.2005.04.032/

Bibliographie
Cité par

[1] Artstein, S. The change in the diameter of a convex body under a random sign-projection (Milman, V.D.; Schechtman, G., eds.), GAFA Seminar Notes 2002–2003, Lecture Notes in Math., vol. 1850, 2004, pp. 31-39

[2] P.L. Bartlett, S. Mendelson, Empirical minimization, Probab. Theory Related Fields, in press

[3] Boucheron, S.; Bousquet, O.; Lugosi, G. Theory of classification: a survey of recent advances, available from http://www.econ.upf.es/lugosi/esaimsurvey.pdf

[4] E. Candes, T. Tao, Near optimal recovery from random projections: universal encoding strategies, Preprint

[5] Garnaev, A.U.; Gluskin, E.D. The widths of a Euclidean ball, Dokl. Acad. Nauk SSSR, Volume 277 (1984), pp. 1048-1052 (in Russian); English translation: Soviet Math. Dokl., 30, 1984, pp. 200-204

[6] Y. Gordon, A. Litvak, S. Mendelson, A. Pajor, private communication

[7] B. Klartag, S. Mendelson, Empirical processes and random projections, J. Funct. Anal., in press

[8] Mendelson, S. GAFA Seminar Notes 2002–2003 (Milman, V.D.; Schechtman, G., eds.), Lecture Notes in Math., vol. 1850, 2004, pp. 193-235

[9] Mendelson, S.; Tishby, N. Statistical Sufficiency for classes in empirical $L_{2}$ spaces (Cesa-Bianchi, N.; Goldman, S.A., eds.), Proceedings of the 13th Annual Conference on Computational Learning Theory COLT00, 2000, pp. 81-89

[10] Milman, V.D.; Pajor, A. Regularization of star bodies by random hyperplane cut off, Studia Math., Volume 159 (2003), pp. 247-261

[11] Pajor, A.; Tomczak-Jaegermann, N. Subspaces of small codimension of finite-dimensional Banach spaces, Proc. Amer. Math. Soc., Volume 97 (1986) no. 4, pp. 637-642

[12] Pajor, A.; Tomczak-Jaegermann, N. Nombres de Gelfand et sections euclidiennes de grande dimension, Séminaire d'Analyse Fonctionelle 1984/1985, Publ. Math. Univ. Paris VII, vol. 26, Univ. Paris VII, Paris, 1986, pp. 37-47 (in French) (Gelfand numbers and high-dimensional Euclidean sections)

[13] M. Rudelson, R. Vershynin, Geometric approach to error correcting codes and reconstruction of signals, Preprint

[14] M. Talagrand, The Generic Chaining, Springer-Verlag, in press

Cité par Sources :