我试图在非常稀疏的数据集上应用随机投影方法.我找到了关于Johnson Lindenstrauss方法的论文和教程,但是每一个方法都充满了方程式,对我没有任何有意义的解释.例如,关于Johnson-Lindenstrauss的这份文件
不幸的是,从这个文档中,我不知道算法的实现步骤.这是一个很长的镜头,但有谁能告诉我简单的英文版本或非常简单的算法伪代码？或者我在哪里可以开始挖掘这个方程式？有什么建议？
例如,通过阅读有关Johnson-Lindenstrauss的论文,我从算法中理解的是:
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.这就是使这种方法非常快的原因.
事实证明这是一个非常简洁的算法,虽然我觉得这个想法太愚蠢了.
我想将稀疏矩阵A与矩阵B相乘,矩阵B具有0,-1或1作为元素.为了降低矩阵乘法的复杂性,我可以忽略它们为0的项目,或者如果项目为1或者sub则继续添加没有乘法的列.如果它是-1.关于这个的讨论在这里:
现在我可以继续实现这个技巧,但我想知道我是否使用Numpy的乘法函数它会更快.
有谁知道他们是否优化了这种矩阵的矩阵乘法？或者你可以建议一些东西来加快这个过程,因为我有一个矩阵300000x1000.