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.
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.
Accepté le :
Publié le :
Shahar Mendelson 1 ; Alain Pajor 2 ; Nicole Tomczak-Jaegermann 3
@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}, }
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] 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] 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] 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] GAFA Seminar Notes 2002–2003 (V.D. Milman; G. Schechtman, eds.), Lecture Notes in Math., vol. 1850, 2004, pp. 193-235
[9] Statistical Sufficiency for classes in empirical spaces (N. Cesa-Bianchi; S.A. Goldman, eds.), Proceedings of the 13th Annual Conference on Computational Learning Theory COLT00, 2000, pp. 81-89
[10] Regularization of star bodies by random hyperplane cut off, Studia Math., Volume 159 (2003), pp. 247-261
[11] Subspaces of small codimension of finite-dimensional Banach spaces, Proc. Amer. Math. Soc., Volume 97 (1986) no. 4, pp. 637-642
[12] 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