algorithm - 约翰逊-林登斯特劳斯引理的正确实现

Question

我正在尝试实施Johnson-Lindenstrauss lemma。我在这里搜索了伪代码，但找不到任何东西。

我不知道我是否正确实施了它。我只希望你们了解引理的人请帮我检查我的代码，并就正确的 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);

Answer 1

首先，要找到求解多项式方程所需的 epsilon。

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.

现在您知道 epsilon 应该等于或大于结果。

Answer 2

对于 R^N 中的任何一组 m 点，并且对于 k = 20*logm/epsilon^2 和 epsilon < 1/2：

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

获得 Pr[success]>=1-2m^(5*epsilon-3)

Answer 3

R 包可用于使用 Johnson Lindenstrauss Lemma RandPro执行随机投影