  In this paper, we investigate mutual information as a cost function for
clustering, and show in which cases hard, i.e., deterministic, clusters are
optimal. Using convexity properties of mutual information, we show that certain
formulations of the information bottleneck problem are solved by hard clusters.
Similarly, hard clusters are optimal for the information-theoretic
co-clustering problem that deals with simultaneous clustering of two dependent
data sets. If both data sets have to be clustered using the same cluster
assignment, hard clusters are not optimal in general. We point at interesting
and practically relevant special cases of this so-called pairwise clustering
problem, for which we can either prove or have evidence that hard clusters are
optimal. Our results thus show that one can relax the otherwise combinatorial
hard clustering problem to a real-valued optimization problem with the same
global optimum.
