Distances and kernels based on cumulative distribution functions - Emerging Trends in Image Processing, Computer Vision, and Pattern Recognition - page 472

The computation of the distance d p ( F , G ) is straightforward. For a discrete dataset of size
n , the complexity for computing the distance is O ( n ). On the other hand, the computation of
earth mover's distance requires the Hungarian algorithm ([ 10 ] ) with a complexity of O ( n 3 ).
4 Experimental results and discussions
The CDF-based kernels and distances can be effective on continuous distributions as well.
A Gaussian mixture distribution ([ 11 ] ) and its variations, shown in Figure 3 , are used to test
the kernel functions. The first chart shows the original Gaussian mixture. The other two dis-
tributions are obtained by moving the middle mode. Clearly the second distribution is much
closer to the original distribution than the third one.
FIGURE 3 A Gaussian mixture and variations.
Indexed in the same order as in Figure 3 , the Bhatacharyya kernel matrix for the three dis-
tributions is:
The Bhatacharyya kernel did not clearly distinguish the second and the third distributions
when comparing to the original. There is no significant difference between the kernel values
k 12 and k 13 , which measure the similarities between the original distribution and the other two
perturbed distributions.
The kernel matrix of our proposed kernel is: