Lema de Johnson-Lindenstrauss - Johnson–Lindenstrauss lemma

Na matemática, o lema de Johnson-Lindenstrauss é um resultado com o nome de William B. Johnson e Joram Lindenstrauss sobre embeddings de baixa distorção de pontos do espaço euclidiano de alta dimensão para o espaço euclidiano de baixa dimensão . O lema afirma que um conjunto de pontos em um espaço de alta dimensão pode ser embutido em um espaço de dimensão muito inferior de tal forma que as distâncias entre os pontos são quase preservadas . O mapa usado para a incorporação é pelo menos Lipschitz , e pode até ser considerado uma projeção ortogonal .

O lema tem aplicações em sensoriamento compactado , aprendizado múltiplo , redução de dimensionalidade e incorporação de gráficos . Muitos dos dados armazenados e manipulados em computadores, incluindo texto e imagens, podem ser representados como pontos em um espaço de alta dimensão (ver modelo de espaço vetorial para o caso de texto). No entanto, os algoritmos essenciais para trabalhar com esses dados tendem a ficar presos muito rapidamente à medida que a dimensão aumenta. Portanto, é desejável reduzir a dimensionalidade dos dados de forma a preservar sua estrutura relevante. O lema de Johnson-Lindenstrauss é um resultado clássico nessa linha.

Além disso, o lema é restrito a um fator constante, ou seja, existe um conjunto de pontos de tamanho m que precisa de dimensão

${\ displaystyle \ Omega \ left ({\ frac {\ log (m)} {\ varepsilon ^ {2}}} \ right)}$

a fim de preservar as distâncias entre todos os pares de pontos dentro de um fator de . ${\ displaystyle (1 \ pm \ varepsilon)}$

Lema

Dado um conjunto de pontos e um número , há um mapa linear tal que ${\ displaystyle 0 <\ varepsilon <1}$${\ displaystyle X}$${\ displaystyle m}$${\ displaystyle \ mathbb {R} ^ {N}}$${\ displaystyle n> 8 \ ln (m) / \ varepsilon ^ {2}}$${\ displaystyle f: \ mathbb {R} ^ {N} \ rightarrow \ mathbb {R} ^ {n}}$

${\ displaystyle (1- \ varejpsilon) \ | uv \ | ^ {2} \ leq \ | f (u) -f (v) \ | ^ {2} \ leq (1+ \ varejpsilon) \ | uv \ | ^ {2}}$

para todos . ${\ displaystyle u, v \ in X}$

A fórmula pode ser reorganizada:

Uma prova do lema considera ƒ um múltiplo adequado da projeção ortogonal em um subespaço aleatório de dimensão em e explora o fenômeno da concentração de medida . ${\ displaystyle n}$${\ displaystyle \ mathbb {R} ^ {N}}$

Obviamente, uma projeção ortogonal irá, em geral, reduzir a distância média entre os pontos, mas o lema pode ser visto como lidando com distâncias relativas , que não mudam com a escala. Resumindo, você lança os dados e obtém uma projeção aleatória, o que reduzirá a distância média, e então você aumenta as distâncias para que a distância média retorne ao seu valor anterior. Se você continuar jogando os dados, você encontrará, em tempo aleatório polinomial, uma projeção para a qual as distâncias (em escala) satisfaçam o lema.

Declaração alternativa

Um lema relacionado é o lema JL distributivo. Este lema afirma que para qualquer 0 <  ε , δ  <1/2 e inteiro positivo d , existe uma distribuição sobre R ^{k × d a} partir da qual a matriz A é desenhada de modo que para k = O ( ε ⁻² log (1 / δ )) e para qualquer vetor de comprimento unitário x ∈ R ^d , a reivindicação abaixo é válida.

${\ displaystyle P (| \ Vert Ax \ Vert _ {2} ^ {2} -1 |> \ varepsilon) <\ delta}$

Pode-se obter o JL lema desde a versão de distribuição, definindo e para alguns par u , v tanto em X . Então, o lema JL segue por uma união ligada a todos esses pares. ${\ displaystyle x = (uv) / \ | uv \ | _ {2}}$${\ displaystyle \ delta <1 / n ^ {2}}$

Acelerando a transformação JL

Dado A , o cálculo do produto do vetor da matriz leva um tempo O ( kd ). Houve algum trabalho em derivar distribuições para as quais o produto do vetor da matriz pode ser calculado em menos de tempo O ( kd ).

Existem duas linhas principais de trabalho. O primeiro, Fast Johnson Lindenstrauss Transform (FJLT), foi introduzido por Ailon e Chazelle em 2006. Este método permite o cálculo do produto do vetor da matriz em apenas para qualquer constante . ${\ displaystyle d \ log d + k ^ {2+ \ gamma}}$${\ displaystyle \ gamma> 0}$

