Implémentation correcte du lemme de Johnson-Lindenstrauss

-1

J'essaie d'implémenter le Johnson-Lindenstrauss lemma. J'ai cherché le pseudocode ici mais je n'ai rien trouvé.Implémentation correcte du lemme de Johnson-Lindenstrauss

Je ne sais pas si je l'ai implémenté correctement ou non. Je veux juste que les gars qui comprennent le lemme vérifient mon code pour moi et me conseillent sur la bonne implémentation de matlab.

n = 2; 
d = 4; 
k = 2; 
G = rand(n,d); 
epsilon = sqrt(log(n)/k); 

% Projection in dim k << d 
% Defining P (k x d) 
P = randn(k,d); 

% Projecting down to k-dim 
proj = P.*G; 
u = proj(:,1); 
v = proj(:,2); 
% u = P * G(:,5); 
% v = P * G(:,36); 
norm(G(:,1)-G(:,2))^2 * k * (1-epsilon); 
norm(u - v)^2; 
norm(G(:,1)-G(:,2))^2 * k * (1+epsilon);

Source

2013-08-12 elizwet

qui lemme que vous essayez de coder . quelle est l'entrée et la sortie du code. J'ai vérifié la page que vous avez mentionnée mais il y a beaucoup de lemmes et de faits. – NKN

Le premier lemme. Le lemme qui contient ceci: (1- \ epsilon) \ | uv \ |^2 \ le \ | f (u) -f (v) \ |^2 \ le (1+ \ epsilon) \ | uv \ |^2. – elizwet

pour la première partie de celle pour trouver l'epsilon dont vous avez besoin pour résoudre une équation polynomiale.

n = 2; 
k = 2; 
pol1 = [-1/3 1/2 0 4*log2(n)/k]; 
c = roots(pol1) 

    1.4654 + 1.4304i 
    1.4654 - 1.4304i 
    -1.4308 + 0.0000i

Ensuite, vous devez supprimer les racines complexes et garder le vrai:

epsilon = c(imag(c)==0); 

% if there are more than one root with imaginary part equal to 0 then you need to select the smaller one.

maintenant vous savez que l'epsilon doit être égale ou supérieure que le résultat.

Source

2013-08-12 19:59:02 NKN

pourquoi est-ce epsilon = sqrt (log (n)/k); Pas correcte? Comment puis-je savoir que ma mise en œuvre du lemme est correcte ou non? Ce que je fais pour voir si ma mise en œuvre du lemme est correcte ou non, c'est regarder norme (u - v)^2; si la valeur se situe entre la norme (G (:, 1) -G (:, 2))^2 * k * (1-epsilon); et norme (G (:, 1) -G (:, 2))^2 * k * (1 + epsilon); inclusivement, alors je conclus qu'il est juste? Je ne sais pas si c'est une façon de savoir si la mise en œuvre du lemme est correcte ou non. Y at-il de toute façon, on peut savoir correctement si la mise en œuvre est correcte ou non? – elizwet

Pour tout ensemble de m points dans R^N et k = 20 * logm/epsilon^2 et epsilon < 1/2.

1/sqrt (k) * randn (k, N)

obtenir Pr [succès]> = 1-2m^(5 * epsilon-3)

Source

2014-01-29 11:37:47 Sarvenaz

Un package R est disponible pour effectuer la projection aléatoire en utilisant Johnson Lindenstrauss lemme RandPro

Source

2017-01-11 13:40:59 Siddhu

Implémentation correcte du lemme de Johnson-Lindenstrauss

Répondre

Questions connexes