Thesis Title

Quantization Points of Densities and Samples

Summer 2000

Degree

Master of Science in Mathematics

Mathematics

Yingcai Su

Mathematics

Abstract

Representing a continuous random variable by a finite number of values is known as quantization. Given a probability density function (p.d.f.) or a random sample, the quantization problem is to choose those k values (or points) that will best represent the given p.d.f. or sample. The optimal quanitization points (also known as principal points or representative points) are those that minimize loss of information, usually measured in terms of mean rth power absolute error. When mean square error is used, principal points occur at the conditional means of the regions they represent. Principal points of location-scale family densities can be found using a simple linear transformation. If the p.d.f. of a random variable is symmetric and strongly unimodal, the variable has a unique set of two principal points, and the points are symmetric about the mean. We outline two algorithms for finding principal points for random variables with known densities. We discuss asymptotically optimal quanizers. These quantizers are easier to find than optimal quantizers and perform well for moderate to large values of k. Representative points can be estimated for sample data. We discuss both parametric and non-parametric cases. Quantizer mismatch occurs when a quantizer is based on one density and the random variable has a different density. Given a random sample, we can estimate the underlying density and find representative points based on this estimated density, or we can use an algorithm to estimate a set of representative points. We introduce a closest pair algorithm that identifies clusters in the sample and uses these clusters to estimate representative points. Given a sample of size n, the algorithm provides a set of k points in n - k iterations. We use the algorithm to find points for three samples and state the results. Several measures of quantizer performance are also discussed.