Solving the metric nearness problem: methods and results
Júlia Guizardi · 2025
The Metric Nearness Problem consists of finding the closest distance matrix, using the ℓ p norm, to a given dissimilarity matrix such that metric properties, particularly the triangle inequalities, are satisfied.This problem can be applied in various contexts, including image processing, data clustering, and sensor location (when additional constraints are imposed), where noisy or incomplete distance data must be corrected.This work provides both theoretical and practical studies of the problem.The minimization formulation is presented under the ℓ 1 , ℓ 2 and ℓ ∞ norms.Two numerical optimization methods are studied and applied: the Augmented Lagrangian method via Algencan, and the Dykstra projection method, which was specifically programmed for this problem.Both are applied to the three norms.Optimizations were implemented to handle the large number of constraints by dealing with patterns in the algorithm.Extensive experiments were conducted on synthetic and real-world datasets to evaluate computational performance and numerical accuracy.The ℓ 2 norm problem was especially suitable for Algencan given its nonlinear structure, while Dykstra's method showed superior performance in large-scale settings due to the specific implementation that generates low memory requirements.In linear cases, such as the ℓ 1 , ℓ ∞ norms, a comparison with the Simplex method was also performed.Results reveal that the Dykstra method, when properly applied, can solve problems up to 10 11 constraints.