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?
