PaperlayerView exact revision on arXiv

Source-linked AI summary

The Why and How of Nonnegative Matrix Factorization

Nicolas Gillis

arXiv:1401.5226v2stat.MLcs.IRcs.LGmath.OC

TL;DR

NMF addresses how to obtain interpretable low-dimensional representations of nonnegative, high-dimensional data. The paper explains its applications, reviews standard algorithms, and presents near-separable cases that admit efficient solution despite general computational hardness.

  • Problem

    NMF is useful for extracting sparse, meaningful features from nonnegative data, but computing such factorizations is a central optimization question.

  • Method

    The paper illustrates NMF in three applications, reviews standard alternating-factor algorithms, and discusses sparsity priors and near-separable NMF.

  • Results

    Near-separable NMF can be solved efficiently in polynomial time even in the presence of noise, whereas standard algorithms are generally heuristic and may only guarantee stationary-point convergence.

  • Takeaways & Limitations

    NMF provides interpretable factors for images, documents, and hyperspectral data, including facial features, topics, and endmember abundances.

  • Takeaways & Limitations

    NMF is ill-posed because non-monomial transformations can produce equivalent factorizations with different interpretations.

Abstract

from arXiv · show

Nonnegative matrix factorization (NMF) has become a widely used tool for the analysis of high-dimensional data as it automatically extracts sparse and meaningful features from a set of nonnegative data vectors. We first illustrate this property of NMF on three applications, in image processing, text mining and hyperspectral imaging --this is the why. Then we address the problem of solving NMF, which is NP-hard in general. We review some standard NMF algorithms, and also present a recent subclass of NMF problems, referred to as near-separable NMF, that can be solved efficiently (that is, in polynomial time), even in the presence of noise --this is the how. Finally, we briefly describe some problems in mathematics and computer science closely related to NMF via the nonnegative rank.

1 Introduction

Linear dimensionality reduction represents high-dimensional data in a lower-dimensional basis, and NMF adds component-wise nonnegativity to make both basis elements and weights nonnegative.

  • 1 Introduction: LDR represents p-dimensional data points in an r-dimensional linear subspace using basis elements and their coordinates.The rank satisfies r < min(p, n).
  • 1 Introduction: LDR is equivalent to approximating the data matrix X with the low-rank product WH.Columns of X are data points, columns of W are basis elements, and columns of H are coordinates.
  • 1 Introduction: The Frobenius norm is widely used because it corresponds to Gaussian noise and permits efficient optimization through truncated SVD.SVD is equivalent to PCA after mean-centering the data.
  • 1 Introduction: NMF constrains both basis elements W and weights H to be component-wise nonnegative while approximating a nonnegative data matrix X.NMF was introduced by Paatero and Tapper in 1994 and gained broader interest after Lee and Seung’s 1999 article.
  • 1 Introduction: The paper introduces NMF through three applications and reviews several algorithms rather than comprehensively covering all applications and contributions.Its focus is explaining why NMF is popular and how NMF factorizations can be computed.

2 The Why – NMF Generates Sparse and Meaningful Features

NMF extracts sparse, interpretable features from nonnegative data across images, documents, and hyperspectral scenes. Its factors represent localized facial features, topics, or endmembers and their nonnegative weights.

  • 2 The Why – NMF Generates Sparse and Meaningful Features: NMF’s popularity comes from automatically extracting sparse and interpretable factors across image processing, text mining, and hyperspectral imaging.The paper illustrates this property through three applications.
  • 2.1 Image Processing – Facial Feature Extraction: In face images, nonnegative basis columns act as basis images, while nonnegative weights combine them only additively to reconstruct each face.Using few basis images encourages localized features shared across images.
  • 2.1 Image Processing – Facial Feature Extraction: Facial basis images capture features such as eyes, noses, mustaches, and lips, while H indicates which features occur in each image.NMF has been observed to be more robust to occlusion than PCA because non-occluded parts can still be approximated.
  • 2.2 Text Mining – Topic Recovery and Document Classification: In document data, X records weighted word occurrences under the bag-of-words model, whose word ordering is ignored and whose matrix is generally sparse.Term frequency–inverse document frequency is one practical construction.
  • 2.2 Text Mining – Topic Recovery and Document Classification: Nonnegative document factors can be interpreted as topics, while H assigns documents to the topics they discuss.NMF therefore identifies topics and simultaneously classifies documents.
  • 2.3 Hyperspectral Unmixing – Identify Endmembers and Classify Pixels: Blind hyperspectral unmixing identifies constituent materials and classifies pixels by determining which endmembers each pixel contains and in what proportions.Pixels are generally mixtures of several endmembers.
  • 2.3 Hyperspectral Unmixing – Identify Endmembers and Classify Pixels: In hyperspectral unmixing, NMF factors represent endmember spectral signatures and pixel abundances under the linear mixing model.The rank r corresponds to the number of endmembers.
  • 2.3 Hyperspectral Unmixing – Identify Endmembers and Classify Pixels: The Urban hyperspectral example uses six endmembers, with columns of W as spectral signatures and rows of H as corresponding abundance maps.The displayed decomposition uses a sparse prior on H.

