Technical Report CS-2005-15

Title: Greedy Aggregation for Vector Quantization
Authors: Yair Koren, Irad Yavneh
Abstract: Vector quantization is a classical problem that appears in many fields. Unfortunately, the quantization problem is generally non-convex, and therefore affords many local minima. The main problem is finding an initial approximation that is close to a ``good'' local minimum. Once such an approximation is found, the Lloyd--Max method may be used to reach a local minimum near it. In recent years, much improvement has been made with respect to reducing the computational costs of quantization algorithms, whereas the task of finding better initial approximations received somewhat less attention. We present a novel greedy algorithm for the vector quantization problem. The algorithm begins by allocating a large number of representation levels throughout the input domain and thereafter iteratively aggregates pairs of representation levels and replaces them by a single one. The pair of representation levels that is aggregated is the one yielding the minimal increase in distortion among all such pairs. Our method achieves better solutions than other contemporary methods such as LBG. In addition, its computational complexity is low, typically quantizing data in time that is equivalent to just a few Lloyd--Max iterations. When quantizing signals with sparse and patchy histograms, e.g. cartoons, the improvement in distortion relative to LBG may be arbitrarily large.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2005
To the main CS technical reports page

Computer science department, Technion