Search

Interactions and relations between objects may be pairwise or higher-order in nature, and so network-valued data are ubiquitous in the real world. The "space of networks", however, has a complex structure that cannot be adequately described using conventional statistical tools. We introduce a measure-theoretic formalism for modeling generalized network structures such as graphs, hypergraphs, or graphs whose nodes come with a partition into categorical classes. We then propose a metric that extends the Gromov-Wasserstein distance between graphs and the co-optimal transport distance between hypergraphs. We characterize the geometry of this space, thereby providing a unified theoretical treatment of generalized networks that encompasses the cases of pairwise, as well as higher-order, relations. In particular, we show that our metric is an Alexandrov space of non-negative curvature, and leverage this structure to define gradients for certain functionals commonly arising in geometric data analysis tasks. We extend our analysis to the setting where vertices have additional label information, and derive efficient computational schemes to use in practice. Equipped with these theoretical and computational tools, we demonstrate the utility of our framework in a suite of applications, including hypergraph alignment, clustering and dictionary learning from ensemble data, multi-omics alignment, as well as multiscale network alignment., Comment: 64 pages, 10 figures

Variational regularization is a classical technique to solve statistical inference tasks and inverse problems, with modern data-driven approaches parameterizing regularizers via deep neural networks showcasing impressive empirical performance. Recent works along these lines learn task-dependent regularizers. This is done by integrating information about the measurements and ground-truth data in an unsupervised, critic-based loss function, where the regularizer attributes low values to likely data and high values to unlikely data. However, there is little theory about the structure of regularizers learned via this process and how it relates to the two data distributions. To make progress on this challenge, we initiate a study of optimizing critic-based loss functions to learn regularizers over a particular family of regularizers: gauges (or Minkowski functionals) of star-shaped bodies. This family contains regularizers that are commonly employed in practice and shares properties with regularizers parameterized by deep neural networks. We specifically investigate critic-based losses derived from variational representations of statistical distances between probability measures. By leveraging tools from star geometry and dual Brunn-Minkowski theory, we illustrate how these losses can be interpreted as dual mixed volumes that depend on the data distribution. This allows us to derive exact expressions for the optimal regularizer in certain cases. Finally, we identify which neural network architectures give rise to such star body gauges and when do such regularizers have favorable properties for optimization. More broadly, this work highlights how the tools of star geometry can aid in understanding the geometry of unsupervised regularizer learning.

Variational analysis presents a unified theory encompassing in particular both smoothness and convexity. In a Euclidean space, convex sets and smooth manifolds both have straightforward local geometry. However, in the most basic hybrid case of feasible regions consisting of pre-images of convex sets under maps that are once (but not necessarily twice) continuously differentiable, the geometry is less transparent. We define a new approximate convexity property, that holds both for such feasible regions and also for all prox-regular sets. This new property requires that nearby points can always be joined by smooth feasible paths that are almost straight. In particular, in the terminology of real algebraic geometry, such feasible regions are locally normally embedded in the Euclidean space.

Input variables in numerical models are often subject to several levels of uncertainty, usually modeled by probability distributions. In the context of uncertainty quantification applied to these models, studying the robustness of output quantities with respect to the input distributions requires: (a) defining variational classes for these distributions; (b) calculating boundary values for the output quantities of interest with respect to these variational classes. The latter should be defined in a way that is consistent with the information structure defined by the ``baseline'' choice of input distributions. Considering parametric families, the variational classes are defined using the geodesic distance in their Riemannian manifold, a generic approach to such problems. Theoretical results and application tools are provided to justify and facilitate the implementation of such robustness studies, in concrete situations where these distributions are truncated -- a setting frequently encountered in applications. The feasibility of our approach is illustrated in a simplified industrial case study.

Based on Welzl's algorithm for smallest circles and spheres we develop a simple linear time algorithm for finding the smallest circle enclosing a point cloud on a sphere. The algorithm yields correct results as long as the point cloud is contained in a hemisphere, but the hemisphere does not have to be known in advance and the algorithm automatically detects whether the hemisphere assumption is met. For the full-sphere case, that is, if the point cloud is not contained in a hemisphere, we provide hints on how to adapt existing linearithmic time algorithms for spherical Voronoi diagrams to find the smallest enclosing circle.

We introduce the notion of Karamata regular operators, which is a notion of regularity that is suitable for obtaining concrete convergence rates for common fixed point problems. This provides a broad framework that includes, but goes beyond, H\"olderian error bounds and H\"older regular operators. By concrete, we mean that the rates we obtain are explicitly expressed in terms of a function of the iteration number $k$ instead, of say, a function of the iterate $x^k$. While it is well-known that under H\"olderian-like assumptions many algorithms converge linearly/sublinearly (depending on the exponent), little it is known when the underlying problem data does not satisfy H\"olderian assumptions, which may happen if a problem involves exponentials and logarithms. Our main innovation is the usage of the theory of regularly varying functions which we showcase by obtaining concrete convergence rates for quasi-cylic algorithms in non-H\"olderian settings. This includes certain rates that are neither sublinear nor linear but sit somewhere in-between, including a case where the rate is expressed via the Lambert W function. Finally, we connect our discussion to o-minimal geometry and show that definable operators in any o-minimal structure are always Karamata regular., Comment: 44 pages, comments welcome

This article considers the problem of 3-dimensional genome reconstruction for single-cell data, and the uniqueness of such reconstructions in the setting of haploid organisms. We consider multiple graph models as representations of this problem, and use techniques from graph rigidity theory to determine identifiability. Biologically, our models come from Hi-C data, microscopy data, and combinations thereof. Mathematically, we use unit ball and sphere packing models, as well as models consisting of distance and inequality constraints. In each setting, we describe and/or derive new results on realisability and uniqueness. We then propose a 3D reconstruction method based on semidefinite programming and apply it to synthetic and real data sets using our models.

Two left-invariant Lorentzian problems on the Heisenberg group are considered. The Pontryagin maximum principle was applied to both problems and a parameterization of abnormal and normal extremal trajectories was obtained. Reachability sets and the existence of optimal trajectories are investigated., Comment: In Russian

We provide a geometric approach to the lasso. We study the tangency of the level sets of the least square objective function with the polyhedral boundary sets $B(t)$ of the parameters in $\mathbb R^p$ with the $\ell_1$ norm equal to $t$. Here $t$ decreases from the value $\hat t$, which corresponds to the actual, nonconstrained minimizer of the least square objective function, denoted by $\hat\beta$. We derive closed exact formulae for the solution of the lasso under the full rank assumption. Our method does not assume iterative numerical procedures and it is, thus, computationally more efficient than the existing algorithms for solving the lasso. We also establish several important general properties of the solutions of the lasso. We prove that each lasso solution form a simple polygonal chain in $\mathbb{R}^p$ with $\hat\beta$ and the origin as the endpoints. There are no two segments of the polygonal chain that are parallel. We prove that such a polygonal chain can intersect interiors of more than one orthant in $\mathbb{R}^p$, but it cannot intersect interiors of more than $p$ orthants, which is, in general, the best possible estimate for non-normalized data. We prove that if a polygonal chain passes from the interior of one to the interior of another orthant, then it never again returns to the interior of the former. The intersection of a chain and the interior of an orthant coincides with a segment minus its end points, which belongs to a ray having $\hat\beta$ as its initial point. We illustrate the results using real data examples as well as especially crafted examples with hypothetical data. Already in $p=2$ case we show a striking difference in the maximal number of quadrants a polygonal chain of a lasso solution can intersect in the case of normalized data, which is $1$ vs. nonnormalized data, which is $2$., Comment: 38 pages, 10 figures, 5 tables

In this paper, we study a two-dimensional Lorentzian problem on the anti-de Sitter plane. Using methods of geometric control theory and differential geometry, it was possible to construct an orthonormal frame, calculate extremal trajectories, describe the reachable set, construct an optimal synthesis, and describe the Lorentzian distance., Comment: In Russian

Two flat sub-Lorentzian problems on the Martinet distribution are studied. For the first one, the attainable set has a nontrivial intersection with the Martinet plane, but for the second one it does not. Attainable sets, optimal trajectories, sub-Lorentzian distances and spheres are described.

