Abstract We propose two graph neural network layers for graphs with features in a Riemannian manifold. First, based on a manifold-valued graph diffusion equation, we construct a diffusion layer that can be applied to an arbitrary number of nodes and graph connectivity patterns. Second, we model a tangent multilayer perceptron by transferring ideas from the vector neuron framework to our general setting. Both layers are equivariant under node permutations and the feature manifold’s isometries. These properties have led to a beneficial inductive bias in many deep-learning tasks. Furthermore, they enable novel, more flexible feature designs. Numerical examples on synthetic data and an Alzheimer’s classification application on triangle meshes of the right hippocampus demonstrate the usefulness of our new layers: While they apply to a much broader class of problems, they outperform task-specific state-of-the-art networks.

Facial analysis is a key component in a wide range of applications such as healthcare, autonomous driving, and entertainment. Despite the availability of various facial RGB datasets, the thermal modality, which plays a crucial role in life sciences, medicine, and biometrics, has been largely overlooked. To address this gap, we introduce the T-FAKE dataset, a new large-scale synthetic thermal dataset with sparse and dense landmarks. To facilitate the creation of the dataset, we propose a novel RGB2Thermal loss function, which enables the domain-adaptive transfer of RGB faces to thermal style. By utilizing the Wasserstein distance between thermal and RGB patches and the statistical analysis of clinical temperature distributions on faces, we ensure that the generated thermal images closely resemble real samples. Using RGB2Thermal style transfer based on our RGB2Thermal loss function, we create the large-scale synthetic thermal T-FAKE dataset†with landmark and segmentation annotations. Leveraging our novel T-FAKE dataset, probabilistic landmark prediction, and label adaptation networks, we demonstrate significant improvements in landmark detection methods on thermal images across different landmark conventions. Our models show excellent performance with both sparse 70-point landmarks and dense 478-point landmark annotations. Moreover, our RGB2Thermal loss leads to notable results in terms of perceptual evaluation and temperature prediction.

We deal with the task of sampling from an unnormalized Boltzmann density $\rho_D$ by learning a Boltzmann curve given by energies $f_t$ starting in a simple density $\rho_Z$. First, we examine conditions under which Fisher-Rao flows are absolutely continuous in the Wasserstein geometry. Second, we address specific interpolations $f_t$ and the learning of the related density/velocity pairs $(\rho_t,v_t)$. It was numerically observed that the linear interpolation, which requires only a parametrization of the velocity field $v_t$, suffers from a "teleportation-of-mass" issue. Using tools from the Wasserstein geometry, we give an analytical example, where we can precisely measure the explosion of the velocity field. Inspired by Máté and Fleuret, who parametrize both $f_t$ and $v_t$, we propose an interpolation which parametrizes only $f_t$ and fixes an appropriate $v_t$. This corresponds to the Wasserstein gradient flow of the Kullback-Leibler divergence related to Langevin dynamics. We demonstrate by numerical examples that our model provides a well-behaved flow field which successfully solves the above sampling task.

In this paper, we introduce Plug-and-Play (PnP) Flow Matching, an algorithm for solving imaging inverse problems. PnP methods leverage the strength of pre-trained denoisers, often deep neural networks, by integrating them in optimization schemes. While they achieve state-of-the-art performance on various inverse problems in imaging, PnP approaches face inherent limitations on more generative tasks like inpainting. On the other hand, generative models such as Flow Matching pushed the boundary in image sampling yet lack a clear method for efficient use in image restoration. We propose to combine the PnP framework with Flow Matching (FM) by defining a time-dependent denoiser using a pre-trained FM model. Our algorithm alternates between gradient descent steps on the data-fidelity term, reprojections onto the learned FM path, and denoising. Notably, our method is computationally efficient and memory-friendly, as it avoids backpropagation through ODEs and trace computations. We evaluate its performance on denoising, super-resolution, deblurring, and inpainting tasks, demonstrating superior results compared to existing PnP algorithms and Flow Matching based state-of-the-art methods. Code available at https://github.com/annegnx/PnP-Flow.

We propose a new approach for unsupervised alignment of heterogeneous datasets, which maps data from two different domains without any known correspondences to a common metric space. Our method is based on an unbalanced optimal transport problem with Gromov-Wasserstein marginal penalization. It can be seen as a counterpart to the recently introduced joint multidimensional scaling method. We prove that there exists a minimizer of our functional and that for penalization parameters going to infinity, the corresponding sequence of minimizers converges to a minimizer of the so-called embedded Wasserstein distance. Our model can be reformulated as a quadratic, multi-marginal, unbalanced optimal transport problem, for which a bi-convex relaxation admits a numerical solver via block-coordinate descent. We provide numerical examples for joint embeddings in Euclidean as well as non-Euclidean spaces.

In inverse problems, many conditional generative models approximate the posterior measure by minimizing a distance between the joint measure and its learned approximation. While this approach also controls the distance between the posterior measures in the case of the Kullback–Leibler divergence, the same in general does not hold true for the Wasserstein distance. In this paper, we introduce a conditional Wasserstein distance via a set of restricted couplings that equals the expected Wasserstein distance of the posteriors. Interestingly, the dual formulation of the conditional Wasserstein-1 distance resembles losses in the conditional Wasserstein GAN literature in a quite natural way. We derive theoretical properties of the conditional Wasserstein distance, characterize the corresponding geodesics and velocity fields as well as the flow ODEs. Subsequently, we propose to approximate the velocity fields by relaxing the conditional Wasserstein distance. Based on this, we propose an extension of OT Flow Matching for solving Bayesian inverse problems and demonstrate its numerical advantages on an inverse problem and class-conditional image generation.

We propose conditional flows of the maximum mean discrepancy (MMD) with the negative distance kernel for posterior sampling and conditional generative modelling. This MMD, which is also known as energy distance, has several advantageous properties like efficient computation via slicing and sorting. We approximate the joint distribution of the ground truth and the observations using discrete Wasserstein gradient flows and establish an error bound for the posterior distributions. Further, we prove that our particle flow is indeed a Wasserstein gradient flow of an appropriate functional. The power of our method is demonstrated by numerical examples including conditional image generation and inverse problems like superresolution, inpainting and computed tomography in low-dose and limited-angle settings.

Wasserstein gradient flows of maximum mean discrepancy (MMD) functionals with non-smooth Riesz kernels show a rich structure as singular measures can become absolutely continuous ones and conversely. In this paper we contribute to the understanding of such flows. We propose to approximate the backward scheme of Jordan, Kinderlehrer and Otto for computing such Wasserstein gradient flows as well as a forward scheme for so-called Wasserstein steepest descent flows by neural networks (NNs). Since we cannot restrict ourselves to absolutely continuous measures, we have to deal with transport plans and velocity plans instead of usual transport maps and velocity fields. Indeed, we approximate the disintegration of both plans by generative NNs which are learned with respect to appropriate loss functions. In order to evaluate the quality of both neural schemes, we benchmark them on the interaction energy. Here we provide analytic formulas for Wasserstein schemes starting at a Dirac measure and show their convergence as the time step size tends to zero. Finally, we illustrate our neural MMD flows by numerical examples.

Abstract. Let [Formula: see text] and [Formula: see text], [Formula: see text], be real numbers. We show by an example that the assignment problem[Formula: see text] is in general neither solved by the identical permutation ([Formula: see text]) nor the anti-identical permutation ([Formula: see text]) if [Formula: see text]. Indeed the above maximum can be, depending on the number of points, arbitrarily far away from [Formula: see text] and [Formula: see text]. The motivation to deal with such assignment problems came from their relation to Gromov–Wasserstein distances, which have recently received a lot of attention in imaging and shape analysis.

