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))。

请问有人能解释一下这是怎么样的/为什么吗？

- GrowinMan

Answer 1

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

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

- Don Reba

---

很奇怪，这篇论文模糊地表述为“涉及寻找方向”，并没有直接说明这是算法的复杂度，只是强烈暗示了这一点。 - Don Reba

太好了！能否提供上述内容的参考资料，以便更容易引用？ - Ébe Isaac

协方差矩阵的复杂度可以直接从定义中推导出来。有一些更低复杂度的特征值分解算法，但它们的复杂度接近于O(p³)，这可能是该论文作者假定的复杂度。不过，除非答案来自Jon Skeet，否则您不应将Stack Overflow上的答案作为权威来源引用。 - Don Reba

Answer 2

假设您的数据集为$X \in \R^{nxp}$，其中n：样本数量，d：样本维数，您对$X^TX$的特征值分解感兴趣，这是PCA的主要计算成本。现在矩阵$X^TX \in \R^{pxp}$和$XX^T \in \R^{nxn}$具有相同的min(n, p)个非负特征值和特征向量。假设p小于n，则可以在$O(p^3)$的时间复杂度内解决特征值分解。如果p大于n（例如，在计算机视觉中，许多情况下，样本的维数-像素数-大于可用样本数），则可以在$O(n^3)$的时间内执行特征值分解。无论哪种情况，您都可以从另一个矩阵的特征值和特征向量获得一个矩阵的特征向量，并且可以在$O(min(p, n)^3)$的时间内完成。

$$X^TX = V \Lambda V^T$$

$$XX^T = U \Lambda U^T$$

$$U = XV\Lambda^{-1/2}$$

- michaelt

---

很遗憾，我们不支持LaTeX。我建议您使用反引号将其格式化为代码，或将您的LaTeX公式导出为png并上传。 - Ash

Answer 3

下面是michaelt提供的答案，包括原始的LaTeX代码和渲染后的PNG图片。

LaTeX 代码:

假设您的数据集为 $X \in R^{n\times p}$，其中 n: 样本数量，p: 样本维度，您对 $X^TX$ 的特征值分解感兴趣，这是 PCA 的主要计算成本。现在，矩阵 $X^TX \in \R^{p \times p}$ 和 $XX^T \in \R^{n\times n}$ 具有相同的 min(n, p) 个非负特征值和特征向量。假设 p 小于 n，您可以在 $O(p^3)$ 的时间复杂度内求解特征值分解。如果 p 大于 n（例如，在计算机视觉中，许多情况下样本的维数（像素数）大于可用样本数），则可以在 $O(n^3)$ 的时间内进行特征值分解。无论如何，您都可以从另一个矩阵的特征值和特征向量获取一个矩阵的特征向量，并且可以在 $O(min(p, n)^3)$ 的时间内完成该操作。

- Ebram

---

请将任何代码作为实际代码发布，图像没有用处。 - Azsgy