Deterministic Annealing for Clustering: Tutorial and Computational Aspects

The deterministic annealing (DA) method, used for the solution of several nonconvex problems, offers the ability to avoid shallow local minima of a given cost surface and the ability to minimize the cost function even when there are many local minima. The method is established in a probabilistic framework through basic information-theoretic techniques such as maximum entropy and random coding. It arises naturally in the context of statistical mechanics by the emulation of a physical process whereby a solid is slowly cooled and at zero temperature assumes its minimum energy configuration. In this paper, we first present some background material on the DA method and its connections to statistical physics and rate-distortion theory. A computational complexity analysis is then presented for a given temperature schedule. The case study focuses on the geometric cooling law T (t) = rho T (t-1); 0 < rho < 1, where T (t) is the temperature at time t.