Nonnegative Matrix Approximation: Algorithms and Applications

Suvrit Sra, Inderjit Dhillon

Abstract:   Low dimensional data representations are crucial to numerous applications in machine learning, statistics, and signal processing. Nonnegative matrix approximation (NNMA) is a method for dimensionality reduction that respects the nonnegativity of the input data while constructing a low-dimensional approximation. NNMA has been used in a multitude of applications, though without commensurate theoretical development. In this report we describe generic methods for minimizing generalized divergences between the input and its low rank approximant. Some of our general methods are even extensible to arbitrary convex penalties. Our methods yield efficient multiplicative iterative schemes for solving the proposed problems. We also consider interesting extensions such as the use of penalty functions, non-linear relationships via “link” functions, weighted errors, and multi-factor approximations. We present some experiments as an illustration of our algorithms. For completeness, the report also includes a brief literature survey of the various algorithms and the applications of NNMA.

Download: pdf


  • Nonnegative Matrix Approximation: Algorithms and Applications (pdf, software)
    S. Sra, I. Dhillon.
    University of Texas Computer Science Technical Report (UTCS Technical Report) TR-06-27, June 2006.