Optimal order reduction of probability distributions by maximizing mutual information
Mathukumalli Vidyasagar · 2011
In a companion paper [16], we defined a metric distance between two probability distributions φ, ψ defined on sets of different cardinality, called the variation of information metric d. In this paper we study of problem of finding an optimal reduced-order approximation in the variation of information metric. Let φ denote the probability distribution of high dimension that is to be approximated. It is shown first that any optimal approximation of φ must be an aggregation of φ. Then it is shown that any optimal aggregation of φ is one that has maximum entropy. Using these two results, we then formulate the problem of optimal order reduction as a nonstandard bin-packing problem with overstuffing. Unfortunately this problem is NP-hard. So a greedy algorithm is presented to solve this problem, and an upper bound on its performance is presented. The application of the greedy algorithm is illustrated via a large example.