Как определить временную сложность алгоритма ЭМ вероятностного СПС?

Question

Я изучал вероятностную книгу из книги епископа, там есть ЭМ-алго, чтобы вычислить основное подпространство.

Здесь М представляет собой матрицу MxM, W является матрицей DXM и (х - х) вектор dx1 матрица. Позже в книге есть утверждение о сложности времени: «Вместо этого наиболее требовательные к вычислению шаги - это те, которые связаны с суммами над набором данных, которые являются O (NDM)».

Мне было интересно, может ли кто-нибудь помочь мне понять временную сложность алгоритма. Заранее спасибо.

Answer 1

Пойдемте один на один

1. E [гп] = M^-1 W»(хп - х)

   • M^-1 может быть предварительно вычисленное, таким образом, вы делаете не платите O (M^3) каждый раз, когда вам нужен этот вид стоимости, а скорее одна стоимость O (M^3) в конце
   • , несмотря на то, что это умножение матриц размеров MxM * MxD * Dx1, которое равно O (M^2D)
   • результат имеет размер Mx1

2. Е [гп гп '] = сигма^2 M^-1 + E [Zn] E [Zn]'

   • сигма 2^М^-1 только умножение на постоянной линейной, таким образом, в размере матрицы, о (М^2)
   • вторая операция является внешним продуктом MX1 и 1xM векторов, таким образом, привести это MxM снова, и занимает O (M^2) слишком
   • результат М х М матрица

3. 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 х М, которая представляет собой О (ДМ^2), и снова приводит к D х М матрицы

4. сигма^2new = 1/ND СУММ [|| х-х ||^2 - 2E [гп] «Wnew» (х-х) + Тр (Е [гп гп '] 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 (НПРО) + O (M^2D) + O (M^2N), и я предположим, что существует предположение, что M < = D < = N, таким образом, O (NMD)