Redução de dimensionalidade com folga?

11

O lema Johnson-Lindenstrauss diz aproximadamente que para qualquer coleção de pontos em , existe um mapa onde tal que para todos : É sabido que declarações semelhantes não são possíveis para a métrica , mas é sabido se existe alguma maneira de contornar tais valores inferiores limites, oferecendo garantias mais fracas? Por exemplo, pode haver uma versão do lema acima para o $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étrica que promete apenas preservar as distâncias da maioria dos pontos, mas pode deixar algumas distorcidas arbitrariamente? Um que não oferece garantia multiplicativa para pontos "muito próximos"?

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

9

A referência padrão para um resultado tão positivo é o artigo de Piotr Indyk sobre distribuições estáveis:

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

Ele mostra uma técnica de redução de dimensão para que a distância entre qualquer par de pontos não aumenta (mais do que o fator ) com probabilidade constante e as distâncias não diminuem (em mais do que o fator ) com alta probabilidade. A dimensão da incorporação será exponencial em . $\ell_1$ $1+\epsilon$ $1-\epsilon$ $1/\epsilon$

Provavelmente existem trabalhos de acompanhamento dos quais não estou ciente.

Moritz
fonte

8

Consulte o documento métricos com garantias relaxadas, que apresenta resultados em (sob as condições de "distorção graciosamente degradante") e em incorporações gerais em . $\ell_1$ $\ell_p$

Veja também os Procedimentos práticos para redução de dimensão no documento . $\ell_1$

spinxl39
fonte

7

Foi recentemente demonstrado por Newman e Rabinovich que, para n pontos em há redução de dimensão para a dimensão . Usando um teorema de Abraham et al. (Incorporação métrica com garantias relaxadas, mencionadas acima), é possível obter uma redução de dimensão na dimensão que funciona para uma fração de dos pares. $\ell_1$ $O(n/\epsilon)$ $O(1/(\delta\epsilon))$ $1-\delta$

Yair
fonte

4

Outro relaxamento da redução de dimensão é exigir que esteja em um subespaço dimensional de e faça depender de . Talagrand provou que, dado um subespaço dimensional de (ele até prova para ), existe um mapa para tal que para todos , $\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$ . Sua incorporação é um procedimento aleatório simples, mas prossegue em etapas e cada etapa é bem-sucedida com probabilidade constante; após cada etapa, é necessário verificar se a etapa foi bem-sucedida e repita se não tiver. Incorporação de tão Talagrand falta uma característica crucial da JLT: o fato de que pode ser escolhido a partir de uma distribuição que é independente do . $f$ $S$

Muito recentemente, Woodruff e Sohler provaram um resultado análogo ao de Talagrand, mas com o recurso adicional de que , assim como no JLT, é um mapeamento linear escolhido de uma distribuição independente de : você precisa escolher uma matriz em que cada entrada é uma variável aleatória iid Cauchy. Isso está no espírito das projeções estáveis de Indyk: Cauchy é 1-estável. $f$ $S$ $k \times d$

Sasho Nikolov
fonte

Redução de dimensionalidade com folga?

Respostas: