Speaker
Description
The nonnegative rank of an $m \times n$ nonnegative matrix $N \geq 0$ is the smallest integer $r$ such that a nonnegative matrix factorization (NMF) $N=L R^T$ exists, where $L \in \mathbb{R}^{m \times r}, R \in \mathbb{R}^{n \times r}$ are both nonnegative [1]. Denoting the usual linear-algebraic rank by $\mathrm{rank} (N)$, clearly $r \geq \mathrm{rank}(N)$; the inequality may be strict when $\mathrm{rank}(N) \geq 3$. A related task is computing a rank-$r$ nonnegative matrix approximation (NMA) of $N$, i.e., a rank-$r$ NMF $N_r=LR^T$ that mimimizes $\| N - N_r \|_F$. Computing a rank-$r$ NMA is NP-hard if $r \geq 3$, and solvable in $O(mn)$ flops if $r=1$; as far as I know, it is an open question to determine whether the problem is NP-hard or not if $r=2$.
The borderline case of computing rank-$2$ NMAs is particularly interesting: it is more accessible to mathematical analysis because the two notions of rank coincide, and it can solved efficiently in some special cases, but it remains computationally challenging for a general input. Furthermore, it arises in many applications, including medical imaging, network analysis, and signal processing. Currently, some of the best general-purpose algorithms are based on Alternating Nonnegative Least Squares (ANLS) [1], though this method can be sensitive to initialization and may converge to suboptimal solutions.
In my talk, I will present a full parametrization of all possible NMFs of a rank-$2$ nonnegative matrix $N$. To my knowledge, this result was previously only available [2] in the special case where $N$ is completely positive, i.e., it admits a symmetric NMF of the form $N=LL^T \in \mathbb{R}^{n \times n}, \ L \geq 0$. (Note: when $n \leq 4$, complete positivity is equivalent to being both nonnegative and positive semidefinite, but this fails when $n \geq 5$.)
Based on this parametrization, I propose a simple algorithm to compute a possibly subomptimal rank-$2$ NMA to an arbitrary input $N \geq 0$. Being very inexpensive, this method can serve as an effective initialization strategy for ANLS. Extensive numerical experiments illustrate that this approach can improve both the efficiency and the accuracy of NMA computations via ANLS. For small input size, we also compare with the guaranteed exact NMA computed by an $O(2^{mn})$ algorithm based on algebraic geometry [3]; the outcome of this experiment suggests that even the probability that the output of ANLS is the correct answer (up to noise due to floating point computations) can be improved by using our newly proposed starting point.
The talk is based on joint research with Etna Lindy and Paul Van Dooren; a preprint is under preparation at the time when this abstract is being written.
References
- N. Gillis, Nonnegative Matrix Factorization, SIAM, 2020.
- V. Kalofolias and E. Gallopoulos, Computing symmetric non-
negative rank factorizations, Linear Algebra Appl. 436:421-435, 2012 - E. Lindy, Best nonnegative rank-2 matrix approximations, MSc Thesis, Aalto University, 2024.
