Non-negative matrix factorization (NMF orNNMF), alsonon-negative matrix approximation^[1][2] is a group ofalgorithms inmultivariate analysis andlinear algebra where amatrixV isfactorized into (usually) two matricesW andH, 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 asastronomy,^[3][4]computer vision,document clustering,^[1]missing data imputation,^[5]chemometrics,audio signal processing,recommender systems,^[6][7] andbioinformatics.^[8]

Inchemometrics 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 namepositive matrix factorization.^[10][11][12]It became more widely known asnon-negative matrix factorization after Lee andSeung investigated the properties of the algorithm and published some simple and usefulalgorithms for two types of factorizations.^[13][14]

Let matrixV be the product of the matricesW andH,

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

Matrix multiplication can be implemented as computing the column vectors ofV as linear combinations of the column vectors inW using coefficients supplied by columns ofH. That is, each column ofV can be computed as follows:

${\displaystyle {\mathbf{v}}_i=\mathbf{W}{\mathbf{h}}_i,}$

wherev_i is thei-th column vector of the product matrixV andh_i is thei-th column vector of the matrixH.

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, ifV is anm ×n matrix,W is anm ×p matrix, andH is ap ×n matrix thenp can be significantly less than bothm andn.

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

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

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 matrixW 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 matrixH 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 inW) where each feature is weighted by the feature's cell value from the document's column inH.

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 theFrobenius norm)

${\displaystyle {\Vert V-WH\Vert }_F,}$ subject to${\displaystyle W\ge 0,H\ge 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 ofK-means clustering.^[15]

Furthermore, the computed${\displaystyle H}$ gives the cluster membership, i.e., if${\displaystyle {\mathbf{H}}_{kj}>{\mathbf{H}}_{ij}}$ for alli ≠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 isKullback–Leibler divergence, NMF is identical to theprobabilistic latent semantic analysis (PLSA), a popular document clustering method.^[16]

Usually the number of columns ofW and the number of rows ofH in NMF are selected so the productWH will become an approximation toV. The full decomposition ofV then amounts to the two non-negative matricesW andH as well as a residualU, such that:V =WH +U. The elements of the residual matrix can either be negative or positive.

WhenW andH are smaller thanV they become easier to store and manipulate. Another reason for factorizingV into smaller matricesW andH, is that if one's goal is to approximately represent the elements ofV by significantly less data, then one has to infer some latent structure in the data.

In standard NMF, matrix factorW ∈R₊^{m ×k}， i.e.,W can be anything in that space. Convex NMF^[17] restricts the columns ofW toconvex combinations of the input data vectors${\displaystyle (v_1,\dots ,v_n)}$. This greatly improves the quality of data representation ofW. Furthermore, the resulting matrix factorH becomes more sparse and orthogonal.

In case thenonnegative rank ofV is equal to its actual rank,V =WH is called a nonnegative rank factorization (NRF).^[18][19][20] The problem of finding the NRF ofV, if it exists, is known to be NP-hard.^[21]

There are different types of non-negative matrix factorizations.The different types arise from using differentcost functions for measuring the divergence betweenV andWH and possibly byregularization of theW and/orH matrices.^[1]

Two simple divergence functions studied by Lee and Seung are the squared error (orFrobenius norm) and an extension of the Kullback–Leibler divergence to positive matrices (the originalKullback–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${\displaystyle \mathbf{V}}$ find nonnegative matrices W and H that minimize the function

${\displaystyle F(\mathbf{W},\mathbf{H})={\Vert \mathbf{V}-\mathbf{W}\mathbf{H}\Vert }_F^2}$

Another type of NMF for images is based on thetotal variation norm.^[22]

WhenL1 regularization (akin toLasso) is added to NMF with the mean squared error cost function, the resulting problem may be callednon-negative sparse coding due to the similarity to thesparse coding problem,^[23][24]although it may also still be referred to as NMF.^[25]

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 instreaming fashion. One such use is forcollaborative filtering inrecommendation 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.^[26][27]

If the columns ofV 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,W is sparse with columns having local non-zero weight windows that are shared across shifts along the spatio-temporal dimensions ofV, representingconvolution kernels. By spatio-temporal pooling ofH and repeatedly using the resulting representation as input to convolutional NMF, deep feature hierarchies can be learned.^[28]

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

initialize:W andH non negative.

Then update the values inW andH 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]}}}$

UntilW andH are stable.

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

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

More recently other algorithms have been developed.Some approaches are based on alternatingnon-negative least squares: in each step of such an algorithm, firstH is fixed andW found by a non-negative least squares solver, thenW is fixed andH is found analogously. The procedures used to solve forW andH may be the same^[29] or different, as some NMF variants regularize one ofW andH.^[23] Specific approaches include the projectedgradient descent methods,^[29][30] theactive 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 beNP-complete.^[35] 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 forW andH 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.^[36]

The sequential construction of NMF components (W andH) was firstly used to relate NMF withPrincipal Component Analysis (PCA) in astronomy.^[37] 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${\displaystyle (n+1)}$-th component with the first${\displaystyle n}$ components constructed.

