Lower bounds on nonnegative rank via nonnegative nuclear norms

Hamza Fawzi, Pablo A. ParriloMath. Program 2015 · DOI

Introduction

The factorization of a nonnegative matrix $A$ into two nonnegative factors $U$ and $V$ such that $A = UV$ is a fundamental problem in fields ranging from combinatorial optimization to communication complexity. The minimum number of columns in $U$ (or rows in $V$) required for such a factorization is the nonnegative rank, denoted $\text{rank}_+(A)$.

Despite its utility, computing the nonnegative rank is NP-hard. Consequently, researchers rely on lower bounds to estimate its value. Traditional lower-bounding techniques, such as the "fooling set" or "rectangle covering" methods, are primarily combinatorial. These methods focus on the sparsity pattern of the matrix—specifically, where the zeros are located. However, for dense or strictly positive matrices, these combinatorial bounds often collapse to trivial values, offering little insight into the true complexity of the factorization.

In this work, Hamza Fawzi and Pablo Parrilo introduce a new approach that utilizes the actual values of the matrix entries. By defining a "nonnegative nuclear norm," they provide a continuous and robust lower bound that remains effective even when the matrix lacks a specific sparsity structure.

The Nonnegative Nuclear Norm

The authors draw an elegant analogy to standard linear algebra. In the context of standard rank, the nuclear norm (the sum of singular values) serves as a convex lower bound. Fawzi and Parrilo propose a nonnegative nuclear norm, denoted $\nu_+(A)$, to serve a similar role for the nonnegative rank.

The definition of $\nu_+(A)$ is rooted in copositive programming, a branch of optimization that deals with matrices that are positive semidefinite on the nonnegative orthant. While copositive programming is generally NP-hard, it provides a powerful theoretical framework for capturing the constraints of nonnegativity in matrix factorizations.

To make the bound computationally tractable, the authors employ a hierarchy of approximations based on Sum-of-Squares (SoS) techniques. Specifically, they utilize a "level 0" relaxation, $\nu_+^{[0]}(A)$, which can be computed efficiently using Semidefinite Programming (SDP). This allows for the practical calculation of lower bounds on the nonnegative rank for matrices of moderate size.

Key Properties and Geometric Insights

A significant advantage of the nonnegative nuclear norm is its continuity. Unlike combinatorial bounds that can change drastically with the addition or removal of a single zero, $\nu_+(A)$ is a continuous function of the matrix entries. This robustness makes it particularly useful for bounding the approximate nonnegative rank—the rank required to approximate a matrix within a certain error margin.

The paper also highlights the deep connection between matrix factorization and polyhedral geometry. The nonnegative rank of a "slack matrix" of a polytope is equivalent to its extension complexity, which measures the number of linear inequalities needed to represent the polytope in a higher-dimensional space. The authors demonstrate that their bound is sensitive to these geometric properties.

Furthermore, the authors introduce a generalized version of the bound that incorporates diagonal scaling matrices ($P$ and $Q$). This ensures that the bound is invariant under row and column scaling, a property essential for many applications in data analysis and optimization.

Results and Performance

The effectiveness of the proposed bound is demonstrated across several challenging cases:

  • Hypercube Slack Matrices: The authors prove that their lower bound is tight for the slack matrix of an $n$-dimensional hypercube, yielding the correct value of $2n$. This provides a novel optimization-based proof for a classic result in polyhedral combinatorics.
  • Beating the Boolean Rank: In specific $4 \times 4$ matrices where the standard rank and nonnegative rank differ, the SDP-based bound correctly identifies a rank of 3, whereas the "rectangle covering number" (Boolean rank) only provides a lower bound of 2.
  • Robustness to Noise: For matrices where zeros are perturbed by small values ($\epsilon$), traditional combinatorial methods fail immediately. In contrast, the $\nu_+(A)$ bound remains stable, providing a strong lower bound that reflects the underlying structure of the matrix.

Limitations and Future Directions

While the nonnegative nuclear norm represents a significant advancement, certain challenges remain. The choice of optimal scaling matrices ($P$ and $Q$) to maximize the bound is not always straightforward. Additionally, for certain classes of matrices, such as "derangement matrices" (matrices with zeros on the diagonal and ones elsewhere), the bound remains relatively loose and does not scale with the matrix dimension.

Future research may explore extending these concepts to the positive semidefinite (psd) rank. However, the authors note that the psd rank lacks the "atomic" structure inherent to the nonnegative rank, making this extension a non-trivial mathematical challenge.

Conclusion

By shifting the focus from sparsity patterns to entry magnitudes and continuous optimization, Fawzi and Parrilo provide a powerful new tool for the study of nonnegative matrix factorization. Their work bridges the gap between combinatorial geometry and semidefinite programming, offering a robust framework for understanding the complexity of nonnegative data representations.

Summary updated

BibTeX
@article{fawzi2015lower,
  author = {Hamza Fawzi and Pablo A. Parrilo},
  title = {{Lower bounds on nonnegative rank via nonnegative nuclear norms}},
  journal = {Math. Program.},
  year = {2015},
  doi = {10.1007/s10107-014-0837-2},
}
Figure