Reconstruction and subgaussian processes

Shahar Mendelson; Alain Pajor; Nicole Tomczak-Jaegermann

doi:10.1016/j.crma.2005.04.032

Functional Analysis

Reconstruction and subgaussian processes

Presented by: Gilles Pisier

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

¹ 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, Volume 340 (2005) no. 12, pp. 885-888.

Abstract
Résumé

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.

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.

Received: 2005-04-03
Accepted: 2005-04-27
Published online: 2005-05-31

DOI: 10.1016/j.crma.2005.04.032

Author's affiliations:

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

¹ 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

@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/

References
Cited by

[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 $L_{2}$ 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

Cited by Sources:

Comments - Policy