summaries: The paper characterizes the perception-distortion in the context of (image) enhancement tradeoff, complementing prior results. For example, in image super resolution, this tradeoff describes the relationship between the point-wise reconstruction quality (distortion) and how well the distribution of the reconstructions match the distribution of the high-resolution data one aims to reconstruct. The paper derives this general tradeoff explicitly and characterizes certain aspects specifically for Gaussian distributions. The theoretical results are illustrated with experiments. Distortion-perception is the phenomenon that the better a criterion (on natural images) is optimized (for instance SNR in image denoising) the stronger the deviation to the distribution of the space of natural images. This paper characterises this phenomenon under Mean Squared Error (MSE) as the criterion under a Wasserstein bound on the conditional distribution. The result is an interpolation between the distribution of the conditional distribution and the distribution itself. An explicit formulation of the optimizer of their Distortion-perception function is provided. Simulations are made, showing that interpolating different models that approximates the quantities in their theoretical formulation can achieve better visual aspect. The authors of this paper suggest that they show four novel contributions to the image compression literature that hold true for MSE distortion and Wasserstein-2 perception index: 1. They prove that the Distortion-perception function is always quadratic in the perception constraint P regardless of the underlying distribution 2.  The show that it is possible to construct estimators of the Distortion-perception curve from estimators at the two extremes of the tradeoff (the one that globally minimizes MSE and the one that minimizes MSE under a perfect perceptual quality constraint). 3.In the gaussian setting, they provide a closed form expression for optimal estimators and the corresponding Distortion-perception curve, they also show that this is a lower bound on the curve of any distribution having the same second-order stats. 4.They illustrate their results conclusively with super-resolution as their test case. The paper studies the trade-off between minimizing the mean-square error (distortion) and the Wasserstein-2 distance (perception) when constructing an estimator \hat{X} of a random variable X. In particular, the work analyzes a distortion-perception function, which given the radius P of a Wasserstein-2 ball around X returns the minimal mean-square error of \hat{X} constrained to be in that ball.   The analysis reveals that for estimators with small Wasserstein-2 distance to the true distribution, one can often obtain an estimator with much better mean-square error by a simple linear interpolation in the output space.   The theoretical results are applied to deep image super-resolution, where it is shown that the perceptual quality of an estimator with small MSE can be improved by interpolating it with one having small Wasserstein-2 distance. Remarkably, the interpolated estimator often still has low MSE, while significantly lower Wasserstein-2 distance, leading to a greatly improved perceptual quality. 
abstractText: The lower the distortion of an estimator, the more the distribution of its outputs generally deviates from the distribution of the signals it attempts to estimate. This phenomenon, known as the perception-distortion tradeoff, has captured significant attention in image restoration, where it implies that fidelity to ground truth images comes at the expense of perceptual quality (deviation from statistics of natural images). However, despite the increasing popularity of performing comparisons on the perception-distortion plane, there remains an important open question: what is the minimal distortion that can be achieved under a given perception constraint? In this paper, we derive a closed form expression for this distortion-perception (DP) function for the mean squared-error (MSE) distortion and the Wasserstein-2 perception index. We prove that the DP function is always quadratic, regardless of the underlying distribution. This stems from the fact that estimators on the DP curve form a geodesic in Wasserstein space. In the Gaussian setting, we further provide a closed form expression for such estimators. For general distributions, we show how these estimators can be constructed from the estimators at the two extremes of the tradeoff: The global MSE minimizer, and a minimizer of the MSE under a perfect perceptual quality constraint. The latter can be obtained as a stochastic transformation of the former.
authors.name: Dror Freirich
authors.name: Tomer Michaeli
references.authors: Mohamed Abderrahmen Abid Ihsen Hedhli Christian Gagné
references.title: A generative model for hallucinating diverse versions of super resolution images
references.venue: arXiv preprint arXiv:2102.06624,
references.authors: Luigi Ambrosio Nicola Gigli Giuseppe Savaré
references.title: Gradient flows: in metric spaces and in the space of probability measures
references.venue: Springer Science & Business Media,
references.authors: Yuval Bahat Tomer Michaeli
references.title: Explorable super resolution
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: Yochai Blau Tomer Michaeli
references.title: The perception-distortion tradeoff
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Yochai Blau Roey Mechrez Radu Timofte Tomer Michaeli Lihi Zelnik-Manor
references.title: The 2018 PIRM challenge on perceptual image super-resolution
references.venue: In Proceedings of the European Conference on Computer Vision (ECCV) Workshops,
references.authors: Xin Deng
references.title: Enhancing image quality via style transfer for single image super-resolution
references.venue: IEEE Signal Processing Letters,
references.authors: Roy Friedman Yair Weiss
references.title: Posterior sampling for image restoration using explicit patch priors
references.venue: arXiv preprint arXiv:2104.09895,
references.authors: Matthias Gelbrich
references.title: On a formula for the l2 wasserstein metric between measures on euclidean and hilbert spaces
references.venue: Mathematische Nachrichten,
references.authors: Robert M Gray
references.title: Toeplitz and circulant matrices: A review
references.authors: Martin Heusel Hubert Ramsauer Thomas Unterthiner Bernhard Nessler Sepp Hochreiter
references.title: Gans trained by a two time-scale update rule converge to a local nash equilibrium
references.venue: Advances in Neural Information Processing Systems,
references.authors: Bahjat Kawar Gregory Vaksman Michael Elad
references.title: Stochastic image denoising by sampling from the posterior distribution
references.venue: arXiv preprint arXiv:2101.09552,
references.authors: Martin Knott Cyril S Smith
references.title: On the optimal mapping of distributions
references.venue: Journal of Optimization Theory and Applications,
references.authors: Christian Ledig Lucas Theis Ferenc Huszár Jose Caballero Andrew Cunningham Alejandro Acosta Andrew Aitken Alykhan Tejani Johannes Totz Zehan Wang
references.title: Photo-realistic single image super-resolution using a generative adversarial network
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Bee Lim Sanghyun Son Heewon Kim Seungjun Nah Kyoung Mu Lee
references.title: Enhanced deep residual networks for single image super-resolution
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition workshops,
references.authors: Andreas Lugmayr Martin Danelljan Luc Van Gool Radu Timofte
references.title: Srflow: Learning the super-resolution space with normalizing flow
references.venue: In European Conference on Computer Vision,
references.authors: David Martin Charless Fowlkes Doron Tal Jitendra Malik
references.title: A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics
references.venue: In Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001,
references.authors: Pablo Navarrete Michelini Dan Zhu Hanwen Liu
references.title: Multi–scale recursive and perception– distortion controllable image super–resolution
references.venue: In Proceedings of the European Conference on Computer Vision (ECCV) Workshops,
references.authors: Guy Ohayon Theo Adrai Gregory Vaksman Michael Elad Peyman Milanfar
references.title: High perceptual quality image denoising with a posterior sampling cgan
references.venue: arXiv preprint arXiv:2103.04192,
references.authors: Felix Otto Cédric Villani
references.title: Generalization of an inequality by talagrand and links with the logarithmic sobolev inequality
references.venue: Journal of Functional Analysis,
references.authors: Victor M Panaretos Yoav Zemel
references.title: An invitation to statistics in Wasserstein space
references.authors: Mangal Prakash Alexander Krull Florian Jug
references.title: Divnoising: diversity denoising with fully convolutional variational autoencoders
references.venue: arXiv preprint arXiv:2006.06072,
references.authors: Mangal Prakash Mauricio Delbracio Peyman Milanfar Florian Jug
references.title: Removing pixel noises and spatial artifacts with generative diversity denoising methods
references.venue: arXiv preprint arXiv:2104.01374,
references.authors: Mehdi SM Sajjadi Bernhard Scholkopf Michael Hirsch
references.title: Enhancenet: Single image super-resolution through automated texture synthesis
references.venue: In Proceedings of the IEEE International Conference on Computer Vision,
references.authors: Tamar Rott Shaham Tali Dekel Tomer Michaeli
references.title: SinGAN: Learning a generative model from a single natural image
references.venue: In Proceedings of the IEEE/CVF International Conference on Computer Vision,
references.authors: Assaf Shocher Nadav Cohen Michal Irani
references.title: zero-shot” super-resolution using deep internal learning
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Alon Shoshan Roey Mechrez Lihi Zelnik-Manor
references.title: Dynamic-net: Tuning the objective without re-training for synthesis tasks
references.venue: In Proceedings of the IEEE/CVF International Conference on Computer Vision,
references.authors: Asuka Takatsu
references.title: On wasserstein geometry of gaussian measures
references.venue: Mathematical Society of Japan,
references.authors: Michel Talagrand
references.title: Transportation cost for gaussian and other product measures
references.venue: Geometric & Functional Analysis GAFA,
references.authors: Dmitry Ulyanov Andrea Vedaldi Victor Lempitsky
references.title: Deep image prior
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Michael Unser
references.title: On the approximation of the discrete karhunen-loeve transform for stationary processes
references.venue: Signal Processing,
references.authors: Xintao Wang Ke Yu Shixiang Wu Jinjin Gu Yihao Liu Chao Dong Yu Qiao Chen Change Loy
references.title: ESRGAN: Enhanced super-resolution generative adversarial networks
references.venue: In Proceedings of the European Conference on Computer Vision (ECCV) Workshops,
references.authors: Xintao Wang Ke Yu Chao Dong Xiaoou Tang Chen Change Loy
references.title: Deep network interpolation for continuous imagery effect transition
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: Zhen Zhang Mianzhi Wang Arye Nehorai
references.title: Optimal transport in reproducing kernel hilbert spaces: Theory and applications
references.venue: IEEE transactions on pattern analysis and machine intelligence,
sections.heading: 1 Introduction
sections.text: Inverse problems that involve signal reconstruction from partial or noisy measurements, arise in numerous scientific domains. Examples range from medical imaging to tomography, microscopy, astronomy and audio enhancement. In many such problems it is desired to design an estimator that (i) has a small reconstruction error (low distortion), and (ii) outputs reconstructions that cannot be told apart from valid signals (good perceptual quality). Interestingly, however, it has been shown that the lower the average distortion of an estimator, the more the distribution of its outputs generally deviates from the distribution of the signals it attempts to estimate [4]. In other words, low distortion generally comes at the price of poor perceptual quality, and vice versa. This phenomenon, known as the perception-distortion tradeoff, has found particular interest in the image restoration domain (see Fig. 1), where algorithms are now commonly being evaluated using both distortion measures and perception indices [5].
  Unfortunately, despite the increasing popularity of performing comparisons on the perceptiondistortion plane, the minimal distortion that can be achieved under a given perception constraint (red curve in Fig. 1) remains an open question. Blau and Michaeli [4] investigated several properties
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  of this distortion-perception function, such as monotonicity and convexity. But beyond this rather general characterization, little is known about its precise nature. In this paper, we derive a closed form expression for the distortion-perception (DP) function for the special case where distortion is measured by mean squared-error (MSE) and perception is measured by the Wasserstein-2 distance between the probability laws of the estimate and the estimand.
  Our main contributions are: (i) We prove that the DP function is always quadratic in the perception constraint P , regardless of the underlying distribution (Theorem 1). (ii) We show that it is possible to construct estimators on the DP curve from the estimators at the two extremes of the tradeoff (Theorem 3): The one that globally minimizes the MSE, and a minimizer of the MSE under a perfect perceptual quality constraint. The latter can be obtained as a stochastic transformation of the former. (iii) In the Gaussian setting, we further provide a closed form expression for optimal estimators and for the corresponding DP curve (Theorems 4 and 5). We show this Gaussian DP curve is a lower bound on the DP curve of any distribution having the same second order statistics. Finally, we illustrate our results, numerically and visually, in a super-resolution setting in Section 5. The proofs of all our theorems are provided in Appendix B.
  Our theoretical results shed light on several topics that are subject to much practical activity. Particularly, many recent works adress the task of diverse perceptual image reconstruction, by employing randomization among possible restorations [15, 3, 22, 1]. Commonly, such works attempt to sample from the posterior distribution of natural images given the degraded input image. This is done, for example, using priors over image patches [7], conditional generative models [18, 21], or implicit priors induced by deep denoiser networks [11]. Theoretically, posterior sampling leads to perfect perceptual quality (the restored outputs are distributed like the prior). However, a fundamental question is whether this is optimal in terms of distortion. As we show in Section 3.1, posterior sampling is often not an optimal strategy, in the sense that there exist perfect perceptual quality estimators that achieve lower distortion.
  Another topic of practical interest is the ability to traverse the distortion-perception tradeoff at test time, without having to train a different model for each working point. Recently, interpolation between distortion-oriented models and perception-oriented ones, has been suggested for this end. Existing methods include interpolation in pixel space [31] or in some latent space [26], interpolation between network weights [31, 32], and style transfer between a low-distortion reconstruction and a high perceptual quality one [6]. In light of this plethora of approaches, it is natural to ask which strategy is optimal. In Section 3.2 we show that for the MSE–Wasserstein-2 tradeoff, linear interpolation in pixel space leads to optimal estimators. We also discuss a geometric connection between interpolation and the fact that estimators on the DP curve form a geodesic in Wasserstein space.
