Nearly Optimal Vector Quantization via Linear Programming
View/ Open
Issue Date
1992Author
Lin, Jyh-Han
Vitter, Jeffrey Scott
Publisher
IEEE
Type
Article
Article Version
Scholarly/refereed, author accepted manuscript
Metadata
Show full item recordAbstract
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.
Collections
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
Items in KU ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
We want to hear from you! Please share your stories about how Open Access to this item benefits YOU.