如何确定概率PCA的EM算法的时间复杂度？
How to determine time complexity of EM algorithm of probabilistic PCA?
我正在研究 bishop 书中的概率 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<=D<=N因此 O(NMD)
我正在研究 bishop 书中的概率 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<=D<=N因此 O(NMD)