next up previous
Next: Design and Analysis of Up: DATA COMPRESSION Previous: Parallel Lossless Image Compression

   
Nearly Optimal Vector Quantization via Linear Programming

J.-H. Lin and J. S. Vitter. ``Nearly Optimal Vector Quantization via Linear Programming,'' Proceedings of the 1992 IEEE Data Compression Conference (DCC '92), Snowbird, UT, March 1992, 22-31.

Full text (gzip-compressed postscript)

Full text (Adobe pdf format)

We present new vector quantization algorithms based on the theory developed by the authors. The new approach is to formulate a vector quantization problem as a 0-1 integer linear program. We first solve its relaxed linear program by linear programming techniques. Then we transform the linear program solution into a provably good solution for the vector quantization problem. These methods lead to the first known polynomial-time full-search vector quantization codebook design algorithm and tree pruning algorithm with provable worst-case performance guarantees. We also introduce the notion of pseudo-random pruned tree-structured vector quantizers. Initial experimental results on image compression are very encouraging.



Jeff Vitter
2008-07-05