Fourier Sliced-Wasserstein Embedding for Multisets and Measures
Sliced Wasserstein distance;Euclidean embedding;bi-Lipschitz;permutation invariance;multisets;optimal transport
There is a fundamental difference between our embedding approach and approaches such as Distributional Sliced Wasserstein and Max-Sliced Wasserstein. Our approach takes one input distribution at a time and computes an _embedding_, whereas the aforementioned approaches take two input distributions and estimate a _distance_ between them. Pairwise methods have two disadvantages in comparison with embeddings: (i) higher computational complexity when computing multiple pairwise disances, and (ii) limited applicability to real-world learning problems.

In terms of applicability, a pairwise method cannot be directly applied to common learning tasks, such as object classification, where the inputs are typically individual distributions. In contrast, an embedding is readily applicable to such tasks, as demonstrated in our experiments.

In terms of computation, pairwise methods to estimate sliced optimal transport distances typically require $\tilde{\mathcal{O}}(mnd)$ time (neglecting logarithmic factors), where $m$ is the number of slices, $n$ is the maximal number of support points, and $d$ is the ambient dimension of the support. Thus, computing all pairwise distances for a set of $k$ distributions would take $\tilde{\mathcal{O}}(k^2 mnd)$ time. In contrast, computing our embedding takes $\tilde{\mathcal{O}}(mnd)$ time for each input distribution, and pairwise distances can then be computed in the Euclidean space $\mathbb{R}^m$, resulting in a considerably lower total complexity of $\tilde{\mathcal{O}}(k mnd + k^2 m)$. This approach is therefore significantly more scalable for large datasets where pairwise distance computations are required.

