Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This submission proposes an algorithm for numerically estimating the optimal transport (OT) map in dimension $3$ between a source distribution $\mu$ admitting a (Hölder) continuous density on $[0,1]^3$, and the Lebesgue measure on $[0,1]^3$. In this context, the optimal transport map can be characterized as the solution of a nonlinear degenerate elliptic partial differential equation (PDE) known as the Monge-Ampère equation. 

The proposed method consists of applying the classical method of continuity to obtain a one-parameter family of PDEs $(\det(D_x^2u(x,t))=\rho(x,t))_{t\in[0,1]}$ for which $u(x,0)$ is known and $u(x,1)$ can be used to obtain the OT map. Next, this family is discretized with respect to its parameter, linearized, and the resulting variable coefficient linear elliptic PDEs are made into constant coefficient PDEs by averaging the coefficients. Given the solution at the previous step, it is updated by solving the resulting constant coefficient PDE; which is amenable to computation by a fast and parallelizable spectral method based on the Fast Fourier Transform (FFT) implemented on GPUs. 

The algorithm is shown to benefit from a linear rate of convergence. Applications to density sampling and volume magnification are also included.
strength_and_weaknesses: # Strengths 
- This submission builds nicely upon the previous work of Loeper-Rapetti [1] and Saumier et al. [2] by providing a fast and parallelizable spectral approach to solving the Monge-Ampère equation characterizing the OT map in this particular setting. This algorithmic improvement is enabled by the simple approach of averaging the coefficients of the variable coefficient PDEs obtained from the linearization approach discussed in [1] and [2].

- The applications to density sampling and volume magnification are of interest and the proposed method appears to give good results in the provided experiments.

# Weaknesses

 - In contrast to [2], the present submission does not cover the case where the target distribution is not the Lebesgue measure. The source distribution is also required to satisfy some conditions which restrict the general applicability of this method.

-Theorem 3 states that "one can choose the step length parameter $\tau$ such that [...] the algorithm has a linear convergence rate." However, per the proof of this Theorem, the choice of $\tau$ depends on the uniform ellipticity properties of the solution to the problem. There is, in particular, no discussion on how $\tau$ was chosen in the experiments, nor how one should choose $\tau$ in general. 

-The submission also contains a number of technical errors which we list below
1. The entire paper appears to work under the assumption that the Brenier potential $u\in C^2(\Omega)$. As discussed in Theorem 2.1 in [2], this requires some additional conditions on the density of $\mu$ which are not mentioned in the present submission.

2. In equation (26), it is claimed that the integral over the boundary is equal to 0 as $\partial \Omega$ has zero measure. The reasoning here is erroneous, as although $\partial \Omega$ has zero Lebesgue measure, integrals over the boundary are taken with respect to the relevant surface measure, not the Lebesgue measure and $\partial \Omega$ has positive measure with respect to the surface measure.

3. Although it is not explicitly mentioned in the submission, the density of $\mu$ with respect to the Lebesgue measure must be positive on $\Omega$ for some of the claims to hold.

4. In the introduction, the OT map is stated to define a distance between any two probability distributions. This is incorrect, in particular there exists no transport map between a Dirac mass supported on one point and a normalized sum of two Dirac masses. It is rather the Kantorovich problem and corresponding OT couplings which are used to define such a distance.

5. Problem 1 is stated in terms of measure preserving maps which, in turn, are only defined in this manuscript in the context of $C^1$ maps. As such the statement of Brenier's theorem provided (Theorem 2) is incorrect, as the OT map provided by the true Brenier theorem need not be $C^1$, rather it is only guaranteed to be differentiable $\mu$-a.e. by Alexandrov's theorem under the present assumptions (cf. eg. Theorem 3.1 and Theorem 3.2 in [3]). Similarly, Problem 1 is typically stated as an optimization problem over arbitrary measurable maps satisfying the pushforward condition $T_{\sharp} \mu =\nu$ i.e. $\mu(T^{-1}(A))=\nu(A)$ for every Borel set $A$.  

6. The proof of the main theorem is difficult to follow to the point where I cannot guarantee its accuracy. In particular, the notation $a_k, A_k,\bar A_k$ is undefined despite these objects playing a central role in the proof. Moreover, I do not understand the meaning of the display after equation (37),
$(f_h-\rho_{h,k})^TA_k\bar A_k^{-1}(f_h-\rho_{h,k})=\text{tr} ((f_h-\rho_{h,k})^TA_k\bar A_k^{-1}(f_h-\rho_{h,k}))$, it is obvious that the trace of a scalar is equal to itself.

## References

[1]: G. Loeper and F. Rapetti. Numerical solution of the Monge-Ampère equation by a Newton's algorithm. _C. R. Acad. Sci. Paris_, Ser. I 340(4), 2005.

[2]: L.-P. Saumier, M. Agueh, and B. Khouider. An efficient numerical algorithm for the L2 optimal transport problem with periodic densities. _IMA J. Appl. Math._, 80(1), 2015.

[3]: G. De Philippis and A. Figalli. The Monge–Ampère equation and its link to optimal transportation. _Bull. Am. Math. Soc_, 51(4), 2014.
clarity,_quality,_novelty_and_reproducibility: # Clarity
The submission is relatively clear, but has a large number of typos and minor inconsistencies. We list the main typos and inconsistencies here.

1. The role of $\tau$ as described in [1] is as a stabilization factor, not a step length as stated in Algorithm 1. Furthermore, I believe the update of the Brenier potential in the same algorithm should be $u_n+v_n$, not $u_n+\tau v_n$ to match with the reference [1] (also $\tau$ should in practice be large).
2. The scores in Figure 5 and Figure 6 do not vary over the rows. This seems like a mistake, as the scores in Figure 2 do vary.
3. In Appendix B.2. and B.3. many of the norms should be squared, but are not.  
4. There is some notation in the proof of the main theorem which is not defined, see the weaknesses section for a more in depth discussion.
5. Names with accents are spelled inconsistently. The correct spellings are Monge-Ampère and Poincaré. This does not effect clarity, but should be fixed.

# Quality 

The paper includes a number of technical errors as discussed in the weaknesses section.

# Novelty 

The novelty of this work is reasonable. Although it presents only a simple modification to the work of [1] and [2] via averaging of the coefficients of the variable coefficient PDEs and applying a spectral method rather than solving these variable coefficient PDEs directly as in [2], the simplicity and speed of the proposed method is certainly of interest.


# Reproducibility

The main algorithmic details of the paper would be simple to reproduce. My only concern is the lack of discussion for how $\tau$ is chosen so as to guarantee linear rates of convergence (see the Weaknesses section for additional details).

## References

[1]: G. Loeper and F. Rapetti, Numerical solution of the Monge-Ampère equation by a Newton's algorithm. _C. R. Acad. Sci. Paris_, Ser. I 340(4), 2005.

[2]: L.-P. Saumier, M. Agueh, and B. Khouider, An efficient numerical algorithm for the L2 optimal transport problem with periodic densities. _IMA J. Appl. Math._, 80(1), 2015.
summary_of_the_review: The method proposed in this submission is of interest due to its simplicity and speed. The main novelty is to average the coefficients of the linearized PDEs to enable a spectral approach. The proposed applications of this work are also of interest. As it stands, however, the submission has a number of technical mistakes and thus I cannot recommend acceptance of this work in its current state.

## Post Rebuttal Comments:

In their rebuttal, the authors have fixed many of the technical issues that were brought up in the previous review. The scores have been amended to reflect these changes. Please also address the following list of issues; some of which were mentioned in the original review, but were not fixed in the revised manuscript. I also suggest that the revised manuscript be proofread to fix typos. 

1. Spelling of names with accents are still inconsistent. 
2. In the appendix many of the norms should be squared, but are not.
3. After equation (37), the sentence "The scalar" followed by the displayed equation does not make sense. I would recommend replacing that sentence by "Remark that the following displayed equation is a scalar" if this emphasis is deemed to be necessary.
4. $o(\tau^{-1})$ is simply dropped after equation (37) without further comment, this is somewhat sloppy.
5. In the display before (38), the upper bound is not used in the remainder of the proof to my understanding; if that is the case, the upper bound can just be dropped. The lower bound in the same display could use a bit more explanation to make it more clear to the reader. 
6. It would be useful to add a comment on why $\bar{A}_k$ is invertible before (37).
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors propose a new method based on Fast Fourier to compute 3D optimal transport problems.

The authors show great speedups and provide theoretical insights using elliptic PDEs. Applications in sampling and for magnification of volumetric data.
strength_and_weaknesses: The methods is very fast but needs more memory (storage complexity increases exponentially). The method can be extended to work with any number of dimensions.

The connection between volumetric magnification and denoising or super resolution should be clarified.

Figures 3 and 4 do not show the magnification ratios used.

The following statement needs clarification :
"Compared with the traditional method requiring tedious zoom in/out, our method only magnifies the
ROI region and keeps the whole subject in the field of view, which enables doctors to visualize the
overall anatomy while scrutinize detailed anatomical structure at the same time."

