Document Open Access Logo

Conditional Hardness of Earth Mover Distance

Author Dhruv Rohatgi

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.12.pdf
  • Filesize: 0.49 MB
  • 17 pages

Document Identifiers

Author Details

Dhruv Rohatgi
  • MIT, Cambridge, Massachusetts, USA

Acknowledgements

I want to thank Piotr Indyk and Arturs Backurs for numerous helpful discussions and guidance. I am also grateful to an anonymous reviewer for pointing towards Theorem 2 and its proof.

Cite As Get BibTex

Dhruv Rohatgi. Conditional Hardness of Earth Mover Distance. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.12

Abstract

The Earth Mover Distance (EMD) between two sets of points A, B subseteq R^d with |A| = |B| is the minimum total Euclidean distance of any perfect matching between A and B. One of its generalizations is asymmetric EMD, which is the minimum total Euclidean distance of any matching of size |A| between sets of points A,B subseteq R^d with |A| <= |B|. The problems of computing EMD and asymmetric EMD are well-studied and have many applications in computer science, some of which also ask for the EMD-optimal matching itself. Unfortunately, all known algorithms require at least quadratic time to compute EMD exactly. Approximation algorithms with nearly linear time complexity in n are known (even for finding approximately optimal matchings), but suffer from exponential dependence on the dimension.
In this paper we show that significant improvements in exact and approximate algorithms for EMD would contradict conjectures in fine-grained complexity. In particular, we prove the following results: 
- Under the Orthogonal Vectors Conjecture, there is some c>0 such that EMD in Omega(c^{log^* n}) dimensions cannot be computed in truly subquadratic time. 
- Under the Hitting Set Conjecture, for every delta>0, no truly subquadratic time algorithm can find a (1 + 1/n^delta)-approximate EMD matching in omega(log n) dimensions. 
- Under the Hitting Set Conjecture, for every eta = 1/omega(log n), no truly subquadratic time algorithm can find a (1 + eta)-approximate asymmetric EMD matching in omega(log n) dimensions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Earth Mover Distance
  • Hardness of Approximation
  • Fine-Grained Complexity

