Kernels on histograms through the transportation polytope

author: Marco Cuturi, Graduate School of Informatics, Kyoto University
published: Feb. 25, 2007,   recorded: August 2006,   views: 4894


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


For two integral histograms and of equal sum, the Monge-Kantorovich distance MK(r,c) between r and c parameterized by a d × d cost matrix T is the minimum of all costs <F,T> taken over matrices F of the transportation polytope U(r,c). Recent results suggest that this distance is not negative definite, and hence, through Schoenberg's well-known result, may not be a positive definite kernel for all t > 0. Rather than using directly MK to define a similarity between r and c, we present in this talk kernels on r and c based on the whole transportation polytope U(r,c). We prove that when r and c have binary counts, which is equivalent to stating that r and c depict clouds of points of equal size, the permanent of their Gram matrix induced by the cost matrix T is a positive definite kernel under favorable conditions on T. We also show that the volume of the polytope U(r,c), that is the number of integral transportation plans, is a positive definite quantity in r and c through the Robinson-Schensted-Knuth correspondence between transportation matrices and Young Tableaux.

See Also:

Download slides icon Download slides: mlss06tw_cuturi_khttp.pdf (796.6 KB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: