Jonas Bresch

Robert Beinert, Jonas Bresch, Michael Quellmalz

The Radon transform is a fundamental tool for analyzing data in tomographic imaging, optimal transport, crystallography, and geometric analysis. Numerical computations require an accurate discretization. To deal with voxelized images and objects, we derive a closed-form, piecewise polynomial expression for the Radon transform of an axis-aligned cube in arbitrary dimension $d$. Building on this formula, we propose a discrete Radon transform in $\mathbb{R}^d$ that is both analytically exact for voxelized data and computationally efficient. For improved numerical stability, we introduce a regularized variant replacing the Radon transform of a cube, i.e.\ the $(d-1)$-dimensional area of the intersection between that cube and a hyperplane, by the $d$-dimensional volume of the intersection between the cube and a thin slab around the hyperplane. Numerical experiments demonstrate the effectiveness of the proposed approach in several applications including 3D shape matching, classification, and sliced Wasserstein barycenters. The computational efficiency in higher dimensions is verified by a comparison with Monte Carlo integration.

Matthias Beckmann, Robert Beinert, Jonas Bresch

The Radon cumulative distribution transform (R-CDT) exploits one-dimensional Wasserstein transport and the Radon transform to represent prominent features in images. It is closely related to the sliced Wasserstein distance and facilitates classification tasks, especially in the small data regime, like the recognition of watermarks in filigranology. Here, a typical issue is that the given data may be subject to affine transformations caused by the measuring process. To make the R-CDT invariant under arbitrary affine transformations, a two-step normalization of the R-CDT has been proposed in our earlier works. The aim of this paper is twofold. First, we propose a family of generalized normalizations to enhance flexibility for applications. Second, we study multi-dimensional and non-Euclidean settings by making use of generalized Radon transforms. We prove that our novel feature representations are invariant under certain transformations and allow for linear separation in feature space. Our theoretical results are supported by numerical experiments based on 2d images, 3d shapes and 3d rotation matrices, showing near perfect classification accuracies and clustering results.

Jonas Bresch

Optimization of quadratic functions and the quotient of those are relevant in subspace and iterative optimization methods. In this paper, the calculation of the generalized operator norm and extremal generalized Rayleigh quotient is considered. In contrast to recent works an unconstrained sampling approach on the entire sphere for the random search direction in each iteration is proposed. Furthermore, the link to zeroth-order methods for Riemannian first- and second-order optimization methods is provided in the sense that the Riemannian gradient and Hessian are estimated by the specific surrogates. Even though the tangent space is not used in this construction the optimal step size problem can be computed in a closed form. The subproblems of this and recent works are illuminated in the context of sub-generalized Rayleigh quotient problems on specific Gram matrices. Together the achieved theory allows to construct an accelerated algorithm which shows state-of-the-art behavior and outperforms recent works.

Matthias Beckmann, Robert Beinert, Jonas Bresch

The Radon cumulative distribution transform (R-CDT), is an easy-to-compute feature extractor that facilitates image classification tasks especially in the small data regime. It is closely related to the sliced Wasserstein distance and provably guaranties the linear separability of image classes that emerge from translations or scalings. In many real-world applications, like the recognition of watermarks in filigranology, however, the data is subject to general affine transformations originating from the measurement process. To overcome this issue, we recently introduced the so-called max-normalized R-CDT that only requires elementary operations and guaranties the separability under arbitrary affine transformations. The aim of this paper is to continue our study of the max-normalized R-CDT especially with respect to its robustness against non-affine image deformations. Our sensitivity analysis shows that its separability properties are stable provided the Wasserstein-infinity distance between the samples can be controlled. Since the Wasserstein-infinity distance only allows small local image deformations, we moreover introduce a mean-normalized version of the R-CDT. In this case, robustness relates to the Wasserstein-2 distance and also covers image deformations caused by impulsive noise for instance. Our theoretical results are supported by numerical experiments showing the effectiveness of our novel feature extractors as well as their robustness against local non-affine deformations and impulsive noise.

Janis Auffenberg, Jonas Bresch, Oleh Melnyk et al.

Data classification without access to labeled samples remains a challenging problem. It usually depends on an appropriately chosen distance between features, a topic addressed in metric learning. Recently, Huizing, Cantini and Peyré proposed to simultaneously learn optimal transport (OT) cost matrices between samples and features of the dataset. This leads to the task of finding positive eigenvectors of a certain nonlinear function that maps cost matrices to OT distances. Having this basic idea in mind, we consider both the algorithmic and the modeling part of unsupervised metric learning. First, we examine appropriate algorithms and their convergence. In particular, we propose to use the stochastic random function iteration algorithm and prove that it converges linearly for our setting, although our operators are not paracontractive as it was required for convergence so far. Second, we ask the natural question if the OT distance can be replaced by other distances. We show how Mahalanobis-like distances fit into our considerations. Further, we examine an approach via graph Laplacians. In contrast to the previous settings, we have just to deal with linear functions in the wanted matrices here, so that simple algorithms from linear algebra can be applied.

Robert Beinert, Jonas Bresch

The handling of manifold-valued data, for instance, plays a central role in color restoration tasks relying on circle- or sphere-valued color models, in the study of rotational or directional information related to the special orthogonal group, and in Gaussian image processing, where the pixel statistics are interpreted as values on the hyperbolic sheet. Especially, to denoise these kind of data, there have been proposed several generalizations of total variation (TV) and Tikhonov-type denoising models incorporating the underlying manifolds. Recently, a novel, numerically efficient denoising approach has been introduced, where the data are embedded in an Euclidean ambient space, the non-convex manifolds are encoded by a series of positive semi-definite, fixed-rank matrices, and the rank constraint is relaxed to obtain a convexification that can be solved using standard algorithms from convex analysis. The aim of the present paper is to extent this approach to new kinds of data like multi-binary and Stiefel-valued data. Multi-binary data can, for instance, be used to model multi-color QR codes whereas Stiefel-valued data occur in image and video-based recognition. For both new data types, we propose TV- and Tikhonov-based denoising modelstogether with easy-to-solve convexification. All derived methods are evaluated on proof-of-concept, synthetic experiments.