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

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.

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.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2005.04.032
Shahar Mendelson 1 ; Alain Pajor 2 ; Nicole Tomczak-Jaegermann 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 = {Shahar Mendelson and Alain Pajor and Nicole Tomczak-Jaegermann},
     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},
}
TY  - JOUR
AU  - Shahar Mendelson
AU  - Alain Pajor
AU  - Nicole Tomczak-Jaegermann
TI  - Reconstruction and subgaussian processes
JO  - Comptes Rendus. Mathématique
PY  - 2005
SP  - 885
EP  - 888
VL  - 340
IS  - 12
PB  - Elsevier
DO  - 10.1016/j.crma.2005.04.032
LA  - en
ID  - CRMATH_2005__340_12_885_0
ER  - 
%0 Journal Article
%A Shahar Mendelson
%A Alain Pajor
%A Nicole Tomczak-Jaegermann
%T Reconstruction and subgaussian processes
%J Comptes Rendus. Mathématique
%D 2005
%P 885-888
%V 340
%N 12
%I Elsevier
%R 10.1016/j.crma.2005.04.032
%G en
%F CRMATH_2005__340_12_885_0
Shahar Mendelson; Alain Pajor; Nicole Tomczak-Jaegermann. Reconstruction and subgaussian processes. Comptes Rendus. Mathématique, Volume 340 (2005) no. 12, pp. 885-888. doi : 10.1016/j.crma.2005.04.032. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2005.04.032/

[1] S. Artstein The change in the diameter of a convex body under a random sign-projection (V.D. Milman; G. Schechtman, 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] S. Boucheron; O. Bousquet; G. Lugosi 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] A.U. Garnaev; E.D. Gluskin 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] S. Mendelson GAFA Seminar Notes 2002–2003 (V.D. Milman; G. Schechtman, eds.), Lecture Notes in Math., vol. 1850, 2004, pp. 193-235

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

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

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

[12] A. Pajor; N. Tomczak-Jaegermann 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 :

Commentaires - Politique


Ces articles pourraient vous intéresser

Geometry of log-concave ensembles of random matrices and approximate reconstruction

Radosław Adamczak; Rafał Latała; Alexander E. Litvak; ...

C. R. Math (2011)


Smallest singular value of random matrices with independent columns

Radosław Adamczak; Olivier Guédon; Alexander Litvak; ...

C. R. Math (2008)