We appreciate the reviewer’s time and insightful feedback. It seems the

W1 and Q1: Complexity. In Appendix C, we discuss the complexity with respect to $K$. Here’s a summary:

Let $n$ be the size of the reference measure and $m$ the average size of all target measures.

• Pairwise computation of PGW/GW distance for $K$ measures requires
  $\binom{K}{2} \mathcal{O}\left(\frac{1}{\epsilon} nm(n + m)nm^2\right),$
  where $\epsilon > 0$ is the accuracy tolerance.

• The time complexity for LGW/LPGW is
  $\binom{K}{2} \mathcal{O}(n^2) + K \mathcal{O}\left(\frac{1}{\epsilon} nm(n + m)n^2 m^2\right).$

Note that if we apply the Sinkhorn algorithm in the solvers for GW/PGW, the term $nm(n + m)$ can be improved to $\frac{1}{\epsilon} nm \ln(n + m)$.

In general, $n, m \gg K$ (i.e., the size of each dataset is much larger than the number of datasets). Therefore, in (a), the term $\binom{K}{2}(n^2)$ is negligible, and the dominant term is $K \mathcal{O}\left(\frac{1}{\epsilon} nm(n + m)n^2 m^2\right)$, which is linear with respect to $K$.

Q1: Approximation Results without Monge Mapping Assumption. In the general case without Monge mapping, LPGW is defined in (55) and LGW in (36). In the approximation error experiment (Section 4.1, Table 2), a Monge mapping does not exist for any embedding since all the reference measures and target measures have distinct sizes and some of the reference measures are non-uniform. See the repo, file ellipse/ellipses.ipynb for details.

Q2: Approximation Errors. As explained above, LPGW (15) and aLPGW (18) are proposed for theoretical completeness and are computationally infeasible. Thus, we use (20) to approximate PGW. This situation is similar for LOT and LGW.

In the LOT paper, both LOT Eq. (27) and aLOT Eq. (32) are inefficient to solve. The only feasible implementation is the approximation of (32):
\|\mathcal{T}_{\gamma^1} - \mathcal{T}_{\gamma^2}\| \tag{a}

Strictly speaking, (a) is neither aLOT nor LOT. However, (a) is used directly as the representation of LOT in much of the LOT literature. In LGW/LPGW, the situation is the same.

Q3: Extensions of Cost Function. To the best of our knowledge, the optimality of barycentric projection has been proven only for LOT and linear partial OT. We plan to extend this result to Euclidean cost in future work. In GW/PGW, we just proposed the proof for inner product. In the future, we will extend this result to more general cost.

In our understanding, to extend the result to general cost, the definition of barycentric projection may need to be modified.

Q4: Elliptical Disks Experiment. A suitable reference measure can be chosen as follows:

• The reference measure size acts as the "resolution" of the embedding, so a larger size is preferred. Typically, we set this to be the maximum/mean/median of the sizes of all target datasets.

• Similar to linear OT and linear GW, the reference measure should ideally be the GW/PGW barycenter, as explained in lines 2364-2366, 2433-2338, and 2476-2478. Corresponding barycenter algorithms can be found in Peyre et al., 2016, Bai et al., 2024.

We would like to express our gratitude for the thorough and insightful feedback provided in the review. In what follows, we offer our explanations to the reviewer's questions and concerns. We welcome follow-up inquiries and would be happy to engage in more in-depth discussions.

W1: Monge Mapping Assumption.

Providing theoretical bounds on the approximation error when a Monge mapping does not exist.

To the best of our knowledge, theoretical bounds for LGW and LPGW have not yet been established. This bound will likely depend heavily on the reference measure. Empirically, we observe that increasing the size of the reference measure (i.e., increasing "resolution") helps decrease the error.

Including empirical experiments comparing performance on datasets known to violate the Monge mapping conditions.

In Table 2, we present the relative error and Pearson correlation coefficient for this purpose. Note that in this experiment, we do not have a Monge mapping for any of the embeddings since all reference measures and target measures have distinct sizes, and some reference measures are non-uniform. We observe that, when the reference measure is appropriate (e.g., $\mathbb{S}_7, \mathbb{S}_8, \mathbb{S}_9$), the relative error is low (0.02) and the PCC is high (0.99).

Discussing potential modifications to make the method more robust when Monge mappings do not exist.

In our understanding, the existence of a Monge mapping is not essential since this situation can occur with the LOT, LGW, and LHK methods, and in these cases, barycentric projection is generally used. In fact, LPGW (or aLPGW) is viewed as a proxy for the original PGW distance rather than an exact approximation.

Our approach for improving accuracy and preserving information in the original target measure includes the following strategies, as discussed in lines 2217-2252. To summarize, accuracy can be enhanced by:

