Illustration of approximate non-negative matrix factorization: the matrix V is represented by the two smaller matrices W and H, which, when multiplied, approximately reconstruct V.

Non-negative matrix factorization (NMF or NNMF), also non-negative matrix approximation^[1][2] is a group of algorithms in multivariate analysis and linear algebra where a matrix V is factorized into (usually) two matrices W and H, 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,^[3][4] computer vision, document clustering,^[1] missing data imputation,^[5] chemometrics, audio signal processing, recommender systems,^[6][7] and bioinformatics.^[8]

History

In chemometrics non-negative matrix factorization has a long history under the name "self modeling curve resolution".^[9] 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.^[10][11][12] 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.^[13][14]

Background

Let matrix V be the product of the matrices W and H,

${\displaystyle \mathbf {V} =\mathbf {W} \mathbf {H} \,.}$

Matrix multiplication can be implemented as computing the column vectors of V as linear combinations of the column vectors in W using coefficients supplied by columns of H. That is, each column of V can be computed as follows:

${\displaystyle \mathbf {v} _{i}=\mathbf {W} \mathbf {h} _{i}\,,}$

where v_i is the i-th column vector of the product matrix V and h_i is the i-th column vector of the matrix H.

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 V is an m × n matrix, W is an m × p matrix, and H is a p × n matrix then p can be significantly less than both m and n.

Here is an example based on a text-mining application:

• Let the input matrix (the matrix to be factored) be V 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 v in V represents a document.
• Assume we ask the algorithm to find 10 features in order to generate a features matrix W with 10000 rows and 10 columns and a coefficients matrix H with 10 rows and 500 columns.
• The product of W and H is a matrix with 10000 rows and 500 columns, the same shape as the input matrix V and, if the factorization worked, it is a reasonable approximation to the input matrix V.
• From the treatment of matrix multiplication above it follows that each column in the product matrix WH is a linear combination of the 10 column vectors in the features matrix W with coefficients supplied by the coefficients matrix H.

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 W 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 H 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 W) where each feature is weighted by the feature's cell value from the document's column in H.

Clustering property

NMF has an inherent clustering property,^[15] i.e., it automatically clusters the columns of input data ${\displaystyle \mathbf {V} =(v_{1},\dots ,v_{n})}$.

More specifically, the approximation of ${\displaystyle \mathbf {V} }$ by ${\displaystyle \mathbf {V} \simeq \mathbf {W} \mathbf {H} }$ is achieved by finding ${\displaystyle W}$ and ${\displaystyle H}$ that minimize the error function (using the Frobenius norm)

${\displaystyle \left\|V-WH\right\|_{F},}$ subject to ${\displaystyle W\geq 0,H\geq 0.}$,

If we furthermore impose an orthogonality constraint on ${\displaystyle \mathbf {H} }$, i.e. ${\displaystyle \mathbf {H} \mathbf {H} ^{T}=I}$, then the above minimization is mathematically equivalent to the minimization of K-means clustering.^[15]

Furthermore, the computed ${\displaystyle H}$ gives the cluster membership, i.e., if ${\displaystyle \mathbf {H} _{kj}>\mathbf {H} _{ij}}$ for all i ≠ k, this suggests that the input data ${\displaystyle v_{j}}$ belongs to ${\displaystyle k}$-th cluster. The computed ${\displaystyle W}$ gives the cluster centroids, i.e., the ${\displaystyle k}$-th column gives the cluster centroid of ${\displaystyle k}$-th cluster. This centroid's representation can be significantly enhanced by convex NMF.

When the orthogonality constraint ${\displaystyle \mathbf {H} \mathbf {H} ^{T}=I}$ 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.^[16]

Types

Algorithms

There are several ways in which the W and H may be found: Lee and Seung's multiplicative update rule^[14] has been a popular method due to the simplicity of implementation. This algorithm is:

initialize: W and H non negative.

Then update the values in W and H by computing the following, with ${\displaystyle n}$ as an index of the iteration.

${\displaystyle \mathbf {H} _{[i,j]}^{n+1}\leftarrow \mathbf {H} _{[i,j]}^{n}{\frac {((\mathbf {W} ^{n})^{T}\mathbf {V} )_{[i,j]}}{((\mathbf {W} ^{n})^{T}\mathbf {W} ^{n}\mathbf {H} ^{n})_{[i,j]}}}}$

and

${\displaystyle \mathbf {W} _{[i,j]}^{n+1}\leftarrow \mathbf {W} _{[i,j]}^{n}{\frac {(\mathbf {V} (\mathbf {H} ^{n+1})^{T})_{[i,j]}}{(\mathbf {W} ^{n}\mathbf {H} ^{n+1}(\mathbf {H} ^{n+1})^{T})_{[i,j]}}}}$

Until W and H are stable.

Note that the updates are done on an element by element basis not matrix multiplication.

