Deterministic annealing for clustering: Tutorial and computational aspects

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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) = ρT (t-1); 0 < ρ < 1, where T(t) is the temperature at time t.

Original languageEnglish (US)
Title of host publicationACC 2015 - 2015 American Control Conference
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2906-2911
Number of pages6
ISBN (Electronic)9781479986842
DOIs
StatePublished - Jul 28 2015
Event2015 American Control Conference, ACC 2015 - Chicago, United States
Duration: Jul 1 2015Jul 3 2015

Publication series

NameProceedings of the American Control Conference
Volume2015-July
ISSN (Print)0743-1619

Other

Other2015 American Control Conference, ACC 2015
CountryUnited States
CityChicago
Period7/1/157/3/15

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Deterministic annealing for clustering: Tutorial and computational aspects'. Together they form a unique fingerprint.

  • Cite this

    Parekh, P. M., Katselis, D., Beck, C. L., & Salapaka, S. M. (2015). Deterministic annealing for clustering: Tutorial and computational aspects. In ACC 2015 - 2015 American Control Conference (pp. 2906-2911). [7171176] (Proceedings of the American Control Conference; Vol. 2015-July). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ACC.2015.7171176