Structure preserving non-negative matrix factorization for dimensionality reduction

Zechao Li, Jing Liu, Hanqing LuCVIU 2013 · DOI

TL;DR

This paper introduces Structure Preserving Non-negative Matrix Factorization (SPNMF), a novel dimensionality reduction technique that goes beyond standard NMF by explicitly preserving both local data structure (affinity) and the separation of distant data points (repulsion). SPNMF achieves better clustering and classification performance by learning more discriminative and compact representations of data.

What Problem Does This Paper Address?

High-dimensional data is ubiquitous in fields like computer vision and information retrieval. Dimensionality reduction aims to map this data into a lower-dimensional space while preserving its inherent structure, which is crucial for tasks like clustering and classification. While Non-negative Matrix Factorization (NMF) is popular for its ability to learn part-based representations, it often overlooks the geometric structure of the data. Existing methods like Graph Regularized NMF (GNMF) attempt to preserve local structure but fail to adequately consider the repulsion between distant data points, potentially leading to distorted embeddings. This paper addresses this gap by proposing a method that simultaneously preserves local affinity, enforces distant repulsion, and promotes basis compactness for more robust dimensionality reduction.

Methods

The core of this paper is the Structure Preserving Non-negative Matrix Factorization (SPNMF) algorithm. SPNMF builds upon the NMF framework by incorporating three key constraints into its objective function:

  • Local Affinity: This constraint ensures that data points that are close in the original high-dimensional space remain close in the low-dimensional embedding. This is achieved using a graph regularization approach, similar to GNMF, where a weighted graph represents the affinity between data points.
  • Distant Repulsion: This novel constraint aims to ensure that data points far apart in the original space are also separated in the embedded space. This helps to prevent distant clusters from merging.
  • Basis Redundancy Elimination: This constraint promotes learning compact and non-redundant basis vectors. It encourages bases to be as orthogonal as possible and discourages bases from being further decomposed into more components.

The SPNMF objective function is then optimized using an iterative multiplicative update algorithm, for which the authors provide a proof of convergence.

Datasets

The paper evaluates SPNMF on six widely used image datasets:

  • Coil20: Contains images of 20 objects from varying angles.
  • PIE: Contains face images of 68 individuals under different lighting and expression conditions.
  • Yale: Contains face images of 15 individuals with different expressions/configurations.
  • ORL: Contains face images of 40 individuals with variations in lighting, facial expressions, and details.
  • UMIST: Contains images of 20 different people.
  • Binary Alphadigits (BA): Contains images of digits and capital letters.

Additionally, the authors use two synthetic toy datasets: one with two rings and another with two perpendicularly crossing lines, to visually demonstrate the effectiveness of their method.

Key Insights and Ideas

  • Beyond Local Affinity: The paper highlights that preserving only local affinity (as in GNMF) is insufficient. Explicitly enforcing distant repulsion is crucial for learning discriminative representations, especially for tasks like clustering.
  • The Power of Combined Constraints: SPNMF's success stems from the synergistic effect of combining local affinity, distant repulsion, and basis compactness. This multi-faceted approach leads to more robust and informative embeddings.
  • Basis Compactness Matters: The inclusion of basis redundancy elimination not only leads to more interpretable bases but also improves performance, outperforming methods that only consider sparseness or orthogonality.
  • NMF's Geometric Blindness: The paper implicitly reinforces that standard NMF, while good for part-based representation, is fundamentally limited by its lack of geometric awareness, making it less effective for tasks where data structure is paramount.

Key Results

  • Clustering Performance: SPNMF consistently outperforms other dimensionality reduction techniques, including PCA, NMF, and GNMF, on all six real-world datasets in terms of both Clustering Accuracy (AC) and Normalized Mutual Information (NMI). For example, on the Coil20 dataset, SPNMF achieved an AC of 73.1 ± 1.7%, outperforming GNMF (66.9 ± 2.0%) and NMF (58.5 ± 1.7%).
  • Classification Performance: SPNMF also demonstrates superior classification performance across various datasets and embedding dimensions, often outperforming GNMF and NMF, and being competitive with supervised methods like LDA.
  • Synthetic Data Visualization: Visualizations on toy datasets clearly show that SPNMF produces embeddings with less overlap between clusters compared to PCA, NMF, and GNMF, indicating better separability.
  • Convergence Speed: The multiplicative update algorithm for SPNMF converges quickly, typically within 100 iterations, making it computationally efficient.
  • Computational Cost: While SPNMF introduces some overhead compared to NMF, its computational cost is comparable to or better than GNMF, especially considering its superior performance.

Limitations and Future Work

  • Parameter Sensitivity: The paper acknowledges that SPNMF's performance can be sensitive to parameter settings, particularly for the neighborhood size (k₁ and k₂) and the regularization parameters (α, β, γ). While experiments are conducted to study this sensitivity, finding optimal parameters might require careful tuning.
  • Future Work: The authors suggest exploring more advanced constraints for basis representation, such as incorporating sparsity properties or leveraging label information for semi-supervised learning. They also aim to investigate more sophisticated regularization techniques to further enhance the model's ability to capture complex data structures.

Summary updated

BibTeX
@article{li2013structure,
  author = {Zechao Li and Jing Liu and Hanqing Lu},
  title = {{Structure preserving non-negative matrix factorization for dimensionality reduction}},
  journal = {Comput. Vis. Image Underst.},
  year = {2013},
  doi = {10.1016/j.cviu.2013.04.003},
}
Figure