ALGORITHMIC APPROACH TO OPTIMAL MEAN-SQUARE QUANTIZATION
Date
1988-07-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
Computer Science