Motivated by the Sard conjecture in sub-Riemannian geometry, and more specifically on Carnot groups, we consider the set of maps defined on a Hilbert space $H$: \[\mathscr{P}_{d}^m(H)=\bigg\{f:H\to \mathbb{R}^m\,\bigg|\, \forall\, E\subset H, \,\dim(E)<\infty \implies f|_{E} \textrm{ is a polynomial map of degree $d$}\bigg\}. \] Example of maps belonging to this class are: the map $f:\ell^2\to \mathbb{R}$ constructed by Kukpa as a counterexample for the Sard theorem in infinite dimension; the Endpoint maps of Carnot groups. We prove that, for infinite-dimensional subspaces $V \subset H$ satisfying quantitative assumptions on their Kolmogorov $n$-width, the restriction of $f$ on $V$ has the Sard property, i.e. the set of critical values of $f|_{V}$ has measure zero in $\mathbb{R}^m$. We prove various quantitative versions of this result, allowing to study the Sard property also for the case $V=H$. By constructing suitable examples, we prove the sharpness of our $n$-width assumptions. We apply these results to sub-Riemannian geometry, proving that on Carnot groups the Sard property holds true for the restriction of the Endpoint map on the set of real-analytic controls with large enough radius of convergence. This is a more functional-analytic approach to the Sard conjecture that, unlike previous ones, does not resort to reduction to finite-dimensions., Comment: 39 pages

We define a new two-parameter family of metrics on a subspace of Borel probability measures on a metric fiber bundle, called the disintegrated Monge--Kantorovich metrics. We then prove the disintegrated Monge--Kantorovich metrics are complete, separable (except an endpoint case), geodesic spaces, with a dual representation. Additionally, we prove existence and duality for an associated barycenter problem, and provide conditions for uniqueness of a barycenter. These results on barycenter problems for the disintegrated Monge--Kantorovich metrics also yield the corresponding existence, duality, and uniqueness results for classical Monge--Kantorovich barycenters in a wide variety of spaces, including a uniqueness result on any connected, complete Riemannian manifold, with or without boundary, with no restriction on the geometry of any kind., Comment: 66 pages. Comments welcome! arXiv admin note: substantial text overlap with arXiv:2311.15874

In this paper, combining the Rashevsky-Chow-Sussmann (orbit) theorem with the Ambrose-Singer theorem, we introduce the notion of controllable principal connections on principal $G$-bundles. Using this concept, under a mild assumption of compactness, we estimate the Gromov-Hausdorff distance between principal $G$-bundles and certain reductive homogeneous $G$-spaces. In addition, we prove that every reduction of the structure group $G$ to a closed connected subgroup gives rise to a sequence of Riemannian metrics on the total space for which the underlying sequence of metric spaces converges, in the Gromov-Housdorff topology, to a normal reductive homogeneous $G$-space. This last finding allows one to detect the presence of certain reductive homogeneous $G$-spaces in the Gromov-Housdorff closure of the moduli space of Riemannian metrics of the total space of the bundle through topological invariants provided by obstruction theory., Comment: 13 pages, Comments are welcome

The moving sofa problem asks for the connected shape with the largest area $\mu_{\text{max}}$ that can move around the right-angled corner of a hallway $L$ with unit width. The best bounds currently known on $\mu_{\max}$ are summarized as $2.2195\ldots \leq \mu_{\max} \leq 2.37$. The lower bound $2.2195\ldots \leq \mu_{\max}$ comes from Gerver's sofa $S_G$ of area $\mu_G := 2.2195\ldots$. The upper bound $\mu_{\max} \leq 2.37$ was proved by Kallus and Romik using extensive computer assistance. It is conjectured that the equality $\mu_{\max} = \mu_G$ holds at the lower bound. We develop a new approach to the moving sofa problem by approximating it as an infinite-dimensional convex quadratic optimization problem. The problem is then explicitly solved using a calculus of variation based on the Brunn-Minkowski theory. Consequently, we prove that any moving sofa satisfying a property named the injectivity condition has an area of at most $1 + \pi^2/8 = 2.2337\dots$. The new conditional bound does not rely on any computer assistance, yet it is much closer to the lower bound $2.2195\ldots$ of Gerver than the computer-assisted upper bound $2.37$ of Kallus and Romik. Gerver's sofa $S_G$, the conjectured optimum, satisfies the injectivity condition in particular., Comment: 53 pages, 9 figures

We propose a gradient descent method for solving optimisation problems arising in settings of tropical geometry - a variant of algebraic geometry that has become increasingly studied in applications such as computational biology, economics, and computer science. Our approach takes advantage of the polyhedral and combinatorial structures arising in tropical geometry to propose a versatile approach for approximating local minima in tropical statistical optimisation problems - a rapidly growing body of work in recent years. Theoretical results establish global solvability for 1-sample problems and a convergence rate of $O(1/\sqrt{k})$. Numerical experiments demonstrate the method's superior performance over classical descent for tropical optimisation problems which exhibit tropical convexity but not classical convexity. Notably, tropical descent seamlessly integrates into advanced optimisation methods, such as Adam, offering improved overall performance., Comment: 26 pages