Recently, variational methods were successfully applied for computing the optical flow in gray and RGB-valued image sequences. A crucial assumption in these models is that pixel-values do not change under transformations. Nowadays, modern image acquisition techniques, such as electron backscatter diffraction (EBSD) used in materials science, can capture images with values in nonlinear spaces. Here, the image values belong to the quotient space ${SO}(3)/ \mathcal S$ of the special orthogonal group modulo the discrete symmetry group of the crystal. For such data, the assumption that pixel-values remain unchanged under transformations appears to be no longer valid. Hence, we propose a variational model for determining the optical flow in ${SO}(3)/\mathcal S$-valued image sequences, taking into account the dependence of pixel-values on the transformation. More precisely, the data is transformed according to the rotation part in the polar decomposition of the Jacobian of the transformation. To model nonsmooth transformations without obtaining so-called staircasing effects, we propose using total generalized variation, such as prior. Then, we prove existence of a minimizer for our model and explain how it can be discretized and minimized by a primal-dual algorithm. Numerical examples illustrate the performance of our method.

Gromov-Wasserstein distances are generalization of Wasserstein distances, which are invariant under distance preserving transformations. Although a simplified version of optimal transport in Wasserstein spaces, called linear optimal transport (LOT), was successfully used in practice, there does not exist a notion of linear Gromov-Wasserstein distances so far. In this paper, we propose a definition of linear Gromov-Wasserstein distances. We motivate our approach by a generalized LOT model, which is based on barycentric projection maps of transport plans. Numerical examples illustrate that the linear Gromov-Wasserstein distances, similarly as LOT, can replace the expensive computation of pairwise Gromov-Wasserstein distances in applications like shape classification.

Entropy maximization is the only principled approach to combine several (partial) selectivity estimates to an estimate for a full conjunction.However, this approach has no appearance in database management systems.We conjecture that the main reason is a lack of implementations with good performance.Indeed, the originally proposed iterative scaling algorithm has a slow convergence rate and high complexity in each iteration.As an alternative, we propose to use a method based on Newton's algorithm to solve the entropy maximization problem.Further, we show how this general approach can be implemented very efficiently for both CPUs and GPUs.Our experiments show that our CPU and GPU implementation is more than 4 orders of magnitude faster than the state-of-the-art method for the most complex problem it could handle.For even more complex problems our new GPU implementation outperforms our CPU implementation by more than 43x.In a few milliseconds it is now possible to compute all partial selectivities for complex conjunctive predicates with 20 or more predicates.We strongly believe that the proposed implementation is ready for production-grade database management systems.

The contribution of this study is twofold. First, we propose an efficient algorithm for the computation of the (weighted) maximum likelihood estimators for the parameters of the multivariate Student-$t$ distribution, which we call the generalized multivariate myriad filter. Second, we use the generalized multivariate myriad filter in a nonlocal framework for the denoising of images corrupted by different kinds of noise. The resulting method is very flexible and can handle heavy-tailed noise such as Cauchy noise, as well as the other extreme, namely Gaussian noise. Furthermore, we detail how the limiting case $\nu\to 0$ of the projected normal distribution in two dimensions can be used for the robust denoising of periodic data, in particular for images with circular data corrupted by wrapped Cauchy noise.

This paper addresses the morphing of manifold-valued images based on the time discrete geodesic paths model of Berkels, Effland, and Rumpf [ SIAM J. Imaging Sci., 8 (2015), pp. 1457--1488]. Although for our manifold-valued setting such an interpretation of the energy functional is not available so far, the model is interesting on its own. We prove the existence of a minimizing sequence within the set of $L^2(\Omega,\mathcal{H})$ images having values in a finite-dimensional Hadamard manifold $\mathcal{H}$ together with a minimizing sequence of admissible diffeomorphisms. To this end, we show that the continuous manifold-valued functions are dense in $L^2(\Omega,\mathcal{H})$. We propose a space discrete model based on a finite difference approach on staggered grids, where we focus on the linearized elastic potential in the regularizing term. The numerical minimization alternates between (i) the computation of a deformation sequence between given images via the parallel solution of certain registration problems for manifold-valued images, and (ii) the computation of an image sequence with fixed first (template) and last (reference) frame based on a given sequence of deformations via the solution of a system of equations arising from the corresponding Euler--Lagrange equation. Numerical examples give a proof of the concept of our ideas.

