Quarterly of Applied Mathematics

Quarterly of Applied Mathematics

Online ISSN 1552-4485; Print ISSN 0033-569X

   
 
 

 

Shape recognition via Wasserstein distance


Authors: Wilfrid Gangbo and Robert J. McCann
Journal: Quart. Appl. Math. 58 (2000), 705-737
MSC: Primary 94A08; Secondary 28A35, 49Q20
DOI: https://doi.org/10.1090/qam/1788425
MathSciNet review: MR1788425
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The Kantorovich-Rubinstein-Wasserstein metric defines the distance between two probability measures $ \mu $ and $ \nu $ on $ {R^{d + 1}}$ by computing the cheapest way to transport the mass of $ \mu $ onto $ \nu $, where the cost per unit mass transported is a given function $ c\left( x, y \right)$ on $ {R^{2d + 2}}$. Motivated by applications to shape recognition, we analyze this transportation problem with the cost $ c\left( x, y \right) = {\left\vert {x - y} \right\vert^2}$ and measures supported on two curves in the plane, or more generally on the boundaries of two domains $ \Omega , \Lambda \subset {R^{d + 1}}$. Unlike the theory for measures that are absolutely continuous with respect to Lebesgue, it turns out not to be the case that $ \mu - a.e.x \in \partial \Omega $ is transported to a single image $ y \in \partial \Lambda $; however, we show that the images of $ x$ are almost surely collinear and parallel the normal to $ \partial \Omega $ at $ x$. If either domain is strictly convex, we deduce that the solution to the optimization problem is unique. When both domains are uniformly convex, we prove a regularity result showing that the images of $ x \in \partial \Omega $ are always collinear, and both images depend on $ x$ in a continuous and (continuously) invertible way. This produces some unusual extremal doubly stochastic measures.


References [Enhancements On Off] (What's this?)

  • [1] G. Alberti, On the structure of singular sets of convex functions, Calc. Var. Partial Differential Equations 2, 17-27 (1994) MR 1384392
  • [2] G. Alberti and L. Ambrosio, A geometrical approach to monotone functions in $ {R^{n}}$, Math. Z. 230, 259-316 (1999) MR 1676726
  • [3] Y. Brenier, Décomposition polaire et réarrangement monotone des champs de vecteurs, C. R. Acad. Sci. Paris Sér. I Math. 305, 805-808 (1987) MR 923203
  • [4] Y. Brenier, Polar factorization and monotone rearrangement of vector-valued functions, Comm. Pure Appl. Math. 44, 375-417 (1991) MR 1100809
  • [5] L. A. Caffarelli, The regularity of mappings with a convex potential, J. Amer. Math. Soc. 5, 99-104 (1992) MR 1124980
  • [6] L. A. Caffarelli, Boundary regularity of maps with convex potentials. II, Ann. of Math. (2) 144, 453-496 (1996) MR 1426885
  • [7] L. A. Caffarelli and R. J. McCann, Free boundary problems in optimal transport, in preparation
  • [8] F. H. Clarke, Optimization and Nonsmooth Analysis, John Wiley and Sons, New York, 1983 MR 709590
  • [9] D. S. Fry, Shape recognition using metrics on the space of shapes, Ph.D. thesis, Harvard University, 1993 MR 2690401
  • [10] W. Gangbo, An elementary proof of the polar factorization of vector-valued functions, Arch. Rational Mech. Anal. 128, 381-399 (1994) MR 1308860
  • [11] W. Gangbo and R. J. McCann, The geometry of optimal transportation, Acta Math. 177, 113-161 (1996) MR 1440931
  • [12] C. R. Givens and R. M. Shortt, A class of Wasserstein metrics for probability distributions, Michigan Math. J. 31, 231-240 (1984) MR 752258
  • [13] L. Kantorovich, On the translocation of masses, C. R. (Doklady) Acad. Sci. URSS (N.S.) 37, 199-201 (1942) MR 0009619
  • [14] L. V. Kantorovich and G. S. Rubinstein, On a functional space and certain extremum problems, Dokl. Akad. Nauk SSSR (N.S.) 115, 1058-1061 (1957) MR 0094707
  • [15] H. G. Kellerer, Duality theorems for marginal problems, Z. Wahrsch. Verwandte Gebiete 67, 399-432 (1984) MR 761565
  • [16] R. J. McCann, Existence and uniqueness of monotone measure-preserving maps, Duke Math. J. 80, 309-323 (1995) MR 1369395
  • [17] R. J. McCann, Equilibrium shapes for planar crystals in an external field, Comm. Math. Phys. 195, 699-723 (1998) MR 1641031
  • [18] D. Mumford, Mathematical theories of shape: Do they model perception, in Geometrical Methods of Computer Vision, vol. 1570 of the Proceedings of the Society for Photo-Optical Instrumentation Engineers, Bellingham, 1991, pp. 2 10
  • [19] S. T. Rachev, The Monge-Kantorovich mass transference problem and its stochastic applications, Theory Probab. Appl. 29, 647 676 (1984) MR 773434
  • [20] R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, 1972 MR 1451876
  • [21] L. Rüschendorf and S. T. Rachev, A characterization of random variables with minimum $ {L^{2}}$-distance, J. Multivariate Anal. 32, 48-54 (1990) MR 1035606
  • [22] T. L. Seethoff and R. C. Shiflett, Doubly stochastic measures with prescribed support, Z. Wahrsch. Verwandte Gebiete 41, 283-288 (1978) MR 0463402
  • [23] C. Smith and M. Knott, On the optimal transportation of distributions, J. Optim. Theory Appl. 52, 323-329 (1987) MR 879207
  • [24] L. N. Wasserstein, Markov processes over denumerable products of spaces describing large systems of automata, Problems of Information Transmission 5, 47-52 (1969) MR 0314115
  • [25] L. Zajíček, On the differentiability of convex functions in finite and infinite dimensional spaces, Czechoslovak Math. J. 29 (104), 340-348 (1979)

Similar Articles

Retrieve articles in Quarterly of Applied Mathematics with MSC: 94A08, 28A35, 49Q20

Retrieve articles in all journals with MSC: 94A08, 28A35, 49Q20


Additional Information

DOI: https://doi.org/10.1090/qam/1788425
Article copyright: © Copyright 2000 American Mathematical Society

American Mathematical Society