The contribution of the sequential NMF components can be compared with theKarhunen–Loève theorem, an application of PCA, using the plot of eigenvalues. A typical choice of the number of components with PCA is based on the "elbow" point, then the existence of the flat plateau is indicating that PCA is not capturing the data efficiently, and at last there exists a sudden drop reflecting the capture of random noise and falls into the regime of overfitting.^[38][39] For sequential NMF, the plot of eigenvalues is approximated by the plot of the fractional residual variance curves, where the curves decreases continuously, and converge to a higher level than PCA,^[4] which is the indication of less over-fitting of sequential NMF.

Exact solutions for the variants of NMF can be expected (in polynomial time) when additional constraints hold for matrixV. A polynomial time algorithm for solving nonnegative rank factorization ifV contains a monomial sub matrix of rank equal to its rank was given by Campbell and Poole in 1981.^[40] Kalofolias and Gallopoulos (2012)^[41] solved the symmetric counterpart of this problem, whereV is symmetric and contains a diagonal principal sub matrix of rank r. Their algorithm runs inO(rm²) time in the dense case. Arora, Ge, Halpern, Mimno, Moitra, Sontag, Wu, & Zhu (2013) give a polynomial time algorithm for exact NMF that works for the case where one of the factors W satisfies a separability condition.^[42]

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

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

NMF with the least-squares objective is equivalent to a relaxed form ofK-means clustering: the matrix factorW contains cluster centroids andH contains cluster membership indicators.^[15][46] 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-layerdirected graphical model with one layer of observed random variables and one layer of hidden random variables.^[47]

NMF extends beyond matrices to tensors of arbitrary order.^[48][49][50] This extension may be viewed as a non-negative counterpart to, e.g., thePARAFAC 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.^[51]

NMF is an instance of nonnegativequadratic programming, just like thesupport 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.^[52]

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

${\displaystyle \mathbf{W}\mathbf{H}={\mathbf{W}\mathbf{B}\mathbf{B}}^{-1}\mathbf{H}}$

If the two new matrices${\displaystyle \stackrel{\mathbf{~}}{\mathbf{W}}\mathbf{=}\mathbf{W}\mathbf{B}}$ and${\displaystyle \stackrel{\mathbf{~}}{\mathbf{H}}={\mathbf{B}}^{-1}\mathbf{H}}$ arenon-negative they form another parametrization of the factorization.

The non-negativity of${\displaystyle \stackrel{\mathbf{~}}{\mathbf{W}}}$ and${\displaystyle \stackrel{\mathbf{~}}{\mathbf{H}}}$ applies at least ifB is a non-negativemonomial matrix.In this simple case it will just correspond to a scaling and apermutation.

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

In astronomy, NMF is a promising method fordimension reduction in the sense that astrophysical signals are non-negative. NMF has been applied to the spectroscopic observations^[55][3] and the direct imaging observations^[4] as a method to study the common properties of astronomical objects and post-process the astronomical observations. The advances in the spectroscopic observations by Blanton & Roweis (2007)^[3] takes into account of the uncertainties of astronomical observations, which is later improved by Zhu (2016)^[37] where missing data are also considered andparallel computing is enabled. Their method is then adopted by Ren et al. (2018)^[4] to the direct imaging field as one of themethods of detecting exoplanets, especially for the direct imaging ofcircumstellar disks.

Ren et al. (2018)^[4] are able to prove the stability of NMF components when they are constructed sequentially (i.e., one by one), which enables thelinearity of the NMF modeling process; thelinearity property is used to separate the stellar light and the light scattered from theexoplanets andcircumstellar disks.

In direct imaging, to reveal the faint exoplanets and circumstellar disks from bright the surrounding stellar lights, which has a typical contrast from 10⁵ to 10¹⁰, various statistical methods have been adopted,^[56][57][38] however the light from the exoplanets or circumstellar disks are usually over-fitted, where forward modeling have to be adopted to recover the true flux.^[58][39] Forward modeling is currently optimized for point sources,^[39] however not for extended sources, especially for irregularly shaped structures such as circumstellar disks. In this situation, NMF has been an excellent method, being less over-fitting in the sense of the non-negativity andsparsity of the NMF modeling coefficients, therefore forward modeling can be performed with a few scaling factors,^[4] rather than a computationally intensive data re-reduction on generated models.

To impute missing data in statistics, NMF can take missing data while minimizing its cost function, rather than treating these missing data as zeros.^[5] This makes it a mathematically proven method fordata imputation in statistics.^[5] By first proving that the missing data are ignored in the cost function, then proving that the impact from missing data can be as small as a second order effect, Ren et al. (2020)^[5] studied and applied such an approach for the field of astronomy. Their work focuses on two-dimensional matrices, specifically, it includes mathematical derivation, simulated data imputation, and application to on-sky data.

The data imputation procedure with NMF can be composed of two steps. First, when the NMF components are known, Ren et al. (2020) proved that impact from missing data during data imputation ("target modeling" in their study) is a second order effect. Second, when the NMF components are unknown, the authors proved that the impact from missing data during component construction is a first-to-second order effect.

