Fast Robust Non-Negative Matrix Factorization for Large-Scale Human Action Data Clustering

De Wang, Feiping Nie, Heng HuangIJCAI 2016 · OpenReview

Abstract: Human action recognition is critical for various applications, yet data noise and outliers frequently degrade clustering performance. Traditional Non-negative Matrix Factorization (NMF) and Tri-Factorization (NMTF) models often fail to achieve optimal results in the presence of such anomalies. This paper proposes three novel NMF and NMTF models designed for robustness against outliers. By deriving efficient algorithms that utilize binary indicator matrices and median-based optimization, the proposed methods achieve convergence speeds comparable to K-means and scalability for large-scale datasets. Experimental evaluations on synthetic and real-world datasets demonstrate that these methods consistently outperform existing NMF/NMTF techniques in both clustering accuracy and computational efficiency.

Introduction

Non-Negative Matrix Factorization (NMF) is a fundamental technique in data science, widely applied in fields ranging from computer vision to topic modeling. However, standard NMF implementations face two significant hurdles: extreme sensitivity to outliers and slow convergence on large-scale datasets. Researchers from the University of Texas at Arlington have developed a new framework to address these limitations, creating algorithms that are as robust as median-based statistics and as fast as the $K$-means algorithm.

Robust Methodology

The core innovation lies in the introduction of three models: RFNMF_L1, RFNMF, and RFNMTF (Robust Fast Non-negative Matrix Tri-Factorization). These models depart from traditional NMF in two critical ways:

  1. Robust Loss Functions: Instead of minimizing the squared-error (Frobenius norm), which disproportionately weights large outliers, the authors employ the $\ell_1$-norm (absolute error) and the $\ell_{2,1}$-norm. This shift effectively changes the underlying noise assumption from Gaussian to Laplacian, making the model far less susceptible to data anomalies.
  2. Hard Indicator Matrices: Traditional models use continuous "soft" indicators. The proposed methods utilize "hard" binary indicators ($0$ or $1$) directly within the optimization process. This allows the algorithm to replace intensive matrix multiplications with a $K$-means-like assignment step, significantly boosting speed.
Clustering results on synthetic data with outliers.

The realization that solving for cluster centroids under an $\ell_1$ loss is equivalent to finding the sample median provides a strong theoretical foundation for the observed empirical success.

Performance and Scalability

The models were rigorously tested against five real-world datasets: DIGIT, HumanEva, YouTube Action, UCF, and KTH. These datasets represent a variety of challenges, from handwritten digits to complex human activities in cluttered video backgrounds.

The results show a clear advantage for the proposed robust methods. In terms of Accuracy, Normalized Mutual Information (NMI), and Purity, the RFNMF variants consistently outperformed standard NMF, Semi-NMF, and previous robust iterations like RNMF.

Performance metrics and convergence rates across multiple datasets.

Beyond accuracy, the speedup is remarkable. For instance, on the YouTube dataset, standard NMF required 366 seconds to converge, whereas RFNMF_L1 achieved better results in just 3.7 seconds—a 100x improvement. The convergence plots indicate that these models reach a stable objective value in significantly fewer iterations than traditional multiplicative update rules.

Conclusion

By integrating robust statistics with efficient binary optimization, this work provides a scalable solution for clustering large-scale, noisy human action data. While the algorithms are sensitive to initial conditions, similar to $K$-means, their efficiency allows for multiple random restarts to ensure high-quality results. Future work may explore deterministic initialization strategies to further improve the stability of these fast, robust algorithms.

Summary updated

Abstract

Human action recognition is important in improving human life in various aspects. However, the outliers and noise in data often bother the clustering tasks. Therefore, there is a great need for the robust data clustering techniques. Nonnegative matrix factorization (NMF) and Nonnegative Matrix Tri-Factorization (NMTF) methods have been widely researched these years and applied to many data clustering applications. With the presence of outliers, most previous NMF/NMTF models fail to achieve the optimal clustering performance. To address this challenge, in this paper, we propose three new NMF and NMTF models which are robust to outliers. Efficient algorithms are derived, which converge much faster than previous NMF methods and as fast as K-means algorithm, and scalable to large-scale data sets. Experimental results on both synthetic and real world data sets show that our methods outperform other NMF and NMTF methods in most cases, and in the meanwhile, take much less computational time.
BibTeX
@inproceedings{wang2016fast,
  author = {De Wang and Feiping Nie and Heng Huang},
  title = {{Fast Robust Non-Negative Matrix Factorization for Large-Scale Human Action Data Clustering}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=SkbPkrGdWS},
}
Figure