Metrics

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

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight Hardness Results for LCS and Other Sequence Similarity Measures. In Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), FOCS '15, pages 59-78, Washington, DC, USA, 2015. IEEE Computer Society. URL: https://doi.org/10.1109/FOCS.2015.14.
  2. Amir Abboud, Virginia Vassilevska Williams, and Joshua Wang. Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs. In Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '16, pages 377-391, Philadelphia, PA, USA, 2016. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=2884435.2884463.
  3. Pankaj K. Agarwal, Kyle Fox, Debmalya Panigrahi, Kasturi R. Varadarajan, and Allen Xiao. Faster Algorithms for the Geometric Transportation Problem. In Boris Aronov and Matthew J. Katz, editors, 33rd International Symposium on Computational Geometry (SoCG 2017), volume 77 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1-7:16, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.SoCG.2017.7.
  4. Josh Alman, Timothy M. Chan, and Ryan Williams. Polynomial Representations of Threshold Functions and Algorithmic Applications. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 467-476, October 2016. URL: https://doi.org/10.1109/FOCS.2016.57.
  5. Jason Altschuler, Jonathan Weed, and Philippe Rigollet. Near-linear Time Approximation Algorithms for Optimal Transport via Sinkhorn Iteration. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS'17, pages 1961-1971, USA, 2017. Curran Associates Inc. URL: http://dl.acm.org/citation.cfm?id=3294771.3294958.
  6. Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev. Parallel Algorithms for Geometric Graph Problems. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, STOC '14, pages 574-583, New York, NY, USA, 2014. ACM. URL: https://doi.org/10.1145/2591796.2591805.
  7. Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein gan. arXiv preprint, 2017. Google Scholar
  8. Arturs Backurs and Piotr Indyk. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False). In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC '15, pages 51-58, New York, NY, USA, 2015. ACM. URL: https://doi.org/10.1145/2746539.2746612.
  9. Amitabh Basu. Open Problem: Maximum weighted assignment problem. In Workshop: Combinatorial Optimization, Oberwolfach Report 50/2018, page 44, 2018. URL: https://doi.org/10.4171/OWR/2018/50.
  10. Nicolas Bonneel, Michiel van de Panne, Sylvain Paris, and Wolfgang Heidrich. Displacement Interpolation Using Lagrangian Mass Transport. ACM Transactions on Graphics, 30(6):158:1-158:12, December 2011. URL: https://doi.org/10.1145/2070781.2024192.
  11. Karl Bringmann and Marvin Kunnemann. Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. In Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), FOCS '15, pages 79-97, Washington, DC, USA, 2015. IEEE Computer Society. URL: https://doi.org/10.1109/FOCS.2015.15.
  12. Lijie Chen. On the Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product. In Proceedings of the 33rd Computational Complexity Conference, CCC '18, pages 14:1-14:45, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.CCC.2018.14.
  13. Rémi Flamary, Marco Cuturi, Nicolas Courty, and Alain Rakotomamonjy. Wasserstein Discriminant Analysis. Machine Learning, 107(12):1923-1945, December 2018. URL: https://doi.org/10.1007/s10994-018-5717-1.
  14. John Hopcroft and Richard Karp. An n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs. SIAM Journal on Computing, 2(4):225-231, 1973. URL: https://doi.org/10.1137/0202019.
  15. Piotr Indyk. A Near Linear Time Constant Factor Approximation for Euclidean Bichromatic Matching (Cost). In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '07, pages 39-42, Philadelphia, PA, USA, 2007. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1283383.1283388.
  16. Piotr Indyk and Rajeev Motwani. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC '98, pages 604-613, New York, NY, USA, 1998. ACM. URL: https://doi.org/10.1145/276698.276876.
  17. Andrey Boris Khesin, Aleksandar Nikolov, and Dmitry Paramonov. Preconditioning for the Geometric Transportation Problem. In Gill Barequet and Yusu Wang, editors, 35th International Symposium on Computational Geometry (SoCG 2019), volume 129 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1-15:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.SoCG.2019.15.
  18. Yin Tat Lee and Aaron Sidford. Path Finding II: An Õ(m√n) Algorithm for the Minimum Cost Flow Problem. arXiv preprint, 2013. URL: http://arxiv.org/abs/1312.6713.
  19. Yin Tat Lee and Aaron Sidford. Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(Vrank) Iterations and Faster Algorithms for Maximum Flow. In Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, FOCS '14, pages 424-433, Washington, DC, USA, 2014. IEEE Computer Society. URL: https://doi.org/10.1109/FOCS.2014.52.
  20. Jonas Mueller and Tommi Jaakkola. Principal Differences Analysis: Interpretable Characterization of Differences Between Distributions. In Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 1, NIPS'15, pages 1702-1710, Cambridge, MA, USA, 2015. MIT Press. URL: http://dl.acm.org/citation.cfm?id=2969239.2969429.
  21. Aviad Rubinstein. Hardness of Approximate Nearest Neighbor Search. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 1260-1268, New York, NY, USA, 2018. ACM. URL: https://doi.org/10.1145/3188745.3188916.
  22. 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, November 2000. URL: https://doi.org/10.1023/A:1026543900054.
  23. Roman Sandler and Michael Lindenbaum. Nonnegative Matrix Factorization with Earth Mover’s Distance Metric for Image Analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(8):1590-1602, August 2011. URL: https://doi.org/10.1109/TPAMI.2011.18.
  24. R. Sharathkumar and Pankaj K. Agarwal. A Near-linear Time ε-approximation Algorithm for Geometric Bipartite Matching. In Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC '12, pages 385-394, New York, NY, USA, 2012. ACM. URL: https://doi.org/10.1145/2213977.2214014.
  25. 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 Transactions on Graphics, 34(4):66:1-66:11, July 2015. URL: https://doi.org/10.1145/2766963.
  26. Cédric Villani. Topics in optimal transportation. Number 58 in Graduate Studies in Mathematics. American Mathematical Society, 2003. Google Scholar
  27. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science, 348(2):357-365, 2005. Automata, Languages and Programming: Algorithms and Complexity (ICALP-A 2004). URL: https://doi.org/10.1016/j.tcs.2005.09.023.
  28. Ryan Williams. On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-linear vs Barely-subquadratic Complexity. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '18, pages 1207-1215, Philadelphia, PA, USA, 2018. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=3174304.3175348.
  29. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the ICM, 2018. Google Scholar
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