Abstract
Standard Non-Negative Matrix Factorization (NMF) often fails to capture the geometric structure of data due to its reliance on Euclidean distance. This paper introduces SDNMF, a novel framework that incorporates Sinkhorn distance—an efficient approximation of Earth Mover’s Distance—into the NMF objective. By combining entropic regularization with graph-based manifold learning, SDNMF achieves superior robustness to local deformations and noise while maintaining computational efficiency.
Introduction
Non-Negative Matrix Factorization (NMF) is a fundamental technique for parts-based data representation, widely used for tasks like feature extraction and clustering. However, traditional NMF formulations typically employ $L_2$ (Euclidean) distance as a reconstruction loss function. This metric assumes feature independence, making it highly sensitive to local deformations; for instance, shifting an image by a single pixel can result in a large Euclidean distance despite the content remaining nearly identical. Furthermore, standard NMF often ignores the intrinsic manifold structure of high-dimensional data.
Methodology
The proposed SDNMF method addresses these limitations through two primary innovations:
Sinkhorn Distance Reconstruction
Instead of rigid Euclidean metrics, SDNMF utilizes the Sinkhorn distance. Sinkhorn distance provides a "soft" measure of dissimilarity by considering the cost of transporting mass between features (e.g., pixels) based on a ground metric. By applying entropic regularization, the authors transform the computationally expensive Earth Mover’s Distance (EMD) into a scalable matrix scaling problem. This allows the model to recognize semantic similarity even when data points are shifted or rotated.
Graph Regularization
To preserve the data's geometric structure, SDNMF incorporates a graph regularization term. A nearest-neighbor graph is constructed where edge weights are determined using the Sinkhorn distance. This ensures that the learned low-dimensional representations respect the natural clusters and manifolds present in the input space, making the model robust to noise and deformations.
Experimental Evaluation
The authors evaluated SDNMF on the COIL20 object dataset and Texture Mosaics. To rigorously test robustness, random translation noise was introduced to the COIL20 images, simulating real-world variability where objects may not be perfectly centered.
Key Results
Experimental results demonstrate that SDNMF significantly outperforms standard NMF and Graph-regularized NMF (GNMF) in clustering accuracy, particularly as noise levels increase. On the COIL20 dataset with a translation noise level of $\delta=4$, SDNMF achieved an accuracy of 23.15%, compared to 19.52% for standard NMF and 21.31% for GNMF.
Beyond accuracy, the most striking result is the computational efficiency. By using the Sinkhorn approximation, the authors achieved a massive speedup over previous EMD-based NMF methods, reducing iteration time from 23 minutes to just 2.9 seconds. This breakthrough makes optimal-transport-based matrix factorization practical for large-scale datasets.
Conclusion
SDNMF represents a significant advancement in parts-based learning. By integrating Sinkhorn distance and graph regularization, it provides a robust and efficient solution for decomposing data that lies on complex manifolds or contains local deformations. Future research may explore the use of landmark-based graph construction to further scale the method to massive datasets.
Summary updated