Clustering is one of the most fundamental tools in data science and machine learning, and k-means clustering is one of the most common of such methods. There is a variety of approximate algorithms for the k-means problem, but only a few methods compute the globally optimal solution, as it is in general NP-hard. In this paper, we consider the k-means problem for instances with low-dimensional data and formulate it as a structured concave assignment problem. This allows us to exploit the low-dimensional structure and solve the problem to global optimality for very large data sets with several clusters, complementing and outperforming state-of-the-art for this class of problems. The method builds on iteratively solving a small concave problem and a large linear programming or assignment problem. This gives a sequence of feasible solutions along with bounds, which we show converges to a zero optimality gap. The paper combines methods from global optimization to accelerate the procedure, and we provide numerical results on synthetic data and real-world data.

We introduce an efficient computational framework for solving a class of multimarginal martingale optimal transport problems, which includes many robust pricing problems of large financial interest. Such problems are typically computationally challenging due to the martingale constraint; however, by extending the state space we can identify them with problems that exhibit a certain sequential martingale structure. Our method exploits such structures in combination with entropic regularization, enabling fast computation of optimal solutions and allowing us to solve problems with a large number of marginals. We demonstrate the method by using it for computing robust price bounds for different options, such as lookback options and Asian options.

Motivation Modelling gene expression is a central problem in systems biology. Single-cell technologies have revolutionized the field by enabling sequencing at the resolution of individual cells. This results in a much richer data compared to what is obtained by bulk technologies, offering new possibilities and challenges for gene regulatory network inference. Results In this work, we introduce GRIT (gene regulation inference by transport) - a method to fit a differential equation model and to infer gene regulatory networks from single-cell data using the theory of optimal transport. The idea consists in tracking the evolution of the cell distribution over time and finding the system whose temporal marginals minimize the transport cost with the observations. GRIT is finally used to identify genes and pathways affected by two Parkinson's disease associated mutations. Availability and implementation Matlab implementation of the method and code for data generation are at gitlab.com/uniluxembourg/lcsb/systems-control/grit together with a user guide. A snapshot of the code used for the results of this article is at doi: 10.5281/zenodo.15582432.

Multi-target tracking is a fundamental task in radar-based perception, where the objective is to accurately estimate the trajectories of multiple moving targets. A principled method for evaluating trajectory estimation performance is the trajectory generalized optimal subpattern (TGOSPA) metric, but it can be expensive to compute. In this paper, we propose a new efficient method for approximating the TGOSPA metric based on graph-structured multi-marginal optimal transport. This is achieved by first showing that the linear programming relaxation of TGOSPA is closely connected to a structured multi-marginal optimal transport problem. Inspired by the recently popular Sinkhorn iterations, entropy regularization is used, which allows the optimal solution to be efficiently approximated via dual coordinate ascent. By leveraging the graph structure of the problem, the computational complexity for each iteration is linear in the number of targets in the ground truth, the number of targets in the estimate, and the number of time steps, respectively. Finally, the efficacy of our proposed method is demonstrated in a simulation study.

This correspondence presents a probabilistic generalization of the generalized optimal subpattern assignment (GOSPA) metric, termed P-GOSPA. The GOSPA metric has been widely used to evaluate the distance between finite sets, particularly in multiobject estimation applications. The P-GOSPA extends GOSPA into the space of multiBernoulli densities, incorporating inherent uncertainty in probabilistic multiobject representations. In addition, P-GOSPA retains the interpretability of GOSPA, such as its decomposition into localization, missed detection, and false detection errors in a sound and meaningful manner. Examples and simulations are provided to demonstrate the efficacy of the proposed P-GOSPA metric.

In this paper we consider the problem of optimally steering an ensemble of battery-powered agents over a network. This is an important problem in applications such as traffic flow control for electric vehicles, where both capacity constraints from the roads and the locations of charging stations need to be taken into account. We extend previous work where origin-destination problems have been formulated using optimal transport. By introducing a state representing the charge level, we can formulate the steering problem as a structured multi-marginal optimal transport problem. The computational method is based on a dual coordinate ascent algorithm applied to the entropy regularized problem, in which we can exploit the decomposable structure of the cost tensor for efficient computations. In this formulation the capacity constraints are represented in terms of certain linear operators, and we derive explicit expressions for the corresponding updates of blocks of the dual variables. Finally, the method is illustrated with a numerical example where vehicles having different charges are required to travel over a grid from origin to destination while minimizing the total energy consumed.

To mitigate the dynamic range problems that low-bit quantization of conventional analog-to-digital converters (ADCs) suffer from, we shift our attention to the novel modulo ADCs (Mod-ADCs). We consider the Cramer-Rao bound (CRB) analysis for signal parameter estimation from Mod-ADC generated data. Four CRB formulas are derived assuming known or unknown folding-counts, for both quantized and unquantized cases. We analyze many of their characteristics, such as monotonicity, boundedness and convergence; and perform detailed comparisons of the CRBs among the conventional ADCs and the two different types of Mod-ADCs. Numerical examples are presented to demonstrate these characteristics, and that the low-bit Mod-ADCs can provide satisfactory signal parameter estimation performances even in high dynamic range situations.

In this work we develop a numerical method for solving a type of convex graph- structured tensor optimization problem. This type of problem, which can be seen as a generalization of multimarginal optimal transport problems with graph-structured costs, appears in many applications. Examples are unbalanced optimal transport and multispecies potential mean field games, where the latter is a class of nonlinear density control problems. The method we develop is based on coordinate ascent in a Lagrangian dual, and under mild assumptions we prove that the algorithm converges globally. Moreover, under a set of stricter assumptions, the algorithm converges R-linearly. To perform the coordinate ascent steps one has to compute projections of the tensor, and doing so by brute force is in general not computationally feasible. Nevertheless, for certain graph structures it is possible to derive efficient methods for computing these projections, and here we specifically consider the graph structure that occurs in multispecies potential mean field games. We also illustrate the methodology on a numerical example from this problem class.

In this work, we develop a new framework for dynamic network flow problems based on optimal transport theory. We show that the dynamic multicommodity minimum-cost network flow problem can be formulated as a multimarginal optimal transport problem, where the cost function and the constraints on the marginals are associated with a graph structure. By exploiting these structures and building on recent advances in optimal transport theory, we develop an efficient method for such entropy-regularized optimal transport problems. In particular, the graph structure is utilized to efficiently compute the projections needed in the corresponding Sinkhorn iterations, and we arrive at a scheme that is both highly computationally efficient and easy to implement. To illustrate the performance of our algorithm, we compare it with a state-of-the-art linear programming (LP) solver. We achieve good approximations to the solution at least one order of magnitude faster than the LP solver. Finally, we showcase the methodology on a traffic routing problem with a large number of commodities.

To overcome the dynamic range problems that conventional coarse quantized analog-to-digital converters (ADCs) suffer from, we consider the modulo ADCs with known folding-count (Mod-ADC-K). Two Cramér-Rao bounds (CRBs) are derived for signal parameter estimation from data generated by Mod-ADC-K, for both quantized and unquantized cases. Then we analyze their characteristics, and compare them to the conventional ADCs. Numerical examples are presented to verify the characteristics of Mod-ADC-K, and show that the low-bit Mod-ADC-K can mitigate the dynamic range problems.