4
$\begingroup$

The general Non-Negative Matrix Factorization (NMF) problem asks that for given a matrix $X \in \mathbb R^{m,n}_{0+}$ (with this notation meaning a matrix containing real numbers greater than or equal to 0 of size $[m,n]$) and a positive integer $k$ we find matrices $T$ and $P$ such that $T \in \mathbb R^{m,k}_{0+}$, $P \in \mathbb R^{n,k}_{0+}$, and $||X-TP^{T}||^{2}_{F}$ is minimized. There are several other variants of the cost function (dividing by the frobienius norm of $X$, using the Kullback-Leibler divergence instead of the frobenius norm, etc), but the general structure of the problem is unchanged.

This problem is known to be NP-Complete, though there are several approximation algorithms that have been analyzed and seem to have nice properties (Lee and Seung provide one of the more famous ones based on multiplicative updates). One method that is used commonly in industry that seems to be much faster in practice is modified version of the alternating least squares (ALS) algorithm. The obvious implementation of this solves the non-negative least squares problem (NNLS) at each iteration, ensuring that the intermediate solutions are viable solutions to the original problem. However, NNLS is expensive to compute so the algorithm is instead often implemented as such:

Given an initial estimate of $T \rightarrow T_{apx} \in \mathbb R^{m,k}_{0+}$, \begin{eqnarray*} P_{apx} &=& (T_{apx} \backslash X)^{T}\\ \forall p \in P_{apx} &\lt& 0 \rightarrow p = 0\\ T_{apx} &=& X / P_{apx}^{T}\\ \forall t \in T_{apx} &\lt& 0 \rightarrow t = 0\\ \end{eqnarray*} Repeat until convergence (the notation $X = A \backslash B$ stands for finding the general least squares solution to the equation $AX = B$).

I believe I have proven that if this algorithm ever finds an intermediate value of either $T$ or $P$ such that the general least squares solution of $X=TP^{T}$ for the other matrix produces a non-negative matrix then the algorithm is guaranteed to converge to a stationary point that is a valid solution to the NMF problem. My question relates to how to prove that the algorithm will eventually find such an intermediate point (or that such a point does not exist).

As the initial estimate of $T$ is already in the non-negative orthant, there are two cases to address for the first iteration of the algorithm. If the resulting solution to $P_{apx} = (T_{apx} \backslash X)^{T}$ contains no non-negative values then we are guaranteed convergence (assume my aforementioned proof is correct for the sake of this question). If the resulting $P_{apx}$ contains any negative values then we shift the general least squares solution to the closest solution in the non-negative orthant. At this point there appear to be three possible outcomes:

1) $P_{apx}$ is now a stationary point to the NMF problem.

2) $P_{apx}$ is not a stationary point to the NMF problem, but $T_{apx} = X / P_{apx}^{T}$ has no non-negative values.

3) $P_{apx}$ is not a stationary point to the NMF problem, and $T_{apx} = X / P_{apx}^{T}$ has negative values.

In cases 1 and 2 we are done (case 1 is obvious, case 2 is guaranteed to converge given the aforementioned assumed proof), so case 3 is the interesting one. If the closest local minimum to the current value of $P_{apx}$ contains negative numbers then I would anticipate the general least squares solutions to consistently contain negatives and any convergence will be to a region on the "edge" of the non-negative orthant. The questions I have are is this assertion correct, and if so, what would be necessary to prove? Additionally, would such a proof guarantee convergence to a stationary point in general (when combined with the previous analysis), or would it still leave open the possibility of oscillation between disparate regions on the edge of the non-negative orthant?

$\endgroup$
1
$\begingroup$

I have not given full thought to whether the algorithm will converge under the hypotheses placed on the intermediate values. However, it is worth noting here (perhaps the OP is already aware of this) that the ALS method with truncation (i.e., by setting intermediate negative entries to 0) can easily oscillate or be substantially inferior to A-NNLS.

See this old paper (disclosure: I am a co-author) that explores exactly this failure of ALS.

On a different note, if scalable solution of NMF is what you are after, then you may want to use stochastic matrix factorization methods, for instance, as implemented in the SPAMS toolbox.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I appreciate the link to your past paper. In my experience, the difference in speed between ALS with truncation and A-NNLS has been substantial (an order of magnitude or greater on optimized C code) with little to no improvement in performance. Regardless, I am investigating the convergence of this algorithm specifically, so my question remains unresolved. $\endgroup$ – nick.schachter Jul 29 '17 at 16:04
  • $\begingroup$ But you do see that ALS can oscillate, right? $\endgroup$ – Suvrit Jul 29 '17 at 16:09
  • $\begingroup$ It's somewhat unclear to me whether or not this oscillation is because the solution is not unique (as solutions to the NMF problem are subject to scaling for obvious reasons) or because the algorithm is actually getting stuck on values that are not valid solutions to the original problem. I cannot read parts of your paper because I do not have access, so perhaps my questions are addressed therein. $\endgroup$ – nick.schachter Jul 30 '17 at 3:43
  • $\begingroup$ You should look at the explicit counterexamples in Sec 2.1 of my linked paper. I've now added a link to a version of the paper available from my website: suvrit.de/papers/kim_sra_nmf.pdf $\endgroup$ – Suvrit Jul 30 '17 at 12:09
  • $\begingroup$ The example shown in section 2.1 doesn't seem to show oscillation, only that on a single iteration the objective function may be increased. It does not show that further iterations will not reach a local minimum. For what it's worth, I was aware that the ALS algorithm with truncation can have intermediate solutions that are worse than prior steps wrt the objective function, the overriding question seems to be showing whether or not this can be overcome. $\endgroup$ – nick.schachter Jul 30 '17 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.