Nonlocal patch-based methods, in particular the Bayesian approach of Lebrun, Buades, and Morel [SIAM J. Imaging Sci., 6 (2013), pp. 1665--1688], are considered to be state-of-the-art methods for denoising (color) images corrupted by white Gaussian noise of moderate variance. This paper is the first attempt to generalize this technique to manifold-valued images. Such images, for example, images with phase or directional entries or with values in the manifold of symmetric positive definite matrices, are frequently encountered in real-world applications. Generalizing the normal law to manifolds is not canonical, and different attempts have been considered. Here, we focus on a straightforward intrinsic model and discuss the relation to other approaches for specific manifolds. We reinterpret the Bayesian approach of Lebrun, Buades, and Morel [SIAM J. Imaging Sci., 6 (2013), pp. 1665--1688] in terms of minimum mean squared error estimation, which motivates our definition of a corresponding estimator on the manifold. With this estimator at hand we present a nonlocal patch-based method for the restoration of manifold-valued images. Various proof-of-concept examples demonstrate the potential of the proposed algorithm.

This paper proposes a novel model for contrast enhancement of RGB images. The average local contrast measure is increased within a variational framework which preserves the hue of the original image by coupling the channels. The user is enabled to intuitively control the level of the contrast as well as the scale of the enhanced details. Moreover, our model avoids large modifications of the original image histogram and thereby preserves the global illumination of the scene. The minimizer of the proposed functional is computed by a hybrid primal-dual algorithm. Numerical experiments show the reliability of the proposed approach in comparison with state-of-the-art methods.

We are interested in restoring images having values in a symmetric Hadamard manifold by minimizing a functional with a quadratic data term and a total variation--like regularizing term. To solve the convex minimization problem, we extend the Douglas--Rachford algorithm and its parallel version to symmetric Hadamard manifolds. The core of the Douglas--Rachford algorithm is reflections of the functions involved in the functional to be minimized. In the Euclidean setting the reflections of convex lower semicontinuous functions are nonexpansive. As a consequence, convergence results for Krasnoselski--Mann iterations imply the convergence of the Douglas--Rachford algorithm. Unfortunately, these general results do not carry over to Hadamard manifolds, where proper convex lower semicontinuous functions can have expansive reflections. However, splitting our restoration functional in an appropriate way, we have only to deal with special functions---namely, several distance-like functions and an indicator function of a special convex set. We prove that the reflections of certain distance-like functions on Hadamard manifolds are nonexpansive, which is an interesting result on its own. Furthermore, the reflection of the involved indicator function is nonexpansive on Hadamard manifolds with constant curvature so that the Douglas--Rachford algorithm converges here. Several numerical examples demonstrate the advantageous performance of the suggested algorithm compared to other existing methods such as the cyclic proximal point algorithm and half-quadratic minimization. Numerical convergence is also observed in our experiments on the Hadamard manifold of symmetric positive definite matrices with the affine invariant metric, which does not have a constant curvature.

In many image and signal processing applications, such as interferometric synthetic aperture radar (SAR), electroencephalogram (EEG) data analysis, ground-based astronomy, and color image restoration, in HSV or LCh spaces the data has its range on the one-dimensional sphere $\mathbb S^1$. Although the minimization of total variation (TV) regularized functionals is among the most popular methods for edge-preserving image restoration , such methods were only very recently applied to cyclic structures. However, as for Euclidean data, TV regularized variational methods suffer from the so-called staircasing effect. This effect can be avoided by involving higher order derivatives into the functional. This is the first paper which uses higher order differences of cyclic data in regularization terms of energy functionals for image restoration. We introduce absolute higher order differences for $\mathbb S^1$-valued data in a sound way which is independent of the chosen representation system on the circle. Our absolute cyclic first order difference is just the geodesic distance between points. Similar to the geodesic distances, the absolute cyclic second order differences have only values in $[0,\pi]$. We update the cyclic variational TV approach by our new cyclic second order differences. To minimize the corresponding functional we apply a cyclic proximal point method which was recently successfully proposed for Hadamard manifolds. Choosing appropriate cycles this algorithm can be implemented in an efficient way. The main steps require the evaluation of proximal mappings of our cyclic differences for which we provide analytical expressions. Under certain conditions we prove the convergence of our algorithm. Various numerical examples with artificial as well as real-world data demonstrate the advantageous performance of our algorithm.

