PCA O(min(p ^ 3，n ^ 3))的复杂度如何? [英] How is the complexity of PCA O(min(p^3,n^3))?

问题描述

我一直在阅读有关稀疏PCA的论文，该论文是: http://stats.stanford.edu/~imj/WEBLIST/AsYetUnpub/sparse .pdf

I've been reading a paper on Sparse PCA, which is: http://stats.stanford.edu/~imj/WEBLIST/AsYetUnpub/sparse.pdf

它指出，如果您有n个数据点，每个数据点都用p个特征表示，则PCA的复杂度为O(min(p^3,n^3)).

And it states that, if you have n data points, each represented with p features, then, the complexity of PCA is O(min(p^3,n^3)).

有人可以解释为什么/为什么吗?

Can someone please explain how/why?

推荐答案

协方差矩阵计算为O(p ² n);其特征值分解为O(p ³ ).因此，PCA的复杂度为O(p ² n + p ³ ).

Covariance matrix computation is O(p²n); its eigen-value decomposition is O(p³). So, the complexity of PCA is O(p²n+p³).

O(min(p ³ ，n ³ ))意味着您可以在固定时间内分析任意大小的二维数据集，这显然是错误的

O(min(p³,n³)) would imply that you could analyze a two-dimensional dataset of any size in fixed time, which is patently false.

这篇关于PCA O(min(p ^ 3，n ^ 3))的复杂度如何?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！