Entropy-based bounds on dimension reduction in L^1

DOI10.1007/S11856-012-0137-6MaRDI QIDQ375695zbMATH OpenOpenAlexFDO

Authors Oded Regev

Publication date 31 October 2013

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

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

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)

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.

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\)

Cites work

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

Cited in

(12)

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

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)