我在研究Bishop的书中的概率主成分分析，发现其中提供了一种EM算法来计算主子空间。
这里M是一个MxM矩阵，W是一个DxM矩阵，(xn − x)是一个Dx1的向量。在书的后面，有关于时间复杂度的声明：“相反，最耗费计算资源的步骤是那些涉及数据集总和的步骤，其复杂度为O(NDM)。”
我想知道是否有人能帮助我理解这个算法的时间复杂度。先谢谢了。
回答：
我们一个一个来看
-
E[zn] = M^-1 W’ (xn – x)
- M^-1可以预先计算，因此每次需要这种值时，你不需要支付O(M^3)的成本，而是在最后一次性支付O(M^3)的成本
- 尽管如此，它是大小为MxM * MxD * Dx1的矩阵相乘，其复杂度为O(M^2D)
- 结果的大小为Mx1
-
E[zn zn’] = sigma^2 M^-1 + E[zn]E[zn]’
- sigma^2 M^-1只是与常数相乘，因此在矩阵大小上是线性的，复杂度为O(M^2)
- 第二个操作是Mx1和1xM向量的外积，因此结果再次是MxM，并且也需要O(M^2)
- 结果是M x M矩阵
-
Wnew = [SUM (xn-x) E[zn]’][SUM E[zn zn’]]
- 第一部分是N次重复的（求和）操作，将Dx1矩阵乘以1xM，因此复杂度为O(NDM)；结果的大小为D x M
- 第二部分再次是N个元素的总和，每个元素是一个M x M矩阵，因此总共为O(NM^2)
- 最后我们计算D x M和M x M的乘积，其复杂度为O(DM^2)，再次得到D x M矩阵
-
sigma^2new = 1/ND SUM[||xn-x||^2 – 2E[zn]’Wnew'(xn-x) + Tr(E[zn zn’]Wnew’Wnew)]
- 我们再次总共求和N次，这次是3个元素的总和 – 第一部分只是一个范数，因此我们以O(D)的复杂度计算（在向量大小上是线性的），第二项是1 x M、M x D和D x 1的乘积，导致每次迭代的复杂度为O(MD)，因此总共为O(NMD)，最后一部分再次涉及到大小为M x M、M x D、D x M的三个矩阵的乘积，导致O(M^3D) (*N)，但你只需要迹，并且可以预计算Wnew’Wnew，因此这部分只是MxM乘以MxM矩阵的迹，导致O(M^2) (*N)
总的来说，你得到O(M^3) + O(NMD) + O(M^2D) + O(M^2N)，我假设有一个假设，即M<=D<=N，因此为O(NMD)