3 The How – Some Algorithms

NMF is useful for nonnegative data, but computing it is difficult because the general problem is NP-hard and can be ill-posed. The paper reviews standard algorithms and discusses near-separable NMF as an efficiently solvable subclass.

  • Computational difficulty: NMF is NP-hard in general, so standard methods may only be guaranteed to converge to stationary points.These methods are nevertheless reported as successful in many applications.
  • Near-separable NMF: Near-separable matrices form a subclass for which NMF can be solved efficiently, including in the presence of noise.The paper presents recent algorithms for this subclass.
  • Computational difficulty: Exact NMF algorithms can be polynomial in dimensions p and n for fixed rank r, but their computational cost prevents their use on real-world problems.Heuristic NMF algorithms typically run in O(pnr) operations.
  • Ill-posedness: NMF is ill-posed because non-monomial transformations can produce equivalent factorizations beyond simple scaling and permutation.The paper distinguishes this from scaling and permutation, which are not considered problematic in practice.
  • Practical issues: Practical NMF may require priors and regularization, such as sparsity, because plain NMF can perform poorly for some hyperspectral unmixing data.Other priors include piece-wise smoothness and spatial coherence.

3.1 Standard NMF Algorithms

Most standard NMF algorithms alternate between optimizing W and H while holding the other factor fixed, reducing each step to a nonnegative least-squares problem. Their differences mainly concern how those subproblems are solved.

  • Two-block coordinate descent: Two-block coordinate descent alternately updates W and H while keeping the other factor fixed.The framework starts from nonnegative initial matrices and repeats factor updates until a stopping criterion is reached.
  • NNLS subproblems: Each factor update is a nonnegative least-squares problem because the objective is convex in one factor when the other is fixed.The problem is symmetric in W and H, so the same framework can update either factor.
  • Algorithmic variants: NMF algorithms based on two-block coordinate descent differ primarily in which NNLS algorithm they use.The paper introduces several standard updates within this common framework.
  • Algorithmic variants: The coordinate-descent update steps usually guarantee that the objective function decreases.The paper compares widely used updates in a later section.

3.1.1 First-Order Optimality Conditions

The first-order conditions characterize stationary points of NMF and explain why zero entries naturally arise. Multiplicative updates decrease the objective, but can fail to reach a stationary point when entries become zero.

  • Optimality conditions: A stationary NMF point satisfies nonnegativity, nonnegative gradients, and complementary products W ◦∇_W F = 0 and H ◦∇_H F = 0.The component-wise product condition requires each variable or its corresponding partial derivative to be zero.
  • Optimality conditions: Complementary conditions formally explain why NMF naturally generates sparse solutions with zero entries.For each entry, either the entry is zero or its partial derivative is zero.
  • Multiplicative updates: Multiplicative updates minimize a quadratic majorizer of F, guaranteeing that F monotonically decreases.They can also be interpreted as a rescaled gradient method.
  • Multiplicative updates: Multiplicative updates increase, decrease, or leave an entry unchanged according to the sign of its partial derivative.This behavior is described as an intuitive interpretation of the updates.
  • Multiplicative updates: Zero entries cannot be modified by multiplicative updates, so the method is not guaranteed to converge to a stationary point.Reinitializing zero entries to a small positive constant when their partial derivatives become negative is one proposed remedy.
  • Multiplicative updates: Multiplicative updates became popular because they are simple, scalable, and applicable to sparse matrices, but they converge relatively slowly.They can be accelerated by updating W several times before updating H because certain products need not be recomputed.

3.1.3 Alternating Least Squares

Alternating least squares solves an unconstrained least-squares problem and projects the result onto the nonnegative orthant. Although inexpensive and useful for initialization, it generally has convergence and scaling problems.

  • ALS procedure: ALS first solves the unconstrained least-squares problem for W and then projects the solution onto the nonnegative orthant.The method applies the analogous alternating procedure to the factor updates.
  • ALS limitations: ALS is relatively cheap and easy to implement, but its objective function may oscillate instead of converging.The oscillation is especially noted for dense input matrices.
  • ALS limitations: Projection can leave ALS solutions improperly scaled, and multiplying the current WH by a constant can sometimes drastically reduce the error.The passage identifies scaling as a consequence of the projection step.
  • ALS use: Despite convergence issues, ALS can be powerful for initialization, especially for sparse matrices.A recommended use is to perform a few ALS steps and then switch to another NMF algorithm.

3.1.4 Alternating Nonnegative Least Squares

Alternating nonnegative least squares solves each factor subproblem exactly, giving strong per-iteration error reduction at higher computational cost. In comparisons, HALS performs best overall, while algorithm performance depends on matrix density.

  • ANLS: ANLS solves the W and H nonnegative least-squares subproblems exactly and is guaranteed to converge to a stationary point.Each iteration decreases the error the most among NMF algorithms in the described coordinate-descent framework, but costs more computationally.
  • HALS: HALS solves NNLS by exact coordinate descent, updating one column of W at a time with closed-form solutions.Because entries within a column do not interact, the corresponding problem decouples into single-variable nonnegative quadratic problems.
  • HALS: HALS converges much faster than MU while having almost the same computational cost, under mild assumptions converging to a stationary point.Careful initialization is important because HALS can otherwise set some columns of W to zero.
  • Comparison: On dense CBCL data, ALS oscillates and performs poorly, whereas ANLS performs well and is second best after HALS.On sparse Classic data, ALS initially converges quickly but stabilizes at a relatively large objective value, and ANLS performs poorly.
  • Comparison: HALS generates the best solutions within the allotted time, while MU converges rather slowly.The comparison uses the same ten random initial matrices for all algorithms.

3.1.7 Stopping Criterion

NMF stopping criteria based on optimality conditions can certify stationarity but may be misleading because they are sensitive to factor scaling and update order. Normalization and careful comparison are therefore necessary.

  • Optimality-based criterion: The criterion C(W, H) = CW(W) + CH(H) equals zero if and only if (W, H) is a stationary point.It is one of several possible stopping criteria, alongside objective evolution and differences between consecutive iterates.
  • Scaling sensitivity: C(W, H) is sensitive to scaling, so equivalent factorizations can yield different criterion values.This occurs because the first two terms in the criterion change under rescaling W and H.
  • Scaling sensitivity: Proper normalization, such as equalizing ||W(:, k)||2 and ||H(k, :)||2 for every k, can address scaling sensitivity.Without normalization, scaling can make part of the criterion arbitrarily small even when the factorization is unchanged.
  • Comparing algorithms: Criterion values after updating W can differ substantially from values after updating H, especially with poor scaling or when |m−n| is large.Consequently, C(W, H) can mislead comparisons between ANLS-type methods and MU or HALS.

3.1.8 Initialization

NMF can be initialized randomly or with more structured estimates intended to reduce iterations or improve the stationary point. Available strategies include clustering, SVD-based constructions, and column subset selection, but most lack theoretical guarantees.

  • General strategies: Random initialization generates all entries of W and H uniformly in [0,1].More sophisticated strategies seek fewer iterations and better stationary points, although most have no theoretical guarantee.
  • Clustering techniques: Clustering initialization uses cluster centroids for W and a properly scaled cluster indicator matrix for H.A document or data point is assigned to a cluster through the nonzero structure of H.
  • SVD-based initialization: SVD-based initialization constructs nonnegative approximations from positive and negative parts of rank-one SVD factors.The first two rank-one factors in the described decomposition are nonnegative, and each factor can be replaced by a larger-norm positive or negative part with appropriate scaling.
  • Column subset selection: Column subset selection initializes W with r data points, setting W = X(:, K) for a set K of cardinality r.This uses observed columns of X as the initial basis elements.
  • General strategies: Using several initializations and retaining the best solution is a practical strategy.The strategy addresses variation in the quality of initial estimates without requiring a theoretical guarantee.

