Convex Algorithms for Nonnegative Matrix Factorization

V. Krishnamurthy, Alexandre d’AspremontarXiv 2012 · DOI · arXiv

Abstract: We derive approximation algorithms for the nonnegative matrix factorization problem, i.e. the problem of factorizing a matrix as the product of two matrices with nonnegative coefficients. We form convex approximations of this problem which can be solved efficiently and test our algorithms on some classic numerical examples.

Introduction

Nonnegative Matrix Factorization (NMF) is a fundamental tool in modern data science, widely applied in fields ranging from bioinformatics to natural language processing. The objective is to decompose a data matrix $A$ into two smaller, non-negative matrices $U$ and $V$ such that $A \approx UV^T$. The non-negativity constraint is essential for ensuring that the resulting factors are "parts-based" and physically interpretable, such as gene expression levels or word frequencies.

Despite its utility, NMF is notoriously difficult to solve. The standard formulation is non-convex and NP-hard. Most existing algorithms, such as Multiplicative Updates or Alternating Least Squares, are descent methods that frequently converge to local minima. Consequently, different random initializations can lead to inconsistent results, none of which may represent the global optimum. This paper by Krishnamurthy and d’Aspremont introduces a novel approach by reframing NMF through the lens of convex optimization.

Methodology: A Convex Restriction

The core innovation of this work involves a mathematical detour through the theory of completely positive (CP) matrices. A matrix $X$ is defined as completely positive if it can be represented as $UU^T$ for some non-negative matrix $U$. While determining if a matrix is CP is generally NP-hard, the authors leverage a powerful result from matrix theory: if a matrix $X$ is positive semidefinite (PSD), then its Hadamard exponential (the element-wise exponential) is guaranteed to be completely positive.

By substituting the target matrix with this exponential form, the authors transform the traditionally non-convex NMF problem into a convex restriction. Instead of searching for $U$ and $V$ directly in a non-convex landscape, they optimize over a matrix $X$ in a well-behaved convex space. This reformulated problem is solved using a Projected Gradient Method, a first-order algorithm that iteratively approaches the solution and projects the result back into the feasible set of matrices.

Experimental Setup

The authors validated their approach using numerical simulations focused on graph partitioning—a classic application of symmetric NMF. The datasets included:

  • Synthetic Random Graphs: Graphs generated with specific "block sparsity" patterns to simulate latent clusters.
  • Adjacency Matrices: These matrices were used to test the algorithm's ability to identify and group nodes within clusters.
  • Benchmarks: The results were compared against Spectral Clustering, the industry-standard method for graph partitioning.

Results and Discussion

The convex NMF algorithm demonstrated high stability and accuracy. Unlike traditional methods, the convex formulation ensures that the algorithm consistently converges to the same global solution for the approximate problem, regardless of the starting point.

Comparison between the original adjacency matrix and the clustered permutation found by the NMF algorithm.

As shown in the figure above, the algorithm successfully recovers the underlying block structure of sparse adjacency matrices. By finding the optimal permutation, the latent clusters become clearly visible as dense blocks along the diagonal.

Numerical Analysis

Quantitative analysis revealed that the NMF approach consistently matched or outperformed spectral clustering, particularly as the graphs became more "messy" or bipartite. Furthermore, the computational complexity of the method proved manageable for medium-scale problems.

Performance metrics and iteration scaling for the proposed convex NMF algorithm.

The performance plot (left) illustrates how accuracy improves as the signal-to-noise ratio (represented by $\beta - \alpha$) increases. The iteration plot (right) shows that the number of iterations required for convergence scales predictably with the matrix size $n$, following a polynomial trend on a log-log scale. Additionally, because the problem is convex, the authors could calculate a "duality gap," providing a mathematical certificate of how close the current solution is to the theoretical global optimum.

Conclusion and Limitations

This work provides a robust framework for making NMF predictable and globally solvable through convex approximation. While the symmetric case ($A = UU^T$) is highly effective for tasks like graph partitioning, the non-symmetric case remains a challenge. For rectangular matrices, the problem must be embedded into a larger block matrix, which increases computational overhead. Future research is needed to optimize the numerical efficiency of this convex representation for general, non-symmetric NMF applications.

Summary updated

Abstract

We derive approximation algorithms for the nonnegative matrix factorization problem, i.e. the problem of factorizing a matrix as the product of two matrices with nonnegative coefficients. We form convex approximations of this problem which can be solved efficiently and test our algorithms on some classic numerical examples.
BibTeX
@misc{krishnamurthy2012convex,
  author = {V. Krishnamurthy and Alexandre d’Aspremont},
  title = {{Convex Algorithms for Nonnegative Matrix Factorization}},
  year = {2012},
  eprint = {1207.0318},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1207.0318},
}
Figure