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

DOI10.1016/J.LAA.2008.03.010MaRDI QIDQ947603zbMATH OpenOpenAlexFDO

Authors Bart Vanluyten, Jan C. Willems, B. De Moor

Publication date 6 October 2008

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.laa.2008.03.010

zbMATH Keywords

clustershidden Markov realizationiterative algorithmKullback-Leibler divergencemultiplicative update formulasnonnegative matrix factorization

Mathematics Subject Classification ID

Factorization of matrices (15A23) Positive matrices and their generalizations; cones of matrices (15B48)

Review text

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.

Recommendations

• Quadratic nonnegative matrix factorization
• Nonnegative matrix factorization and I-divergence alternating minimization
• Non-negative matrix factorization with fixed row and column sums
• Nonnegative matrix factorization
• Computing a nonnegative matrix factorization -- provably

Cites work

• Approximation of stationary processes by hidden Markov models
• scientific article; zbMATH DE number 1933860 (Why is no real title available?)
• Learning the parts of objects by non-negative matrix factorization
• Nonnegative matrix factorization and I-divergence alternating minimization
• Nonnegative matrix factorization for spectral data analysis
• On reduced rank nonnegative matrix factorization for symmetric nonnegative matrices

Cited in

(6)

• Issues of stability and uniqueness of stochastic matrix factorization
• Approximation of nonnegative systems by moving averages of fixed order
• Low-rank nonnegative tensor approximation via alternating projections and sketching
• Nonnegative matrix factorization for interactive hidden Markov models
• Adaptive low-nonnegative-rank approximation for state aggregation of Markov chains
• Quadratic nonnegative matrix factorization

This page was built for publication: Structured nonnegative matrix factorization with applications to hidden Markov realization and clustering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q947603)