acceptodds
Under review as a conference paper at ICLR 2027

Breaking the Quadratic Space Barrier for Optimal Transport via Cost Matrix Compression

Abstract

Optimal transport (OT) is a fundamental tool for comparing probability distributions, but the quadratic memory requirements of dense solvers limit scalability, especially on GPUs. We compress the ground-cost matrix using a sampling scheme inspired by Thorup–Zwick. We retain exact distances to nearby points and approximate the remaining distances through sampled landmarks. For arbitrary ground metrics, this gives at most factor- distortion using expected space. More generally, a -level scheme uses expected space with distortion . We obtain two results using this compression scheme. First, we adapt the push–relabel framework of Lahn, Raghvendra, and Zhang to compute an -additive approximation under the compressed costs using expected space, parallel time, and expected solver work. Under the original metric, the guarantee combines factor- distortion with additive error. In typical instances, especially when the input distributions are similar, much of the transport mass flows along local pairs whose costs are preserved exactly. Consequently, the compression yields high accuracy while substantially reducing storage. Our GPU implementation scales to approximately k points on RTX 2060, compared to approximately k for dense Sinkhorn implementations, with solution costs between and times the optimum on the evaluated high-dimensional datasets. Second, the compressed representation yields a -approximation for incremental metric bipartite matching with expected amortized insertion time and expected space after preprocessing, for fixed . This improves the superlinear update-time bound of Seth et al. (ICLR, 2026) for constant-factor approximation.

Primary area:
optimization
Keywords:
optimal transport, GPU algorithms, metric compression, approximation algorithms, Wasserstein distance, min-cost matching, incremental matching

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_xT82OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes an optimal transport (OT) cost matrix compression method inspired by the Thorup–Zwick sampling scheme. By retaining exact local distances and approximating non-local distances via landmarks, the method achieves sub-quadratic space complexity with bounded metric distortion. Based on this compressed representation, the authors adapt the push-relabel algorithm to accelerate approximate OT computation and extend the framework to incremental minimum-cost bipartite matching, establishing the corresponding complexity bounds and approximation guarantees.

Critical strengths
  1. The proposed algorithm reduces both space and computational complexity while retaining theoretical approximation guarantees.
  2. In experiments, the proposed algorithm demonstrates a clear memory advantage (over dense baselines such as Sinkhorn).
Critical weaknesses

Insufficient baselines: For example, a simple baseline can randomly partition the nn uniformly weighted samples into batches of size ≈B\approx B, solve each batch exactly via POT (ot.emd), and merge them into a globally valid coupling. In preliminary experiments on a Gaussian-to-data benchmark with ℓ22\ell_2^2 cost (n=131,072n = 131,072, B∈{512,1024,2048}B \in \{512, 1024, 2048\}), this method achieved a relative objective error around 10−210^{-2} with faster runtime. Although this setup differs from the paper, it indicates that simple classical baselines can be competitive. The authors should include such baselines.

Questions for authors
  1. Figures 1, 4, and 7 suffer from formatting and readability problems: legends, axis ticks, and labels frequently overlap, and subplots are noticeably misaligned. This significantly degrades the readability of the experimental results. Unless there is a specific justification for this layout, the authors should redraw these figures properly.
  2. In lines 688–690, the paper deduces that δ\delta-feasibility under dˉ′\bar{d}' implies standard dual feasibility under dd because d~≥d\tilde{d} \ge d. Could the authors clarify how this inference is derived?
  3. Is the proposed algorithm limited only to uniformly weighted points with equal support sizes (n=mn=m)? Can the framework be extended to more general settings, such as non-uniform marginals and differing support sizes (n≠mn \ne m)?
  4. Have the authors considered scalable approaches based on hierarchical, multi-scale, or column-generation schemes? To the best of my knowledge, certain methods in these categories can obtain high-precision solutions with a linear memory footprint and high efficiency, while also being accelerated on GPUs. If relevant to the scope of this work, it would be beneficial to incorporate them into the related work discussion.
1 comment
AuthorsOpenReview ↗

Response to Reviewer xT82

We thank the reviewer for their careful reading and thoughtful feedback.

Although this setup differs from the paper, it indicates that simple classical baselines can be competitive.

Response: Thank you for suggesting this baseline. Random batching produces a valid coupling, but its relative error can be unbounded even for two independent sets of points sampled uniformly from the unit square, using Euclidean distance as the ground cost.

For two sets of nn points, the expected average Euclidean edge length in an optimal matching is Θ(log⁡n/n)\Theta(\sqrt{\log n/n}), which approaches zero as nn increases (Ajtai, Komlós, and Tusnády, 1984). If we independently partition the sets into random batches of size BB, pair the batches independently of their coordinates, and solve each batch pair exactly, the expected average cost is instead Θ(log⁡B/B)\Theta(\sqrt{\log B/B}). Consequently, the ratio of expected costs is $\frac{\mathbb{E}[C_{\mathrm{batch}}]} {\mathbb{E}[\mathrm{OPT}_n]}= \Theta\left(\sqrt{\frac{n\log B}{B\log n}}\right)$, which grows without bound for fixed BB as n→∞n \to \infty.

This does not contradict the favorable results reported on the reviewer’s benchmark, but shows that random batching lacks a uniform constant approximation guarantee. Our compressed representation provides a bounded factor 33-approximation independent of nn. Our experiments show the same trend: with fixed batch size B=128B=128, the mean cost ratio increases from 1.6010 at n=512n=512 to 4.8696 at n=4096n=4096, while our two-level GPU solver achieves mean ratios of 1.0405–1.04911.0405–1.0491 across these sizes, using additive ε=0.001\varepsilon=0.001 on diameter-normalized inputs and evaluating matching costs under the original Euclidean metric.

Q1. Figures 1, 4, and 7 suffer from formatting and readability problems: legends, axis ticks, and labels frequently overlap, and subplots are noticeably misaligned.

Response: We agree and will redraw the affected figures with larger labels, consistent subplot alignment, and sufficient spacing between legends, ticks, and axes.

Q2. Could the authors clarify how this inference is derived?

Response: The reviewer is correct that domination of the original costs by the rounded proxy costs does not imply dual feasibility under the original costs. We have corrected the argument. The revised analysis establishes the additive guarantee under the proxy costs and then uses the distortion bound to obtain the approximation factor.

Q3. Is the proposed algorithm limited only to uniformly weighted points with equal support sizes? Can the framework be extended to non-uniform marginals and differing support sizes?

Response: The framework extends to non-uniform masses through the reduction of Lahn, Mulchandani, and Raghvendra, as described in Appendix E.1. The reduction creates collocated copies of support points. While compression is still performed over the original support points, storing the expanded matching requires an additional O(n/ε)O(n/\varepsilon) space, which is now included in our bounds (See Theorem 2 and Appendix E)

Q4. Have the authors considered scalable approaches based on hierarchical, multi-scale, or column-generation schemes?

Response: Thank you for highlighting these approaches. Our experiments already include a comparison with HiRef, a hierarchical-refinement method that produces explicit matchings. We will expand the related-work discussion to address multiscale and column-generation approaches and clarify their assumptions and guarantees.

Our contribution is a compressed representation of general metric costs with provable distortion, together with algorithms that operate directly on this representation. We will make this distinction clearer when discussing other approaches to reducing OT memory usage.

Reviewer_GVNBOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Dense optimal-transport solvers materialize the n × n cost matrix, which caps GPU scalability at roughly 15k points. This paper compresses the cost matrix with a Thorup–Zwick-inspired sampling scheme: sample n^{1/k} landmarks per level, keep exact distances to each point's local neighborhood (closer than its nearest landmark), and route all other distances through landmarks. For arbitrary ground metrics this yields expected size O(kn^{1+1/k}) with worst-case distortion 2k − 1, while the nearest n^{1/k} neighbors of each point are preserved exactly. Building on this representation, the paper (i) adapts the push–relabel algorithm of Lahn, Raghvendra, and Zhang so that admissible-edge search runs on local lists plus per-landmark shifted-dual summaries, giving an ε-additive OT solver with O(n^{1+1/k}/ε²) work and O(kn^{1+1/k}) expected space — an instance-adaptive (1 + 2γ)-relative guarantee, where γ is the share of optimal cost on non-local edges; (ii) obtains a (15 + ε)-approximation for incremental metric bipartite matching with Õ(n) expected amortized insertion time and O(n^{3/2}) expected space, improving the superlinear update time of Seth et al. (ICLR 2026) for constant-factor approximation; and (iii) provides a PyTorch implementation that solves instances up to n = 650k on an 8 GB RTX 2060, at 1.01–1.35 times the optimal cost, one to two orders of magnitude faster than HiRef at comparable accuracy.

