Entropy-based bounds on dimension reduction in L^1

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

Authors: 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)

• 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/)
• Almost-Euclidean subspaces of \(\ell_1^N\) via tensor products: a simple approach to randomness reduction
• A lower bound on the error in dimensionality reduction resulting from projection onto a restricted subspace
• Metric structures in \(L_1\): dimension, snowflakes, and average distortion
• New limits to classical and quantum instance compression
• Hard Core via PCA: Entropy Bounds
• On the impossibility of dimension reduction for doubling subsets of \(\ell_{p}\)
• 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)