Non-Negative Matrix Factorization Algorithm

Non-negative matrix factorization is an algorithm in linear algebra and multivariate data analysis that decomposes a matrix of non-negative values into two smaller matrices, also constrained to contain no negative values, whose product approximates the original. Because every value involved stays non-negative, the columns of the first resulting matrix can be read as a set of additive parts or features learned from the data and the second matrix as the coefficients describing how strongly each of those parts contributes to each original data point, tending to produce a more directly interpretable decomposition than techniques such as principal component analysis that allow negative values and therefore additive-and-subtractive combinations; the technique is especially suited to data that is naturally non-negative, such as word counts in documents, pixel intensities in images or the magnitudes in an audio spectrogram. The underlying idea traces back to a 1971 chemometrics technique called self modeling curve resolution and was independently developed as positive matrix factorization by Finnish researchers in the 1990s, but the technique became widely known under its current name after Daniel Lee and H. Sebastian Seung published simple, effective algorithms for computing it around 1999 to 2001, after which it spread into applications across astronomy, computer vision, document clustering, audio processing, recommender systems and bioinformatics.