# An efficient algorithm for the ℓp norm based metric nearness problem

arXiv: https://arxiv.org/abs/2211.01245 · HTML: https://mlsanity.com/paper/2211.01245/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 46 references that are in the map.
- First posted on arXiv 2 Nov 2022.

## Builds on (most cited first, 4 of 4)

- [An asymptotically superlinearly convergent semismooth Newton augmented Lagrangian method for Linear Programming](https://mlsanity.com/paper/1903.09546/) (2019)
- [A Parallel Projection Method for Metric Constrained Optimization](https://mlsanity.com/paper/1901.10084/) (2019)
- [Project and Forget: Solving Large-Scale Metric Constrained Problems](https://mlsanity.com/paper/2005.03853/) (2020)
- [An augmented Lagrangian method with constraint generation for shape-constrained convex regression problems](https://mlsanity.com/paper/2012.04862/) (2020)

## Built on by (most cited first, 1 of 1)

- [Euclidean Distance Deflation Under High-Dimensional Heteroskedastic Noise](https://mlsanity.com/paper/2507.18520/) (2025)

## Abstract (arXiv)

Given a dissimilarity matrix, the metric nearness problem is to find the nearest matrix of distances that satisfy the triangle inequalities. This problem has wide applications, such as sensor networks, image processing, and so on. But it is of great challenge even to obtain a moderately accurate solution due to the O(n3) metric constraints and the nonsmooth objective function which is usually a weighted ℓp norm based distance. In this paper, we propose a delayed constraint generation method with each subproblem solved by the semismooth Newton based proximal augmented Lagrangian method (PALM) for the metric nearness problem. Due to the high memory requirement for the storage of the matrix related to the metric constraints, we take advantage of the special structure of the matrix and do not need to store the corresponding constraint matrix. A pleasing aspect of our algorithm is that we can solve these problems involving up to 108 variables and 1013 constraints. Numerical experiments demonstrate the efficiency of our algorithm. In theory, firstly, under a mild condition, we establish a primal-dual error bound condition which is very essential for the analysis of local convergence rate of PALM. Secondly, we prove the equivalence between the dual nondegeneracy condition and nonsingularity of the generalized Jacobian for the inner subproblem of PALM. Thirdly, when q(·)=|·|1 or |·|∞, without the strict complementarity condition, we also prove the equivalence between the the dual nondegeneracy condition and the uniqueness of the primal solution.