  We propose a new variant of nonnegative matrix factorization (NMF), combining
separability and sparsity assumptions. Separability requires that the columns
of the first NMF factor are equal to columns of the input matrix, while
sparsity requires that the columns of the second NMF factor are sparse. We call
this variant sparse separable NMF (SSNMF), which we prove to be NP-complete, as
opposed to separable NMF which can be solved in polynomial time. The main
motivation to consider this new model is to handle underdetermined blind source
separation problems, such as multispectral image unmixing. We introduce an
algorithm to solve SSNMF, based on the successive nonnegative projection
algorithm (SNPA, an effective algorithm for separable NMF), and an exact sparse
nonnegative least squares solver. We prove that, in noiseless settings and
under mild assumptions, our algorithm recovers the true underlying sources.
This is illustrated by experiments on synthetic data sets and the unmixing of a
multispectral image.
