An optimal pairwise merge algorithm improves the quality and consistency of nonnegative matrix factorization

Non-negative matrix factorization (NMF) is widely used for dimensionality reduction of large datasets and is an important feature extraction technique for source separation. However, NMF algorithms may converge to poor local minima, or to one of several minima with similar objective value but differing feature parametrizations. Here we show that some of these weaknesses may be mitigated by performing NMF in a higher-dimensional feature space and then iteratively combining components with an efficient and analytically solvable pairwise merge strategy. Both theoretical and experimental results demonstrate that our method allows optimizers to escape poor minima and achieve greater consistency of the solutions. Despite these extra steps, our approach exhibits computational performance similar to established methods by reducing the occurrence of "plateau phenomena" near saddle points. Our method is compatible with a variety of standard NMF algorithms and exhibits an average performance that exceeds all algorithms tested. Thus, this can be recommended as a preferred approach for most applications of NMF.