Structured nonnegative matrix factorization with applications to hidden Markov realization and clustering
type: Item
instance of: scholarly article
title: Structured nonnegative matrix factorization with applications to hidden Markov realization and clustering
zbMATH Open document ID: 1154.15017
author: Bart Vanluyten
author: Jan C. Willems
author: B. De Moor
published in: Linear Algebra and its Applications
publication date: 2008-10-06T00:00:00Z
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.
reviewed by: John D. Dixon
Mathematics Subject Classification ID: 15A23
Mathematics Subject Classification ID: 15B48
zbMATH DE Number: 5349121
zbMATH Keywords: nonnegative matrix factorization
zbMATH Keywords: Kullback-Leibler divergence
zbMATH Keywords: multiplicative update formulas
zbMATH Keywords: iterative algorithm
zbMATH Keywords: hidden Markov realization
zbMATH Keywords: clusters
MaRDI profile type: Publication
full work available at URL: j.laa.2008.03.010
OpenAlex ID: W2004778949
cites work: Q4405832
cites work: On reduced rank nonnegative matrix factorization for symmetric nonnegative matrices
cites work: Approximation of stationary processes by hidden Markov models
cites work: Nonnegative matrix factorization and I-divergence alternating minimization
cites work: Learning the parts of objects by non-negative matrix factorization
cites work: Nonnegative matrix factorization for spectral data analysis
DOI: 10.1016/J.LAA.2008.03.010
description: scientific article; zbMATH DE number 5349121