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:
- 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.
- 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.
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.
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