On the impossibility of dimension reduction in l 1

DOI10.1145/1089023.1089026MaRDI QIDQ3546289zbMATH OpenOpenAlexDBLPWikidataFDO

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)

Cited in

(29)

Sketching information divergences
Maximum gradient embeddings and monotone clustering
No dimension reduction for doubling subsets of $\ell_q$ when $q>2$ revisited
Linear dimension reduction approximately preserving a function of the $1$-norm
Nonexistence of embeddings with uniformly bounded distortions of Laakso graphs into diamond 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
Low dimensional embeddings of doubling metrics
Low distortion metric embedding into constant dimension
Limitations on quantum dimensionality reduction
DIAMOND GRAPHS AND SUPER-REFLEXIVITY
On Flattenability of Graphs
On variants of the Johnson–Lindenstrauss lemma
Entropy-based bounds on dimension reduction in L^1
Dimension reduction for finite trees in _1
Distortion of embeddings of binary trees into diamond graphs
Representation and coding of signal geometry
Real-valued embeddings and sketches for fast distance and similarity estimation
Bounds on Dimension Reduction in the Nuclear Norm
Some applications of Ball’s extension theorem
On the impossibility of dimension reduction for doubling subsets of $\ell_{p}$
Dimension reduction for finite trees in $\ell_1$
On multiplicative $\lambda$-approximations and some geometric applications
Stochastic approximation of lamplighter metrics
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
Dimensionality of Hamming metrics and Rademacher type

This page was built for publication: On the impossibility of dimension reduction in l ₁

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