sections.heading: 2 Problem setting and preliminaries
sections.heading: 2.1 The distortion-perception tradeoff
sections.text: Let X,Y be random vectors taking values in Rnx and Rny , respectively. We consider the problem of constructing an estimator X̂ ofX based on Y . Namely, we are interested in determining a conditional distribution pX̂|Y such that X̂ constitutes a good estimate of X . For example, in the super-resolution setting shown in Fig. 1, Y is the low resolution image (left), X is the corresponding ground-truth high-resolution image (not shown), and X̂ is a super-resolution reconstruction generated from Y (e.g. the EDSR or ESRGAN estimators in the middle).
  In many practical cases, the goodness of an estimator is associated with two factors: (i) the degree to which X̂ is close to X on average (low distortion), and (ii) the degree to which the distribution of X̂ is close to that of X (good perceptual quality). An important question, then, is what is the minimal distortion that can be achieved under a given level of perceptual quality? and how can we construct estimators that achieve this lower bound? In mathematical language, we are interested in analyzing the distortion-perception (DP) function (defined similarly to the perception-distortion function of [4])
  D(P ) = min pX̂|Y
  { E[d(X, X̂)] : dp(pX , pX̂) ≤ P } . (1)
  Here, d : Rnx × Rnx → R+ ∪ {0} is some distortion criterion, dp(·, ·) is some divergence between probability measures, and pX̂ is the probability measure on R nx induced by pX̂|Y and pY . The
  expectation is taken w.r.t. the measure pXX̂ induced by pX̂|Y and pXY , where we assume that X̂ is independent of X given Y .
  As discussed in [4], the function D(P ) is monotonically non-increasing and is convex whenever dp(·, ·) is convex in its second argument (which is the case for most popular divergences). However, without further concrete assumptions on the distortion measure d(·, ·) and the perception index dp(·, ·), little can be said about the precise nature of D(P ). Here, we focus our attention on the squared-error distortion d(x, x̂) = ‖x−x̂‖2 and the Wasserstein-2 distance dp(pX , pX̂) = W2(pX , pX̂), with which (1) reads
  D(P ) = min pX̂|Y
  { E[‖X − X̂‖2] : W2(pX , pX̂) ≤ P } . (2)
  We assume that all distributions have finite first and second moments. In addition, from Theorem 3 below it will follow that the minimum is indeed attained, so that (2) is well defined.
  It is well known that the estimator minimizing the mean squared error (MSE) without any constraints, is given by X∗ = E[X|Y ]. This implies that D(P ) monotonically decreases until P reaches P ∗ ,W2(pX , pX∗), beyond which point D(P ) takes the constant value D∗ , E[‖X −X∗‖2]. This is illustrated in Fig. 2. It is also known that D(0) ≤ 2D∗ since the posterior sampling estimator pX̂|Y = pX|Y achieves W2(pX , pX̂) = 0 and E[‖X − X̂‖2] = 2D∗ [4]. However, apart from these rather general properties, the precise shape of the DP curve has not been determined to date, and neither have the estimators that achieve the optimum in (2). This is our goal in this paper.
sections.heading: 2.2 The Wasserstein and Gelbrich Distances
sections.text: Before we present our main results, we briefly survey a few properties of the Wasserstein distance, mostly taken from [20]. The Wasserstein-p (p ≥ 1) distance between measures µ and γ on a separable Banach space X with norm ‖ · ‖ is defined by
  W pp (µ, γ) , inf { E(U,V )∼ν [‖U − V ‖p] : ν ∈ Π(µ, γ) } , (3)
  where Π(µ, γ) is the set of all probabilities on X × X with marginals µ and γ. A joint probability ν achieving the optimum in (3) is often referred to as optimal plan. The Wasserstein space of probability measures is defined as
  Wp(X ) , { γ : ∫
  X ‖x‖pdγ <∞
  } ,
  and Wp constitutes a metric onWp(X ). For any (m1,Σ1), (m2,Σ2) ∈ Rd × Sd+ (where Sd+ is the set of symmetric positive semidefinite matrices in Rd×d), the Gelbrich distance is defined as
  G2((m1,Σ1), (m2,Σ2)) , ‖m1 −m2‖22 + Tr { Σ1 + Σ2 − 2 ( Σ 1 2 1 Σ2Σ 1 2 1 ) 1 2 } . (4)
  The root of a PSD matrix is always taken to be PSD. For any two probability measures µ1, µ2 on Rd with means and covariances (m1,Σ1), (m2,Σ2), from [8, Thm. 2.1] we have that
  W 22 (µ1, µ2) ≥ G2((m1,Σ1), (m2,Σ2)). (5)
  When µ1 = N (m1,Σ1) and µ2 = N (m2,Σ2) are Gaussian distributions on Rd, we have that W2(µ1, µ2) = G((m1,Σ1), (m2,Σ2)). This equality is obvious for non-singular measures but is true for any two Gaussian distributions [20, p. 18]. If Σ1 and Σ2 are non-singular, then the distribution attaining the optimum in (3) corresponds to
  U ∼ N (m1,Σ1), V = m2 + T1→2(U −m1), (6)
  where
  T1→2 = Σ − 12 1 ( Σ 1 2 1 Σ2Σ 1 2 1 ) 1 2 Σ − 12 1 (7)
  is the optimal transformation pushing forward from N (0,Σ1) to N (0,Σ2) [12]. This transformation satisfies Σ2 = T1→2Σ1T1→2. For a discussion on singular distributions, please see App. A.
