On the impossibility of dimension reduction in l 1
From MaRDI portal
Publication:3546289
DOI10.1145/1089023.1089026zbMath1310.68199OpenAlexW2149463264WikidataQ58198040 ScholiaQ58198040MaRDI QIDQ3546289
Publication date: 21 December 2008
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1089023.1089026
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (29)
Nonexistence of embeddings with uniformly bounded distortions of Laakso graphs into diamond graphs ⋮ On Flattenability of Graphs ⋮ The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite ⋮ Learning and inferencing in user ontology for personalized semantic web search ⋮ On the geometry of the countably branching diamond graphs ⋮ Entropy-based bounds on dimension reduction in \(L^1\) ⋮ Dimension reduction for finite trees in \(\ell_1\) ⋮ Stochastic approximation of lamplighter metrics ⋮ Distortion of embeddings of binary trees into diamond graphs ⋮ Lipschitz geometry of operator spaces and Lipschitz-free operator spaces ⋮ \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\) ⋮ Matrix deviation inequality for ℓp-norm ⋮ Maximum gradient embeddings and monotone clustering ⋮ Representation and coding of signal geometry ⋮ Bounds on Dimension Reduction in the Nuclear Norm ⋮ On variants of the Johnson–Lindenstrauss lemma ⋮ Linear dimension reduction approximately preserving a function of the $1$-norm ⋮ Low Distortion Metric Embedding into Constant Dimension ⋮ Real-valued embeddings and sketches for fast distance and similarity estimation ⋮ Limitations on Quantum Dimensionality Reduction ⋮ Impossibility of dimension reduction in the nuclear norm ⋮ Sketching information divergences ⋮ No dimension reduction for doubling subsets of \(\ell_q\) when \(q>2\) revisited ⋮ Some applications of Ball’s extension theorem ⋮ DIAMOND GRAPHS AND SUPER-REFLEXIVITY ⋮ On the Impossibility of Dimension Reduction for Doubling Subsets of $\ell_{p}$ ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Low dimensional embeddings of doubling metrics
This page was built for publication: On the impossibility of dimension reduction in l 1
