  This paper presents an algorithm to solve the Soft k-Means problem globally.
Unlike Fuzzy c-Means, Soft k-Means (SkM) has a matrix factorization-type
objective and has been shown to have a close relation with the popular
probability decomposition-type clustering methods, e.g., Left Stochastic
Clustering (LSC). Though some work has been done for solving the Soft k-Means
problem, they usually use an alternating minimization scheme or the projected
gradient descent method, which cannot guarantee global optimality since the
non-convexity of SkM. In this paper, we present a sufficient condition for a
feasible solution of Soft k-Means problem to be globally optimal and show the
output of the proposed algorithm satisfies it. Moreover, for the Soft k-Means
problem, we provide interesting discussions on stability, solutions
non-uniqueness, and connection with LSC. Then, a new model, named Minimal
Volume Soft k-Means (MVSkM), is proposed to address the solutions
non-uniqueness issue. Finally, experimental results support our theoretical
results.