Color image enhancement is a complex and challenging task in digital imaging with abundant applications. Preserving the hue of the input image is crucial in a wide range of situations. We propose simple image enhancement algorithms which conserve the hue and preserve the range (gamut) of the R, G, B channels in an optimal way. In our setup, the intensity input image is transformed into a target intensity image whose histogram matches a specified, well-behaved histogram. We derive a new color assignment methodology where the resulting enhanced image fits the target intensity image. We analyse the obtained algorithms in terms of chromaticity improvement and compare them with the unique and quite popular histogram based hue and range preserving algorithm of Naik and Murthy. Numerical tests confirm our theoretical results and show that our algorithms perform much better than the Naik-Murthy algorithm. In spite of their simplicity, they compete with well-established alternative methods for images where hue-preservation is desired.

This paper provides a fast algorithm to order in a meaningful, strict way the integer gray values in digital (quantized) images. It can be used in any exact histogram specification-based application. Our algorithm relies on the ordering procedure based on the specialized variational approach. This variational method was shown to be superior to all other state-of-the art ordering algorithms in terms of faithful total strict ordering but not in speed. Indeed, the relevant functionals are in general difficult to minimize because their gradient is nearly flat over vast regions. In this paper, we propose a simple and fast fixed point algorithm to minimize these functionals. The fast convergence of our algorithm results from known analytical properties of the model. Our algorithm is equivalent to an iterative nonlinear filtering. Furthermore, we show that a particular form of the variational model gives rise to much faster convergence than other alternative forms. We demonstrate that only a few iterations of this filter yield almost the same pixel ordering as the minimizer. Thus, we apply only few iteration steps to obtain images, whose pixels can be ordered in a strict and faithful way. Numerical experiments confirm that our algorithm outperforms by far its main competitors.

Motivated by a recent halftoning method which is based on electrostatic principles, we analyze a halftoning framework where one minimizes a functional consisting of the difference of two convex functions. One describes attracting forces caused by the image's gray values; the other one enforces repulsion between points. In one dimension, the minimizers of our functional can be computed analytically and have the following desired properties: The points are pairwise distinct, lie within the image frame, and can be placed at grid points. In the two-dimensional setting, we prove some useful properties of our functional, such as its coercivity, and propose computing a minimizer by a forward-backward splitting algorithm. We suggest computing the special sums occurring in each iteration step of our dithering algorithm by a fast summation technique based on the fast Fourier transform at nonequispaced knots, which requires only $\mathcal{O}(m\log m)$ arithmetic operations for m points. Finally, we present numerical results showing the excellent performance of our dithering method.

Query optimizers rely on accurate estimations of the sizes of intermediate results. Wrong size estimations can lead to overly expensive execution plans. We first define the q-error to measure deviations of size estimates from actual sizes. The q-error enables the derivation of two important results: (1) We provide bounds such that if the q-error is smaller than this bound, the query optimizer constructs an optimal plan. (2) If the q-error is bounded by a number q , we show that the cost of the produced plan is at most a factor of q 4 worse than the optimal plan. Motivated by these findings, we next show how to find the best approximation under the q-error. These techniques can then be used to build synopsis for size estimates. Finally, we give some experimental results where we apply the developed techniques.

Image restoration and simplification methods that respect important features such as edges play a fundamental role in digital image processing. However, known edge-preserving methods like common nonlinear diffusion methods tend to round vertices for large diffusion times. In this paper, we adapt the diffusion tensor for anisotropic diffusion to avoid this effects in images containing rotated and sheared rectangles, respectively. In this context, we propose a new method for estimating rotation angles and shear parameters based on the so-called structure tensor. Further, we show how the knowledge of appropriate diffusion tensors can be used in variational models. Numerical examples including orientation estimation, denoising and segmentation demonstrate the good performance of our methods.

We present novel wavelet-based inpainting algorithms. Applying ideas from anisotropic regularization and diffusion, our models can better handle degraded pixels at edges. We interpret our algorithms within the framework of forward-backward splitting methods in convex analysis and prove that the conditions for ensuring their convergence are fulfilled. Numerical examples illustrate the good performance of our algorithms.