Not clear why this is better than magnifying the entire volume. Isn't it puzzling for the doctor looking at some regions being zoomed?

clarity,_quality,_novelty_and_reproducibility: The paper is clear and novel.

The figures need to be improved by providing zoom factors and highlighting both upper and lower rows.

The code is not provided. Therefore the paper is hard to reproduce. However, the major algorithms are provided and they seem straightforward.
summary_of_the_review: Overall, this is novel work and valuable. The speedups and theoretical connections are impressive.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper develops a fast method for solving the optimal transport problem on 3d densities. The authors convert a linearized functional equation to a set of elliptic differential equations, and solve those using an FFT solver---converting finite differences scheme to an algebraic system by passing to the frequency space. The authors perform a convergence analysis and show applications that highlight the usefulness of the method.
strength_and_weaknesses: The main strength is that the method converges quickly and allows parallel calculation via gpus. It also provides a novel algorithm for nD approximate optimal transport (using the g=1, inversion trick). 

A primary weakness in this work is that the method is not rigorously evaluated on relevant application areas for this conference. The most relevant experiments in Section 4.2, on adaptive sampling, are very limited. Only a single density is shown, and while the numerical comparisons presented to common sampling algorithms look good I don't think it can be said that this approach is much better for sampling. In part because of obvious patterns that appear in the transported grid centers. Perhaps this could be cleaned up with a more sophisticated algorithm, but then a more thorough analysis would be called for. I think the paper could benefit from that. The 3d magnification example is also lacking in my opinion, I cannot understand the need to perform 3d magnification with this method, as opposed to restricting a new viewing window to the ROI. For medical imaging, I suspect that the resulting distortion would make whatever benefits could be obtained through magnification useless.
clarity,_quality,_novelty_and_reproducibility: The derivations are clear and the value of the work is clear, as optimal transport is a commonly arising problem in both machine learning and applied scientific computing. One minor note on clarity is that in some cases citations contain repeated author names: e.g. in the final paragraph of Section 1 "Though Lei and Gu [Lei & Gu] (2021) also uses FFT to solve the 2-dimensional OT problem..." and this occurs occasionally throughout.

One question that arose for me while reading was the use of the simplification in algorithm 1: g=1. This is not a valid simplification for optimal transport that I am aware of, could the authors provide some more reasoning for this simplification?

A central concern for me with this paper is novelty. As mentioned in the paper, Lei and Gu have already derived a very similar method. The algorithm is nearly identical, barring the fact that the aforementioned work only applies to 2d densities. I am not confident that this extension merits a full conference paper since the differences are mostly formal based on my understanding. 
summary_of_the_review: Contributions in this field are important for a wide range of machine learning problems. I think that the result in this paper are promising and worthy of publication in some forum. However, the experimental analysis and is not in a condition to be published presently. More extensive analysis on the use of 3d FFT-OT for sampling could result in a more appropriate submission in my opinion, including comparison of runtime and more thorough empirical and theoretical analysis of the algorithm used as a sampler.

--- 
I have updated more overall assessment of the contribution after more carefully reviewing the literature. The authors addressed my concerns with the g=1 assumption, which I believe that they should make more explicit in their manuscript. Other than that I think the work is acceptable, if slightly below my standards for rigorous empirical analysis. Time permitting, experiments assessing the quality of the sampling algorithm they propose on nD canonical distributions (e.g. Cauchy, Gaussian, comb) from the standpoint of information theoretic metrics would overcome my reservations here, but I don't think they're strictly necessary for publication.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Summary:

This  paper proposes an algorithm for numerically estimating the optimal transport (OT) map in dimension 3. In this context, the optimal transport map can be characterized as the solution of the Monge-Ampère equation. After discretization and linearization the paper builds on the work of  Loeper-Rapetti and Saumier et al to solve it using the FFT. A GPU implementation ensures a fast and parralelized implementation. The algorithm has a linear rate of convergence. Applications to density sampling and volume magnification are also provided in the paper. 

Reviewers agreed on the merits of the paper. The paper improved a lot during the rebuttal thanks to the detailed reviews of reviewers Reviewer Q68w and Reviewer AQZc.  Thanks to them ! Many corrections to the rigor and the experimental setup made the paper in a better shape for publication. 
 
justification_for_why_not_higher_score: The application of OT in 3D are important in medical imaging domain and perhaps in robotics,  the applications of such technical work are not of general interest.
Decision: Accept: poster