TY - JOUR

T1 - Entropy-based bounds on dimension reduction in L1

AU - Regev, Oded

N1 - Funding Information:
Supported by the Israel Science Foundation and by a European Research Council (ERC) Starting Grant.
Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.

PY - 2013/6

Y1 - 2013/6

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84883797119&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84883797119&partnerID=8YFLogxK

U2 - 10.1007/s11856-012-0137-6

DO - 10.1007/s11856-012-0137-6

M3 - Article

AN - SCOPUS:84883797119

VL - 195

SP - 825

EP - 832

JO - Israel Journal of Mathematics

JF - Israel Journal of Mathematics

SN - 0021-2172

IS - 2

ER -