Depending on the way that the NMF components are obtained, the former step above can be either independent or dependent from the latter. In addition, the imputation quality can be increased when the more NMF components are used, see Figure 4 of Ren et al. (2020) for their illustration.^[5]

NMF can be used fortext mining applications.In this process, adocument-term matrix is constructed with the weights of various terms (typically weighted word frequency information) from a set of documents.This matrix is factored into aterm-feature and afeature-document matrix.The features are derived from the contents of the documents, and the feature-document matrix describesdata clusters of related documents.

One specific application used hierarchical NMF on a small subset of scientific abstracts fromPubMed.^[59]Another research group clustered parts of theEnron email dataset^[60]with 65,033 messages and 91,133 terms into 50 clusters.^[61]NMF has also been applied to citations data, with one example clusteringEnglish Wikipedia articles andscientific journals based on the outbound scientific citations in English Wikipedia.^[62]

Arora, Ge, Halpern, Mimno, Moitra, Sontag, Wu, & Zhu (2013) have given polynomial-time algorithms to learn topic models using NMF. The algorithm assumes that the topic matrix satisfies a separability condition that is often found to hold in these settings.^[42]

Hassani, Iranmanesh and Mansouri (2019) proposed a feature agglomeration method for term-document matrices which operates using NMF. The algorithm reduces the term-document matrix into a smaller matrix more suitable for text clustering.^[63]

NMF is also used to analyze spectral data; one such use is in the classification of space objects and debris.^[64]

NMF is applied in scalable Internet distance (round-trip time) prediction. For a network with${\displaystyle N}$ hosts, with the help of NMF, the distances of all the${\displaystyle N^2}$ end-to-end links can be predicted after conducting only${\displaystyle O(N)}$ measurements. This kind of method was firstly introduced in InternetDistance Estimation Service (IDES).^[65] Afterwards, as a fully decentralized approach, Phoenix network coordinate system^[66]is proposed. It achieves better overall prediction accuracy by introducing the concept of weight.

Speech denoising has been a long lasting problem inaudio signal processing. There are many algorithms for denoising if the noise is stationary. For example, theWiener filter is suitable for additiveGaussian noise. However, if the noise is non-stationary, the classical denoising algorithms usually have poor performance because the statistical information of the non-stationary noise is difficult to estimate. Schmidt et al.^[67] use NMF to do speech denoising under non-stationary noise, which is completely different from classical statistical approaches. The key idea is that clean speech signal can be sparsely represented by a speech dictionary, but non-stationary noise cannot. Similarly, non-stationary noise can also be sparsely represented by a noise dictionary, but speech cannot.

The algorithm for NMF denoising goes as follows. Two dictionaries, one for speech and one for noise, need to be trained offline. Once a noisy speech is given, we first calculate the magnitude of the Short-Time-Fourier-Transform. Second, separate it into two parts via NMF, one can be sparsely represented by the speech dictionary, and the other part can be sparsely represented by the noise dictionary. Third, the part that is represented by the speech dictionary will be the estimated clean speech.

Sparse NMF is used inPopulation genetics for estimating individual admixture coefficients, detecting genetic clusters of individuals in a population sample or evaluatinggenetic admixture in sampled genomes. In human genetic clustering, NMF algorithms provide estimates similar to those of the computer program STRUCTURE, but the algorithms are more efficient computationally and allow analysis of large population genomic data sets.^[68]

NMF has been successfully applied inbioinformatics for clusteringgene expression andDNA methylation data and finding the genes most representative of the clusters.^{[24][69][70][71]} In the analysis of cancer mutations it has been used to identify common patterns of mutations that occur in many cancers and that probably have distinct causes.^[72] NMF techniques can identify sources of variation such as cell types, disease subtypes, population stratification, tissue composition, and tumor clonality.^[73]

A particular variant of NMF, namely Non-Negative Matrix Tri-Factorization (NMTF),^[74] has been use fordrug repurposing tasks in order to predict novel protein targets and therapeutic indications for approved drugs^[75] and to infer pair of synergic anticancer drugs.^[76]

NMF, also referred in this field as factor analysis, has been used since the 1980s^[77] to analyze sequences of images inSPECT andPET dynamic medical imaging. Non-uniqueness of NMF was addressed using sparsity constraints.^[78][79][80]

This section needs to beupdated. Please help update this article to reflect recent events or newly available information.(February 2024)

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.^[81]
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),^[82] Scalable Nonnegative Matrix Factorization (ScalableNMF),^[83] Distributed Stochastic Singular Value Decomposition.^[84]
3. Online: how to update the factorization when new data comes in without recomputing from scratch, e.g., see online CNSC^[85]
4. Collective (joint) factorization: factorizing multiple interrelated matrices for multiple-view learning, e.g. multi-view clustering, see CoNMF^[86] and MultiNMF^[87]
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.^[88]

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

Scholia has atopic profile forNon-negative matrix factorization.

• Linear algebra
• Matrix theory
• Machine learning algorithms
• Factorization

• CS1 maint: multiple names: authors list
• Articles with short description
• Short description matches Wikidata
• Wikipedia articles in need of updating from February 2024
• All Wikipedia articles in need of updating