Critical strengths

S1 — A correct, simple compression with an instance-adaptive guarantee, made algorithmically load-bearing. The O(n^{3/2})-space, factor-3 proxy with exact local distances is easy to state and prove, and the (1 + 2γ) bound converts it from a worst-case object into a practical one: when transport is mostly local, accuracy is near-exact. Crucially, the paper shows the representation is not just storable but solvable over: the shifted-dual landmark summaries eliminate the admissible-graph materialization that makes push–relabel solvers quadratic. I verified all of this line-by-line and numerically, which makes the claims credible rather than conjectural.

S2 — Convincing and honest empirics at a scale that matters. Reaching n = 650k on an 8 GB consumer GPU (versus ≈15k for dense Sinkhorn) at 1.01–1.35 times optimal, with 12–117× speedups over HiRef at comparable cost, is a strong practical result. The reporting is unusually honest: the Chamfer non-metric caveat, the soft-plan bias and ε-semantics caveats in the Sinkhorn comparison, the memory-measurement protocol, and the acknowledgment that Figure 2 compares quality only. Code is included in the supplement.

Critical weaknesses

W1 — The proof of the flagship efficiency claim has a genuine gap. Theorem 2's O(n^{3/2}/ε²) work bound rests on Appendix A's claim that at most |A1| distinct (a_b, τ) pairs occur per phase; this is false, and the pseudocode as written is Ω(n²) per phase. The repair (per-landmark row bucketing) is straightforward and I verified it preserves the bound, so likely fixable — but as submitted the central complexity claim is unsupported by its own argument. The scope is also under-specified: the search is described only for k = 2 although Theorem 2 covers general k and general OT, the 3-Level solver in the experiments is undocumented, and the LMR reduction's space accounting is unexplained.

W2 — The claims layer is under-proofread. Two named load-bearing sources (Thorup–Zwick; Agarwal–Sharathkumar) are missing from the bibliography; Section 3.1's dual initialization is infeasible as printed; Lemma 3's refined bound has an explicit counterexample; the stated extrema (1.16, 1.35) contradict Figure 1(a) (1.178, 1.355); Sinkhorn's memory limit appears as 15k, 45k, and ≈23k in three places; the n = 1.1M claim has no described experiment; Seth et al.'s factor is misquoted. Each item is minor; collectively they erode confidence in the statement layer.

Questions for authors

Q1 (clarification, affects Theorem 2). Appendix A asserts that the number of distinct (a_b, τ) pairs per phase is at most |A1|. Since τ = w̄_b + δ − y(b) varies across free vertices sharing a landmark, this seems false; do you bucket each V-row once per phase? If so, please correct the counting argument and Algorithm 1 (lines 5–7).

Q2 (clarification, affects scope). How does the 3-Level solver used in the experiments implement admissible-edge search over the multi-level proxy? The V-matrix construction in Section 3.2 is specific to single-landmark routing (k = 2).

Q3 (clarification, affects scope). For general (non-uniform) OT via the reduction of Lahn, Mulchandani, and Raghvendra, the instance grows to n/ε points. Is the compression rebuilt on the blown-up instance, and how is the O(kn^{1+1/k}) space bound then preserved?

Q4 (clarification, affects correctness of Section 3.1). With δ = ε/3 and y(b) = ε initially, y(a) + y(b) = 3δ exceeds d̄(a,b) + δ whenever d̄ < 2δ (e.g., zero-cost edges). Is y(b) = δ (as in Algorithm 1) intended?

Q5 (clarification). Lemma 3's refined bound (2j − 1) appears to be off by two: for k = 2, j = 1, the premise holds universally, yet non-local pairs have d′ > d (my example: d = 4, d′ = 6). Should the statement be 2j + 1, or should the premise be a rank condition?

Q6 (suggestion). An experimental evaluation of the incremental matching algorithm against Seth et al. and a phase-count plot would strengthen the empirical section.

Q7 (suggestion, affects baseline fairness). The dense baseline is plain log-domain Sinkhorn from POT. High-precision proximal-point solvers that wrap entropic subproblems for near-exact Wasserstein (e.g., Xie et al., UAI 2020) and their Newton-accelerated variants share this precision regime; a comment or quantified comparison would clarify the trade-off.

1 comment
AuthorsOpenReview ↗

Response to Reviewer GVNB

We thank the reviewer for the thorough review and detailed comments, which have helped us improve the clarity and precision of the paper. We address each point below.

Q1 (clarification, affects Theorem 2). Appendix A asserts that the number of distinct (ab,τ)(a_b,\tau) pairs per phase is at most ∣A1∣|A_1|. Since τ=wˉb+δ−y(b)\tau=\bar w_b+\delta-y(b) varies across free vertices sharing a landmark, this seems false; do you bucket each VV-row once per phase? If so, please correct the counting argument and Algorithm 1 (lines 5–7).

Response: Section 3 already described the shared-row approach, but the wording in Appendix A was unclear. We scan each VV-row once to compute its maximum m(a′)m(a') and a shared list T(a′)T(a') of maximizers. These summaries suffice: feasibility implies V[ab][a]≤τbV[a_b][a]\le\tau_b for every aa, so an admissible nonlocal edge can exist only when τb=m(ab)\tau_b=m(a_b). A vertex satisfying this equality accesses the shared list T(ab)T(a_b), while local candidates are checked separately. Thus, no threshold bucketing is needed. Section 3.2 and Algorithm 1 now consistently describe this construction.

Q2 (clarification, affects scope). How does the 3-Level solver used in the experiments implement admissible-edge search over the multi-level proxy? The VV-matrix construction in Section 3.2 is specific to single-landmark routing (k=2k=2).

Response: Our general kk-level construction uses a symmetric proxy, unlike the two-level representation. Appendix E.1 provides a sketch of the corresponding push–relabel algorithm. For the experiments, we use the asymmetric recursive proxy defined in Appendix F, which uses approximately half the storage of the symmetric alternative in our implementation. Its worst-case distortion is 77, compared with 55 for the symmetric three-level construction.

Each free point routes through its nearest first-level landmark and, when needed, that landmark’s nearest second-level landmark. Admissible edges are found using explicit local neighborhoods and shared landmark summaries, extending the two-level search strategy recursively.

Q3 (clarification, affects scope). For general (non-uniform) OT via the reduction of Lahn, Mulchandani, and Raghvendra, the instance grows to n/εn/\varepsilon points. Is the compression rebuilt on the blown-up instance, and how is the O(kn1+1/k)O(kn^{1+1/k}) space bound then preserved?

Response: The compression is constructed over the original support locations. Collocated copies share the stored distances, representatives, and neighborhood information, so the representation need not be rebuilt on the expanded instance. Maintaining an explicit matching on the O(n/ε)O(n/\varepsilon) copies nevertheless requires an additional O(n/ε)O(n/\varepsilon) space which we have added.

Q4 (clarification, affects correctness of Section 3.1). With δ=ε/3\delta=\varepsilon/3 and y(b)=εy(b)=\varepsilon initially, y(a)+y(b)=3δy(a)+y(b)=3\delta exceeds dˉ(a,b)+δ\bar d(a,b)+\delta whenever dˉ<2δ\bar d<2\delta (e.g., zero-cost edges). Is y(b)=δy(b)=\delta (as in Algorithm 1) intended?

Response: Yes, y(b)=δy(b)=\delta is intended. We have corrected Section 3.1 to initialize y(a)=0y(a)=0 and y(b)=δy(b)=\delta, consistently with Algorithm 1.

