For a given metric measure space (X, d,μ) we consider finite samples of points, calculate the matrix of distances between them and then reconstruct the points in some finite-dimensional space using the multidimensional scaling (MDS) algorithm with this distance matrix as an input. We show that this procedure gives a natural limit as the number of points in the samples grows to infinity and the density of points approaches the measure μ. This limit can be viewed as “infinite MDS” embedding of the original space, now not anymore into a finite-dimensional space but rather into an infinitedimensional Hilbert space. We further show that this embedding is stable with respect to the natural convergence of metric measure spaces. However, contrary to what is usually believed in applications, we show that in many cases it does not preserve distances, nor is even bi-Lipschitz, but may provide snowflake (Assouad-type) embeddings of the original space to a Hilbert space (this is, for instance, the case of a sphere and a flat torus equipped with their geodesic distances).

The Hough transform, interpreted as the discretization of the Radon transform, is a widely used tool in image processing and machine vision. The primary way to speed it up is to employ the Brady–Yong algorithm. However, the accuracy of the straight line discretization utilized in this algorithm is limited. In this study, we propose a novel algorithm called $ASD2$ that offers fast computation of the Hough transform for images of arbitrary sizes. Our approach adopts a computation scheme similar to the Brady–Yong algorithm but incorporates the best possible line discretization for improved accuracy. By employing the Method of Four Russians, we demonstrate that for an image of size $n\times n$ where $n=8^q$ and $q\in \mathbb{N}$, the computational complexity of the $ASD2$ algorithm is $O\left(n^{8/3}\right)$ when summing over $O\left(n^2\right)$ digital straight line segments.

The Hough transform (HT) is widely used in computer vision, tomography, and neural networks. Numerous algorithms for HT computation have been proposed, making their systematic comparison essential. However, existing comparative methodologies are either non-universal and limited to certain HT formulations or task-oriented, relying on application-specific criteria that do not fully capture algorithmic properties. This paper introduces a novel unified methodology for the systematic comparison of HT algorithms. It evaluates key characteristics, including computational complexity, accuracy, and auxiliary space complexity, while explicitly accounting for the property of self-adjointness. The methodology integrates both implementation-level and theoretical considerations related to the interpretation of HT as a discrete approximation of the Radon transform. A set of mathematically justified evaluation functions, not previously described in the literature, is proposed to support our methodology. Importantly, the methodology is universal, applicable across diverse HT paradigms, encompasses pattern-based and Fourier-based fast HT (FHT) algorithms, and offers a comprehensive alternative to existing task-specific methodologies. Its application to several state-of-the-art FHT algorithms ($FHT2DT$, $FHT2SP$, $ASD2$, $KHM$, and Fast Slant Stack) yields new experimentally confirmed theoretical insights, identifies $ASD2$ as the most balanced algorithm, and provides practical guidelines for algorithm selection. In particular, the methodology reveals that for image sizes up to 3000, the maximum normalized computational complexity increases as follows: $FHT2DT$ (1.1), $ASD2$ (15.3), and $KHM$ (30.6), while the remaining algorithms exhibit at least 1.1 times higher values. The maximum orthotropic approximation error equals 0.5 for $ASD2$, $KHM$, and Fast Slant Stack; lies between 0.5 and 1.5 for $FHT2SP$; and reaches 2.1 for $FHT2DT$. In terms of worst-case normalized auxiliary space complexity, the lowest values are achieved by $FHT2DT$ (2.0), Fast Slant Stack (4.0, lower bound), and $ASD2$ (6.8), with all other algorithms requiring at least 8.2 times more memory.

For a given metric measure space $(X,d,\mu)$ we consider finite samples of points, calculate the matrix of distances between them and then reconstruct the points in some finite-dimensional space using the multidimensional scaling (MDS) algorithm with this distance matrix as an input. We show that this procedure gives a natural limit as the number of points in the samples grows to infinity and the density of points approaches the measure $\mu$. This limit can be viewed as "infinite MDS" embedding of the original space, now not anymore into a finite-dimensional space but rather into an infinitedimensional Hilbert space. We further show that this embedding is stable with respect to the natural convergence of metric measure spaces. However, contrary to what is usually believed in applications, we show that in many cases it does not preserve distances, nor is even bi-Lipschitz, but may provide snowflake (Assouad-type) embeddings of the original space to a Hilbert space (this is, for instance, the case of a sphere and a flat torus equipped with their geodesic distances).

A travers et autour des barycentres de Wasserstein: Le problème du transport optimal, initialement introduit par G. Monge en 1781 et redécouvert par L. Kantorovich en 1942, consiste à transformer une distribution de masse en une autre avec le minimum de travail. Dans cette thèse, on considère quelques problèmes variationnels impliquant un transport optimal. On est principalement motivé par le problème du barycentre de Wasserstein introduit par M. Agueh et G. Carlier en 2011. On traite les problèmes suivants : • les barycentres par rapport à un coût général de transport, leur existence et leur stabilité; • concentration et théorème central limite pour les barycentres empiriques de Wasserstein des mesures gaussiennes; • caractérisation, propriétés et théorème central limite pour les barycentres de Wasserstein pénalisés par l’entropie; • le problème de transport optimal, pénalisé en l’énergie de Dirichlet d’un plan de transport. Une autre partie de la thèse est consacrée à l’analyse de la complexité de l’algorithme des projections itératives de Bregman. Il s’agit d’une généralisation de l’algorithme bien connu de Sinkhorn, qui nous permet de trouver une solution approximative du problème de transport optimal ainsi que du problème du barycentre de Wasserstein.