Правильная реализация леммы Johnson-Lindenstrauss

-1

Я пытаюсь реализовать Johnson-Lindenstrauss lemma. У меня есть поиск псевдокода здесь, но я не смог его получить.Правильная реализация леммы Johnson-Lindenstrauss

Я не знаю, правильно ли я его реализовал или нет. Я просто хочу, чтобы вы, ребята, поняли эту лемму, чтобы проверить мой код и посоветуйте мне правильную реализацию 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);

источник

2013-08-12 elizwet

которой лемма вы пытаетесь код , каков вход и выход кода. Я проверил указанную вами страницу, но есть много лемм и фактов. – NKN

Первая лемма. Лемма, которая содержит это: (1- \ epsilon) \ | uv \ |^2 \ le \ | f (u) -f (v) \ |^2 \ le (1+ \ epsilon) \ | uv \ |^2. – elizwet

для первой части этого, чтобы найти эпсилон, вам нужно решить уравнение полинома.

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

Затем вам нужно удалить сложные корни и сохранить реальный:

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.

теперь вы знаете, что эпсилон должна быть равна или больше, что результат.

источник

2013-08-12 19:59:02 NKN

Почему это epsilon = sqrt (log (n)/k); не верно? Как я могу знать, что моя реализация леммы верна или нет? Что я делаю, чтобы убедиться, что моя реализация леммы верна или нет, смотрит на norm (u - v)^2; если значение лежит между нормой (G (:, 1) -G (:, 2))^2 * k * (1-эпсилон); и норма (G (:, 1) -G (:, 2))^2 * k * (1 + epsilon); включительно, тогда я заключу, что это правильно? Я не знаю, является ли это способом узнать, правильно ли реализована лемма. Нужно ли в любом случае правильно знать, правильно ли реализована реализация? – elizwet

Для любого множества т точек в R^N, и при к = 20 * logm/эпсилон^2 и эпсилон < 1/2:.

1/SQRT (к) * randn (K, N)

получить Pr [успех]> = 1-2m^(5 * эпсилон-3)

источник

2014-01-29 11:37:47 Sarvenaz

пакет R доступен для выполнения в случайном порядке проекции с помощью Johnson Линденштраусс Лемма RandPro

источник

2017-01-11 13:40:59 Siddhu

Правильная реализация леммы Johnson-Lindenstrauss

ответ

Смежные вопросы