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 len R d f : R dR k k = O ( log n / ϵ 2 ) x , y S ( 1 - ϵ ) | | f ( x ) - f ( y ) | | 2| | x - y | | 2( 1 + ϵ ) |SnRF:RRkk=O(Journaln/ϵ2)X,yS1 1

(1-ϵ)||F(X)-F(y)||2||X-y||2(1+ϵ)||F(X)-F(y)||2
11mé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"?
Aaron Roth
la source

Réponses:

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 . 1 + ϵ 1 - ϵ 1 / ϵ11+ϵ1-ϵ1/ϵ

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

Moritz
la source
7

1O(n/ϵ)O(1/(δϵ))1-δ

Yair
la source
4

1ScRdkccV1dL1F:11kk=O(ϵ-2cJournalc)X,yV(1-ϵ)F(X)-F(y)1X-y1(1+ϵ)F(X)-F(y)1FS

FSk×

Sasho Nikolov
la source