Abstract
We consider the dictionary learning problem when observations are normalized histograms of features. Traditional non-negative matrix factorization (NMF) approaches using Euclidean or Kullback-Leibler fitting errors are often "blind" to feature similarities. We propose using the Wasserstein distance as a fitting error to leverage prior knowledge of feature relationships. Our method utilizes entropic regularization and Fenchel duality to create a scalable, smooth optimization framework. We demonstrate the effectiveness of this approach on face images and text documents, including cross-lingual topic modeling.
1. Introduction
Dictionary learning seeks to represent data as linear combinations of a few basis elements. In applications like computer vision or natural language processing, data is often represented as histograms. Standard loss functions like KL divergence treat each bin independently, ignoring the underlying geometry of the feature space. For example, a small spatial shift in an image or a synonym in a text document can lead to large reconstruction errors under standard metrics. The Wasserstein distance, or Earth Mover's Distance (EMD), addresses this by incorporating a ground metric, but its high computational cost has limited its adoption in NMF.
2. Smoothed Wasserstein NMF
To overcome computational barriers, we introduce a smoothed Wasserstein loss. The smoothing is achieved through entropic regularization, which replaces the hard constraints of the transport plan with a soft, entropy-penalized version. This allows the use of Sinkhorn's algorithm, which scales linearly with the number of features.
Furthermore, by formulating the problem through Fenchel duality, we avoid the non-smoothness of the original Wasserstein distance. We derive a dual objective with a closed-form gradient, enabling the use of efficient block-coordinate descent and projected gradient methods. This approach allows the dictionary to "move" mass across the feature space, capturing semantic or spatial relationships that are invisible to separable losses.
3. Experimental Results
We evaluated our method against standard NMF baselines across several datasets, focusing on both geometric recovery and computational efficiency.
3.1 Toy Data and Geometry
On toy Gaussian mixtures, Wasserstein NMF demonstrates a superior ability to recover the underlying data distribution compared to KL-based methods. While KL NMF produces fragmented basis elements, the Wasserstein approach recovers intuitive "blobs" that match the data's geometric structure.
3.2 Performance and Scalability
On the ORL face dataset, our method achieved a 20-90 second runtime, a significant improvement over the 20 minutes required by previous EMD-NMF implementations. In text classification tasks (BBCsport), Wasserstein NMF reduced the error rate to 5.4%, compared to 9.4% for KL-NMF and 12.8% for Euclidean NMF. The ground metric allows the model to understand that missing words in a document are semantically related to words present in the dictionary.
3.3 Cross-Lingual Topic Modeling
A key advantage of the Wasserstein loss is the ability to learn across different feature spaces. By using bilingual word embeddings as a ground metric, we successfully learned French topics from an English corpus. This demonstrates that the dictionary can be learned in a "target" space that differs from the "source" space.
4. Conclusion
The proposed smoothed Wasserstein NMF framework provides a scalable and geometrically-aware alternative to traditional dictionary learning. By adding a small amount of entropy, we turn a combinatorial problem into a matrix balancing problem, allowing us to scale to dimensions previously impossible for Wasserstein-based methods. While the problem remains biconvex and requires careful initialization, the speedups and accuracy gains on high-dimensional data are substantial. Future research will explore additional regularizers for dictionary sparsity and further optimizations for large-scale vocabularies.
Summary updated