A sharp NMF result with applications in network modeling

Given an n × n non-negative rank-K matrix Ω where m eigenvalues are negative, when can we write Ω = ZPZ (cid:48) for non-negative matrices Z ∈ R n,K and P ∈ R K,K ? While most existing works focused on the case of m = 0 , our primary interest is on the case of general m . With new proof ideas, we present sharp results on when the NMF problem is solvable, which significantly extend existing results on this topic. The NMF problem is partially motivated by applications in network modeling. For a network with K communities, rank-K models are especially popular. The Degree-Corrected Mixed-Membership (DCMM) model is a recent rank-K model which is especially useful and interpretable in practice. To enjoy such properties, it is of interest to study when a rank-K model can be rewritten as a DCMM model. Using our NMF results, we show that for a rank-K model in the most interesting parameter ranges, we can always rewrite it as a DCMM model.