Entropy-based bounds on dimension reduction in L-1

Oded Regev 1
1 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : We show that for every large enough integer N, there exists an N-point subset of L (1) such that for every D > 1, embedding it into a"" (1) (d) with distortion D requires dimension d at least , and that for every E > > 0 and large enough integer N, there exists an N-point subset of L (1) such that embedding it into a"" (1) (d) with distortion 1 + E > requires dimension d at least ). These results were previously proven by Brinkman and Charikar [JACM, 2005] and by Andoni, Charikar, Neiman and Nguyen [FOCS 2011]. We provide an alternative and arguably more intuitive proof based on an entropy argument.
Type de document :
Article dans une revue
Israël Journal of Mathematics, The Hebrew University Magnes Press, 2013, 195 (2), pp.825-832. 〈10.1007/s11856-012-0137-6〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01111562
Contributeur : Brigitte Briot <>
Soumis le : vendredi 30 janvier 2015 - 15:37:00
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Lien texte intégral

Identifiants

Collections

Citation

Oded Regev. Entropy-based bounds on dimension reduction in L-1. Israël Journal of Mathematics, The Hebrew University Magnes Press, 2013, 195 (2), pp.825-832. 〈10.1007/s11856-012-0137-6〉. 〈hal-01111562〉

Partager

Métriques

Consultations de la notice

105