Entropy-based bounds on dimension reduction in L^1

DOI10.1007/S11856-012-0137-6zbMATH Open1311.68176arXiv1108.1283OpenAlexW2045745231MaRDI QIDQ375695FDOQ375695

Oded Regev

Publication date: 31 October 2013

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

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 $el{l}_1^d$ with distortion $D$ requires dimension $d$ at least $N^{Omega(1/D^2)}$, and that for every $eps>0$ and large enough integer $N$, there exists an $N$-point subset of $L_1$ such that embedding it into $el{l}_1^d$ with distortion $1+eps$ requires dimension $d$ at least $N^{1-O(1/log(1/eps))}$. 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.

Full work available at URL: https://arxiv.org/abs/1108.1283

Recommendations

• Embedding the diamond graph in \(L_p\) and dimension reduction in \(L_1\)
• Metric structures in \(L_1\): dimension, snowflakes, and average distortion
• LATIN 2004: Theoretical Informatics
• Dimension reduction for finite trees in \(\ell_1\)
• Improved lower bounds for embeddings into \(L_1\)

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Measures of information, entropy (94A17) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Elements of Information Theory
• Embedding the diamond graph in \(L_p\) and dimension reduction in \(L_1\)
• On the impossibility of dimension reduction in l ₁
• Near Linear Lower Bound for Dimension Reduction in L1

Cited In (12)

• New Limits to Classical and Quantum Instance Compression
• LATIN 2004: Theoretical Informatics
• Distortion of embeddings of binary trees into diamond graphs
• Cross-entropy optimal dimensionality reduction with a condition on information capacity
• Bounds on Dimension Reduction in the Nuclear Norm
• Entropy-based uncertainty measures for L/sup 2/(/spl Ropf//sup n/), /spl lscr//sup 2/(/spl Zopf/), and /spl lscr//sup 2/(/spl Zopf//N/spl Zopf/) with a Hirschman optimal transform for /spl lscr//sup 2/(/spl Zopf//N/spl Zopf/)
• A lower bound on the error in dimensionality reduction resulting from projection onto a restricted subspace
• On the Impossibility of Dimension Reduction for Doubling Subsets of $\ell_{p}$
• Metric structures in \(L_1\): dimension, snowflakes, and average distortion
• Hard Core via PCA: Entropy Bounds
• Impossibility of dimension reduction in the nuclear norm
• Lower bounds for local versions of dimension reductions

This page was built for publication: Entropy-based bounds on dimension reduction in \(L^1\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q375695)