1. Choosing a good reference measure:

   • The size of the reference measure acts as the "resolution" of the embedding, so larger sizes are preferred. Typically, we set this size to be either the maximum or mean/median of the sizes of all target datasets.

   • Similar to linear OT and linear GW, the reference measure should ideally be set to the GW/PGW barycenter, as explained in lines 2364-2366, 2433-2338, and 2476-2478.

2. Setting the mass of each point in the reference and target measures to be equal if feasible.

W2: Computational Implementation. We appreciate the reviewer’s observation and suggestion. To clarify the "two-layer approximation":

• (20) is an approximation of (19), aLPGW.
• aLPGW (19) approximates LPGW (15).
• LPGW (15) approximates PGW (11).

This relationship explains the derivation of (20). However, it is not a multi-layers approximation. (15)(19) are only proposed for theoretical completeness and is not computational feasible.

In practice, we directly approximate PGW with (20), rather than through (19) or (15), which were proposed for theoretical completeness, similar to LOT and LGW.

The above approximation is similar to LOT/LGW. That is LOT, aLOT, LGW, aLGW are only proposed for theoretical completeness. The practical formulations are $aLOT(\mu,\nu)\approx \|\mathcal{T}_{\gamma^1}-\mathcal{T}_{\gamma^2}\|_{L(\mu)}^2$

$aLGW(\mu,\nu)\approx \|\mathcal{T}_{\gamma^1}-\mathcal{T}_{\gamma^2}\|_{L(\mu^{\otimes2})}^2.$

Provide theoretical error bounds.

Developing a theoretical error bound is part of our future work. To our knowledge, there is a gap in this area for both LGW and LPGW.

Discuss the trade-offs between computational efficiency.

Similar to LOT and LGW, both (15) and (19) are computationally inefficient (in fact, there is not an existing solver for (15) or (19)). These formulations are presented primarily for theoretical completeness and to potentially support future developments (e.g., LPGW geodesics). Thus, only (20) is computationally efficient.

W3: Comparisons with Existing Methods. LPGW is proposed as a proxy for Partial GW distance, and, to the best of our knowledge, low-rank GW and sliced-GW have not been extended to the partial GW setting.

Additionally, sliced-GW [C] solves a variant of the GW problem: $\sum_{l=1}^L GW((\theta_l)_\#\mathbb{X}, (\theta_l)_\#\mathbb{Y}).$

Apart from the difference between GW and PGW, there are other issues:

• The optimal value in the formulation above represents the average transport cost based on 1D projections, which can differ significantly from the transport cost in the original GW/PGW problem.
• Theorem 3.1 in [C] requires the Monge mapping assumption. However, in our ellipse experiment (Section 4.1) and MNIST classification experiment (Section 4.3), a Monge mapping does not exist and so the closed form in their main theorem cannot be applied.

W1: Novelty of this paper:

The paper is mostly combining existing methods and theoretical novelty is limited, with discussions following from the the original ideas and definitions of linearized/partial GW/OT.

While the general principle of linear partial GW is inspired by linear GW/OT, our proposed formulation of the LPGW embedding is not as simple as combining existing techniques.

Notably, for prior linear GW/OT works in the balanced setting, the linear embedding represents the displacement between the reference measure and the given target measures based on the optimal transport plans.

In our work, it is essential to incorporate information about mass creation and destruction into the embedding. Formulating such an embedding within the partial GW setting is highly non-trivial. As such, we feel that describing our approach as simply a combination of existing methods does not fully capture its unique contributions.

In the classical OT/GW/UOT framework, the problem admits a dynamic formulation. Consequently, the linear embedding can be interpreted as a logarithm mapping, capturing the velocity of particles involved in mass transportation as well as the derivatives governing mass creation and destruction. However, the dynamic formulation for UGW/PGW has not yet been thoroughly explored. Incorporating this dynamic information to define an embedding and establishing a similarity measure between two embeddings that can recover LGW and PGW is a significant challenge.

In contrast, these challenges do not arise in the balanced OT/GW setting, where the formulation is inherently simpler.

We kindly encourage the reviewer to reconsider this perspective.

What if TV is replaced by a general divergence for unbalanced formulation as in [1]?

As explained above, defining a new embedding in the unbalanced GW setting based on general divergence penalty is non-trivial. To the best of our knowledge, linear unbalanced GW has not been studied in any setting, regardless of whether the penalty is TV or another divergence (e.g., KL divergence). Even in classical OT setting, the unblanced linear OT embedding has only been studied with the KL penalty or the TV penalty (see e.g., Linear HK and Linear OPT); a formulation using general divergences has not yet been proposed.

W2: Additional References. We appreciate the reviewer’s observation. We would like to remark that [2,3] are already cited in our work (note that they do not directly address unbalanced GW however). We will add [4] to our related works section. (See the updated pdf.)

W3: Barycentric LGW & Notation. LGW’s theoretical formulation is (8), and its approximation is (10). Equation (10) can be further simplified as: \|g_{Y^1}(\mathcal{T}_{\gamma^1}(\cdot_1),\mathcal{T}_{\gamma^1}(\cdot_2))-g_{Y^2}(\mathcal{T}_{\gamma^2}(\cdot_1),\mathcal{T}_{\gamma^2}(\cdot_2))\|^2_{L(\mu^{\otimes2})} \tag{a} (We've added a label to this equation in the paper.)

In all experiments, the numerical implementation of LGW is based on (a) rather than (8) or (10). The code in Github also uses (a), similar to LOT and LPGW. We will add a sentence to clarify this point.

Notation $\gamma^1 \wedge \gamma^2$ on line 260 seems to be incorrect and should be $\inf_A \gamma^1(A\cap E)+\gamma^2(A^C\cap E)$.

We thank the reviewer for this comment and have corrected the typo.

The authors sincerely thank the reviewer for their valuable comments and thoughtful discussion. The additional reference [4] has been added, and the typo in line 260 has been corrected.

The dynamic formulation of PGW is part of our future research direction. We aim to explore how our new formulation aligns with the tangent space and GW geodesics discussed in Sturm, Beier et al., 2021, and Beier et al., 2024.

However, to the best of our knowledge, there is currently no dynamic formulation for GW (specifically, the related continuity equation) in the general gauge measure space setting. Dynamic GW in a special setting has been studied very recently (see Zhang et al., 2024).

In conclusion, we agree with the reviewer on the importance of having a dynamic formulation for PGW, and it will be part of our future work.

Many of the results require the existence of a Monge map for the PGW problem.

To clarify, similar to LOT/LGW, none of the formulations for the LPGW embedding technique (e.g., LPGW distance, LPGW embedding, aLPGW distance, etc.) rely on the Monge mapping assumption. The formulation of the LPGW distance (e.g., Eq. (14)), which requires a Monge mapping, is presented in the main text only as a simplified formulation for the reader’s convenience. However, when a Monge mapping does not exist, these concepts can still be well-defined. We would be happy to discuss this in further detail if the reviewer so pleases.

The theoretical results requiring the Monge mapping assumption are:

• Proposition 3.1 (2), (3), (4)
• Theorem 3.2 (3)

Proposition 3.1 (2) characterizes the relationship between the barycentric projection and the Monge mapping, and we felt its inclusion important for the reader to understand the barycentric projection.

Proposition 3.1 (3), (4), and Theorem 3.2 (3) address the gap between the proposed (approximated) LPGW distance and the PGW distance. In Proposition 3.1 (3), we clarify the conditions under which the LPGW distance can exactly recover the PGW distance. Proposition 3.1 (4) shows when the numerical implementation (Eq. (20)) can recover PGW, and Theorem 3.2 (3) states the conditions for aLPGW to recover LPGW.

Conditions for the existence of Monge mapping: In the continuous measure setting and the empirical discrete measure setting (i.e., where the mass of each point in $\mu$ and $\nu$ is the same), GW admits a Monge mapping (e.g., Dumont et al., 2024, Proposition 1.16, Theorem 2.1; Courty et al., 2019, Theorem 3.2). However, it is unclear whether this result extends to unbalanced GW (including PGW), as these formulations were proposed only recently. Further characterization of the conditions under which the Monge mapping assumption hold is an open problem left for future work.

Note: Empirically, we observe that both GW and PGW admit Monge mappings when data are in an empirical distribution.

These results appear to be of limited applicability.

We respectfully disagree with this point. Based on our understanding, the only effect of the absence of Monge mappings in PGW is an increased gap between the LPGW distance and PGW distance (see lines 2231-2234 in the appendix). In a machine learning setting, when target datasets have different sizes or the reference measure has non-uniform distribution, then the Monge mapping assumption may not hold in all linear OT methods, including LOT, Linear HK, Linear OPT, and LGW. However, these methods are still viable and of broad importance.

(We would like to briefly remark, however, that if we manually set the mass for each point in all datasets to be the same, the Monge mapping assumption will still hold in the linear unbalanced OT setting, including our LPGW.)

Nonetheless, similar to Linear OT/Linear GW, we present the LPGW distance as a proxy for PGW rather than as an exact approximation. In fact, in our shape retrieval experiment, the PGW distance performs worse than LPGW distance in measuring similarity in the 2D dataset (see Table 2).

W3: Approximation of LPGW. Equation (20) is the empirical implementation of the LPGW distance, formulated analogously to the empirical implementation of the LGW distance (see line 215).

In Table 1, we show the relative error gap (MRE) and Pearson correlation (PCC) between (20) and PGW. We find that when the reference measure is well-chosen (i.e., $\mathbb{S}_7, \mathbb{S}_8, \mathbb{S}_9$), (20) and PGW exhibit low MRE (0.02) and high PCC (0.99). Note that in this experiment, we do not have a Monge mapping for any embedding, since all the reference measures and target measures have distinct sizes and some of the reference measures are non-uniform. See the repo, file ellipse/ellipses.ipynb for details.

Using approximation formulations to replace the original linear OT/GW/PGW is common in other linear OT-based techniques as well.

For example, in the LOT method, LOT (Eq. (27)) is proposed to approxiamte OT. aLOT (Eq. (32)) is then proposed to approximate LOT.

Furthermore, the aLOT (Eq. (32)) is approximated by: \|\mathcal{T}_{\gamma^1}-\mathcal{T}_{\gamma^2}\|^2\tag{b}.

Note, to clarify it, it is not a multi-layers approximation. LOT (27) and aLOT (32) are only proposed for theoretical completeness and are not computational feasible.

In practice, (b) is used to approximate OT, though (b) is neither LOT (27) nor aLOT (32). However, in most of the existing literature that cites LOT, (b) is generally treated as the LOT distance and (27), (32) are not presented.

Our approximation (20) follows analogously from the previous works.

We would like to thank the reviewer for their feedback. We hope the following adequately addresses the reviewer's concerns and would be more than happy to engage in further discussions.

W1: Novelty. First, we would like to clarify a potential misunderstanding of the LPGW formulation and our main contributions. The following will be emphasised in the main text and abstract.

From a theoretical perspective, our proposed LPGW formulation consists of two parts: the LPGW embedding and the LPGW distance.

• The LPGW embedding is the primary contribution of this paper, and we numerically demonstrate that this embedding is robust to rotation/flipping/noise corruption, compared with the LOT embedding or the LGW embedding. In addition, the embedding can be used to reconstruct (denoised) data (see the following figure, which we plan to add to the paper). Meanwhile, the embedding is orthogonal to PGW, as OT/GW/PGW does not provide such an embedding.

• The LPGW distance is a byproduct of the LPGW embedding. This distance can be treated as a proxy/approximation of PGW, and it significantly improves the computational complexity.

We would like to clarify that the LPGW distance is not the primary contribution of our work; rather, it is a byproduct of the proposed LPGW embedding. Specifically, our main contribution lies beyond providing an approximation for the PGW distance, as the reviewer's comment might suggest.

Combining these two approaches to obtain a linearized partial GW problem appears to be incremental progress on the important question of efficient computation for the GW problem.

The authors respectfully disagree with the opinion that the proposed LPGW is merely a combination of PGW and LGW.

In the classical OT/GW setting, the problem admits a dynamic formulation, where the embedding is defined through the logarithm mapping. This mapping incorporates both the velocity of mass transportation and the derivative related to mass creation and destruction (noting that in balanced OT/GW, the derivative for mass creation/destruction is zero). However, in UGW, including PGW, a dynamic formulation has not yet been explored. Incorporating this dynamic information to define the embedding and establishing a similarity measure between embeddings that can recover LGW and PGW in specific settings remains a significant challenge in the field.

From a computational perspective, we demonstrate that for $K$ different metric measure spaces, computing their pairwise PGW distances requires solving the PGW problem $\mathcal{O}(K^2)$ times. In contrast, computing the LPGW distances pairwise requires only $\mathcal{O}(K)$ distance computations, representing a dramatic improvement in computational efficiency.

In addition, our work completes the theoretical analysis of linear GW in the original paper regarding barycentric projection (see Proposition 2.1 (3)), which is essential for explaining why the barycentric projection mapping can be used in the approximate aLGW formulation (e.g., (10)). We then extend this result to the PGW setting (see Proposition 3.2).

The authors sincerely thank the reviewer for their valuable comments and constructive discussion. The paper will be updated to include the detailed discussion on Monge mapping, approximation error and MNIST experiments. Additionally, the statement of Proposition 3.3 and the citation issue raised by the reviewer has been addressed/updated.

LPGW VS PGW (We refer Appendix M.2 in the updated pdf for details discussion)

LPGW utilize the partial matching property of PGW while significantly improving computational efficiency. The larger the dataset, the more pronounced the computational advantage becomes. For instance, in the MNIST classification task with a training dataset of 4000 samples, LPGW trains the model in 5 minutes, whereas PGW takes approximately 15 days.