Functional Analysis
Reconstruction and subgaussian processes
Comptes Rendus. Mathématique, Volume 340 (2005) no. 12, pp. 885-888.

This Note presents a randomized method to approximate any vector v from some set TRn. The data one is given is the set T, and k scalar products (Xi,v)i=1k, where (Xi)i=1k are i.i.d. isotropic subgaussian random vectors in Rn, and kn. We show that with high probability any yT for which (Xi,y)i=1k is close to the data vector (Xi,v)i=1k 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.

Dans cette Note, on présente une méthode stochastique pour approcher un vecteur v d'une partie TRn. 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 kn. On montre qu'avec une grande probabilité, tout yT 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.

Received:
Accepted:
Published online:
DOI: 10.1016/j.crma.2005.04.032
Mendelson, Shahar 1; Pajor, Alain 2; Tomczak-Jaegermann, Nicole 3

1 Centre for Mathematics and its Applications, The Australian National University, Canberra, ACT 0200, Australia
2 É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
3 Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Alberta, Canada T6G 2G1
@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://archive.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://archive.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://archive.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, Volume 340 (2005) no. 12, pp. 885-888. doi : 10.1016/j.crma.2005.04.032. http://archive.numdam.org/articles/10.1016/j.crma.2005.04.032/

[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 L2 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

Cited by Sources: