Browsing by Author "Wu, Xiaolin"
Now showing 1 - 3 of 3
Results Per Page
Sort Options
- ItemOpen AccessALGORITHMIC APPROACH TO OPTIMAL MEAN-SQUARE QUANTIZATION(1988-07-01) Wu, XiaolinThis 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.
- ItemOpen AccessAlgorithmic approaches to optimal mean-square quantization(1988) Wu, Xiaolin; Rokne, Jon G.
- ItemOpen AccessA FAST K-MEANS TYPE CLUSTERING ALGORITHM(1985-06-01) Wu, Xiaolin; Witten, Ian H.This paper describes a new $k$-means type clustering algorithm which gives excellent results for a moderate computational cost. It is particularly suitable for partitioning large data sets into a number of clusters where the conventional $k$-means algorithm becomes computationally unmanageable. While it does not guarantee to reach a global optimum, its performance in practice is very good indeed, as demonstrated by theoretical analysis and experiments on color image data.