Document Open Access Logo

Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost

Authors Alexandr Andoni, Assaf Naor, Ofer Neiman

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.83.pdf
  • Filesize: 0.64 MB
  • 14 pages

Document Identifiers

Author Details

Alexandr Andoni
Assaf Naor
Ofer Neiman

Cite As Get BibTex

Alexandr Andoni, Assaf Naor, and Ofer Neiman. Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 83:1-83:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.83

Abstract

Transportation cost metrics, also known as the Wasserstein distances W_p, are a natural choice for defining distances between two pointsets, or distributions, and have been applied in numerous fields. From the computational perspective, there has been an intensive research effort for understanding the W_p metrics over R^k, with work on the W_1 metric (a.k.a earth mover distance) being most successful in terms of theoretical guarantees. However, the W_2 metric, also known as the root-mean square (RMS) bipartite matching distance, is often a more suitable choice in many application areas, e.g. in graphics. Yet, the geometry of this metric space is currently poorly understood, and efficient algorithms have been elusive. For example, there are no known non-trivial algorithms for nearest-neighbor search or sketching for this metric.

In this paper we take the first step towards explaining the lack of efficient algorithms for the W_2 metric, even over the three-dimensional Euclidean space R^3. We prove that there are no meaningful embeddings of W_2 over R^3 into a wide class of normed spaces, as well as that there are no efficient sketching algorithms for W_2 over R^3 achieving constant approximation. For example, our results imply that: 1) any embedding into L1 must incur a distortion of Omega(sqrt(log(n))) for pointsets of size n equipped with the W_2 metric; and 2) any sketching algorithm of size s must incur Omega(sqrt(log(n))/sqrt(s)) approximation. Our results follow from a more general statement, asserting that W_2 over R^3 contains the 1/2-snowflake of all finite metric spaces with a uniformly bounded distortion. These are the first non-embeddability/non-sketchability results for W_2.

Subject Classification

