Quantization complexity and training sample size in detection
Demetrios Kazakos · IEEE Transactions on Information Theory · 1978
For thek-hypothesis detection problem, it is shown that, among thek-classes of probability density functions withmfixed quantiles, histograms achieve the least favorable performance as measured by the probability of correct detection and Chernoff distance. It is assumed that themcell probabilities are estimated usingntraining samples per class. With the aid of the estimated cell probabilities, new observations are processed. A distribution-free upper bound to the probability of\epsilon-deviation between the actual probability of correct detection and the theoretical (known quantiles) probability is derived as a function of(m,n,\epsilon,k,u_{o}), whereu_{o}is a uniform upper bound to the true class densities. The bound converges exponentially to zero asn \rightarrow \infty. Exponential convergence is obtained by choosingm = n^{\alpha}, 0 < \alpha < 1. Hence, the rulem = n^{\alpha}answers the long standing question of how to relatemandnin a distribution-free manner. The question of the optimal choice of a is also discussed.