我从主教的书中学习概率pca，那里提供了一种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']]
第一部分是Dx1矩阵乘以1xM的N次重复（求和）运算，因此复杂度为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
关于machine-learning - 如何确定概率PCA EM算法的时间复杂度？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37119428/