Generalized Nonnegative Matrix Approximations with Bregman Divergences

Inderjit S. Dhillon, Suvrit SraNeurIPS 2005 · OpenReview

This foundational paper by Inderjit Dhillon and Suvrit Sra generalizes the popular Nonnegative Matrix Factorization (NMF) framework to a much broader class of distance measures, providing a unified algorithmic approach for data analysis.

TL;DR

The authors extend Nonnegative Matrix Approximation (NNMA) from specific cases—like Euclidean distance and Kullback-Leibler divergence—to the entire family of Bregman divergences. They provide a generalized framework for deriving efficient multiplicative update algorithms capable of handling various noise models, constraints, and non-linear relationships.

The Problem with Standard NNMA

Nonnegative Matrix Approximation (NNMA) is a powerful tool for dimensionality reduction. By forcing basis vectors and coefficients to be non-negative, it leads to "parts-based" representations (e.g., representing a face as a collection of localized features like eyes and noses, rather than abstract, holistic eigenfaces).

Prior to this work, most NNMA research focused on two specific distance measures: the Frobenius norm (squared Euclidean distance) and Kullback-Leibler (KL) divergence. However, real-world data often contains noise distributions that do not fit these standard models. Furthermore, researchers lacked a principled, unified way to incorporate additional constraints (like sparsity or linear inequalities) or non-linear "link" functions into the factorization process.

A Generalized Method: Bregman Divergences

The core contribution of this paper is the shift from specific, hardcoded loss functions to Bregman divergences. A Bregman divergence $D_\phi(x, y)$ is generated by a strictly convex function $\phi$. By choosing different $\phi$ functions, one can recover the squared loss, KL-divergence, Itakura-Saito distance, and many others.

Because Bregman divergences are generally asymmetric, the authors tackle two distinct versions of the approximation problem for a matrix $A$ and its factors $B$ and $C$:

  1. $\min D_\phi(BC, A)$
  2. $\min D_\phi(A, BC)$

To solve these, they employ two main optimization strategies:

  • Auxiliary Functions: For the first problem, they use a technique similar to the Expectation-Maximization (EM) algorithm to construct a "surrogate" function that is easier to minimize. They prove that their iterative updates lead to a monotonic decrease in the objective function.
  • KKT Conditions: For the second problem, they derive updates based on the Karush-Kuhn-Tucker (KKT) optimality conditions. This results in elegant multiplicative update rules that are easy to implement and computationally efficient.
  • Penalty & Link Functions: The framework naturally accommodates penalty terms $\alpha(B)$ and $\beta(C)$ to enforce constraints, as well as "link" functions $h(BC)$ to model non-linear relationships between the latent factors and the observed data.
Table summarizing how various NNMA algorithms are special cases of the proposed generalized Bregman divergence framework.

Key Insights

  • Unification of NMF: As shown in the table above, the famous multiplicative updates by Lee and Seung (2001), along with several other variants, are revealed to be specific instances of this broader Bregman framework.
  • Noise-Loss Duality: The authors highlight that choosing a Bregman divergence is mathematically equivalent to assuming a specific noise distribution from the exponential family. For instance, Gaussian noise corresponds to the Frobenius norm, while Poisson noise corresponds to KL-divergence.
  • Multifactor NNMA: The framework is flexible enough to extend beyond two factors ($A \approx BC$) to multiple factors ($A \approx B_1 B_2 \dots B_R$), which is particularly useful for complex tasks like co-clustering.
  • The "Multiplicative" Advantage: By utilizing multiplicative updates rather than additive gradient steps, the algorithms naturally maintain the non-negativity constraint without requiring expensive projection steps in every iteration.

Empirical Convergence and Results

As a theoretical and algorithmic paper, the authors primarily use synthetic data to demonstrate the convergence properties of their proposed algorithms. They test the algorithms on random non-negative matrices (e.g., approximating a $20 \times 8$ matrix $A$ with a $20 \times 4$ matrix $B$ and a $4 \times 8$ matrix $C$).

The paper provides "master equations" that allow researchers to plug in any convex function $\phi$ and automatically generate a valid NMF algorithm.

Convergence plots for three different objective functions showing rapid monotonic decrease.

As demonstrated in the convergence plots above, the algorithms decrease the objective function consistently and rapidly. For various divergences—including the PMF objective, $\phi(x) = -\log x$, and $\phi(x) = x \log x - x$—the algorithms typically converge within 20–40 iterations. Furthermore, the authors derived updates for weighted NNMA that are significantly simpler than previous state-of-the-art methods.

Limitations and Future Work

  • Local Optima: Like most NMF methods, the objective function is non-convex in $B$ and $C$ simultaneously. Consequently, the algorithms are only guaranteed to find local minima, and the final factorization can depend heavily on the initial starting matrices.
  • Formal Convergence Proofs: While the authors rigorously prove monotonic decrease for the auxiliary function approach, they note that a formal convergence proof for the KKT-based updates in the general case remained an open problem at the time of publication, despite strong empirical evidence.
  • Automated Divergence Selection: The paper thoroughly explains how to use different divergences, but it leaves the question of which divergence is optimal for a specific, real-world dataset as a subject for future empirical research.

Summary updated

Abstract

Nonnegative matrix approximation (NNMA) is a recent technique for dimensionality reduction and data analysis that yields a parts based, sparse nonnegative representation for nonnegative input data. NNMA has found a wide variety of applications, including text analysis, document clustering, face/image recognition, language modeling, speech processing and many others. Despite these numerous applications, the algorithmic development for computing the NNMA factors has been relatively deficient. This paper makes algorithmic progress by modeling and solving (using multiplicative updates) new generalized NNMA problems that minimize Bregman divergences between the input matrix and its lowrank approximation. The multiplicative update formulae in the pioneering work by Lee and Seung [11] arise as a special case of our algorithms. In addition, the paper shows how to use penalty functions for incorporating constraints other than nonnegativity into the problem. Further, some interesting extensions to the use of "link" functions for modeling nonlinear relationships are also discussed.
BibTeX
@inproceedings{dhillon2005generalized,
  author = {Inderjit S. Dhillon and Suvrit Sra},
  title = {{Generalized Nonnegative Matrix Approximations with Bregman Divergences}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2005},
  url = {https://openreview.net/forum?id=ryEak_WdbS},
}
Figure