Sensor network localization has a benign landscape after low-dimensional relaxation
研究了传感器网络定位问题，发现即使已知所有距离，优化问题也可能有虚假局部极小点；但将配置维度提高到一定值后，所有二阶临界点都成为全局极小点。
Abstract 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 $${\mathbb {R}}^\ell $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>ℓ</mml:mi> </mml:msup> </mml:math> , 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> \ell $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>></mml:mo> <mml:mi>ℓ</mml:mi> </mml:mrow> </mml:math> . Specifically, we show this for two settings, both when all pairwise distances are known: (1) for arbitrary ground truth points, and $$k= O(\sqrt{\ell n})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>=</mml:mo> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msqrt> <mml:mrow> <mml:mi>ℓ</mml:mi> <mml:mi>n</mml:mi> </mml:mrow> </mml:msqrt> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , and: (2) for isotropic random ground truth points, and $$k= O(\ell + \log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>=</mml:mo> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>ℓ</mml:mi> <mml:mo>+</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . To prove these results, we identify and exploit key properties of the linear map which sends inner products to squared distances.