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

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

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₁
• 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₁
• Near Linear Lower Bound for Dimension Reduction in L1
• On the impossibility of dimension reduction in l ₁

Cited in

(12)

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

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)