Spectral Observable Operator Algorithm (LEARN-HMM) for Learning Hidden Markov Models

A polynomial-time spectral method-of-moments algorithm (LEARN-HMM, introduced by Daniel Hsu, Sham M. Kakade, and Tong Zhang in 2009/2012) for learning the observable operator representation of an $m$-state, $n$-observation Hidden Markov Model (HMM) from marginal unigram, bigram, and trigram probabilities $(P_1, P_{2,1}, P_{3,x,1})$ without nonconvex Baum-Welch / EM local-optima susceptibility. Under the structural factorization $P_1 = O\vec{\pi}$, $P_{2,1} = O T \mathrm{diag}(\vec{\pi}) O^\top$, and $P_{3,x,1} = O A_x T \mathrm{diag}(\vec{\pi}) O^\top$ where $A_x = T\mathrm{diag}(O_{x,1},\dots,O_{x,m})$, any matrix $U\in\mathbb{R}^{n\times m}$ whose columns span $\mathrm{range}(O)$ (such as the top-$m$ left singular vectors of $P_{2,1}$) defines transformed $m$-dimensional observable parameters $\vec{b}_1 = U^\top P_1$, $\vec{b}_\infty = (P_{2,1}^\top U)^\dagger P_1$, and $B_x = (U^\top P_{3,x,1})(U^\top P_{2,1})^\dagger$ satisfying the exact similarity relation $B_x = (U^\top O) A_x (U^\top O)^{-1}$ (Lemma 3). Consequently, for every sequence length $t$, $\Pr[x_1,\dots,x_t] = \vec{b}_\infty^\top B_{x_t}\cdots B_{x_1} \vec{b}_1$ and internal state beliefs update recursively via $\vec{b}_{t+1} = B_{x_t}\vec{b}_t / (\vec{b}_\infty^\top B_{x_t}\vec{b}_t)$ with $L_1$ total-variation error $O(t\sqrt{m/(\sigma_m(O)^4 \sigma_m(T)^2 N)})$ independent of the observation alphabet size $n$ (Theorem 6).