Réduction de la dimensionnalité avec du mou?

11

Le lemme de Johnson-Lindenstrauss dit grosso modo que pour toute collection de points dans , il existe une carte où tel que pour tout : Il est connu que des instructions similaires ne sont pas possibles pour la métrique , mais est-il connu s'il existe un moyen de contourner une telle baisse limites en offrant des garanties plus faibles? Par exemple, peut-il y avoir une version du lemme ci-dessus pour le $S$ $n$ $\mathbb{R}^d$ $f:\mathbb{R}^d \rightarrow \mathbb{R}^k$ $k = O(\log n/\epsilon^2)$ $x, y \in S$

(1 - ϵ) | | F (X) - F (y) | |_{2} \leq | | X - y | |_{2} \leq (1 + ϵ) | | F (X) - F (y) | |_{2}

$(1-\epsilon)||f(x)-f(y)||_2 \leq ||x-y||_2 \leq (1+\epsilon)||f(x)-f(y)||_2$

ℓ_{1}

$\ell_1$

ℓ_{1}

$\ell_1$ métrique qui ne promet que de préserver les distances de la plupart des points, mais pourrait en laisser une distorsion arbitraire? Celui qui ne fait aucune garantie multiplicative pour les points "trop proches"?

ds.algorithms approximation-algorithms cg.comp-geom metrics embeddings Aaron Roth
la source

9

La référence standard pour un résultat aussi positif est l'article de Piotr Indyk sur les distributions stables:

http://people.csail.mit.edu/indyk/st-fin.ps

Il montre une technique de réduction de dimension pour où la distance entre n'importe quelle paire de points n'augmente pas (de plus de facteur ) avec une probabilité constante et les distances ne diminuent pas (de plus de facteur ) avec une valeur élevée probabilité. La dimension de l'incorporation sera exponentielle en . $\ell_1$ $1+\epsilon$ $1-\epsilon$ $1/\epsilon$

Il y a probablement des travaux de suivi que je ne connais pas.

Moritz
la source

8

Voir le document sur les plongements métriques avec des garanties détendues qui donne des résultats sur (dans les conditions de "distorsion dégradante gracieuse") et les plongements généraux sur . $\ell_1$ $\ell_p$

Consultez également les Procédures pratiques pour la réduction des dimensions dans le papier . $\ell_1$

spinxl39
la source

7

$\ell_1$ $O(n/\epsilon)$ $O(1/(\delta\epsilon))$ $1-\delta$

Yair
la source

4

$\ell_1$ $S$ $c$ $\mathbb{R}^d$ $k$ $c$ $c$ $V$ $\ell_1^d$ $L_1$ $f:\ell_1^d \rightarrow \ell_1^k$ $k = O(\epsilon^{-2}c\log c)$ $x, y \in V$ $(1-\epsilon)\|f(x) - f(y)\|_1 \leq \|x - y\|_1 \leq (1+\epsilon)\|f(x) - f(y)\|_1$ $f$ $S$

$f$ $S$ $k \times d$

Sasho Nikolov
la source

Réduction de la dimensionnalité avec du mou?

Réponses: