# Sensor network localization has a benign landscape after low-dimensional relaxation

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jul 2025.

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

- [Escaping Local Minima Provably in Non-convex Matrix Sensing: A Deterministic Framework via Simulated Lifting](https://mlsanity.com/paper/2602.05887/) (2026)
- [Sparse Variable Projection in Robotic Perception: Exploiting Separable Structure for Efficient Nonlinear Optimization](https://mlsanity.com/paper/2512.07969/) (2025)
- [Provable Non-Convex Euclidean Distance Matrix Completion: Geometry, Reconstruction, and Robustness](https://mlsanity.com/paper/2508.00091/) (2025)

## Abstract (arXiv)

We consider the sensor network localization problem, which is closely related to multidimensional scaling and Euclidean distance matrix completion. Given a ground truth configuration of n points in ℝℓ, we observe a subset of the pairwise distances and aim to recover the underlying configuration (up to rigid transformations). We show with a simple counterexample that the associated optimization problem is nonconvex and may admit spurious local minimizers, even when all distances are known. Yet, inspired by numerical experiments, we argue that all second-order critical points become global minimizers when the problem is relaxed by optimizing over configurations in dimension k > ℓ. Specifically, we show this for two settings, both when all pairwise distances are known: (1) for arbitrary ground truth points, and k= O(√ℓ n), and: (2) for isotropic random ground truth points, and k = O(ℓ + log n). To prove these results, we identify and exploit key properties of the linear map which sends inner products to squared distances.