随机投影算法伪code [英] Random projection algorithm pseudo code

问题描述

我想在一个非常稀疏的数据集应用随机预测方法。我发现的文件和教程关于约翰逊Lindenstrauss方法，但他们每个人都充满了方程式，这使得任何有意义的解释给我。例如，在约翰逊Lindenstrauss

I am trying to apply Random Projections method on a very sparse dataset. I found papers and tutorials about Johnson Lindenstrauss method, but every one of them is full of equations which makes no meaningful explanation to me. For example, this document on Johnson-Lindenstrauss

不幸的是，从这个文件，我可以不知道有关实施步骤的算法。这是一个长镜头，但是否有任何人谁可以告诉我这个算法的纯英文版本，或者非常简单的伪code？或者，在那里我可以开始去挖掘这个公式？有什么建议么？

Unfortunately, from this document, I can get no idea about the implementation steps of the algorithm. It's a long shot but is there anyone who can tell me the plain English version or very simple pseudo code of the algorithm? Or where can I start to dig this equations? Any suggestions?

例如，我从算法的理解通过阅读本文关于约翰逊-Lindenstrauss 是：

For example, what I understand from the algorithm by reading this paper concerning Johnson-Lindenstrauss is that:

1. 假设我们有一个 AXB 矩阵，其中 A 为样本的数量和 B 是维数，例如 100x5000 。我想，以减少它的尺寸为 500 ，这将产生一个 100x500 基质。

1. Assume we have a AxB matrix where A is number of samples and B is the number of dimensions, e.g. 100x5000. And I want to reduce the dimension of it to 500, which will produce a 100x500 matrix.

据我的理解：首先，我需要构造一个 100x500 矩阵和 +1 和 1 （有50％的概率）。

As far as I understand: first, I need to construct a 100x500 matrix and fill the entries randomly with +1 and -1 (with a 50% probability).

编辑：
好吧，我想我开始明白这一点。因此，我们有一个矩阵 A 是 MXN 。我们希望将其降低到电子是 MXK 。

Okay, I think I started to get it. So we have a matrix A which is mxn. We want to reduce it to E which is mxk.

我们需要做的是，构建一个矩阵研究具有 N×K个尺寸，并用填充 0 ， 1 或 +1 ，相对于 2/3 ， 1/6 和 1/6 概率。

What we need to do is, to construct a matrix R which has nxk dimension, and fill it with 0, -1 or +1, with respect to 2/3, 1/6 and 1/6 probability.

构造之后研究，我们只是做一个矩阵乘法 AXR 找到我们缩减了的矩阵è。但是，我们并不需要做一个全面的矩阵乘法，因为如果日是 0 ，我们不要的元素'T需要做的计算。简单地跳过它。但是，如果我们面对 1 ，我们刚才添加的列，或者如果它是 1 ，从刚才减去它的计算。因此，我们可以简单的将求和，而不是乘法找到电子。这是什么使这个方法非常快。

After constructing this R, we'll simply do a matrix multiplication AxR to find our reduced matrix E. But we don't need to do a full matrix multiplication, because if an element of Ri is 0, we don't need to do calculation. Simply skip it. But if we face with 1, we just add the column, or if it's -1, just subtract it from the calculation. So we'll simply use summation rather than multiplication to find E. And that is what makes this method very fast.

原来一个非常整洁的算法，但我觉得自己太愚蠢的想法。

It turned out a very neat algorithm, although I feel too stupid to get the idea.

推荐答案

从高维数据A到低维数据E的映射给出定理1.1在后文的声明 - 这是一个简单的标量乘法随后的矩阵乘法。数据向量是矩阵A和E的行正​​如作者指出，在第7.1节，你并不需要使用一个完整的矩阵乘法算法。

The mapping from high-dimensional data A to low-dimensional data E is given in the statement of theorem 1.1 in the latter paper - it is simply a scalar multiplication followed by a matrix multiplication. The data vectors are the rows of the matrices A and E. As the author points out in section 7.1, you don't need to use a full matrix multiplication algorithm.

这篇关于随机投影算法伪code的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！