Keywords
  • Transportation metric
  • embedding
  • snowflake
  • sketching

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Pankaj Agarwal and Kasturi Varadarajan. A near-linear constant-factor approximation for euclidean bipartite matching? In Proceedings of the Twentieth Annual Symposium on Computational Geometry, SCG'04, pages 247-252, New York, NY, USA, 2004. ACM. URL: http://dx.doi.org/10.1145/997817.997856.
  2. Pankaj K. Agarwal, Alon Efrat, and Micha Sharir. Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications. SIAM Journal on Computing, 29(3):912-953, 2000. Google Scholar
  3. Pankaj K. Agarwal and R. Sharathkumar. Approximation algorithms for bipartite matching with metric and geometric costs. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC'14, pages 555-564, New York, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2591796.2591844.
  4. Alexandr Andoni, Khanh Do Ba, Piotr Indyk, and David Woodruff. Efficient sketches for Earth-Mover Distance, with applications. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), 2009. Google Scholar
  5. Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer. Earth mover distance over high-dimensional spaces. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 343-352, 2008. Previously ECCC Report TR07-048. Google Scholar
  6. Alexandr Andoni, Robert Krauthgamer, and Ilya Razenshteyn. Sketching and embedding are equivalent for norms. In Proceedings of the Symposium on Theory of Computing (STOC), 2015. Full version at URL: http://arxiv.org/abs/1411.2577.
  7. Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev. Parallel algorithms for geometric graph problems. In Proceedings of the Symposium on Theory of Computing (STOC), 2014. Full version at http://arxiv.org/abs/1401.0042. URL: http://dx.doi.org/10.1145/2591796.2591805.
  8. T. Austin and A. Naor. On the bi-Lipschitz structure of Wasserstein spaces. In preparation, 2016. Google Scholar
  9. Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. J. Comput. Syst. Sci., 68(4):702-732, 2004. Previously in FOCS'02. Google Scholar
  10. Yair Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996), pages 184-193. IEEE Comput. Soc. Press, Los Alamitos, CA, 1996. URL: http://dx.doi.org/10.1109/SFCS.1996.548477.
  11. Nicolas Bonneel, Julien Rabin, Gabriel Peyré, and Hanspeter Pfister. Sliced and radon wasserstein barycenters of measures. Journal of Mathematical Imaging and Vision, 51(1):22-45, 2015. Google Scholar
  12. Nicolas Bonneel, Michiel Van De Panne, Sylvain Paris, and Wolfgang Heidrich. Displacement interpolation using lagrangian mass transport. ACM Transactions on Graphics (TOG), 30(6):158, 2011. Google Scholar
  13. J. Bourgain. The metrical interpretation of superreflexivity in Banach spaces. Israel J. Math., 56(2):222-230, 1986. URL: http://dx.doi.org/10.1007/BF02766125.
  14. Moses Charikar. Similarity estimation techniques from rounding. In Proceedings of the Symposium on Theory of Computing (STOC), pages 380-388, 2002. Google Scholar
  15. Marco Cuturi and Arnaud Doucet. Fast computation of wasserstein barycenters. In Proceedings of The 31st International Conference on Machine Learning, pages 685-693, 2014. Google Scholar
  16. Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. Mechanism design via optimal transport. In Proc. of the 14th ACM Conf. on Electronic Commerce, EC'13, pages 269-286, New York, NY, USA, 2013. ACM. URL: http://dx.doi.org/10.1145/2482540.2482593.
  17. Guy David and Stephen Semmes. Fractured fractals and broken dreams, volume 7 of Oxford Lecture Series in Mathematics and its Applications. The Clarendon Press, Oxford University Press, New York, 1997. Self-similar geometry through metric and measure. Google Scholar
  18. Fernando de Goes, Katherine Breeden, Victor Ostromoukhov, and Mathieu Desbrun. Blue noise through optimal transport. ACM Transactions on Graphics (TOG), 31(6):171, 2012. Google Scholar
  19. Fernando De Goes, David Cohen-Steiner, Pierre Alliez, and Mathieu Desbrun. An optimal transport approach to robust reconstruction and simplification of 2d shapes. Computer Graphics Forum, 30(5):1593-1602, 2011. Google Scholar
  20. Norm Ferns, Pablo Samuel Castro, Doina Precup, and Prakash Panangaden. Methods for computing state similarity in markov decision processes. In UAI'06, Proc. of the 22nd Conf. in Uncertainty in Artificial Intelligence, Cambridge, MA, USA, July 13-16, 2006, 2006. Google Scholar
  21. Kristen Grauman and Trevor Darrell. The pyramid match kernel: Discriminative classification with sets of image features. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), Beijing, China, October 2005. Google Scholar
  22. Kristen Grauman and Trevor Darrell. Approximate correspondences in high dimensions. In Proceedings of Advances in Neural Information Processing Systems (NIPS), 2006. Google Scholar
  23. Sariel Har-Peled and Manor Mendel. Fast construction of nets in low-dimensional metrics and their applications. SIAM J. Comput., 35(5):1148-1184 (electronic), 2006. URL: http://dx.doi.org/10.1137/S0097539704446281.
  24. Piotr Indyk. A near linear time constant factor approximation for euclidean bichromatic matching (cost). In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007. Google Scholar
  25. Piotr Indyk and Nitin Thaper. Fast color image retrieval via embeddings. Workshop on Statistical and Computational Theories of Vision (at ICCV), 2003. Google Scholar
  26. Subhash Khot and Assaf Naor. Nonembeddability theorems via Fourier analysis. Math. Ann., 334(4):821-852, 2006. URL: http://dx.doi.org/10.1007/s00208-005-0745-0.
  27. Eyal Kushilevitz, Rafail Ostrovsky, and Yuval Rabani. Efficient search for approximate nearest neighbor in high dimensional spaces. SIAM J. Comput., 30(2):457-474, 2000. Preliminary version appeared in STOC'98. Google Scholar
  28. Svetlana Lazebnik, Cordelia Schmid, and Jean Ponce. Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2006. Google Scholar
  29. N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215-245, 1995. Google Scholar
  30. Jiří Matoušek and Assaf Naor. Open problems on embeddings of finite metric spaces, August 2011. Available at URL: http://kam.mff.cuni.cz/~matousek/metrop.ps.
  31. Manor Mendel and Assaf Naor. Metric cotype. Ann. of Math. (2), 168(1):247-298, 2008. URL: http://dx.doi.org/10.4007/annals.2008.168.247.
  32. Manor Mendel and Assaf Naor. Maximum gradient embeddings and monotone clustering. Combinatorica, 30(5):581-615, 2010. URL: http://dx.doi.org/10.1007/s00493-010-2302-z.
  33. David M. Mount, Nathan S. Netanyahu, and San Ratanasanya. New approaches to robust, point-based image registration. In Jacqueline Le Moigne, Nathan S. Netanyahu, and Roger D. Eastman, editors, Image Registration for Remote Sensing, pages 179-199. Cambridge University Press, 2011. Cambridge Books Online. URL: http://dx.doi.org/10.1017/CBO9780511777684.009.
  34. Patrick Mullen, Pooran Memari, Fernando de Goes, and Mathieu Desbrun. Hot: Hodge-optimized triangulations. ACM Transactions on Graphics (TOG), 30(4):103, 2011. Google Scholar
  35. Assaf Naor. Comparison of metric spectral gaps. Anal. Geom. Metr. Spaces, 2:1-52, 2014. URL: http://dx.doi.org/10.2478/agms-2014-0001.
  36. Assaf Naor, Yuval Peres, Oded Schramm, and Scott Sheffield. Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces. Duke Math. J., 134(1):165-197, 2006. URL: http://dx.doi.org/10.1215/S0012-7094-06-13415-4.
  37. Assaf Naor and Gideon Schechtman. Planar earthmover is not in L₁. SIAM J. Comput. (SICOMP), 37(3):804-826, 2007. An extended abstract appeared in FOCS'06. Google Scholar
  38. Kangyu Ni, Xavier Bresson, Tony F. Chan, and Selim Esedoglu. Local histogram based segmentation using the wasserstein distance. International Journal of Computer Vision, 84(1):97-111, 2009. URL: http://dx.doi.org/10.1007/s11263-009-0234-0.
  39. Yann Ollivier, Herve Pajot, and Cedric Villani. Optimal Transport, Theory and Applications. Cambridge University Press, New York, NY, USA, 2014. Google Scholar
  40. List of open problems in sublinear algorithms: Problem 7. URL: http://sublinear.info/7.
  41. List of open problems in sublinear algorithms: Problem 49. URL: http://sublinear.info/49.
  42. Ofir Pele and Michael Werman. Fast and robust earth mover’s distances. In IEEE 12th International Conference on Computer Vision, ICCV 2009, Kyoto, Japan, September 27 - October 4, 2009, pages 460-467, 2009. URL: http://dx.doi.org/10.1109/ICCV.2009.5459199.
  43. Jeff M. Phillips and Pankaj K. Agarwal. On bipartite matching under the RMS distance. In Proceedings of the 18th Annual Canadian Conference on Computational Geometry, CCCG 2006, August 14-16, 2006, Queen’s University, Ontario, Canada, 2006. URL: http://www.cs.queensu.ca/cccg/papers/cccg37.pdf.
  44. Svetlozar T. Rachev and Ludger Rüschendorf. Mass transportation problems. Vol. I. Probability and its Applications (New York). Springer-Verlag, New York, 1998. Theory. Google Scholar
  45. Yossi Rubner, Carlo Tomasi, and Leonidas J. Guibas. A metric for distributions with applications to image databases. In ICCV, pages 59-66, 1998. Google Scholar
  46. Yossi Rubner, Carlo Tomasi, and Leonidas J. Guibas. The earth mover’s distance as a metric for image retrieval. Int. J. Comput. Vision, 40(2):99-121, November 2000. URL: http://dx.doi.org/10.1023/A:1026543900054.
  47. Yossi Rubner, Carlo Tomasi, and Leonidas J. Guibas. The earth mover’s distance as a metric for image retrieval. International Journal of Computer Vision, 40(2):99-121, 2000. Google Scholar
  48. Michael Saks and Xiaodong Sun. Space lower bounds for distance approximation in the data stream model. In Proceedings of the Symposium on Theory of Computing (STOC), pages 360-369, 2002. URL: http://dx.doi.org/10.1145/509907.509963.
  49. R. Sharathkumar and Pankaj K. Agarwal. Algorithms for the transportation problem in geometric settings. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 306-317, 2012. Google Scholar
  50. R. Sharathkumar and Pankaj K. Agarwal. A near-linear time approximation algorithm for geometric bipartite matching. In Proceedings of the Symposium on Theory of Computing (STOC), pages 385-394, 2012. Google Scholar
  51. Justin Solomon, Fernando de Goes, Gabriel Peyré, Marco Cuturi, Adrian Butscher, Andy Nguyen, Tao Du, and Leonidas Guibas. Convolutional wasserstein distances: Efficient optimal transportation on geometric domains. ACM Trans. Graph., 34(4):66:1-66:11, July 2015. In SIGGRAPH'15. URL: http://dx.doi.org/10.1145/2766963.
  52. Justin Solomon, Leonidas Guibas, and Adrian Butscher. Dirichlet energy for analysis and synthesis of soft maps. Computer Graphics Forum, 32(5):197-206, 2013. Google Scholar
  53. Justin Solomon, Raif Rustamov, Leonidas Guibas, and Adrian Butscher. Earth mover’s distances on discrete surfaces. ACM Trans. Graph., 33(4):67:1-67:12, July 2014. URL: http://dx.doi.org/10.1145/2601097.2601175.
  54. Justin Solomon, Raif Rustamov, Leonidas Guibas, and Adrian Butscher. Wasserstein propagation for semi-supervised learning. In Proceedings of The 31st International Conference on Machine Learning, pages 306-314, 2014. Google Scholar
  55. Pravin M. Vaidya. Geometry helps in matching. SIAM Journal on Computing, 18(6):1201-1225, 1989. Google Scholar
  56. Kasturi R. Varadarajan and Pankaj K. Agarwal. Approximation algorithms for bipartite and non-bipartite matching in the plane. In Proc. of the 10th annual ACM-SIAM Symp. on Discrete algorithms, pages 805-814. SIAM, 1999. Google Scholar
  57. Cédric Villani. Topics in optimal transportation, volume 58 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2003. Google Scholar
  58. Michael Werman, Shmuel Peleg, and Azriel Rosenfeld. A distance metric for multidimensional histograms. Computer Vision, Graphics, and Image Processing, 32(3):328-336, 1985. URL: http://dx.doi.org/10.1016/0734-189X(85)90055-6.
  59. P. Wojtaszczyk. Banach spaces for analysts, volume 25 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1991. URL: http://dx.doi.org/10.1017/CBO9780511608735.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact