Entropy-based bounds on dimension reduction in L1

Research output: Contribution to journalArticle

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 ℓ 1 d with distortion D requires dimension d at least NΩ (1/D2), and that for every e{open} > 0 and large enough integer N, there exists an N-point subset of L 1 such that embedding it into ℓ 1 d with distortion 1 + e{open} requires dimension d at least NΩ (1/D2)). 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.

Original languageEnglish (US)
Pages (from-to)825-832
Number of pages8
JournalIsrael Journal of Mathematics
Volume195
Issue number2
DOIs
StatePublished - Jun 2013

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Entropy-based bounds on dimension reduction in L<sup>1</sup>'. Together they form a unique fingerprint.

  • Cite this