sections.heading: 3 Main results
sections.heading: 3.1 The MSE–Wasserstein-2 tradeoff
sections.text: The DP function (2) depends, of course, on the underlying joint probability pXY of the signal X and measurements Y . Our first key result is that this dependence can be expressed solely in terms of D∗ and P ∗. In other words, knowing the distortion and perception index attained by the minimum MSE estimator X∗, suffices for determining D(P ) for any P .
  Theorem 1 (The DP function). The DP function (2) is given by
  D(P ) = D∗ + [(P ∗ − P )+]2 , (8) where (x)+ = max(0, x). Furthermore, an estimator achieving perception index P and distortion D(P ) can always be constructed by applying a (possibly stochastic) transformation to X∗.
  Theorem 1 is of practical importance because in many cases constructing an estimator that achieves a low MSE (i.e. an approximation of X∗) is a rather simple task. This is the case, for example, in image restoration with deep neural networks. There, it is common practice to train a network by minimizing its average squared error on a training set. Measuring the MSE of such a network on a large test set provides an approximation for D∗. We can also obtain an approximation of at least a lower bound on P ∗ by estimating the second order statistics of X and X∗. Specifically, recall that P ∗ is lower bounded by the Gelbrich distance between (mX ,ΣX) and (mX∗ ,ΣX∗), which is given by (G∗)2 , Tr{ΣX + ΣX∗ − 2(Σ1/2X ΣX∗Σ 1/2 X )
  1/2} (see (5)). Given approximations for D∗ and G∗, we can approximate a lower bound on the DP function for any P ,
  D(P ) ≥ D∗ + [(G∗ − P )+]2. (9) The bound is attained when X and Y are jointly Gaussian.
  Uniqueness A remark is in place regarding the uniqueness of an estimator achieving (8). As we discuss below, what defines an optimal estimator X̂ is its joint distribution with X∗. This joint distribution may not be unique, in which case the optimal estimator is not unique. Moreover, even if pX̂X∗ is unique, the uniqueness of the estimator is not guaranteed because there may be different conditional distributions pX̂|Y that lead to the same optimal pX̂X∗ . In other words, given the optimal pX̂X∗ , one can choose any joint probability pX̂Y X∗ that has marginals pX̂X∗ and pY X∗ . One option is to take the estimator X̂ to be a (possibly stochastic) transformation of X∗, namely pX̂|Y = pX̂|X∗pX∗|Y . But there may be other options. In cases where either Y or X̂ are a deterministic transformation of X∗ (e.g. when X∗ has a density, or is an invertible function of Y ), there is a unique joint distribution pX̂Y X∗ with the given marginals [2, Lemma 5.3.2]. In this case, if pX̂X∗ is unique then so is the estimator pX̂|Y .
  Randomness Under the settings of image restoration, many methods encourage diversity in their output by adding randomness [15, 3, 22]. In our setting, we may ask under what conditions there exists an optimal estimator X̂ which is a deterministic function of Y . For example, when pY = δ0 but X has some non-atomic distribution, it is clear that no deterministic function of Y can attain perfect perceptual quality. It turns out that a sufficient condition for the optimal X̂ to be a deterministic function of Y is that X∗ have a density. We discuss this in App. B and explicitly illustrate it in the Gaussian case (see Sec. 3.3), where if X∗ has a non-singular covariance matrix then X̂ is a deterministic function of Y .
  When is posterior sampling optimal? Many recent image restoration methods attempt to produce diverse high perceptual quality reconstructions by sampling from the posterior distribution pX|Y [7, 18, 11]. As discussed in [4], the posterior sampling estimator attains a perception index of 0 (namely W2(pX , pX̂) = 0) and distortion 2D
  ∗. But an interesting question is: when is this strategy optimal? In other words, in what cases do we have that the DP function at P = 0 equals precisely 2D∗ and is not strictly smaller? Note from the definition of the Wasserstein distance (3), that (P ∗)2 = W 22 (pX , pX∗) ≤ E[‖X −X∗‖2] = D∗. Using this in (8) shows that the DP function at P = 0 is upper bounded by D(0) = D∗ + (P ∗)2 ≤ 2D∗, (10) and the upper bound is attained when (P ∗)2 = D∗. To see when this happens, observe that
  Tr { ΣX + ΣX∗ − 2(Σ 1 2 XΣX∗Σ 1 2 X) 1 2 } = (G∗)2 ≤ (P ∗)2 ≤ D∗ = Tr{ΣX − ΣX∗}. (11)
  We can see that when Tr{ΣX∗} = Tr{(Σ1/2X ΣX∗Σ 1/2 X ) 1/2}, the leftmost and rightmost sides become equal, and thus (P ∗)2 = D∗. To understand the meaning of this condition, let us focus on the case where ΣX and ΣX∗ are jointly diagonalizable. This is a reasonable assumption for natural images,
  where shift-invariance induces diagonalization by the Fourier basis [30]. In this case, the condition can be written in terms of the eigenvalues of the matrices, namely ∑ i λi(ΣX∗) = ∑ i √ λi(ΣX∗)λi(ΣX). This condition is satisfied when each λi(ΣX∗) equals either λi(ΣX) or 0. Namely, the ith eigenvalue of the error covariance of X∗, which is given by ΣX −ΣX∗ , is either λi(ΣX) or 0. We conclude that posterior sampling is optimal when there exists a subspace S spanned by some of the eigenvectors of ΣX , such that the projection of X onto S can be recovered from Y with zero error, but the projection of X onto S⊥ cannot be recovered at all (the optimal estimator is trivial). This is likely not the case in most practical scenarios. Therefore, it seems that posterior sampling is often not optimal. That is, posterior sampling can be improved upon in terms of MSE without any sacrifice in perceptual quality.
