PaperlayerView exact revision on arXiv

Source-linked AI summary

Conditional Hardness of Earth Mover Distance

Dhruv Rohatgi

arXiv:1909.11068v1cs.CC

TL;DR

Exact and approximate Earth Mover Distance remain costly in high dimensions, despite nearly linear-time approximation algorithms whose running time depends exponentially on dimension. This paper gives conditional fine-grained evidence that substantially faster exact or matching-reporting algorithms would contradict hardness conjectures.

  • Problem

    Computing transportation cost or an optimal transportation map is important in machine learning, computer vision, and related applications, but existing approximation algorithms have exponential dependence on dimension.

  • Method

    The paper uses reductions from bichromatic closest pair and Hitting Set-related Find-OV procedures to establish conditional hardness for exact and approximate EMD matching.

  • Results

    The paper establishes conditional quadratic hardness for exact EMD and for approximate EMD when the approximately optimal matching must be reported.

  • Takeaways & Limitations

    High-dimensional geometric transportation problems are unlikely to admit truly subquadratic algorithms across both exact and matching-reporting approximate variants under the stated conjectures.

  • Takeaways & Limitations

    The hardness results restrict exact instances to polynomially bounded integer coordinates and approximate instances to Boolean coordinates.

Abstract

from arXiv · show

