Wasserstein k-means with sparse simplex projection
This work addresses the computational bottleneck of Wasserstein k-means for researchers and practitioners working with histogram data, offering an incremental improvement in speed.
This paper proposes SSPW k-means, a faster Wasserstein k-means algorithm for histogram data that reduces Wasserstein distance computations by shrinking data samples, centroids, and the ground cost matrix. It also dynamically reduces computational complexity by removing lower-valued data samples and using sparse simplex projection, all while maintaining clustering quality.
This paper presents a proposal of a faster Wasserstein $k$-means algorithm for histogram data by reducing Wasserstein distance computations and exploiting sparse simplex projection. We shrink data samples, centroids, and the ground cost matrix, which leads to considerable reduction of the computations used to solve optimal transport problems without loss of clustering quality. Furthermore, we dynamically reduced the computational complexity by removing lower-valued data samples and harnessing sparse simplex projection while keeping the degradation of clustering quality lower. We designate this proposed algorithm as sparse simplex projection based Wasserstein $k$-means, or SSPW $k$-means. Numerical evaluations conducted with comparison to results obtained using Wasserstein $k$-means algorithm demonstrate the effectiveness of the proposed SSPW $k$-means for real-world datasets