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.
(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.
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.
The University of Kansas prohibits discrimination on the basis of race, color, ethnicity, religion, sex, national origin, age, ancestry, disability, status as a veteran, sexual orientation, marital status, parental status, gender identity, gender expression and genetic information in the University’s programs and activities. The following person has been designated to handle inquiries regarding the non-discrimination policies: Director of the Office of Institutional Opportunity and Access, IOA@ku.edu, 1246 W. Campus Road, Room 153A, Lawrence, KS, 66045, (785)864-6414, 711 TTY.