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.