python - t-SNE的计算瓶颈是其内存复杂性吗？

我一直在探索不同的降维算法，特别是pca和t-sne。我从mnist数据集中提取一小部分（约780维），并尝试将原始数据降到三维，以将其可视化为散点图。t-sne可以非常详细地描述here。
我使用pca作为t-sne之前的中间降维步骤，正如t-sne的原始创造者在source code from their website.
我发现t-sne需要永远运行（从2000 x 25到2000 x 3功能空间需要10-15分钟），而pca运行相对较快（2000 x 780=>2000 x 20需要几秒钟）。
为什么是这个案子？我的理论是，在pca实现中（直接来自python中主要作者的源代码），他使用numpy点积符号计算X和X.T：

def pca(X = Math.array([]), no_dims = 50):
    """Runs PCA on the NxD array X in order to reduce its dimensionality to no_dims dimensions."""

    print "Preprocessing the data using PCA..."
    (n, d) = X.shape;
    X = X - Math.tile(Math.mean(X, 0), (n, 1));
    (l, M) = Math.linalg.eig(Math.dot(X.T, X));
    Y = Math.dot(X, M[:,0:no_dims]);
    return Y;

据我所知，这比标量操作更有效，也意味着只有2N（其中N是行数）的数据加载到内存中（您需要加载一行X和一列X.T）。
不过，我不认为这是根本原因T-SNE当然也包含向量运算，例如，在计算成对距离时：

D = Math.add(Math.add(-2 * Math.dot(X, X.T), sum_X).T, sum_X);

或者，当计算P（高维）和Q（低维）时然而，在t-SNE中，您必须创建两个N X N矩阵来存储每个数据之间的成对距离，一个用于其原始高维空间表示，另一个用于其降维空间。
在计算梯度时，还必须创建另一个称为D的N X N矩阵，即PQ。
在我看来，这里的内存复杂性是瓶颈。t-sne需要3n^2的内存。这不可能适合本地内存，因此算法会遇到严重的缓存线未命中，需要转到全局内存来检索值。
这是对的吗如何向客户或合理的非技术人员解释为什么t-SNE比PCA慢？
共同作者的Python实现可以找到here。

最佳答案

T-SNE比PCA慢的主要原因是对于优化的准则没有解析解存在。相反，一个解决方案必须通过梯度下降迭代近似。
实际上，这意味着很多for循环至少在第129行循环的主迭代中是这样的，它最多可以运行max_iter=1000次此外，x2p函数使用for循环遍历所有数据点。
参考实现是为了可读性而优化的，而不是为了计算速度。作者还链接了一个optimised Torch implementation，这将大大加快计算速度。如果您想继续使用纯python，我建议您使用Scikit-Learn中的实现，它应该更快。

关于python - t-SNE的计算瓶颈是其内存复杂性吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45824724/