skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: A new perspective on denoising based on optimal transport
Abstract In the standard formulation of the classical denoising problem, one is given a probabilistic model relating a latent variable $$\varTheta \in \varOmega \subset{\mathbb{R}}^{m} \; (m\ge 1)$$ and an observation $$Z \in{\mathbb{R}}^{d}$$ according to $$Z \mid \varTheta \sim p(\cdot \mid \varTheta )$$ and $$\varTheta \sim G^{*}$$, and the goal is to construct a map to recover the latent variable from the observation. The posterior mean, a natural candidate for estimating $$\varTheta $$ from $$Z$$, attains the minimum Bayes risk (under the squared error loss) but at the expense of over-shrinking the $$Z$$, and in general may fail to capture the geometric features of the prior distribution $$G^{*}$$ (e.g. low dimensionality, discreteness, sparsity). To rectify these drawbacks, in this paper we take a new perspective on this denoising problem that is inspired by optimal transport (OT) theory and use it to study a different, OT-based, denoiser at the population level setting. We rigorously prove that, under general assumptions on the model, this OT-based denoiser is mathematically well-defined and unique, and is closely connected to the solution to a Monge OT problem. We then prove that, under appropriate identifiability assumptions on the model, the OT-based denoiser can be recovered solely from information of the marginal distribution of $$Z$$ and the posterior mean of the model, after solving a linear relaxation problem over a suitable space of couplings that is reminiscent of standard multimarginal OT problems. In particular, due to Tweedie’s formula, when the likelihood model $$\{ p(\cdot \mid \theta ) \}_{\theta \in \varOmega }$$ is an exponential family of distributions, the OT-based denoiser can be recovered solely from the marginal distribution of $$Z$$. In general, our family of OT-like relaxations is of interest in its own right and for the denoising problem suggests alternative numerical methods inspired by the rich literature on computational OT.  more » « less
Award ID(s):
2311062 2236447 2023239
PAR ID:
10611437
Author(s) / Creator(s):
;
Publisher / Repository:
Published by Oxford University Press on behalf of the Institute of Mathematics and its Applications
Date Published:
Journal Name:
Information and Inference: A Journal of the IMA
Volume:
13
Issue:
4
ISSN:
2049-8772
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Due to the high dimensional integration over latent variables, computing marginal likelihood and posterior distributions for the parameters of a general hierarchical model is a difficult task. The Markov Chain Monte Carlo (MCMC) algorithms are commonly used to approximate the posterior distributions. These algorithms, though effective, are computationally intensive and can be slow for large, complex models. As an alternative to the MCMC approach, the Laplace approximation (LA) has been successfully used to obtain fast and accurate approximations to the posterior mean and other derived quantities related to the posterior distribution. In the last couple of decades, LA has also been used to approximate the marginal likelihood function and the posterior distribution. In this paper, we show that the bias in the Laplace approximation to the marginal likelihood has substantial practical consequences. 
    more » « less
  2. Celebrated theorems of Roth and of Matoušek and Spencer together show that the discrepancy of arithmetic progressions in the first $$n$$ positive integers is $$\Theta (n^{1/4})$$ . We study the analogous problem in the $$\mathbb {Z}_n$$ setting. We asymptotically determine the logarithm of the discrepancy of arithmetic progressions in $$\mathbb {Z}_n$$ for all positive integer $$n$$ . We further determine up to a constant factor the discrepancy of arithmetic progressions in $$\mathbb {Z}_n$$ for many $$n$$ . For example, if $n=p^k$ is a prime power, then the discrepancy of arithmetic progressions in $$\mathbb {Z}_n$$ is $$\Theta (n^{1/3+r_k/(6k)})$$ , where $$r_k \in \{0,1,2\}$$ is the remainder when $$k$$ is divided by $$3$$ . This solves a problem of Hebbinghaus and Srivastav. 
    more » « less
  3. Summary Motivated by the problem of estimating bacterial growth rates for genome assemblies from shotgun metagenomic data, we consider the permuted monotone matrix model $$Y=\Theta\Pi+Z$$ where $$Y\in \mathbb{R}^{n\times p}$$ is observed, $$\Theta\in \mathbb{R}^{n\times p}$$ is an unknown approximately rank-one signal matrix with monotone rows, $$\Pi \in \mathbb{R}^{p\times p}$$ is an unknown permutation matrix, and $$Z\in \mathbb{R}^{n\times p}$$ is the noise matrix. In this article we study estimation of the extreme values associated with the signal matrix $$\Theta$$, including its first and last columns and their difference. Treating these estimation problems as compound decision problems, minimax rate-optimal estimators are constructed using the spectral column-sorting method. Numerical experiments on simulated and synthetic microbiome metagenomic data are conducted, demonstrating the superiority of the proposed methods over existing alternatives. The methods are illustrated by comparing the growth rates of gut bacteria in inflammatory bowel disease patients and control subjects. 
    more » « less
  4. Abstract This is a continuation, and conclusion, of our study of bounded solutions u of the semilinear parabolic equation $$u_t=u_{xx}+f(u)$$ u t = u xx + f ( u ) on the real line whose initial data $$u_0=u(\cdot ,0)$$ u 0 = u ( · , 0 ) have finite limits $$\theta ^\pm $$ θ ± as $$x\rightarrow \pm \infty $$ x → ± ∞ . We assume that f is a locally Lipschitz function on $$\mathbb {R}$$ R satisfying minor nondegeneracy conditions. Our goal is to describe the asymptotic behavior of u ( x ,  t ) as $$t\rightarrow \infty $$ t → ∞ . In the first two parts of this series we mainly considered the cases where either $$\theta ^-\ne \theta ^+$$ θ - ≠ θ + ; or $$\theta ^\pm =\theta _0$$ θ ± = θ 0 and $$f(\theta _0)\ne 0$$ f ( θ 0 ) ≠ 0 ; or else $$\theta ^\pm =\theta _0$$ θ ± = θ 0 , $$f(\theta _0)=0$$ f ( θ 0 ) = 0 , and $$\theta _0$$ θ 0 is a stable equilibrium of the equation $${{\dot{\xi }}}=f(\xi )$$ ξ ˙ = f ( ξ ) . In all these cases we proved that the corresponding solution u is quasiconvergent—if bounded—which is to say that all limit profiles of $$u(\cdot ,t)$$ u ( · , t ) as $$t\rightarrow \infty $$ t → ∞ are steady states. The limit profiles, or accumulation points, are taken in $$L^\infty _{loc}(\mathbb {R})$$ L loc ∞ ( R ) . In the present paper, we take on the case that $$\theta ^\pm =\theta _0$$ θ ± = θ 0 , $$f(\theta _0)=0$$ f ( θ 0 ) = 0 , and $$\theta _0$$ θ 0 is an unstable equilibrium of the equation $${{\dot{\xi }}}=f(\xi )$$ ξ ˙ = f ( ξ ) . Our earlier quasiconvergence theorem in this case involved some restrictive technical conditions on the solution, which we now remove. Our sole condition on $$u(\cdot ,t)$$ u ( · , t ) is that it is nonoscillatory (has only finitely many critical points) at some $$t\ge 0$$ t ≥ 0 . Since it is known that oscillatory bounded solutions are not always quasiconvergent, our result is nearly optimal. 
    more » « less
  5. Though generative adversarial networks (GANs) are prominent models to generate realistic and crisp images, they are unstable to train and suffer from the mode collapse problem. The problems of GANs come from approximating the intrinsic discontinuous distribution transform map with continuous DNNs. The recently proposed AE-OT model addresses the discontinuity problem by explicitly computing the discontinuous optimal transform map in the latent space of the autoencoder. Though have no mode collapse, the generated images by AE-OT are blurry. In this paper, we propose the AE-OT-GAN model to utilize the advantages of the both models: generate high quality images and at the same time overcome the mode collapse problems. Specifically, we firstly embed the low dimensional image manifold into the latent space by autoencoder (AE). Then the extended semi-discrete optimal transport (SDOT) map is used to generate new latent codes. Finally, our GAN model is trained to generate high quality images from the latent distribution induced by the extended SDOT map. The distribution transform map from this dataset related latent distribution to the data distribution will be continuous, and thus can be well approximated by the continuous DNNs. Additionally, the paired data between the latent codes and the real images gives us further restriction about the generator and stabilizes the training process. Experiments on simple MNIST dataset and complex datasets like CIFAR10 and CelebA show the advantages of the proposed method. 
    more » « less