Recovery Guarantee of Non-negative Matrix Factorization via Alternating Updates
Non-negative matrix factorization is a popular tool for decomposing data into feature and weight matrices under non-negativity constraints. It enjoys practical success but is poorly understood theoretically. This paper proposes an algorithm that alternates between decoding the weights and updating the features, and shows that assuming a generative model of the data, it provably recovers the groundtruth under fairly mild conditions. In particular, its only essential requirement on features is linear independence. Furthermore, the algorithm uses ReLU to exploit the non-negativity for decoding the weights, and thus can tolerate adversarial noise that can potentially be as large as the signal, and can tolerate unbiased noise much larger than the signal. The analysis relies on a carefully designed coupling between two potential functions, which we believe is of independent interest.
The paper shows recovery guarantees for non-negative matrix factorization under adversarial noise and unbiased noise. The algorithm proceeds by alternatively decoding and encoding, which correspond to updating weight matrix and updating feature matrix respectively. The analysis requires some conditions including linear independence among feature columns, independent sampling of weights for different features, balanced second moments of the weights and some good initialization. 
The recovery guarantee for NMF with mild conditions is very important for the machine learning community. This paper provides a solution under three main conditions as follows.  1) The conditions, A0 and A1, on the feature matrix are very mild. 2) The condition of the weights, A2, is also reasonable except for the independent requirement.  3) The condition for a good initialization, A3. However, it is unclear if this initialization can be achieved.  The proof technique seems to be novel, i.e., different from the popular techniques used for alternating minimization of matrix completion or the tensor methods. Therefore, it will probably be useful for the community. Therefore, I vote poster-level for novelty and oral-level for potential impact.   I have two concerns for this paper,  1. It seems that the theorems hold only with some (high) probability, which is not stated in the theorem. The reason is that the encoding step uses empirical expectation rather than the population expectation. Even if provided large enough samples as claimed on Line 643 and Line 647 in the appendix, as long as the number of samples is finite, the theorems will not hold almost surely without more assumptions on the weights.   2. If I understand Sec. 5 correctly (Sec. 5 is a little harder to read), the goal of this section is to provide solutions when the weights don't satisfy Assumption A2. However, according to Theorem 6, A^* is required to satisfy Assumption A0, which implies A^*D will not satisfy A0. Therefore, we can't apply Algorithm 1 afterwards to get A^* as claimed on Line 293. This will invalidate the whole Sec. 5.   Due to the above two concerns, I just vote poster-level for the technical quality.   The paper is not hard to understand, so I vote poster-level for clarity.   Some minor comments: 1. At the end of the paper Line 292-297, the authors mention how to initialize. However, it lacks reference and clear statement. 2. It will be better to provide some experimental results to verify the theoretical analysis, even if it is on synthetic data.  3. The lemma number is missing near Line 411 in the appendix.  4. Line 294, pontentially -> potentially  ========= To authors' feedback.  I have read the feedback. The feedback clarified my concerns.