We note that the multiplicative factors for W and H, i.e. the ${\textstyle {\frac {\mathbf {W} ^{\mathsf {T}}\mathbf {V} }{\mathbf {W} ^{\mathsf {T}}\mathbf {W} \mathbf {H} }}}$ and ${\textstyle {\textstyle {\frac {\mathbf {V} \mathbf {H} ^{\mathsf {T}}}{\mathbf {W} \mathbf {H} \mathbf {H} ^{\mathsf {T}}}}}}$ terms, are matrices of ones when ${\displaystyle \mathbf {V} =\mathbf {W} \mathbf {H} }$.

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 H is fixed and W found by a non-negative least squares solver, then W is fixed and H is found analogously. The procedures used to solve for W and H may be the same^[29] or different, as some NMF variants regularize one of W and H.^[23] Specific approaches include the projected gradient descent methods,^[29][30] the active set method,^[6][31] the optimal gradient method,^[32] and the block principal pivoting method^[33] among several others.^[34]

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.^[35] However, as in many other data mining applications, a local minimum may still prove to be useful.

Fractional residual variance (FRV) plots for PCA and sequential NMF;^[4] for PCA, the theoretical values are the contribution from the residual eigenvalues. In comparison, the FRV curves for PCA reaches a flat plateau where no signal are captured effectively; while the NMF FRV curves are declining continuously, indicating a better ability to capture signal. The FRV curves for NMF also converges to higher levels than PCA, indicating the less-overfitting property of NMF.

Relation to other techniques

In Learning the parts of objects by non-negative matrix factorization Lee and Seung^[42] proposed NMF mainly for parts-based decomposition of images. It compares NMF to vector quantization and principal component analysis, and shows that although the three techniques may be written as factorizations, they implement different constraints and therefore produce different results.

NMF as a probabilistic graphical model: visible units (V) are connected to hidden units (H) through weights W, so that V is generated from a probability distribution with mean ${\displaystyle \sum _{a}W_{ia}h_{a}}$.^[13]: 5

It was later shown that some types of NMF are an instance of a more general probabilistic model called "multinomial PCA".^[43] When NMF is obtained by minimizing the Kullback–Leibler divergence, it is in fact equivalent to another instance of multinomial PCA, probabilistic latent semantic analysis,^[44] trained by maximum likelihood estimation. That method is commonly used for analyzing and clustering textual data and is also related to the latent class model.

NMF with the least-squares objective is equivalent to a relaxed form of K-means clustering: the matrix factor W contains cluster centroids and H contains cluster membership indicators.^[15][45] This provides a theoretical foundation for using NMF for data clustering. However, k-means does not enforce non-negativity on its centroids, so the closest analogy is in fact with "semi-NMF".^[17]

NMF can be seen as a two-layer directed graphical model with one layer of observed random variables and one layer of hidden random variables.^[46]

NMF extends beyond matrices to tensors of arbitrary order.^[47][48][49] This extension may be viewed as a non-negative counterpart to, e.g., the PARAFAC model.

Other extensions of NMF include joint factorization of several data matrices and tensors where some factors are shared. Such models are useful for sensor fusion and relational learning.^[50]

NMF is an instance of nonnegative quadratic programming, just like the support vector machine (SVM). However, SVM and NMF are related at a more intimate level than that of NQP, which allows direct application of the solution algorithms developed for either of the two methods to problems in both domains.^[51]

Uniqueness

The factorization is not unique: A matrix and its inverse can be used to transform the two factorization matrices by, e.g.,^[52]

${\displaystyle \mathbf {WH} =\mathbf {WBB} ^{-1}\mathbf {H} }$

If the two new matrices ${\displaystyle \mathbf {{\tilde {W}}=WB} }$ and ${\displaystyle \mathbf {\tilde {H}} =\mathbf {B} ^{-1}\mathbf {H} }$ are non-negative they form another parametrization of the factorization.

The non-negativity of ${\displaystyle \mathbf {\tilde {W}} }$ and ${\displaystyle \mathbf {\tilde {H}} }$ applies at least if B is a non-negative monomial matrix. In this simple case it will just correspond to a scaling and a permutation.

More control over the non-uniqueness of NMF is obtained with sparsity constraints.^[53]

Applications

Current research

Current research (since 2010) in nonnegative matrix factorization includes, but is not limited to,

1. Algorithmic: searching for global minima of the factors and factor initialization.^[80]
2. Scalability: how to factorize million-by-billion matrices, which are commonplace in Web-scale data mining, e.g., see Distributed Nonnegative Matrix Factorization (DNMF),^[81] Scalable Nonnegative Matrix Factorization (ScalableNMF),^[82] Distributed Stochastic Singular Value Decomposition.^[83]
3. Online: how to update the factorization when new data comes in without recomputing from scratch, e.g., see online CNSC^[84]
4. Collective (joint) factorization: factorizing multiple interrelated matrices for multiple-view learning, e.g. multi-view clustering, see CoNMF^[85] and MultiNMF^[86]
5. Cohen and Rothblum 1993 problem: whether a rational matrix always has an NMF of minimal inner dimension whose factors are also rational. Recently, this problem has been answered negatively.^[87]

See also

• Multilinear algebra
• Multilinear subspace learning
• Tensor
• Tensor decomposition
• Tensor software

Sources and external links