随机投影算法伪码

Question

我试图在非常稀疏的数据集上应用随机投影方法.我找到了关于Johnson Lindenstrauss方法的论文和教程,但是每一个方法都充满了方程式,对我没有任何有意义的解释.例如,关于Johnson-Lindenstrauss的这份文件

不幸的是,从这个文档中,我不知道算法的实现步骤.这是一个很长的镜头,但有谁能告诉我简单的英文版本或非常简单的算法伪代码？或者我在哪里可以开始挖掘这个方程式？有什么建议？

例如,通过阅读有关Johnson-Lindenstrauss的论文,我从算法中理解的是:

1. 假设我们有一个AxB矩阵,其中A是样本B数,是维数,例如100x5000.我想减小它的尺寸500,这将产生一个100x500矩阵.

据我所知:首先,我需要构建一个100x500矩阵并随机填充条目+1和-1(概率为50%).

编辑:
好的,我想我开始明白了.因此,我们有一个矩阵A是mxn.我们希望减少它E是mxk.

我们需要做的是,建立一个矩阵R具有nxk尺寸,并与填充它0,-1或者+1,对于2/3,1/6和1/6概率.

在构造之后R,我们将简单地进行矩阵乘法AxR以找到我们的简化矩阵E.但我们并不需要做一个完整的矩阵乘法,因为如果一个元素Ri是0,我们不需要做计算.简单地跳过它.但是如果我们面对1,我们只需要添加列,或者如果是-1,只需从计算中减去它.所以我们只需使用求和而不是乘法来找到E.这就是使这种方法非常快的原因.

事实证明这是一个非常简洁的算法,虽然我觉得这个想法太愚蠢了.

Answer 1

从高维数据 A 到低维数据 E 的映射在后一篇论文的定理 1.1 的陈述中给出 - 它只是一个标量乘法和一个矩阵乘法。数据向量是矩阵 A 和 E 的行。正如作者在第 7.1 节中指出的那样，您不需要使用完整的矩阵乘法算法。