A Metric Between Probability Distributions on Finite Sets of Different Cardinalities and Applications to Order Reduction

Details A Metric Between Probability Distributions on Finite Sets of Different Cardinalities and Applications to Order Reduction A Metric Between Probability Distributions on Finite Sets of Different Cardinalities and Applications to Order Reduction

2011-04-23

arxiv.org/abs/1104.4521v2

Computer Science

Systems and Control

32 pages, no figures

Scientific paper

With increasing use of digital control it is natural to view control inputs and outputs as stochastic processes assuming values over finite alphabets rather than in a Euclidean space. As control over networks becomes increasingly common, data compression by reducing the size of the input and output alphabets without losing the fidelity of representation becomes relevant. This requires us to define a notion of distance between two stochastic processes assuming values in distinct sets, possibly of different cardinalities. If the two processes are i.i.d., then the problem becomes one of defining a metric between two probability distributions over distinct finite sets of possibly different cardinalities. This is the problem addressed in the present paper. A metric is defined in terms of a joint distribution on the product of the two sets, which has the two given distributions as its marginals, and has minimum entropy. Computing the metric exactly turns out to be NP-hard. Therefore an efficient greedy algorithm is presented for finding an upper bound on the distance. This problem also turns out to be NP-hard, so again a greedy algorithm is constructed for finding a suboptimal reduced order approximation. Taken together, all the results presented here permit the approximation of an i.i.d. process over a set of large cardinality by another i.i.d. process over a set of smaller cardinality. In future work, attempts will be made to extend this work to Markov processes over finite sets.

Affiliated with

Also associated with

No associations

Rating

A Metric Between Probability Distributions on Finite Sets of Different Cardinalities and Applications to Order Reduction does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Metric Between Probability Distributions on Finite Sets of Different Cardinalities and Applications to Order Reduction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Metric Between Probability Distributions on Finite Sets of Different Cardinalities and Applications to Order Reduction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-483817