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

The structured nonnegative matrix factorization problem is the following: Given a square real matrix \(P\) with nonnegative entries, find nonnegative matrices \(V\) and \(A\) such that \(P=VAV^{\top}\) with the dimension of \(A\) as small as possible. It appears that an exact solution to this problem is hard (non-polynomial), and so the authors consider the problem of approximating \(P\) by a product of the form \(VAV^{\top}\) where the dimension of \(A\) is prescribed and the error in the approximation is measured by the Kullback-Leibler divergence between the two matrices. The main part of this paper is the derivation of an iterative algorithm for finding increasingly good approximations, both in the general case and in the special case where \(P\) is symmetric and \(A=I\). They illustrate their algorithm by applying it to several problems: The hidden Markov realization problem with string probabilities of length 2, and the determination of clusters in a population of points in \(n\)-dimensional space.