Orthogonal Tensor Decomposition and Robust Tensor Power Method for Latent Variable Models

A spectral and tensor-algebraic method-of-moments framework (introduced by Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M. Kakade, and Matus Telgarsky in 2014) for polynomial-time globally consistent parameter estimation in multi-view exchangeable latent variable models, spherical Gaussian mixtures, Independent Component Analysis (ICA), Latent Dirichlet Allocation (LDA), and Hidden Markov Models (HMMs). Given modified low-order empirical moments $M_2 = \sum_{i=1}^k \omega_i \mu_i \otimes \mu_i$ and $M_3 = \sum_{i=1}^k \omega_i \mu_i \otimes \mu_i \otimes \mu_i$ with linearly independent components $\{\mu_1,\dots,\mu_k\}$, whitening $M_2$ by $W = U D^{-1/2}\in\mathbb{R}^{d\times k}$ ($W^\top M_2 W = I_k$) transforms $M_3$ into an orthogonally decomposable symmetric tensor $T = M_3(W,W,W) = \sum_{i=1}^k \tilde{\omega}_i v_i^{\otimes 3}\in\mathbb{R}^{k\times k\times k}$ where $\tilde{\omega}_i = \omega_i^{-1/2}$ and $v_i = \omega_i^{1/2} W^\top \mu_i$ form an orthonormal basis (Section 4.3.1, Equations 4.3–4.4). Unlike matrices, orthogonal symmetric tensors of order $p \ge 3$ have unique stable eigendecompositions $T(I,v_i,v_i) = \tilde{\omega}_i v_i$ up to signs and permutations (Theorem 4.1). For noisy empirical tensors $\hat{T} = T + E$ with operator-norm perturbation $\|E\| \le \epsilon \le c\lambda_{\min}/k$, the *Robust Tensor Power Method* (Algorithm 1) runs $L = \mathrm{poly}(k)\log(1/\eta)$ random spherical initializations $\theta_0^{(0)}\sim\mathcal{S}^{k-1}$ for $N = O(\log k + \log\log(\lambda_{\max}/\epsilon))$ power updates $\theta_{t+1} = \hat{T}(I,\theta_t,\theta_t)/\|\hat{T}(I,\theta_t,\theta_t)\|_2$, selects the candidate maximizing $\hat{T}(\theta_N,\theta_N,\theta_N)$, performs $N$ refinement steps, and deflates $\hat{T} \leftarrow \hat{T} - \hat{\lambda}\hat{v}^{\otimes 3}$, recovering all $(\tilde{\omega}_i,v_i)$ with $\|\hat{v}_i - v_i\|_2 \le 8\epsilon/\tilde{\omega}_i$ and $|\hat{\lambda}_i - \tilde{\omega}_i| \le 5\epsilon$ (Theorem 5.1) due to quadratic contraction of the second-largest projection ratio in Lemma 5.1.