Outra abordagem é construir uma distribuição com suporte em matrizes esparsas. Este método permite manter apenas uma fração das entradas na matriz, o que significa que o cálculo pode ser feito em tempo hábil. Além disso, se o vetor tiver apenas entradas não zereo, o Sparse JL leva tempo , que pode ser muito menor do que o tempo usado pelo Fast JL. ${\ displaystyle \ varepsilon}$${\ displaystyle kd \ varepsilon}$${\ displaystyle b}$${\ displaystyle kb \ varepsilon}$${\ displaystyle d \ log d}$

Projeções aleatórias tensorizadas

É possível combinar duas matrizes JL, considerando que o chamado produto de divisão de face é definido como os produtos tensores das linhas (foi proposto por V. Slyusar em 1996 para aplicações de radar e conjuntos de antenas digitais ). Mais diretamente, deixe e seja duas matrizes. Então, o produto de divisão facial é ${\ displaystyle {C} \ in \ mathbb {R} ^ {3 \ vezes 3}}$${\ displaystyle {D} \ in \ mathbb {R} ^ {3 \ vezes 3}}$ ${\ displaystyle {C} \ bullet {D}}$

${\ displaystyle {C} \ bullet {D} = \ left [{\ begin {array} {c} {C} _ {1} \ otimes {D} _ {1} \\\ hline {C} _ {2 } \ otimes {D} _ {2} \\\ hline {C} _ {3} \ otimes {D} _ {3} \\\ end {array}} \ right].}$

Essa ideia de tensorização foi usada por Kasiviswanathan et al. 2010 para privacidade diferencial .

Matrizes JL definidas dessa forma usam menos bits aleatórios e podem ser aplicadas rapidamente a vetores que possuem estrutura tensorial, devido à seguinte identidade:

${\ displaystyle (\ mathbf {C} \ bullet \ mathbf {D}) (x \ otimes y) = \ mathbf {C} x \ circ \ mathbf {D} y = \ left [{\ begin {array} {c } (\ mathbf {C} x) _ {1} (\ mathbf {D} y) _ {1} \\ (\ mathbf {C} x) _ {2} (\ mathbf {D} y) _ {2 } \\\ vdots \ end {array}} \ right]}$,

onde está o produto element-wise ( Hadamard ). Esses cálculos têm sido usados ​​para calcular com eficiência kernels polinomiais e muitos outros algoritmos de álgebra linear. ${\ displaystyle \ circ}$

Em 2020 foi mostrado que se as matrizes são matrizes independentes ou matrizes Gaussianas, a matriz combinada satisfaz o lema JL distributivo se o número de linhas for pelo menos ${\ displaystyle C_ {1}, C_ {2}, \ dots, C_ {c}}$${\ displaystyle \ pm 1}$${\ displaystyle C_ {1} \ bullet \ dots \ bullet C_ {c}}$

${\ displaystyle O (\ epsilon ^ {- 2} \ log 1 / \ delta + \ epsilon ^ {- 1} ({\ tfrac {1} {c}} \ log 1 / \ delta) ^ {c})}$.

Para grandes, isso é tão bom quanto o completamente aleatório de Johnson-Lindenstrauss, mas um limite inferior correspondente no mesmo artigo mostra que essa dependência exponencial de é necessária. São sugeridas construções alternativas de JL para contornar isso. ${\ displaystyle \ epsilon}$${\ displaystyle (\ log 1 / \ delta) ^ {c}}$

Veja também

• Projeção aleatória

Notas

Leitura adicional

• Achlioptas, Dimitris (2003), "Database-friendly random projections: Johnson-Lindenstrauss with binary coins", Journal of Computer and System Sciences , 66 (4): 671-687, doi : 10.1016 / S0022-0000 (03) 00025- 4 , MR  2005771. Versão de jornal de um artigo publicado anteriormente no PODC 2001.
• Baraniuk, Richard ; Davenport, Mark; DeVore, Ronald ; Wakin, Michael (2008), "Uma prova simples da propriedade de isometria restrita para matrizes aleatórias", Constructive Approximation , 28 (3): 253–263, doi : 10.1007 / s00365-007-9003-x , hdl : 1911/21683 , MR  2453366.
• Dasgupta, Sanjoy; Gupta, Anupam (2003), "Uma prova elementar de um teorema de Johnson e Lindenstrauss" (PDF) , Random Structures & Algorithms , 22 (1): 60-65, doi : 10.1002 / rsa.10073 , MR  1943859.
• Landweber, Peter ; Lazar, Emanuel A .; Patel, Neel (2016). "Em diâmetros de fibra de mapas contínuos". American Mathematical Monthly . 123 : 392–397. arXiv : 1503.07597 .
• Slyusar, VI (20/05/1997). "Modelo analítico do arranjo de antenas digitais com base em produtos de matriz de divisão de face" (PDF) . Proc. ICATT-97, Kiev : 108-109.
• Slyusar, VI (13 de março de 1998). "Uma família de produtos faciais de matrizes e suas propriedades" (PDF) . Cibernética e Análise de Sistemas C / C de Kibernetika I Sistemnyi Analiz.- 1999 . 35 (3): 379–384. doi : 10.1007 / BF02733426 .