Separable Nonnegative Matrix Factorization and Robust-Loner Recovery

Separable Nonnegative Matrix Factorization and Robust-Loner Recovery is a polynomial-time provable factorization framework introduced by Arora, Ge, Kannan, and Moitra (2012/2016) that circumvents the general NP-hardness of exact Nonnegative Matrix Factorization (NMF) M = A W (Theorem 3.1) by imposing the separability condition (Definition 5.1) on the first factor A in R_+^{n x r}. After normalizing the rows of M, A, and W to have unit l_1 norm, separability requires that for each latent basis index i in {1,...,r} there exists at least one canonical ('anchor') row j_i of A equal to the standard basis vector e_i^T, so that the r rows of W appear directly among the rows of M and every other row M^j = sum_{i=1}^r A_{j,i} W^i lies in the convex hull conv(W^1,...,W^r). When W is alpha-robust simplicial (each row W^i has l_1 distance at least alpha from conv({W^{i'} : i' != i}), Definition 5.6) and the observed matrix M' satisfies ||M'^j - M^j||_1 <= epsilon with 20 epsilon/alpha + 13 epsilon < alpha, the Robust-Loners algorithm identifies all r canonical rows via linear programming convex-hull tests at distance threshold d = 5 epsilon/alpha + 2 epsilon and clusters them to reconstruct A' W' within row-wise l_1 error 10 epsilon/alpha + 7 epsilon (Theorem 5.7).