3.2 Near-Separable NMF

Near-separable NMF identifies a subset of columns that approximately generates the remaining data, enabling polynomial-time algorithms even with noise. The section reviews self-dictionary and geometric approaches, their application assumptions, robustness, and computational limitations.

  • Problem formulation: Separable NMF seeks r columns whose nonnegative combinations reconstruct all columns of X.In the noiseless case, normalized columns can be viewed as points in a convex hull, with selected columns representing its vertices.
  • Applications and assumptions: Separable structure corresponds to application-specific assumptions such as anchor documents or words in text mining and pure pixels in hyperspectral unmixing.The pure-pixel assumption is more plausible for relatively high-spatial-resolution hyperspectral images; facial feature extraction does not naturally satisfy separability.
  • Geometric algorithms and limitations: Geometric and related algorithms provide efficient recovery guarantees, including polynomial-time recovery under noise, while self-dictionary approaches can require optimization problems with n^2 variables.Further work seeks faster and more robust algorithms; no algorithm is known to be robust for every W with α(W) > 0 in O(n) operations.
  • Problem formulation: In near-separable NMF, noisy columns indexed by K approximate the unknown basis W in X̃ = W[I_r, H′]Π + N.The goal is to find r indices whose columns are close to the basis columns.
  • Self-dictionary and sparse regression: Self-dictionary methods model separability by selecting a small number of nonzero rows in a reconstruction matrix Y, with noisy variants using relaxed constraints or penalties.Convex relaxations can be linked to compressive sensing, but highly correlated rows and columns make robustness theory unclear.
  • Self-dictionary and sparse regression: Convex relaxation may extract duplicate basis columns and lacked developed robustness results under noise when duplicates are absent only asymptotically.A weighted diagonal-sparsity model breaks symmetry between duplicates and has been shown to be robust.

4 Connections with Problems in Mathematics and Computer Science

The nonnegative rank connects exact NMF to combinatorial, probabilistic, communication, and geometric problems. These connections relate matrix factorization to biclique covers, independent-variable mixtures, communication protocols, and polyhedral formulations.

  • Nonnegative rank: The nonnegative rank rank+(X) is the minimum number of components in an exact nonnegative factorization X = WH.It provides the common language linking NMF to several problems outside data mining and machine learning.
  • Graph theory: In graph theory, nonnegative rank is bounded below by the minimum biclique cover size of the bipartite graph induced by X.This lower bound is called the rectangle covering bound.
  • Extended formulations: For a polytope’s slack matrix, the nonnegative rank equals the minimum number of facets in an extended formulation.Approximate extended formulations are directly related to approximate factorizations.
  • Probability: For a probability distribution represented as a mixture of independent-variable distributions, factorization corresponds to explaining the distribution with as few independent variables as possible.Each component distribution corresponds to a nonnegative rank-one matrix.
  • Communication complexity: In communication complexity, the nondeterministic communication complexity of a function is upper bounded by the logarithm of the nonnegative rank of its communication matrix.The result is closely related to the rectangle covering bound.
  • Computational geometry: In computational geometry, nonnegative rank is related to finding a minimum-vertex polytope nested between two given polytopes.This is known as the nested polytopes problem.

5 Conclusion

NMF is presented as an interpretable and versatile dimensionality-reduction technique for nonnegative data, with broad application potential. The conclusion highlights its relevance to increasingly important Big Data analysis.

  • Conclusion: NMF is an easily interpretable linear dimensionality reduction technique for nonnegative data.The paper describes it as versatile, with applications across a broad range of research areas.
  • Conclusion: The paper links NMF’s future to Big Data science and illustrates growing publication activity related to NMF.Figure 5 is cited as an illustration of publication counts since the Lee and Seung paper.
Loading 1401.5226v2…