The Earth Mover Distance (EMD) between two sets of points $A, B \subseteq \mathbb{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 \mathbb{R}^d$ with $|A| \leq |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: (1) 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. (2) 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. (3) 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.

1 Introduction

The paper studies conditional lower bounds for exact and approximate geometric transportation, showing that substantial improvements over existing algorithms would refute fine-grained complexity conjectures.

  • Introduction: Exact EMD computes the minimum perfect-matching cost, while EMD matching requires reporting an optimal transportation map; asymmetric EMD generalizes this to injections when |A| < |B|.These problems have applications including image retrieval, where asymmetric EMD handles occlusions and clutter, and interpolation between distributions.
  • Introduction: The results address a gap in lower-bound evidence for geometric matching, where existing approximation algorithms can be nearly linear in n but exponential in dimension.The paper asks whether runtimes such as O(n · poly(d, log n, 1/ε)) could be achieved and provides conditional evidence against such improvements.
  • Exact EMD and Orthogonal Vectors Conjecture: Under the Orthogonal Vectors Conjecture, exact EMD in d(n) = Ω(c^log*n) dimensions cannot be computed in truly subquadratic time.The result applies to O(log n)-bit vectors and implies that a truly subquadratic EMD algorithm in these dimensions would falsify the conjecture.
  • Approximate EMD and the Hitting Set Conjecture: Under the Hitting Set Conjecture, finding a (1 + 1/n^δ)-approximate EMD matching in d(n) = ω(log n) dimensions requires quadratic time up to subquadratic factors.This hardness concerns reporting the approximately optimal matching, not merely estimating its cost.
  • Approximate EMD and the Hitting Set Conjecture: Under the Hitting Set Conjecture, finding a (1 + η)-approximate asymmetric EMD matching is not truly subquadratic for η = 1/ω(log n) and d(n) = ω(log n).Asymmetric EMD requires an injection from A to B when |A| < |B|.
  • Approximate EMD and the Hitting Set Conjecture: The reductions use the Orthogonal Vectors and Hitting Set conjectures, including intermediate (k, 2k)-Find-OV problems between them in difficulty.The (k, 2k)-Find-OV problem asks for k orthogonal pairs given a guarantee of at least 2k orthogonal pairs.

2 Preliminaries

The paper formalizes EMD, asymmetric EMD, and matching variants, then introduces Maximum Orthogonal Matching and Find-OV as reduction intermediates. It also invokes a prior conditional hardness result for bichromatic closest pair.

  • 2 Preliminaries: EMD takes equal-size vector sets and seeks the minimum-cost perfect matching, with dimensions treated as a function d(n) of input size.The hardness analysis restricts exact EMD to polynomially bounded integer vectors and approximate EMD to Boolean vectors.
  • 2 Preliminaries: Asymmetric EMD allows |A| ≤ |B| and requires an injection rather than a bijection.
  • 2 Preliminaries: EMD matching asks algorithms to output the optimal matching, with approximation measured by additive or multiplicative error in its cost.
  • 2 Preliminaries: Maximum Orthogonal Matching maximizes orthogonal pairs under an injection from A to B, while Find-OV identifies vectors in A having an orthogonal partner in B.
  • 2 Preliminaries: The exact-EMD argument relies on a prior result that bichromatic ℓ2-Closest Pair in c log^* n dimensions requires n^2−o(1) time under OVC [12].

3 Exact EMD in low dimensions

The paper reduces bichromatic closest pair to exact EMD by augmenting both sets with carefully engineered vectors whose matching costs isolate one original pair. The construction uses extra dimensions and square decompositions, yielding a truly subquadratic EMD algorithm whenever closest pair is solvable that quickly.

  • 3 Exact EMD in low dimensions: The reduction adds n−1 copies of specially chosen vectors to each set so all but one matching edge have controlled costs, leaving one edge to encode a closest pair.The construction seeks vectors equidistant from the opposite set and much closer to the added copies; the optimal matching therefore minimizes designated edge types.
  • 3 Exact EMD in low dimensions: Disjoint free dimensions adjust the two augmented sets separately, preserving original inner products while making the relevant distances accountable.
  • 3 Exact EMD in low dimensions: The construction uses a constant-size perfect-square decomposition: any positive integer can be decomposed into O(log 1/ρ) squares in O(m^ρ) time.The algorithm combines a greedy phase with dynamic programming and Lagrange’s four-square theorem.
  • 3 Exact EMD in low dimensions: A truly subquadratic exact EMD algorithm would yield a truly subquadratic algorithm for bichromatic closest pair through the stated reduction.Theorem 3.2 maps sets in [1,n^k]^d to EMD instances in [1,n^16k]^(2d+2c+2), preserving O(n^2−ε) time.
  • 3 Exact EMD in low dimensions: The augmented instance has O(n) vectors in dimension 2d+2c+2 with entries bounded by n^16k, and its EMD can be computed in O(n^2−ε) time if the assumed algorithm exists.Constructing the augmented sets takes O(n^5/4 d^1/8) time, so the overall reduction remains O(n^2−ε).
  • 3 Exact EMD in low dimensions: Combining the reduction with the prior closest-pair hardness theorem establishes Theorem 1.1.

4 Approximate EMD under the Hitting Set Conjecture

The section reduces approximate EMD matching to orthogonality-based problems and uses Maximum Orthogonal Matching, Find-OV, and Hitting Set reductions to establish conditional hardness in high dimensions.

  • Limitation of the first approach: The closest-pair route loses a factor of n because EMD sums n distances, so it cannot establish hardness for approximation errors larger than about 1/n.This motivates the Hitting Set and orthogonality-based approach for stronger approximation hardness.
  • Reduction to orthogonality: Approximate Maximum Orthogonal Matching reduces to approximate EMD matching with additive error O(ε|A|d) in dimension 12d + 1.The construction maps orthogonal pairs to lower-distance pairs and uses auxiliary vectors to encode unmatched choices.
  • Orthogonal Vectors hardness: A (1 + 1/n^δ)-approximate EMD matching algorithm in d = ω(log n) dimensions would contradict the Orthogonal Vectors Conjecture if it ran in O(n^(2−ε)) time.The reduction proves this for every ε > 0 and δ ∈ (0, 1).
  • Hitting Set hardness: If Maximum Orthogonal Matching is solvable in truly subquadratic time with suitable additive error, Find-OV and then Hitting Set become solvable in truly subquadratic time.The intermediate Find-OV construction preserves subquadratic time up to polynomial dimension factors.
  • Hitting Set reduction: The Hitting Set reduction converts Find-OV into O(log n) approximate-orthogonality phases, each removing vectors certified to have orthogonal partners.Success means every vector has an orthogonal partner; failure certifies a hitting vector.
  • Asymmetric EMD: Under the Hitting Set Conjecture, no truly subquadratic algorithm finds a (1 + η)-approximate asymmetric EMD matching in d = ω(log n) dimensions when η = 1/ω(log n).The reduction yields additive error O(ηnd), which is at most n/2 for the stated choice of η and dimension.

A Hardness of Low-Rank Minimum Weighted Assignment

The appendix transfers the paper’s EMD hardness machinery to minimum weighted assignment with low-rank weight matrices by encoding transformed squared EMD costs in a low-rank matrix.

  • Reduction: Bichromatic closest pair in d dimensions reduces to minimum weighted assignment when the weight matrix has rank O(d).The transformed assignment cost equals the squared EMD quantity encoding the closest-pair distance.
  • Conditional consequence: Under the stated algorithmic assumption, bichromatic closest pair would be solvable in O(n^(2−ε)) time.The reduction preserves the assumed subquadratic exponent for rank-O(d) minimum assignment.
  • Encoding closest pair: The transformed instance makes the optimal assignment isolate one pair whose squared distance determines SQEMD(A′, B′).Large auxiliary distances force the remaining matching structure, leaving the closest-pair contribution identifiable.
  • Low-rank structure: The assignment matrix is a sum of 2d + 2c + 4 rank-1 matrices, so its rank is at most 2d + 2c + 4.Consequently, a fast low-rank assignment algorithm would compute the transformed SQEMD cost quickly.

B Proof of Theorem 4.5

The proof of Theorem 4.5 amplifies approximate Maximum Orthogonal Matching instances and uses the resulting matching to decide whether an orthogonal pair exists.

  • Amplification reduction: If Maximum Orthogonal Matching has additive error n^δ and runs in O(n^γ) time for δ < 1/2, then OV can be solved in O(n^(γ/(1−δ))) time.The reduction replicates every vector 2n^(δ/(1−δ)) times before running the approximate matching algorithm.
  • Correctness: A found orthogonal pair certifies a positive OV instance, while absence of such a pair is returned as a negative answer.If an orthogonal pair existed but none were found, the approximation guarantee would be violated because a large orthogonal matching was available.

C Hardness of (k, 2k)-Find-OV

This section establishes conditional hardness for (k, 2k)-Find-OV under both the Orthogonal Vectors and Hitting Set conjectures. It gives a randomized partition-and-search algorithm whose correctness and runtime yield a strongly subquadratic contradiction.

  • Under OVC, (n^δ, 2n^δ)-Find-OV requires Ω(n^(2−δ−o(1))) time for every fixed δ ∈ (0, 1).
  • A hypothetical O(n^(2−δ−ε)) algorithm for (n^δ, 2n^δ)-Find-OV would imply a subquadratic algorithm for OV via vector duplication.
  • Under the Hitting Set Conjecture, an O(n^(2−ε)) algorithm for (n, 2n)-Find-OV would yield an O(n^(2−δ)) algorithm for Hitting Set.
  • The algorithm samples vectors, partitions A and B into k = n^(1/3−α) groups, and repeatedly calls find on each pair while marking vectors with discovered orthogonal partners.
  • Correctness follows because hitting vectors remain unmarked, whereas if every vector has an orthogonal partner, the remaining pairs are handled in Step 4 and all vectors become marked.
  • The complete procedure runs in O(n^(2−ε/7)) time, combining the costs of sampling, find calls, and final exhaustive checks.The final exhaustive step costs O(n^(2−3α/2)).
Loading 1909.11068v1…