A Fast Non-Smooth Nonnegative Matrix Factorization for Learning Sparse Representation

Zuyuan Yang, Yu Zhang, Wei Yan, Yong Xiang, Shengli Xie

Abstract

Nonnegative Matrix Factorization (NMF) is a fundamental tool for parts-based data representation, yet it often struggles to produce sufficiently sparse results or suffers from slow convergence. This paper presents FNsNMF (Fast Non-Smooth Nonnegative Matrix Factorization), an algorithm designed to accelerate the learning of sparse representations. By establishing the Lipschitz continuity of the model's sub-problems and implementing a Nesterov-style proximal gradient acceleration, FNsNMF achieves a nonlinear convergence rate of $O(1/k^2)$. Experimental results on synthetic and facial image datasets demonstrate that FNsNMF significantly outperforms traditional non-smooth NMF in speed while maintaining or improving sparsity and classification accuracy.

Introduction

Nonnegative Matrix Factorization (NMF) has become a cornerstone of machine learning, particularly for tasks requiring the decomposition of complex data into interpretable "parts," such as facial features or document topics. However, standard NMF often fails to produce the high degree of sparsity required for clear interpretability. To address this, researchers previously developed Non-smooth NMF (NsNMF), which utilizes a "non-smoothness" matrix to enforce sparser, more distinct feature extraction.

While NsNMF yields high-quality sparse representations, its reliance on multiplicative update rules leads to a slow linear convergence rate. This computational bottleneck makes NsNMF impractical for large-scale modern datasets. This paper introduces FNsNMF to bridge the gap between high-quality sparsity and computational efficiency.

Methodology: Accelerating Sparsity

The FNsNMF algorithm reformulates the factorization problem into a series of convex sub-problems. The acceleration is achieved through two primary mathematical advancements:

  1. Lipschitz Continuity Proof: The authors provide a rigorous mathematical proof that the gradients of the NsNMF cost functions are Lipschitz continuous. This property ensures that the function's slope changes predictably, enabling the use of more aggressive optimization steps without compromising stability.
  2. Proximal Gradient Acceleration: Moving beyond traditional multiplicative updates, FNsNMF employs a proximal function integrated with a Nesterov-style acceleration scheme. By maintaining a "momentum" sequence, the algorithm navigates the optimization landscape more efficiently, shifting the convergence rate from a linear crawl to a nonlinear $O(1/k^2)$ rate.

Experimental Validation

The performance of FNsNMF was evaluated across three distinct data environments:

  • Synthetic Data: Rank-50 matrices were used to benchmark convergence speed and error reduction under controlled settings.
  • CBCL Face Database: 2,429 facial images were used to test the algorithm's ability to learn localized "parts" (e.g., eyes, noses).
  • Cohn-Kanade (CK) Facial Expression Database: 486 image sequences were used to evaluate the utility of learned sparse features in a real-world classification task.

Performance and Convergence

A critical finding of this research is that the trade-off between sparsity and speed is not mandatory. FNsNMF consistently reached stable solutions significantly faster than its predecessors. For instance, on the CBCL dataset, FNsNMF achieved convergence in approximately 15 seconds, compared to over 130 seconds for the original NsNMF—a nearly ninefold speedup.

Figure 6: Convergence comparison showing Error (e) vs. CPU Seconds (t). FNsNMF demonstrates rapid error reduction compared to standard NsNMF.

As shown in the convergence plots, FNsNMF (marked with asterisks) maintains a low error rate while requiring significantly less computation time than the standard NsNMF (inverted triangles).

Key Results and Insights

  • Superior Sparsity and Accuracy: FNsNMF produced sparser factor matrices ($S_W$ and $S_H$) than standard NMF and other accelerated variants. This increased sparsity translated directly into better performance; when used with a Support Vector Machine (SVM) for facial expression classification, FNsNMF achieved an accuracy of 91.35%, surpassing both standard NMF (89.27%) and the original NsNMF (90.46%).
  • Mathematical Rigor: The proof of the Lipschitz constant was the key "unlock" that allowed the application of advanced optimization techniques previously thought inapplicable to non-smooth models.
  • Interpretability: The results reinforce that sparsity is vital for feature salience. By focusing on non-overlapping features, the model becomes more robust for downstream classification tasks.

Conclusion and Future Directions

FNsNMF represents a significant advancement in sparse matrix factorization, proving that high-performance optimization can be applied to non-smooth models to achieve both speed and interpretability. Future work will focus on analyzing the stationarity of solutions in complex scenarios and exploring "block multi-convex" structures to handle more intricate constraints. Additionally, the authors aim to refine the framework to better distinguish between common and individual features within datasets.

Reference: Yang, Z., Zhang, Y., Yan, W., Xiang, Y., & Xie, S. (2016). A Fast Non-Smooth Nonnegative Matrix Factorization for Learning Sparse Representation. IEEE Access, 4, 5161-5168.

Summary updated

Abstract

Nonnegative matrix factorization (NMF) is a hot topic in machine learning and data processing. Recently, a constrained version, non-smooth NMF (NsNMF), shows a great potential in learning meaningful sparse representation of the observed data. However, it suffers from a slow linear convergence rate, discouraging its applications to large-scale data representation. In this paper, a fast NsNMF (FNsNMF) algorithm is proposed to speed up NsNMF. In the proposed method, it first shows that the cost function of the derived sub-problem is convex and the corresponding gradient is Lipschitz continuous. Then, the optimization to this function is replaced by solving a proximal function, which is designed based on the Lipschitz constant and can be solved through utilizing a constructed fast convergent sequence. Due to the usage of the proximal function and its efficient optimization, our method can achieve a nonlinear convergence rate, much faster than NsNMF. Simulations in both computer generated data and the real-world data show the advantages of our algorithm over the compared methods.
BibTeX
@article{yang2016fast,
  author = {Zuyuan Yang and Yu Zhang and Wei Yan and Yong Xiang and Shengli Xie},
  title = {{A Fast Non-Smooth Nonnegative Matrix Factorization for Learning Sparse Representation}},
  journal = {IEEE Access},
  year = {2016},
  doi = {10.1109/access.2016.2605704},
}
Figure