We appreciate the reviewer's comment and will clarify this in the paper.
Response to Reviewer Ew1o
Yes
No ethics review needed.
See Weaknes section.
- The paper is well-written and easy to follow. Proofs are rigorous. 
- Proposing the sliced embedding Wasserstein (SEW) through a cosine transform of the projected quantile function. Sampling the quantile function via cosine transform is novel.
- Injectivity and bi-Lipschitz properties of FSEW on the collection of multisets.
- Numerical experiments showcase better Wasserstein approximation on simulated datasets and three real datasets than NProductNet, WPCE, NSDeepSets, and Sinkhorn.
This paper considers Fourier slicing embedding both for a collection of probability distributions and multisets over $\mathbb{R}^d$ and supported at $n$ points. The embedding consists of a projection sample on a 1-dimensional vector on the sphere then calculates a cosine transform of the projected quantile function. Under a specific probability distribution of the frequency, the authors prove that the expectation of the estimation error between the embedded measures is exactly the sliced Wasserstein distance. A second part of the theoretical results consists of proving the injectivity of the embedding under the assumption that the dimension embedding $m \geq 2n(d+1) +1$. Numerical experiments are conducted on point cloud classification.
- Several approaches for the derivative of sliced Wasserstein distance like, distributional sliced Wasserstein (Nguen et al, ICLR'21), max-sliced Wasserstein, etc ... Could you highlight the difference between FSW and the SOTA derivative of sliced Wasserstein?
Yes
No ethics review needed.
I am new to this field. Could the authors elaborate more on the practical motivation and applications of this approach?
The theoretical contribution seems to be sound, with explicitly stated technical assumptions and results. Numerical study is solid.
This paper presents a novel approach to high-dimensional dataset embedding. The authors provided theoretical performance guarantees and numerical study to show the superior performance of the framework.
1. The authors denovted much space to describe the p-wasserstein and infinity-type Wasserstein distance. Why it is necessary to introduce infinity-type Wasserstein distance?
2. In line 222, the authors mentioned that in the special case of d=1, Wasserstien can be computed significantly fast. So what is the complexity rate?
3. In line 344, what is the definition of STD???
4. The authors should provide proof ideas for the main technical results in the main content.
Yes
No ethics review needed.
I haven't any question.
The paper is well-structured, and its message is clear. The proofs provided are rigorous and exceptionally clear. This particular problem is quite interesting. I really enjoyed reading the paper.
The paper seeks to establish a mapping from multisets and measures over $ \mathbb{R}^d $ into Euclidean space, ensuring that the sliced Wasserstein distance corresponds to the distance between their mappings in the target space. The authors propose a mapping that is bi-Lipschitz for multisets and injective for measures. Additionally, they demonstrate that a bi-Lipschitz map for measures does not exist.
I don't see any weaknesses. Therefore, I recommend accepting it.
Yes
No ethics review needed.
1. Regarding point (2), is "Multisets" simply another term for "discrete distributions"?  
2. Could you clarify what "E2" refers to in lines 473-474?
1. The combination of the Fourier/cosine transform and the sliced Wasserstein distance (see Eq. (6)) is a novel approach.
2. Theoretical properties for this new technique with respect to the uniform distribution, along with its empirical approximation, are proposed (see Theorem 3.2, Corollary 3.3).
3. Injectivity and bi-Lipschitz properties of the embedding have been investigated.
**Summary:**  
The paper introduces the "Fourier Sliced Wasserstein (FSW) embedding" for data in \(\mathbb{R}^d\).

**Theoretical Contributions:**  
1. The authors prove that the embedding preserves or approximates the sliced Wasserstein distance.  
2. They also demonstrate that the embedding technique is injective and bi-Lipschitz.

**Numerical Experiments:**  
1. The authors evaluate the approximation error of the proposed Fourier Sliced Wasserstein embedding.  
2. They showcase an application of FSW for approximating the Wasserstein distance using a Multi-Layer Perceptron (MLP).
1. I recommend adding a section to introduce baseline methods. For example, explaining how Sinkhorn [Cuturi, 2013] can be used to train a neural network as a Wasserstein distance estimator. Currently, the experimental setup (E1, E2, Phi, Leaky-ReLU) appears tailored only to the proposed method in this paper.
2. It would be beneficial to introduce a real-data application of the proposed Sliced Wasserstein distance embedding technique to illustrate its practical utility.
3. I’m unclear on why 'bi-Lipschitz' is considered a crucial property. Could you provide an example to clarify? For instance, in which applications would the lack of a bi-Lipschitz property cause issues, and where having this property could offer distinct advantages?
Euclidean embedding for multisets and measures with injectivity and bi-Lipschitzness guarantees, based on the sliced Wasserstein distance
@inproceedings{
anonymous2024fourier,
title={Fourier Sliced-Wasserstein Embedding for Multisets and Measures},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=BcYt84rcKq},
note={under review}
}
We present the _Fourier Sliced Wasserstein (FSW) embedding_—a novel method to embed multisets and measures over $\mathbb{R}^d$ into Euclidean space.

Our proposed embedding approximately preserves the sliced Wasserstein distance on distributions, thereby yielding geometrically meaningful representations that better capture the structure of the input. Moreover, it is injective on measures and _bi-Lipschitz_ on multisets—a significant advantage over prevalent embedding methods based on sum- or max-pooling, which are provably not bi-Lipschitz, and in many cases, not even injective.
The required output dimension for these guarantees is near optimal: roughly $2 n d$, where $n$ is the maximal number of support points in the input.

Conversely, we prove that it is _impossible_ to embed distributions over $\mathbb{R}^d$ into Euclidean space in a bi-Lipschitz manner. Thus, the metric properties of our embedding are, in a sense, the best achievable.

Through numerical experiments, we demonstrate that our method yields superior representations of input multisets and offers practical advantage for learning on multiset data. Specifically, we show that (a) the FSW embedding induces significantly lower distortion on the space of multisets, compared to the leading method for computing sliced-Wasserstein-preserving embeddings; and (b) a simple combination of the FSW embedding and an MLP achieves state-of-the-art performance in learning the (non-sliced) Wasserstein distance.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Sliced Wasserstein distance Euclidean embedding bi-Lipschitz permutation invariance multisets optimal transport
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/1a1a0a75e310f9efebc31fab2ef0bc15a2671f1a.pdf
learning on graphs and other geometries & topologies
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Fourier Sliced-Wasserstein Embedding for Multisets and Measures
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission