Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-01111562
Contributor : Brigitte Briot <>
Submitted on : Friday, January 30, 2015 - 3:37:00 PM
Last modification on : Tuesday, May 4, 2021 - 2:06:02 PM

Links full text

Identifiers

Collections

Citation

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

Share

Metrics

Record views

192