Reducción de dimensionalidad con holgura?

11

El lema de Johnson-Lindenstrauss dice aproximadamente que para cualquier colección $S$ de $n$ puntos en $\mathbb{R}^d$ , existe un mapa $f:\mathbb{R}^d \rightarrow \mathbb{R}^k$ donde $k = O(\log n/\epsilon^2)$ tal que para todos $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$ Se sabe que declaraciones similares no son posibles para lamétrica

ℓ_{1}

$\ell_1$ , pero ¿se sabe si hay alguna forma de sortear esos límites inferiores ofreciendo garantías más débiles? Por ejemplo, ¿puede haber una versión del lema anterior para

ℓ_{1}

$\ell_1$ métrica que solo promete preservar las distancias de la mayoría de los puntos, pero que podría dejar algunas distorsionadas arbitrariamente? ¿Uno que no garantice multiplicativamente los puntos que están "demasiado cerca"?

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

9

La referencia estándar para un resultado tan positivo es el artículo de Piotr Indyk sobre distribuciones estables:

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

Muestra una técnica de reducción de dimensiones para $\ell_1$ donde la distancia entre cualquier par de puntos no aumenta (en más del factor $1+\epsilon$ ) con probabilidad constante y las distancias no disminuyen (en más del factor $1-\epsilon$ ) con alta probabilidad. La dimensión de la incrustación será exponencial en $1/\epsilon$ .

Probablemente hay trabajos de seguimiento que no conozco.

Moritz
fuente

8

$\ell_1$ $\ell_p$

$\ell_1$

spinxl39
fuente

7

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

Yair
fuente

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$

Muy recientemente, Woodruff y Sohler han demostrado un resultado análogo al de Talagrand, pero con la característica adicional de que , al igual que en JLT, es un mapeo lineal seleccionado de una distribución independiente de : es necesario elegir una matriz donde cada entrada es una variable aleatoria iid Cauchy. Esto está en el espíritu de las proyecciones estables de Indyk: Cauchy es 1-estable. $f$ $S$ $k \times d$

Sasho Nikolov
fuente

Reducción de dimensionalidad con holgura?

Respuestas: