Dimension Reduction Taxonomy - 10. Non-Negative Matrix Factorization (NMF)

10. Non-Negative Matrix Factorization (NMF) and Dictionary Learning

Non-Negative Matrix Factorization (NMF) factorizes a non-negative matrix V into non-negative matrices W (basis) and H (coefficients): $V\approx WH$. This parts-based representation is highly interpretable and is standard for topic modeling and facial feature extraction.

This figure shows the mathematical factorization that NMF performs. The data matrix V (size n × p, where n is samples and p is features) is decomposed into W (n × k, the basis or dictionary) and H (k × p, the coefficients). The key constraint is that all three matrices must be non-negative (W ≥ 0, H ≥ 0). This non-negativity leads to a parts-based representation because there are no subtractions; everything is additive. For example, if V represents a set of face images, W might learn "basis faces" like eyes, noses, and mouths, and H would represent how these parts are combined to form each face. This additive nature makes NMF highly interpretable, as the components often correspond to semantically meaningful parts. For text data, W can represent topics (e.g., "sports," "politics," "technology"), and H represents the topic distribution for each document. NMF is a powerful tool for dimensionality reduction because the rank k is typically much smaller than p, reducing the number of features to a manageable, interpretable set.

10.1 Mathematical Formulation

NMF solves:

subject to $W,H\ge 0$. Multiplicative update rules:

The parameter k dictates the reduced dimension.

The multiplicative updates are derived from the gradient of the Frobenius norm and are guaranteed to converge to a local minimum. They are simple to implement and maintain non-negativity. However, NMF is sensitive to initialization and can converge to different local minima. Common initialization methods include random initialization, SVD-based initialization, and non-negative double singular value decomposition (NNDSVD). The choice of k is often guided by the desired level of compression or by cross-validation for downstream tasks. NMF has been extended to handle missing data and to incorporate sparsity constraints, making it a versatile tool.

10.2 Dictionary Learning and Sparse Coding

Sparse Dictionary Learning imposes sparsity on H:

Algorithms like OMP (greedy) or Lasso solve sparse coding; KSVD updates the dictionary.

Dictionary learning goes beyond NMF by allowing an overcomplete basis (k > p) and forcing sparse coefficients. This is powerful for signal processing tasks like image denoising, inpainting, and compression. The sparse representation captures the essential structure with few non-zero coefficients, making it robust and interpretable. The alternating optimization (sparse coding and dictionary update) is computationally efficient and can be applied to large datasets. KSVD is a popular dictionary learning algorithm that updates each dictionary atom and the corresponding coefficients sequentially. Sparse coding is also used in feature learning for deep networks, where sparse representations can improve classification performance.

Applications

• Topic modeling in text documents.
• Image feature extraction.
• Hyperspectral unmixing.
• Recommendation systems.

Strengths and limitations