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$:
- $\min D_\phi(BC, A)$
- $\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.
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.
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