Anchor Words and RecoverL2 Topic-Word Matrix Factorization

Anchor Words and RecoverL2 Topic-Word Matrix Factorization is a practical polynomial-time provable topic modeling pipeline introduced by Arora, Ge, Halpern, Mimno, Moitra, Sontag, Wu, and Zhu (2013) for learning the V x K word-topic matrix A and K x K topic-topic moment matrix R = E[W W^T] from the empirical word-word co-occurrence matrix Q = A R A^T estimated via the unbiased single-document second-order statistic Q = (1/M) sum_d (tilde{H}_d tilde{H}_d^T - hat{H}_d). Under the p-separability assumption that each topic k in {1,...,K} has an anchor word s_k with A_{s_k,k} >= p and A_{s_k,k'} = 0 for all k' != k, the row-normalized co-occurrence rows Q_bar_i satisfy Q_bar_i = sum_{k=1}^K C_{i,k} Q_bar_{s_k} where C_{i,k} = P(z = k | w = i) lies in the K-simplex Delta^K. The pipeline replaces O(V) linear programs with (1) FastAnchorWords (Algorithm 4), a combinatorial furthest-point orthogonal-subspace projection / simplex-volume maximization routine that greedily selects K anchor rows of Q_bar in O(V^2 + V K / epsilon^2) operations (Theorem 4.2), and (2) RecoverL2 (Algorithms 3 and 5), which solves the K x K quadratic program min_{C_i in Delta^K} ||Q_bar_i - sum_k C_{i,k} Q_bar_{s_k}||_2^2 via Exponentiated Gradient for each word i and applies Bayes' rule A_{i,k} propto C_{i,k} (Q 1)_i to recover A without matrix inversion.