Please use this identifier to cite or link to this item: http://hdl.handle.net/1880/46511
Title: ALGORITHMIC APPROACH TO OPTIMAL MEAN-SQUARE QUANTIZATION
Authors: Wu, Xiaolin
Keywords: Computer Science
Issue Date: 1-Jul-1988
Abstract: This thesis is concerned with algorithmic approaches to the optimal quantization under the mean-square error measure, a classical and fundamental problem in digital signal processing and information theory. Many new properties of this special nonlinear programming problem have been verified. These properties provide rationales for developing much more efficient computer algorithms than the current ones for optimal mean-square quantization. The major contributions of the thesis to its field are: a family of new algorithms which can generate the globally optimal $K$-level quantizer for the least mean-square error, catering to any discrete amplitude density function of $N$ entries, in $O(K N lg N)$ time (the worst case) and $O(N)$ space, and a real-time quantization algorithm which can satisfactorily approximate the optimal $K$-level quantizers in only $O(N)$ time and $O(N)$ space. It is also demonstrated that the global and local approaches to optimal quantization can enhance each other to obtain a fast and exact solution to the problem. Through the development of efficient global algorithms for optimal mean-square quantization, the thesis presents the first example how the three well-known algorithmic techniques, divide-and-conquer, dynamic programming and backtracking, can be combined to achieve a higher algorithm efficiency than any of these techniques alone, contributing a new effective methodology to the field of algorithm design and analysis.
URI: http://hdl.handle.net/1880/46511
Appears in Collections:Technical Reports

Files in This Item:
File Description SizeFormat 
1988-337-49.pdf10.11 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.