Loading...
Nearly Optimal Vector Quantization via Linear Programming
Lin, Jyh-Han Vitter, Jeffrey Scott
Lin, Jyh-Han
Vitter, Jeffrey Scott
Citations
Altmetric:
Abstract
We present new vector quantization algorithms based on the theory devel-
oped in [LiV]. The new approach is to formulate a vector quantization problem
as a 0-1 integer linear program. We rst solve its relaxed linear program by
linear programming techniques. Then we transform the linear program solu-
tion into a provably good solution for the vector quantization problem. These
methods lead to the rst known polynomial-time full-search vector quanti-
zation 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.
Description
(c) 1992 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.
Date
1992
Journal Title
Journal ISSN
Volume Title
Publisher
IEEE
Research Projects
Organizational Units
Journal Issue
Keywords
Citation
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. http://dx.doi.org/10.1109/DCC.1992.227479