Kernels on histograms through the transportation polytope
published: Feb. 25, 2007, recorded: August 2006, views: 302
Report a problem or upload filesIf 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.
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.
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !