ALGORITHMIC APPROACH TO OPTIMAL MEAN-SQUARE QUANTIZATION
| dc.contributor.author | Wu, Xiaolin | eng |
| dc.date.accessioned | 2008-05-20T23:28:05Z | |
| dc.date.available | 2008-05-20T23:28:05Z | |
| dc.date.computerscience | 1999-05-27 | eng |
| dc.date.issued | 1988-07-01 | eng |
| dc.description.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. | eng |
| dc.description.notes | We are currently acquiring citations for the work deposited into this collection. We recognize the distribution rights of this item may have been assigned to another entity, other than the author(s) of the work.If you can provide the citation for this work or you think you own the distribution rights to this work please contact the Institutional Repository Administrator at digitize@ucalgary.ca | eng |
| dc.identifier.department | 1988-337-49 | eng |
| dc.identifier.doi | http://dx.doi.org/10.11575/PRISM/31265 | |
| dc.identifier.uri | http://hdl.handle.net/1880/46511 | |
| dc.language.iso | Eng | eng |
| dc.publisher.corporate | University of Calgary | eng |
| dc.publisher.faculty | Science | eng |
| dc.subject | Computer Science | eng |
| dc.title | ALGORITHMIC APPROACH TO OPTIMAL MEAN-SQUARE QUANTIZATION | eng |
| dc.type | unknown | |
| thesis.degree.discipline | Computer Science | eng |