Q5 (clarification). Lemma 3's refined bound (2j−1)(2j-1) appears to be off by two: for k=2k=2, j=1j=1, the premise holds universally, yet non-local pairs have d′>dd'>d (my example: d=4d=4, d′=6d'=6). Should the statement be 2j+12j+1, or should the premise be a rank condition?

Response: The reviewer is correct: with our level indexing, the corresponding factor is 2j+12j+1, rather than 2j−12j-1. We have removed the incorrect refined statement and rewritten the proof, now presented as Lemma 5.

Q6 (suggestion). An experimental evaluation of the incremental matching algorithm against Seth et al. and a phase-count plot would strengthen the empirical section.

Response: We agree that a direct comparison with Seth et al. and a phase-count plot would strengthen the empirical evaluation. Our current incremental matching contribution is theoretical, while the experiments focus on the GPU OT solver. We will make this scope explicit and clarify that the incremental update-time improvement is an analytical guarantee.

Q7 (suggestion, affects baseline fairness). The dense baseline is plain log-domain Sinkhorn from POT. High-precision proximal-point solvers that wrap entropic subproblems for near-exact Wasserstein (e.g., Xie et al., UAI 2020) and their Newton-accelerated variants share this precision regime; a comment or quantified comparison would clarify the trade-off.

Response: IPOT is relevant when targeting high-precision solutions to the original OT problem. However, its original dense formulation maintains full cost, kernel, and transport matrices and therefore requires quadratic space. Our work addresses this storage bottleneck through a compressed cost representation, accepting controlled cost distortion to improve scalability.

Reviewer_MkBCOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper considers the optimal transport problem (OT) in general metrics in static and (partially) dynamic settings. Given two sets A and B of size n in a metric space, the goal is to find a maximal matching between A and B, such that the sum of the weights of all edges (i.e. distances between its endpoints) in the matching is minimum. In the dynamic setting, the set A is fixed, while we allow insertions of points into B. The authors give quadratic run-time algorithm that computes a constant approximation to OT, while using n3/2n^{3/2} space. In the incremental setting, using the same space, the authors obtain a constant approximation algorithm in near-linear amortized update time. Both results crucially rely on a metric compression scheme, which allows us to obtain algorithms using only sub-quadratic space.

In particular, instead of storing the distance matrix between A and B directly, we sample a subset A' of A of size O(sqrt(n)). Intuitively, the proxy distance between b∈Bb\in B and a∈Aa\in A is either the actual distance d(b,a)d(b, a) (if a and b are close), or d(b, a')+d(a', a), where a′∈Aa'\in A is the closest sampled point in A′A' to bb (if aa and bb are far). This way, the O(n2)O(n^2) distace matrix is compressed into a matrix of size O(n(n))O(n\sqrt(n)). The algorithm then adapts the push-relabel algorithm of Lahn, Raghvendra, and Zhang under this proxy distance.

Critical strengths
  • The paper studies an important problem of optimal transport, with a focus on reducing the space complexity of previous works in this area.

  • The metric compression scheme is interesting, and could be of independent interest.

Critical weaknesses
  • The presentation of the paper could be improved, in particular Section 4 and the Appendix. The algorithms and the analysis are often presented in parallel, making it hard to distinguish between the two. For example, the readilility could be greatly improved if the paper contained clear poofs of Theorems 1-3, which are right now somewhat hidden in the description of the algorithms.

  • The paper does not cite the relevant literature: for example, there is an extensive literature on bipartite matching/optimal transport in Euclidean spaces. For example, there is a (1+epsilon)-approximate algorithm in sub-quadratic time by Raghvendra and Agarwal (2020), and a fully dynamic constant-approx algorithm in sub-linear update time by Goranci et al. (2025). This is particularly important since the majority of the data-bases used are under l1 or l2 norms in the experiment section.

Questions for authors

My two main concerns are listed in the field above. In addition to these, it would benefit the paper if the authors would also include some data-sets under non-Euclidean matrics (that are actually metrics, unlike Chamfer distance).

Although the paper studies an important problem of OT, the presentation could be improved, and the relevant literature needs to be added. For this reason, I am leaning towards rejecting the paper from ICLR27.

2 comments
AuthorsOpenReview ↗

Response to Reviewer MkBC

Thank you for your review and feedback. We have used the additional page to significantly improve the presentation of our algorithm, particularly in Sections 3 and 4.

The presentation of the paper could be improved, in particular Section 4 and the Appendix. The algorithms and the analysis are often presented in parallel, making it hard to distinguish between the two. For example, the readilility could be greatly improved if the paper contained clear poofs of Theorems 1-3, which are right now somewhat hidden in the description of the algorithms.

Response: We have used the additional page to expand Sections 2, 3, and 4, which develop the results underlying Theorems 1, 2, and 3, respectively. Each section now presents the construction or algorithm followed by separate correctness, efficiency, and approximation analyses, making the arguments supporting the three theorems easier to locate and follow.

The paper does not cite the relevant literature: for example, there is an extensive literature on bipartite matching/optimal transport in Euclidean spaces. For example, there is a (1+epsilon)-approximate algorithm in sub-quadratic time by Raghvendra and Agarwal (2020), and a fully dynamic constant-approx algorithm in sub-linear update time by Goranci et al. (2025). This is particularly important since the majority of the data-bases used are under l1 or l2 norms in the experiment section.

Response: Thank you for the suggestion. We have expanded the discussion of geometric matching and optimal transport to include relevant work, including Raghvendra and Agarwal (2020) and Goranci et al. (2025).

it would benefit the paper if the authors would also include some data-sets under non-Euclidean matrics

Response: We have conducted experiments on additional datasets. We construct two sets AA and BB, each containing nn empirical distributions formed from mm equally weighted samples from one-dimensional Gaussians with varying means. The ground metric is exact 11-Wasserstein distance, computed by sorting the samples and averaging absolute differences between corresponding sorted samples. We consider three settings: (i) independently sampled means for both sets, (ii) the same set of means for AA and BB, with independently generated samples, and (iii) independently sampled means from intervals shifted by 22 between the sets.

Across 18 configurations, each averaged over three independently generated datasets, our two-level GPU solver achieved mean cost ratios between 1.0030 and 1.0888 relative to the exact OT cost between AA and BB. The largest individual ratio across all 54 runs was 1.1173. We used additive ε=0.001\varepsilon=0.001 after diameter normalization and evaluated costs using the original Wasserstein distances.

We will include this dataset across all experiments in the next version of the paper, including baseline comparisons and evaluations of approximation quality, runtime, memory usage, and scalability.

I thank the reviews for their response. I appriciate the authors adding additional experiments and extending the literature. I see also that the authors made substantial changes to the manuscript, which potentially improves the quality of the paper. However, in this limited time, I cannot go through the whole paper again. For this reason, although I am convinced that the paper has somewhat improved, I keep my score.

Reviewer_6woTOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes an algorithm for OT that runs with subquadratic space by sketching the cost metric first, and then running fast solvers on top of the sketched metric. This is efficiently implementable in practice, and gives good empirical results. The theoretical result also has an implication for incremental min-cost matching, where it gives a new algorithm for allocating requests to servers online.

Critical strengths

-- The paper clearly conveys an interesting, new algorithm for better approximations of optimal transport. -- The authors provide experiments showing that the algorithm works well in practice.

Critical weaknesses

-- While this is not a critical weakness, the authors are overlooking two very relevant works which break the subquadratic barrier in the special case of euclidean metric. The ideas in those settings are similar: sketch the cost matrix, and then run a fast OT solver on top: "Approximating the Quadratic Transportation Metric in Near-Linear Time" and "Massively Scalable Sinkhorn Distances via the Nyström Method" . In light of those results, the results of this paper can be viewed as a different sketch of the metric space, which works for general metrics.

Questions for authors

-- Please add citations to the relevant literature: "Approximating the Quadratic Transportation Metric in Near-Linear Time" and "Massively Scalable Sinkhorn Distances via the Nyström Method"

1 comment
AuthorsOpenReview ↗

Response to Reviewer 6woT

We thank the reviewer for the positive assessment and for pointing out these relevant works. We have added both references and a discussion of their approaches in the revised manuscript (Section 1, page 2, lines 71–76; references [6] and [7]). We agree with the reviewer that these works share the broad strategy of constructing a compact representation and running an efficient transport solver on it. Specifically, [7] combines low-rank approximation of the Gaussian kernel matrix with Sinkhorn scaling to approximate squared-Euclidean OT, while [6] uses Nyström approximation to accelerate the computation of entropically regularized OT. Our contribution is a complementary compression scheme with guarantees for arbitrary ground metrics, without requiring low-dimensional geometry or a low-rank kernel.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.