Structured nonnegative matrix factorization with applications to hidden Markov realization and clustering

In this paper, we study the structured nonnegative matrix factorization problem: given a square, nonnegative matrix P, decompose it as P=VAV⊤ with V and A nonnegative matrices and with the dimension of A as small as possible. We propose an iterative approach that minimizes the Kullback–Leibler divergence between P and VAV⊤ subject to the nonnegativity constraints on A and V with the dimension of A given. The approximate structured decomposition P≃VAV⊤ is closely related to the approximate symmetric decomposition P≃VV⊤. It is shown that the approach for finding an approximate structured decomposition can be adapted to solve the symmetric decomposition problem approximately. Finally, we apply the nonnegative decomposition VAV⊤ to the hidden Markov realization problem and to the clustering of data vectors based on their distance matrix.