Non-negative matrix factorization (NMF or NNMF), also non-negative matrix approximation is a group of algorithms in multivariate analysis and linear algebra where a matrix is factorized into (usually) two matrices and , with the property that all three matrices have no negative elements. This non-negativity makes the resulting matrices easier to inspect. Also, in applications such as processing of audio spectrograms or muscular activity, non-negativity is inherent to the data being considered. Since the problem is not exactly solvable in general, it is commonly approximated numerically.
NMF finds applications in such fields as astronomy, computer vision, document clustering, missing data imputation, chemometrics, audio signal processing, recommender systems, and bioinformatics.
History In chemometrics non-negative matrix factorization has a long history under the name "self modeling curve resolution". In this framework the vectors in the right matrix are continuous curves rather than discrete vectors. Also early work on non-negative matrix factorizations was performed by a Finnish group of researchers in the 1990s under the name positive matrix factorization. It became more widely known as non-negative matrix factorization after Lee and Seung investigated the properties of the algorithm and published some simple and useful algorithms for two types of factorizations.
Background Let matrix be the product of the matrices and ,
Matrix multiplication can be implemented as computing the column vectors of as linear combinations of the column vectors in using coefficients supplied by columns of . That is, each column of can be computed as follows:
where is the -th column vector of the product matrix and is the -th column vector of the matrix .
When multiplying matrices, the dimensions of the factor matrices may be significantly lower than those of the product matrix and it is this property that forms the basis of NMF. NMF generates factors with significantly reduced dimensions compared to the original matrix. For example, if is an matrix, is an matrix, and is a matrix then can be significantly less than both and .
Here is an example based on a text-mining application: Let the input matrix (the matrix to be factored) be with 10000 rows and 500 columns where words are in rows and documents are in columns. That is, we have 500 documents indexed by 10000 words. It follows that a column vector in represents a document. Assume we ask the algorithm to find 10 features in order to generate a features matrix with 10000 rows and 10 columns and a coefficients matrix with 10 rows and 500 columns. The product of and is a matrix with 10000 rows and 500 columns, the same shape as the input matrix and, if the factorization worked, it is a reasonable approximation to the input matrix . From the treatment of matrix multiplication above it follows that each column in the product matrix is a linear combination of the 10 column vectors in the features matrix with coefficients supplied by the coefficients matrix .
This last point is the basis of NMF because we can consider each original document in our example as being built from a small set of hidden features. NMF generates these features.
It is useful to think of each feature (column vector) in the features matrix as a document archetype comprising a set of words where each word's cell value defines the word's rank in the feature: The higher a word's cell value the higher the word's rank in the feature. A column in the coefficients matrix represents an original document with a cell value defining the document's rank for a feature. We can now reconstruct a document (column vector) from our input matrix by a linear combination of our features (column vectors in ) where each feature is weighted by the feature's cell value from the document's column in .
Clustering property NMF has an inherent clustering property, i.e., it automatically clusters the columns of input data .
More specifically, the approximation of by is achieved by finding and that minimize the error function (using the Frobenius norm)
subject to ,
If we furthermore impose an orthogonality constraint on , i.e. , then the above minimization is mathematically equivalent to the minimization of K-means clustering.
Furthermore, the computed gives the cluster membership, i.e., if for all i ≠ k, this suggests that the input data belongs to -th cluster. The computed gives the cluster centroids, i.e., the -th column gives the cluster centroid of -th cluster. This centroid's representation can be significantly enhanced by convex NMF.
When the orthogonality constraint is not explicitly imposed, the orthogonality holds to a large extent, and the clustering property holds too.
When the error function to be used is Kullback–Leibler divergence, NMF is identical to the probabilistic latent semantic analysis (PLSA), a popular document clustering method.
Types
Approximate non-negative matrix factorization Usually the number of columns of and the number of rows of in NMF are selected so the product will become an approximation to . The full decomposition of then amounts to the two non-negative matrices and as well as a residual , such that: . The elements of the residual matrix can either be negative or positive.
When and are smaller than they become easier to store and manipulate. Another reason for factorizing into smaller matrices and , is that if one's goal is to approximately represent the elements of by significantly less data, then one has to infer some latent structure in the data.
Convex non-negative matrix factorization In standard NMF, matrix factor ， i.e., can be anything in that space. Convex NMFC Ding, T Li, MI Jordan, Convex and semi-nonnegative matrix factorizations, IEEE Transactions on Pattern Analysis and Machine Intelligence, 32, 45-55, 2010 restricts the columns of to convex combinations of the input data vectors . This greatly improves the quality of data representation of . Furthermore, the resulting matrix factor becomes more sparse and orthogonal.
Nonnegative rank factorization In case the nonnegative rank of is equal to its actual rank, is called a nonnegative rank factorization (NRF). The problem of finding the NRF of , if it exists, is known to be NP-hard.
Different cost functions and regularizations There are different types of non-negative matrix factorizations. The different types arise from using different cost functions for measuring the divergence between and and possibly by regularization of the and/or matrices.
Two simple divergence functions studied by Lee and Seung are the squared error (or Frobenius norm) and an extension of the Kullback–Leibler divergence to positive matrices (the original Kullback–Leibler divergence is defined on probability distributions). Each divergence leads to a different NMF algorithm, usually minimizing the divergence using iterative update rules.
The factorization problem in the squared error version of NMF may be stated as: Given a matrix find nonnegative matrices W and H that minimize the function
Another type of NMF for images is based on the total variation norm.
When L1 regularization (akin to Lasso) is added to NMF with the mean squared error cost function, the resulting problem may be called non-negative sparse coding due to the similarity to the sparse coding problem, although it may also still be referred to as NMF.
Online NMF Many standard NMF algorithms analyze all the data together; i.e., the whole matrix is available from the start. This may be unsatisfactory in applications where there are too many data to fit into memory or where the data are provided in streaming fashion. One such use is for collaborative filtering in recommendation systems, where there may be many users and many items to recommend, and it would be inefficient to recalculate everything when one user or one item is added to the system. The cost function for optimization in these cases may or may not be the same as for standard NMF, but the algorithms need to be rather different.
Convolutional NMF If the columns of represent data sampled over spatial or temporal dimensions, e.g. time signals, images, or video, features that are equivariant w.r.t. shifts along these dimensions can be learned by Convolutional NMF. In this case, is sparse with columns having local non-zero weight windows that are shared across shifts along the spatio-temporal dimensions of , representing convolution kernels. By spatio-temporal pooling of and repeatedly using the resulting representation as input to convolutional NMF, deep feature hierarchies can be learned.
Algorithms There are several ways in which the and may be found: Lee and Seung's multiplicative update rule has been a popular method due to the simplicity of implementation. This algorithm is: initialize: and non negative. Then update the values in and by computing the following, with as an index of the iteration.
and
Until and are stable. Note that the updates are done on an element by element basis not matrix multiplication.
We note that the multiplicative factors for and , i.e. the and terms, are matrices of ones when .
More recently other algorithms have been developed. Some approaches are based on alternating non-negative least squares: in each step of such an algorithm, first is fixed and found by a non-negative least squares solver, then is fixed and is found analogously. The procedures used to solve for and may be the same or different, as some NMF variants regularize one of and . Specific approaches include the projected gradient descent methods, the active set method, the optimal gradient method, coordinate descent, and the block principal pivoting method among several others.
Current algorithms are sub-optimal in that they only guarantee finding a local minimum, rather than a global minimum of the cost function. A provably optimal algorithm is unlikely in the near future as the problem has been shown to generalize the k-means clustering problem which is known to be NP-complete. However, as in many other data mining applications, a local minimum may still prove to be useful.
In addition to the optimization step, initialization has a significant effect on NMF. The initial values chosen for and may affect not only the rate of convergence, but also the overall error at convergence. Some options for initialization include complete randomization, SVD, k-means clustering, and more advanced strategies based on these and other paradigms.
Variable rank methods Between any two local minima of rank , there is a "mostly downhill" path between them in the space of rank solutions. This motivates the idea of rank expansion and contraction as tools to escape poor local minima. To increase the rank, new components can be discovered using the generalized singular value decomposition. To decrease the rank, pairs of components may be greedily merged by a least-loss criterion. These techniques can be used in conjunction with a variety of NMF algorithms. Rank-modification does not necessarily increase computation time, largely because NMF algorithms frequently slow at one or more "plateaus" and empirically one finds that higher-rank solutions are less likely to plateau.
Sequential NMF The sequential construction of NMF components ( and ) was firstly used to relate NMF with Principal Component Analysis (PCA) in astronomy. The contribution from the PCA components are ranked by the magnitude of their corresponding eigenvalues; for NMF, its components can be ranked empirically when they are constructed one by one (sequentially), i.e., learn the -th component with the first components constructed.