Non-Negative Matrix Factorization (NMF)

The defining mathematical property of NMF is the hard constraint that all entries in the factor matrices W (basis) and H (coefficients) must be non-negative (≥ 0). This constraint fundamentally alters the solution space compared to unconstrained methods like SVD.

• Impact: It forces an additive, parts-based representation. Components can only be added together to reconstruct the original data, never subtracted.
• Consequence: This often leads to sparser, more interpretable factors that correspond to intuitive "parts" of the data, such as facial features in images or topics in text.

A direct result of the non-negativity constraint, NMF typically learns a set of localized basis components. Each component represents a coherent "part" of the data, and the original samples are reconstructed as additive combinations of these parts.

• Example in Images: When applied to a dataset of faces, NMF factors might represent individual facial features like eyes, noses, or mouths. A full face is the sum of these features with positive weights.
• Contrast with PCA: Principal Component Analysis (PCA) learns global, holistic eigenvectors (eigenfaces) that have both positive and negative entries, representing directions of variance rather than constituent parts.

NMF naturally promotes sparse representations, meaning many coefficients in the H matrix are zero or near-zero. This enhances model interpretability.

• Why It's Sparse: The non-negative solution space often lies at the boundaries (where values are zero), and optimization encourages using fewer components to explain the data.
• Practical Benefit: A data sample is explained by only a small subset of the learned basis components. For example, a document might be associated with only 2-3 topics (non-zero coefficients) out of a larger set of 50 possible topics.

Unlike Singular Value Decomposition (SVD), which provides a unique solution (up to sign), NMF solutions are generally not unique. This is due to the non-convex nature of the optimization problem and the existence of scale and permutation ambiguities.

• Scale Ambiguity: If you multiply a column of W by a constant and divide the corresponding row of H by the same constant, the product W x H remains unchanged.
• Permutation Ambiguity: The order of the learned components is arbitrary; swapping columns in W and corresponding rows in H yields an equivalent factorization.
• Implication: Results can vary with different random initializations, requiring multiple runs or careful initialization strategies.

NMF is formulated as an optimization problem to minimize the reconstruction error between the original matrix V and its approximation WH. The choice of error metric leads to different algorithms.

• Frobenius Norm (Euclidean Distance): Minimizes ||V - WH||²_F. Solved via Multiplicative Update Rules (a special case of gradient descent) or Alternating Least Squares (ALS) with projected non-negativity.
• Kullback-Leibler (KL) Divergence: Minimizes a probabilistic divergence measure. Also solved with Multiplicative Updates. Often preferred for count data (e.g., word counts in documents) as it models a Poisson-like process.
• It is Non-Convex: Optimization is challenging; algorithms typically find local minima, not the global optimum.

NMF excels with data that is inherently non-negative and where an additive, parts-based decomposition is meaningful.

• Computer Vision: Image decomposition (e.g., facial features, object parts), hyperspectral unmixing.
• Text Mining & NLP: Topic Modeling, where W represents topics (distributions over words) and H represents document compositions over topics.
• Bioinformatics: Analysis of gene expression data, identifying molecular patterns.
• Audio Signal Processing: Source separation (e.g., separating instruments in a musical track), as audio spectrograms are non-negative.
• Recommendation Systems: Collaborative filtering, where the non-negativity constraint aligns with the idea of users having positive affinities for item features.

Low-rank factorization is a general model compression and dimensionality reduction technique that approximates a large matrix (e.g., a neural network weight matrix) as the product of two or more smaller matrices. The core assumption is that the original matrix is not full-rank, meaning its information can be represented more efficiently.

• Mechanism: Decomposes a matrix W (m x n) into U (m x r) and V (r x n), where r (the rank) is much smaller than m and n.
• Primary Benefit: Drastically reduces the parameter count from m * n to r * (m + n), lowering memory and computational cost for matrix-vector multiplications.
• Relation to NMF: NMF is a specific type of low-rank factorization that adds the constraint that all elements in the factor matrices U and V must be non-negative.

Singular Value Decomposition (SVD) is a fundamental matrix factorization method that decomposes any real or complex matrix A into three matrices: A = U Σ V^T, where U and V are orthogonal matrices and Σ is a diagonal matrix of singular values.

• Foundation for Compression: The truncated SVD, which keeps only the top-k largest singular values, provides the optimal rank-k approximation of the original matrix (Eckart–Young theorem).
• Key Difference from NMF: SVD factors can contain negative values and are orthogonal, leading to holistic, global feature representations. NMF's non-negativity constraint forces a parts-based representation, where features are additive combinations of basis elements.

Principal Component Analysis (PCA) is a statistical procedure for dimensionality reduction and feature extraction that transforms data to a new coordinate system of orthogonal principal components.

• Mathematical Basis: For a centered data matrix X, PCA is performed via the eigendecomposition of the covariance matrix X^T X or the SVD of X.
• Contrast with NMF: Both seek a lower-dimensional representation. However, PCA components are orthogonal and can have both positive and negative loadings, representing directions of maximum variance. NMF components are non-negative and non-orthogonal, often yielding more interpretable, additive features (e.g., facial parts in images, topics in documents).

Canonical Polyadic Decomposition (CPD), also known as PARAFAC, is a tensor factorization method that generalizes low-rank factorization to multi-dimensional arrays (tensors). It expresses a tensor as a sum of rank-one tensors.

• Higher-Order Data: Essential for compressing and analyzing data with more than two modes (e.g., a dataset of users, items, and timestamps).
• Relation to Matrix Methods: For a matrix (a 2D tensor), CPD reduces to factorizing into two matrices, analogous to standard low-rank factorization. NMF can be extended to Non-Negative Tensor Factorization (NTF), applying the non-negativity constraint to all factor matrices in a CP or Tucker decomposition.

Alternating Least Squares (ALS) is a ubiquitous optimization algorithm for solving matrix and tensor factorization problems, including NMF.

• Algorithm: It optimizes the factor matrices by alternating between holding one set of factors fixed while solving a least squares problem for the other set. This process repeats until convergence.
• Application to NMF: For NMF, the standard least squares update is modified (e.g., via multiplicative update rules) to enforce non-negativity after each step. ALS is favored for its simplicity and effectiveness, especially in large-scale and distributed settings for problems like recommendation systems.

Robust Principal Component Analysis (Robust PCA) is a matrix decomposition technique that separates a data matrix M into a low-rank component L and a sparse component S (i.e., M = L + S).

• Goal: To recover the underlying low-rank structure even when the data is corrupted by outliers or gross errors (contained in S).
• Contrast with NMF: While both perform matrix decomposition, their objectives differ. Robust PCA explicitly models corruption and does not enforce non-negativity. NMF seeks a purely additive, parts-based representation under noise but is not designed to be robust to large, sparse corruptions. They address complementary problem domains.