sections.heading: 3.2 Optimal estimators
sections.text: While Theorem 1 reveals the shape of the DP function, it does not provide a recipe for constructing optimal estimators on the DP tradeoff. We now discuss the nature of such estimators.
  Our first observation is that since X̂ is independent of X given Y , its MSE can be decomposed as E[‖X − X̂‖2] = E[‖X −X∗‖2 + E[‖X∗ − X̂‖2] (see App. B). Therefore, the DP function (2) can be equivalently written as
  D(P ) = D∗ + min pX̂|Y
  { E[‖X̂ −X∗‖2] : W2(pX , pX̂) ≤ P } . (12)
  Note that the objective in (12) depends on the MSE between X̂ and X∗, so that we can perform the minimization on pX̂|X∗ rather than on pX̂|Y (once we determine the optimal pX̂|X∗ we can construct a consistent pX̂|Y as discussed above).
  Now, let us start by examining the leftmost side of the curve D(P ), which corresponds to a perfect perceptual quality estimator (i.e. P = 0). In this case, the constraint becomes pX̂ = pX . Therefore,
  D(0) = D∗ + min pX̂X∗
  { E[‖X̂ −X∗‖2] : pX̂X∗ ∈ Π(pX , pX∗) } , (13)
  where Π(pX , pX∗) is the set of all probabilities on Rnx × Rnx with marginals pX , pX∗ . One may readily recognize this as the optimization problem underlying the Wasserstein-2 distance between pX and pX∗ . This leads us to the following conclusion.
  Theorem 2 (Optimal estimator for P = 0). Let X̂0 be an estimator achieving perception index 0 and MSE D(0). Then its joint distribution with X∗ attains the optimum in the definition of W2(pX , pX∗). Namely, pX̂0X∗ is an optimal plan between pX and pX∗ .
  Having understood the estimator X̂0 at the leftmost end of the tradeoff, we now turn to study optimal estimators for arbitrary P . Interestingly, we can show that Problem (12) is equivalent to (see App. B)
  D(P ) = D∗ + min pX̂
  { W 22 (pX̂ , pX∗) : W2(pX̂ , pX) ≤ P } . (14)
  Namely, an optimal pX̂ is closest to pX∗ among all distributions within a ball of radius P around pX , as illustrated in Fig. 2. Moreover, pX̂X∗ is an optimal plan between pX̂ and pX∗ . As it turns out, this somewhat abstract viewpoint leads to a rather practical construction for X̂ from the estimators X̂0 and X∗ at the two extremes of the tradeoff. Specifically, we have the following result.
  Theorem 3 (Optimal estimators for arbitrary P ). Let X̂0 be an estimator achieving perception index 0 and MSE D(0). Then for any P ∈ [0, P ∗], the estimator
  X̂P =
  ( 1− P
  P ∗
  ) X̂0 + P
  P ∗ X∗ (15)
  is optimal for perception index P . Namely, it achieves perception index P and distortion D(P ).
  Theorem 3 has important implications for perceptual signal restoration. For example, in the task of image super-resolution, there exist many deep network based methods that achieve a low MSE [14, 29, 25]. These provide an approximation for X∗. Moreover, there is an abundance of methods that achieve good perceptual quality at the price of a reasonable degradation in MSE (often by
  incorporating a GAN-based loss) [13, 31, 24]. These constitute approximations for X̂0. However, achieving results that strike other prescribed balances between MSE and perceptual quality commonly require training a different model for each setting. Shoshan et al. [26] and Navarrete Michelini et al. [17] tried to address this difficulty by introducing new training techniques that allow traversing the distortion-perception tradeoff at test time. However, Theorem 3 shows that such specialized training methods are not required in our setting. Having a model that leads to low MSE and one that leads to good perceptual quality, it is possible to construct any other estimator on the DP tradeoff, by simply averaging the outputs of these two models with appropriate weights. We illustrate this in Sec. 5.
sections.heading: 3.3 The Gaussian setting
sections.text: When X and Y are jointly Gaussian, it is well known that the minimum MSE estimator X∗ is a linear function of the measurements Y . However, it is not a-priori clear whether all estimators along the DP tradeoff are linear in this case, and what kind of randomness they possess. As we now show, equipped with Theorem 3, we can obtain closed form expressions for optimal estimators for any P . For simplicity, we assume here that X and Y have zero means and that ΣX ,ΣY 0. It is instructive to start by considering the simple case, where ΣX∗ is non-singular (in Theorem 4 below we address the more general case of a possibly singular ΣX∗ ). It is well known that
  X∗ = ΣXY Σ −1 Y Y, ΣX∗ = ΣXY Σ −1 Y ΣY X . (16)
  Now, since we assumed that ΣX ,ΣX∗ 0, we have from Theorem 2 and (6),(7) that
  X̂0 = Σ − 12 X∗
  ( Σ 1 2
  X∗ΣXΣ 1 2 X∗
  ) 1 2
  Σ − 12 X∗X ∗. (17)
  Finally, we know that P ∗ = G∗, which is given by the left-hand side of (11). Substituting these expressions into (15), we obtain that an optimal estimator for perception P ∈ [0, G∗] is given by
  X̂P =
  (( 1− P
  G∗
  ) Σ − 12 X∗ ( Σ 1 2 X∗ΣXΣ 1 2 X∗ ) 1 2 Σ − 12 X∗ + P
  G∗ I
  ) ΣXY Σ −1 Y Y. (18)
  As can be seen, this optimal estimator is a deterministic linear transformation of Y for any P .
  The setting just described does not cover the case where Y is of lower dimensionality than X because in that case ΣX∗ is necessarily singular (it is a nx × nx matrix of rank at most ny; see (16)). In this case, any deterministic linear function of Y would result in an estimator X̂ with a rank-ny covariance. Obviously, the distribution of such an estimator cannot be arbitrarily close to that of X , whose covariance has rank nx. What is the optimal estimator in this more general setting, then? Theorem 4 (Optimal estimators in the Gaussian case). Assume X and Y are zero-mean jointly Gaussian random vectors with ΣX ,ΣY 0. Denote T ∗ , TpX→pX∗ = Σ −1/2 X (Σ 1/2 X ΣX∗Σ 1/2 X ) 1/2Σ −1/2 X . Then for any P ∈ [0, G∗], an estimator with perception index P and MSE D(P ) can be constructed as
  X̂P =
  (( 1− P
  G∗
  ) Σ 1 2
  X
  ( Σ 1 2
  XΣX∗Σ 1 2 X
  ) 1 2
  Σ − 12 X Σ † X∗ + P
  G∗ I
  ) ΣXY Σ −1 Y Y + ( 1− P
  G∗
  ) W, (19)
  whereW is a zero-mean Gaussian noise with covariance ΣW = Σ 1/2 X (I−Σ 1/2 X T ∗Σ†X∗T ∗Σ 1/2 X )Σ 1/2 X , which is independent of Y,X , and Σ†X∗ is the pseudo-inverse of ΣX∗ .
  Note that in this case, we indeed have a random noise component that shapes the covariance of X̂P to become closer to ΣX as P gets closer to 0. It can be shown (see App. B) that when ΣX∗ is invertible, ΣW = 0 and (19) reduces to (18). Also note that, as in (18), the dependence of X̂P on Y in (19) is only through X∗ = ΣXY Σ−1Y Y .
  As mentioned in Sec. 3.1, the optimal estimator is generally not unique. Interestingly, in the Gaussian setting we can explicitly characterize a set of optimal estimators. Theorem 5 (A set of optimal estimators in the Gaussian case). Consider the setting of Theorem 4. Let ΣX̂0Y ∈ R nx×ny satisfy
  ΣX̂0Y Σ −1 Y ΣY X = Σ
  1 2 X(Σ 1 2 XΣX∗Σ 1 2 X) 1 2 Σ − 12 X , (20)
  and W0 be a zero-mean Gaussian noise with covariance
  ΣW0 = ΣX − ΣX̂0Y Σ −1 Y Σ T X̂0Y
  0 (21)
  that is independent of X,Y . Then, for any P ∈ [0, G∗], an optimal estimator with perception index P can be obtained by
  X̂P =
  (( 1− P
  G∗
  ) ΣX̂0Y + P
  G∗ ΣXY
  ) Σ−1Y Y + ( 1− P
  G∗
  ) W0. (22)
  The estimator given in (19) is one solution to (20)-(21), but is generally not unique.
sections.heading: 3.4 A Comment on the MSE–Wasserstein-p tradeoff
sections.text: While our results concern the MSE−W2 tradeoff, they can be used to draw conclusions regarding the DP tradeoff with other divergences. In particular, (8) constitutes a lower bound on the MSEWasserstein-p tradeoff for any p ≥ 2. Furthermore, we can show that the MSE−W1 DP function is lower bounded by D∗ + [(P ∗1 − P )+]2, where P ∗1 ,W1(pX , pX∗). Note that at the point P = 0, the DP function coincides with (8) for any plausible divergence. For a detailed discussion, we kindly refer the reader to the Appendix.
sections.heading: 4 A geometric perspective on the distortion-perception tradeoff
sections.text: In this section we provide a geometric point of view on our main results. Specifically, we show that the results of Theorems 1 and 3 are a consequence of a more general geometric property of the space W2(Rnx). In the Gaussian case, this is simplified to a geometry of covariance matrices. Recall from (14) that the optimal pX̂ is the one closest to pX∗ (in terms of Wasserstein distance) among all measures at a distance P from pX . This implies that to determine pX̂ , we should traverse the geodesic between pX∗ and pX until reaching a distance of P from pX . Furthermore, pX̂X∗ should be the optimal plan between pX̂ and pX∗ . Interestingly, geodesics in Wasserstein spaces take a particularly simple form, and their explicit construction also turns out to satisfy the latter requirement. Specifically, let γ, µ be measures inW2(Rd), let ν ∈ Π(γ, µ) be an optimal plan attaining W2(γ, µ), and let πi denote the projection πi : Rd × Rd → Rd such that πi((x1, x2)) = xi, i = 1, 2. Then, the curve γt , [(1− t)π1 + tπ2] #ν, t ∈ [0, 1] (23) is a constant-speed geodesic from γ to µ inW2(Rd) [2], where # is the push-forward operation1. Particularly, W2(γt, γs) = |t− s|W2(γ, µ), (24) and it follows that W2(γt, γ) = tW2(γ, µ) and W2(γt, µ) = (1 − t)W2(γ, µ). Furthermore, if γt, t ∈ [0, 1] is a constant-speed geodesic with γ0 = γ, γ1 = µ, then the optimal plans between γ, γt and between γt, µ are given by
  [π1, (1− t)π1 + tπ2] #ν, [(1− t)π1 + tπ2, π2] #ν, (25) respectively, where ν ∈ Π(γ, µ) is some optimal plan. Applying (23) to (X̂0, X∗) ∼ ν with t = P/P ∗, we obtain (15), where we show that the obtained estimator achieves E[‖X̂P −X∗‖2] = (1− t)2W 22 (pX , pX∗). This explains the result of Theorem 3. It is worth mentioning that this geometric interpretation is simplified under some common settings. For example, when γ is absolutely continuous (w.r.t. the Lebesgue measure), we have a measurable map Tγ→µ which is the solution to the optimal transport problem with the quadratic cost [20, Thm 1.6.2, p.16]. The geodesic (23) then takes the form
  γt = [Id+ t(Tγ→µ − Id)]#γ, t ∈ [0, 1]. (26)
  Therefore, in our setting, if γ = pX∗ has a density, then we can obtain X̂P by the deterministic transformation [X∗+ ( 1− PP∗ ) (TpX∗→pX (X
  ∗)−X∗)] (see Remark about randomness in Sec. 3.1). 1For measures γ, µ on X ,Y , we say that a measurable transform T : X → Y pushes γ forward to µ (denoted
  T#γ = µ) iff γ(T−1(B)) = µ(B) for any measurable B ⊆ Y.
  Further simplification arises when γ, µ are centered non-singular Gaussian measures, in which case Tγ→µ is the linear and symmetric transformation (7). Then, γt is a Gaussian measure with covariance Σγt = TtΣγTt, where Tt , [I + t(Tγ→µ − I)]. Therefore, in the Gaussian case, the shortest path (23) between distributions is reduced to a trajectory in the geometry of covariance matrices induced by the Gelbrich distance [27]. If additionally Σγ and Σµ commute, then the Gelbrich distance is further reduced to the `2-distance between matrices, as we discuss in App. D.
sections.heading: 5 Numerical illustration
sections.text: We now experimentally illustrate the results of Theorems 1 and 3. We compute distortion and perception indices for 13 super resolution algorithms in a 4× magnification task on the BSD100 dataset2 [16]. We then demonstrate the efficiency of approximating the lower bound (9) on the distortion D(P ), and of the estimators suggested in (15), in this practical setting. The evaluated algorithms include EDSR [14], ESRGAN [31], SinGAN [24], ZSSR [25], DIP [29], SRResNet variants which optimize MSE and VGG2,2, SRGAN variants which optimize MSE, VGG2,2 and VGG5,4 in addition to an adversarial loss [13], ENet [23] (“PAT” and “E” variants), and the stochastic explorable SR method of [3] (ExpSR). Low resolution images were obtained by 4× downsampling of BSD100 images using a bicubic kernel.
  In Fig. 3 we plot each method on the distortion-perception plane. In the left pane, we consider natural (and reconstructed) images to be stationary random sources, and use 9× 9 patches (totally 1.6× 106 patches) to empirically estimate the mean and covariance matrix for the ground-truth images, and for the reconstructions produced by each method. We then use the estimated Gelbrich distances (4) between the patch distribution of each method and that of ground-truth images, as a perceptual quality index. Recall this is a lower bound on the Wasserstein distance. In the right pane of Fig. 3, we measure perception using the popular FID index [10], which relies on the Fréchet distance between deep feature distributions of ground-truth and reconstructed images (assuming they are normally distributed). FID is known to correlate well with visual quality, and while it is not directly related to our theory, we can see a qualitatively similar behavior to that depicted in the left pane.
  We consider the EDSR method [14] to constitute a good approximation for the minimum MSE estimator X∗ since it achieves the lowest MSE among the evaluated methods. We therefore estimate the lower bound (9) as D̂(P ) = DEDSR + [(PEDSR − P )+]2 , where DEDSR is the MSE of EDSR, and PEDSR is the estimated Gelbrich distance between EDSR reconstructions and ground-truth images. Note the unoccupied region under the estimated curve in Fig. 3, which is indeed unattainable according to the theory.
  The figure also shows 9 estimators X̂t, which we construct by interpolation between EDSR and ESRGAN, X̂t = tXEDSR + (1− t)XESRGAN with t ∈ [0, 1]. We observe that estimators constructed using these two extreme points are closer to the optimal DP tradeoff than the other evaluated methods. This is true both for the Gelbrich perception index and for FID. In Fig. 4 we present a visual comparison between SRGAN-VGG2,2 [13] and our interpolated estimator X̂0.12. Both achieve roughly the same RMSE distortion (18.08 for SRGAN, 18.14 for X̂0.12), but our estimator achieves a lower perception index. Namely, by using interpolation, we manage to achieve improvement in perceptual quality, without degradation in distortion. The improvement in visual quality is also apparent in the figure. Additional visual comparisons including more points along the DP curve and ground-truth images can be found in the Appendix.
sections.heading: 6 Conclusion
sections.text: In this paper we provide a full characterization of the distortion-perception tradeoff for the MSE distortion and the Wasserstein-2 perception index. We show that optimal estimators are obtained by interpolation between the minimum MSE estimator and an optimal perfect perceptual quality estimator. In the Gaussian case, we explicitly formulate these estimators. To the best of our knowledge, this is the first work to derive such closed-form expressions. Our work paves the way towards fully
  2All codes are freely available and provided by the authors.
  S R
  G A N V G G 2, 2
  X̂ 0. 12
  E S
  R
  G
  A
  N
  E D S
  R L ow R es .
  G ro
  u n
  d .
  4853 1420 4592
  Figure 4: A visual comparison between estimators with approximately the same MSE. Upper: SRGAN-VGG2,2. Lower: X̂0.12, an interpolation between EDSR and ESRGAN using t = 0.12. Observe the improvement in perceptual quality, without any significant degradation in distortion.
  understanding the DP tradeoff under more general distortions and perceptual criteria, and bridging between fidelity and visual quality at test-time, without training different models.
  Broader impact Synthesis of photo-realistic visual contents may raise concerns of inappropriate and malicious use. This is true for image generation in general (e.g. with GANs), but to some extent also for image restoration tasks like super-resolution. However, even without malicious intent, the outputs of a high perceptual quality algorithm can often not be very close to the ground truth images. In this paper we quantify this effect, by studying the best similarity (lowest distortion) one can hope to achieve with an algorithm having a prescribed level of perceptual quality.
  Acknoledgments This work was partially supported by grants 451/17 and 852/17 from the Israel Science Foundation, by the Ollendorff Center of the Viterbi Faculty of Electrical and Computer Engineering at the Technion, and by the Skillman chair in biomedical sciences.
  10
title: A Theory of the Distortion-Perception Tradeoff in Wasserstein Space