Low-dimensional polytope approximation and its applications to nonnegative matrix factorization

Moody T. Chu, Matthew M. Lin

Research output: Contribution to journalArticle

24 Citations (Scopus)


In this study, nonnegative matrix factorization is recast as the problem of approximating a polytope on the probability simplex by another polytope with fewer facets. Working on the probability simplex has the advantage that data are limited to a compact set with a known boundary, making it easier to trace the approximation procedure. In particular, the supporting hyperplane that separates a point from a disjoint polytope, a fact asserted by the Hahn-Banach theorem, can be calculated in finitely many steps. This approach leads to a convenient way of computing the proximity map which, in contrast to most existing algorithms where only an approximate map is used, finds the unique and global minimum per iteration. This paper sets up a theoretical framework, outlines a numerical algorithm, and suggests an effective implementation. Testing results strongly evidence that this approach obtains a better low rank nonnegative matrix approximation in fewer steps than conventional methods.

Original languageEnglish
Pages (from-to)1131-1155
Number of pages25
JournalSIAM Journal on Scientific Computing
Issue number3
Publication statusPublished - 2007 Dec 1


All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Applied Mathematics

Cite this