MDL Principle for Robust Vector Quantisation

Abstract

We address the problem of finding the optimal number of reference vectors for vector quantisation from the point of view of the Minimum Description Length (MDL) principle. We formulate vector quantisation in terms of the MDL principle, and then derive different instantiations of the algorithm, depending on the coding procedure. Moreover, we develop an efficient algorithm (similar to EM-type algorithms) for optimising the MDL criterion. In addition, we use the MDL principle to increase the robustness of the training algorithm, namely, the MDL principle provides a criterion to decide which data points are outliers. We illustrate our approach on 2D clustering problems (in order to visualise the behaviour of the algorithm), and present applications on image coding. Finally, we outline various ways to extend the algorithm.