PCA O的复杂程度如何(min(p ^ 3,n ^ 3))？

Question

我一直在阅读关于稀疏PCA的论文,其中包括:http: //stats.stanford.edu/~imj/WEBLIST/AsYetUnpub/sparse.pdf

并且它表明,如果你有n数据点,每个数据都用p功能表示,那么,PCA的复杂性就是O(min(p^3,n^3)).

有人可以解释一下/为什么？

Answer 1

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

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