The P\'al inequality is a classical result which asserts that among all planar convex sets of given width the equilateral triangle is the one of minimal area. In this paper we prove three quantitative versions of this inequality, by quantifying how the closeness of the area of a convex set, of certain width, to the minimal value implies its closeness to the equilateral triangle. As a by-product, we also present a novel result concerning a quantitative inequality for the inradius of a set, under minimal width constraint.

Dimension reduction techniques typically seek an embedding of a high-dimensional point cloud into a low-dimensional Euclidean space which optimally preserves the geometry of the input data. Based on expert knowledge, one may instead wish to embed the data into some other manifold or metric space in order to better reflect the geometry or topology of the point cloud. We propose a general method for manifold-valued multidimensional scaling based on concepts from optimal transport. In particular, we establish theoretical connections between the recently introduced semi-relaxed Gromov-Wasserstein (srGW) framework and multidimensional scaling by solving the Monge problem in this setting. We also derive novel connections between srGW distance and Gromov-Hausdorff distance. We apply our computational framework to analyze ensembles of political redistricting plans for states with two Congressional districts, achieving an effective visualization of the ensemble as a distribution on a circle which can be used to characterize typical neutral plans, and to flag outliers.

In this note, we investigate the possibility of defining meaningful upper and lower quantization dimensions for a compactly supported Borel probability measure of order $r$, also for negative values of $r$. To this end, we utilize the concept of partition functions, which generalizes the idea of the $L^{q}$-spectrum and, in this way, naturally extends the work in [M. Kesseb\"ohmer, A. Niemann, and S. Zhu. Quantization dimensions of probability measures via R\'enyi dimensions. $\textit{Trans. Amer. Math. Soc.}$ 376.7 (2023), 4661$\unicode{x2013}$4678]. In particular, we provide natural fractal geometric bounds as well as easily verifiable necessary conditions for the existence of the quantization dimensions. Exact asymptotics for the absolutely continuous case are also given., Comment: 12 pages, 1 figure

We propose a new metric between probability measures on a compact metric space that mirrors the Riemannian manifold-like structure of quadratic optimal transport but includes entropic regularization. Its metric tensor is given by the Hessian of the Sinkhorn divergence, a debiased variant of entropic optimal transport. We precisely identify the tangent space it induces, which turns out to be related to a Reproducing Kernel Hilbert Space (RKHS). As usual in Riemannian geometry, the distance is built by looking for shortest paths. We prove that our distance is geodesic, metrizes the weak-star topology, and is equivalent to a RKHS norm. Still it retains the geometric flavor of optimal transport: as a paradigmatic example, translations are geodesics for the quadratic cost on $\mathbb{R}^d$. We also show two negative results on the Sinkhorn divergence that may be of independent interest: that it is not jointly convex, and that its square root is not a distance because it fails to satisfy the triangle inequality., Comment: 52 pages, 6 figures

This book uses optimal control theory to prove that the most unpackable centrally symmetric convex disk in the plane is a smoothed polygon. A smoothed polygon is a polygon whose corners have been rounded in a special way by arcs of hyperbolas. To be highly unpackable means that even densest packing of that disk has low density. Motivated by Minkowski's geometry of numbers, researchers began to search for the most unpackable centrally symmetric convex disk (in brief, the most unpackable disk) starting in the early 1920s. In 1934, Reinhardt conjectured that the most unpackable disk is a smoothed octagon. Working independently of Reinhardt, Mahler attempted without success in 1947 to prove that the most unpackable disk must be a smoothed polygon. This book proves what Mahler set out to prove: Mahler's First conjecture on smoothed polygons. His second conjecture is identical to the Reinhardt conjecture, which remains open. This book explores the many remarkable structures of this packing problem, formulated as a problem in optimal control theory on a Lie group, with connections to hyperbolic geometry and Hamiltonian mechanics. Bang-bang Pontryagin extremals to the optimal control problem are smoothed polygons. Extreme difficulties arise in the proof because of chattering behavior in the optimal control problem, corresponding to possible smoothed polygons with infinitely many sides that need to be ruled out. To analyze and eliminate the possibility of chattering solutions, the book introduces a discrete dynamical system (the Poincare first recurrence map) and gives a full description of its fixed points, stable and unstable manifolds, and basin of attraction on a blowup centered at a singular set. Some proofs in this book are computer-assisted using a computer algebra system., Comment: 283 page book

We prove that the $D_4$ root system (the set of vertices of the regular $24$-cell) is the unique optimal kissing configuration in $\mathbb R^4$, and is an optimal spherical code. For this, we use semidefinite programming to compute an exact optimal solution to the second level of the Lasserre hierarchy. We also improve the upper bound for the kissing number problem in $\mathbb R^6$ to $77$.

The starting point of this paper is the computation of minimal hyperbolic polynomials of duals of cones arising from chordal sparsity patterns. From that, we investigate the relation between ranks of homogeneous cones and their minimal polynomials. Along the way, we answer in the negative a question posed in an earlier paper and show examples of homogeneous cones that cannot be realized as rank-one generated (ROG) hyperbolicity cones., Comment: 20 pages, 1 figure. The proof of Theorem 4.6 was simplified, some extra comments on related works by Nakashima were added and some typos were fixed

In the classical best approximation pair (BAP) problem, one is given two nonempty, closed, convex and disjoint subsets in a finite- or an infinite-dimensional Hilbert space, and the goal is to find a pair of points, each from each subset, which realizes the distance between the subsets. This problem, which has a long history, has found applications in science and technology. We discuss the problem in more general normed spaces and with possibly non-convex subsets, and focus our attention on the issues of uniqueness and existence of the solution to the problem. To the best of our knowledge these fundamental issues have not received much attention. In particular, we present several sufficient geometric conditions for the (at most) uniqueness of a BAP relative to these subsets. These conditions are related to the structure of the boundaries of the subsets, their relative orientation, and the structure of the unit sphere of the space. In addition, we present many sufficient conditions for the existence of a BAP, possibly without convexity . Our results allow us to significantly extend the horizon of the recent alternating simultaneous Halpern-Lions-Wittmann-Bauschke (A-S-HLWB) algorithm [Censor, Mansour and Reem, The alternating simultaneous Halpern-Lions-Wittmann-Bauschke algorithm for finding the best approximation pair for two disjoint intersections of convex sets, arXiv:2304.09600 (2023)] for solving the BAP problem.

We show that the spectral embeddings of all known triangle-free strongly regular graphs are optimal spherical codes (the new cases are $56$ points in $20$ dimensions, $50$ points in $21$ dimensions, and $77$ points in $21$ dimensions), as are certain mutually unbiased basis arrangements constructed using Kerdock codes in up to $1024$ dimensions (namely, $2^{4k} + 2^{2k+1}$ points in $2^{2k}$ dimensions for $2 \le k \le 5$). As a consequence of the latter, we obtain optimality of the Kerdock binary codes of block length $64$, $256$, and $1024$, as well as uniqueness for block length $64$. We also prove universal optimality for $288$ points on a sphere in $16$ dimensions. To prove these results, we use three-point semidefinite programming bounds, for which only a few sharp cases were known previously. To obtain rigorous results, we develop improved techniques for rounding approximate solutions of semidefinite programs to produce exact optimal solutions., Comment: 32 pages, 1 figure

We consider 2-step free-Carnot groups equipped with sub-Finsler distances. We prove that the metric spheres are codimension-one rectifiable from the Euclidean viewpoint. The result is obtained by studying how the Lipschitz constant for the distance function behaves near abnormal geodesics., Comment: 18 pages

The primary objective of this paper is to establish the Ahlfors regularity of minimizers of set functions that satisfy a suitable maxitive condition on disjoint unions of sets. Our analysis focuses on minimizers within continua of the plane with finite one-dimensional Hausdorff measure. Through quantitative estimates, we prove that the length of a minimizer inside the ball centered at one of its points is comparable to the radius of the ball. By operating within an abstract framework, we are able to encompass a diverse range of entities, including spectral functionals defined in terms of the eigenvalues of elliptic operators, the inradius, and the maximum of the torsion function. These entities are of interest for several applications, such as structural engineering, urban planning, and quantum mechanics.

We prove the convergence of a modified Jordan--Kinderlehrer--Otto scheme to a solution to the Fokker--Planck equation in $\Omega \Subset \mathbb{R}^d$ with general, positive and temporally constant, Dirichlet boundary conditions. We work under mild assumptions on the domain, the drift, and the initial datum. In the special case where $\Omega$ is an interval in $\mathbb{R}^1$, we prove that such a solution is a gradient flow -- curve of maximal slope -- within a suitable space of measures, endowed with a modified Wasserstein distance. Our discrete scheme and modified distance draw inspiration from contributions by A. Figalli and N. Gigli [J. Math. Pures Appl. 94, (2010), pp. 107--130], and J. Morales [J. Math. Pures Appl. 112, (2018), pp. 41--88] on an optimal-transport approach to evolution equations with Dirichlet boundary conditions. Similarly to these works, we allow the mass to flow from/to the boundary $\partial \Omega$ throughout the evolution. However, our leading idea is to also keep track of the mass at the boundary by working with measures defined on the whole closure $\overline \Omega$. The driving functional is a modification of the classical relative entropy that also makes use of the information at the boundary. As an intermediate result, when $\Omega$ is an interval in $\mathbb{R}^1$, we find a formula for the descending slope of this geodesically nonconvex functional., Comment: v2: more detailed abstract and minor changes

The quantization problem looks for best approximations of a probability measure on a given metric space by finitely many points, where the approximation error is measured with respect to the Wasserstein distance. On particular smooth domains, such as $\mathbb{R}^d$ or complete Riemannian manifolds, the quantization error is known to decay polynomially as the number of points is taken to infinity, provided the measure satisfies an integral condition which controls the amount of mass outside compact sets. On Riemannian manifolds, the existing integral condition involves a quantity measuring the growth of the exponential map, for which the only available estimates are in terms of lower bounds on sectional curvature. In this paper, we provide a more general integral condition for the asymptotics of the quantization error on Riemannian manifolds, given in terms of the growth of the covering numbers of spheres, which is purely metric in nature and concerns only the large-scale growth of the manifold. We further estimate the covering growth of manifolds in two particular cases, namely lower bounds on the Ricci curvature and geometric group actions by a discrete group of isometries. These estimates can themselves generalize beyond manifolds, and hint at a future treatment of asymptotic quantization also on non-smooth metric measure spaces., Comment: 34 pages, 8 figures

The convex shape contained in a disk having prescribed area and maximal perimeter is completely characterized in terms of the area fraction. The solution is always a polygon having all but one sides equal. The lengths of the sides are characterized through explicit equations. The case of more general containing shapes is also discussed from both theoretical and numerical perspectives.

In this paper, we prove the existence theorem for longest paths in sub-Lorentzian problems, which generalizes the classical theorem for globally hyperbolic Lorentzian manifolds. We specifically address the case of invariant structures on homogeneous spaces, as the conditions for the existence theorem in this case can be significantly simplified. In particular, it turns out that longest paths exist for any left-invariant sub-Lorentzian structures on Carnot groups., Comment: 11 pages

In this paper we present a new semidefinite programming hierarchy for covering problems in compact metric spaces. Over the last years, these kind of hierarchies were developed primarily for geometric packing and for energy minimization problems; they frequently provide the best known bounds. Starting from a semidefinite programming hierarchy for the dominating set problem in graph theory, we derive the new hierarchy for covering and show some of its basic properties: The hierarchy converges in finitely many steps, but the first level collapses to the volume bound when the compact metric space is homogeneous., Comment: 14 pages

We introduce a one-parameter family of metrics on the space of Borel probability measures on Euclidean space with finite $p$th moment for $1\leq p <\infty$, called the $\textit{sliced Monge--Kantorovich metrics}$, which include the sliced Wasserstein and max-sliced Wasserstein metrics. We then show that these are complete, separable metric spaces that are topologically equivalent to the classical Monge--Kantorovich metrics and these metrics have a dual representation. However, we also prove these sliced metrics are $\textit{not}$ bi-Lipschitz equivalent to the classical ones in most cases, and also the spaces are (except for an endpoint case) $\textit{not}$ geodesic. The completeness, duality, and non-geodesicness are new even in the sliced and max-sliced Wasserstein cases, and non bi-Lipschitz equivalence is only known for a few specific cases. In particular this indicates that sliced and max-sliced Wasserstein metrics are not suitable direct replacements for the classical Monge--Kantorovich metrics in problems where the specific metric or geodesic structure are critical., Comment: 26 pages, added results on non bi-Lipschitz equivalence when q is infinity, split off results on disintegrated metrics (to be posted separately), changed title. Comments welcome!

We present an extension of known semidefinite and linear programming upper bounds for spherical codes. We apply the main result for the distance distribution of a spherical code and show that this method can work effectively In particular, we get a shorter solution to the kissing number problem in dimension 4., Comment: 14 pages, 1 figure. arXiv admin note: substantial text overlap with arXiv:1903.05767

During the COVID-19 pandemic, medical imaging techniques like computed tomography (CT) scans have demonstrated effectiveness in combating the rapid spread of the virus. Therefore, it is crucial to conduct research on computerized models for the detection of COVID-19 using CT imaging. A novel processing method has been developed, utilizing radiomic features, to assist in the CT-based diagnosis of COVID-19. Given the lower specificity of traditional features in distinguishing between different causes of pulmonary diseases, the objective of this study is to develop a CT-based radiomics framework for the differentiation of COVID-19 from other lung diseases. The model is designed to focus on outlining COVID-19 lesions, as traditional features often lack specificity in this aspect. The model categorizes images into three classes: COVID-19, non-COVID-19, or normal. It employs enhancement auto-segmentation principles using intensity dark channel prior (IDCP) and deep neural networks (ALS-IDCP-DNN) within a defined range of analysis thresholds. A publicly available dataset comprising COVID-19, normal, and non-COVID-19 classes was utilized to validate the proposed model's effectiveness. The best performing classification model, Residual Neural Network with 50 layers (Resnet-50), attained an average accuracy, precision, recall, and F1-score of 98.8%, 99%, 98%, and 98% respectively. These results demonstrate the capability of our model to accurately classify COVID-19 images, which could aid radiologists in diagnosing suspected COVID-19 patients. Furthermore, our model's performance surpasses that of more than 10 current state-of-the-art studies conducted on the same dataset., Comment: 8 pages, 2 figures, The 1st International Conference on Electronic and Computer Engineering, Universiti Teknologi Malaysia, "accept"

Mohar recently adapted the classical game of Cops and Robber from graphs to metric spaces, thereby unifying previously studied pursuit-evasion games. He conjectured that finitely many cops can win on any compact geodesic metric space, and that their number can be upper-bounded in terms of the ranks of the homology groups when the space is a simplicial pseudo-manifold. We disprove these conjectures by constructing a metric on $\mathbb{S}^3$ with infinite cop number. More problems are raised than settled.

This short note gives a proof of the triangle inequality based on the Kantorovich duality formula for the Wasserstein distances of exponent $p\in[1,+\infty)$ in the case of a general Polish space. In particular it avoids the "glueing of couplings" procedure used in most textbooks on optimal transport., Comment: 10 pages, no figure

The sliced Wasserstein distance as well as its variants have been widely considered in comparing probability measures defined on $\mathbb R^d$. Here we derive the notion of sliced Wasserstein distance for measures on an infinite dimensional separable Hilbert spaces, depict the relation between sliced Wasserstein distance and narrow convergence of measures and quantize the approximation via empirical measures., Comment: 11 pages, 0 figures

We investigate location problems whose optimum lies in the tropical convex hull of the input points. Firstly, we study geodesically star-convex sets under the asymmetric tropical distance and introduce the class of tropically quasiconvex functions whose sub-level sets have this shape. The latter are related to monotonic functions. Then we show that location problems whose distances are measured by tropically quasiconvex functions as before give an optimum in the tropical convex hull of the input points. We also show that a similar result holds if we replace the input points by tropically convex sets. Finally, we focus on applications to phylogenetics presenting properties of consensus methods arising from our class of location problems., Comment: 19 pages, 3 figures

We prove the following fundamental property for the Fermat-Torricelli point for four non-collinear and non-coplanar points forming a tetrahedron in $\mathbb{R}^{3},$ which states that: The three bisecting lines having as a common vertex the Fermat-Torricelli point formed by each pair of equal angles, which are seen by the opposite edges of the tetrahedron meet perpendicularly at the Fermat-Torricelli point. Furthermore, we give an alternative proof, which is different from the one obtained by Bajaj and Mehlhos for the unsolvability of the Fermat-Torricelli problem for tetrahedra in $\mathbb{R}^{3}$ using only algebraic computations for some angles, which have as a common vertex the Fermat-Torricelli point of the tetrahedron., Comment: 7 pages

We compute the robustness of Fermat--Weber points with respect to any finite gauge. We show a breakdown point of $1/(1+\sigma)$ where $\sigma$ is the asymmetry measure of the gauge. We obtain quantitative results indicating how far a corrupted Fermat--Weber point can lie from the true value in terms of the original sample and the size of the corrupted part. If the distance from the true value depends only on the original sample, then we call the gauge 'uniformly robust'. We show that polyhedral gauges are uniformly robust, but locally strictly convex norms are not., Comment: 19 pages, 4 figures

In this paper we consider a two-parameter family {dGWp,q}p,q of Gromov- Wasserstein distances between metric measure spaces. By exploiting a suitable interaction between specific values of the parameters p and q and the metric of the underlying spaces, we determine the exact value of the distance dGW4,2 between all pairs of unit spheres of different dimension endowed with their Euclidean distance and their uniform measure., Comment: 1. Added a Section 4, Section 5, and Appendix C; 2. Swapped Sections 2 and 3; 3. "Relagated Proofs" section (Section 4 in the old version) is now in appendix

We show that the $k$-point bound of de Laat, Machado, Oliveira, and Vallentin, a hierarchy of upper bounds for the independence number of a topological packing graph derived from the Lasserre hierarchy, converges to the independence number., Comment: 10 pages

We investigate the following question: how close can two disjoint lattice polytopes contained in a fixed hypercube be? This question stems from various contexts where the minimal distance between such polytopes appears in complexity bounds of optimization algorithms. We provide nearly matching lower and upper bounds on this distance and discuss its exact computation. We also give similar bounds in the case of disjoint rational polytopes whose binary encoding length is prescribed., Comment: 28 pages, 3 figures

We study the structure of the set of all possible affine hyperplane sections of a convex polytope. We present two different cell decompositions of this set, induced by hyperplane arrangements. Using our decomposition, we bound the number of possible combinatorial types of sections and craft algorithms that compute optimal sections of the polytope according to various combinatorial and metric criteria, including sections that maximize the number of $k$-dimensional faces, maximize the volume, and maximize the integral of a polynomial. Our optimization algorithms run in polynomial time in fixed dimension, but the same problems show hardness otherwise. Our tools can be extended to intersection with halfspaces and projections onto hyperplanes. Finally, we present several experiments illustrating our theorems and algorithms on famous polytopes., Comment: Comments are very welcome!

In order to compare and interpolate signals, we investigate a Riemannian geometry on the space of signals. The metric allows discontinuous signals and measures both horizontal (thus providing many benefits of the Wasserstein metric) and vertical deformations. Moreover, it allows for signed signals, which overcomes the main deficiency of optimal transportation-based metrics in signal processing. We characterize the metric properties of the space of signals and establish the regularity and stability of geodesics. Furthermore, we introduce an efficient numerical scheme to compute the geodesics and present several experiments which highlight the nature of the metric., Comment: 34 pages, 8 figures

Witsenhausen's problem asks for the maximum fraction $\alpha_n$ of the $n$-dimensional unit sphere that can be covered by a measurable set containing no pairs of orthogonal points. The best upper bounds for $\alpha_n$ are given by extensions of the Lov\'asz theta number. In this paper, optimization hierarchies based on the Lov\'asz theta number, like the Lasserre hierarchy, are extended to Witsenhausen's problem and similar problems. These hierarchies are shown to converge and are used to compute the best upper bounds for $\alpha_n$ in low dimensions., Comment: 34 pages

In the setting of subFinsler Carnot groups, we consider curves that satisfy the normal equation coming from the Pontryagin Maximum Principle. We show that, unless it is constant, each such a curve leaves every compact set, quantitatively. Namely, the distance between the points at time 0 and time $t$ grows at least of the order of $t^{1/s}$, where $s$ denotes the step of the Carnot group. In particular, in subFinsler Carnot groups there are no periodic normal geodesics.

We construct an example of an infinite planar embedded self-similar binary tree $\Sigma$ which is the essentially unique solution to the Steiner problem of finding the shortest connection of a given planar self-similar fractal set $C$ of positive Hausdorff dimension. The set $C$ can be considered the set of leaves, or the ``boundary``, of the tree $\Sigma$, so that $\Sigma$ is an irreducible solution to the Steiner problem with datum $C$ (i.e. $\Sigma\setminus C$ is connected).

In this paper we give a first study of perfect copositive $n \times n$ matrices. They can be used to find rational certificates for completely positive matrices. We describe similarities and differences to classical perfect, positive definite matrices. Most of the differences occur only for $n \geq 3$, where we find for instance lower rank and indefinite perfect matrices. Nevertheless, we find for all $n$ that for every classical perfect matrix there is an arithmetically equivalent one which is also perfect copositive. Furthermore we study the neighborhood graph and polyhedral structure of perfect copositive matrices. As an application we obtain a new characterization of the cone of completely positive matrices: It is equal to the set of nonnegative matrices having a nonnegative inner product with all perfect copositive matrices., Comment: 20 pages, 1 figure