Doubling the dimension yields a benign landscape for the squared-stress

Abstract

We consider the Euclidean distance geometry problem (EDG): given a subset of the pairwise distances of an unknown cloud of $n$ points in $\mathbb{R}^\ell$, recover the point cloud up to rigid motions. When $n$ is large, a popular practical approach is to minimize a nonconvex quartic, known as the squared-stress or s-stress, over point clouds in $\mathbb{R}^k$, with $k$ potentially larger than $\ell$. It is a long-standing open problem to understand the optimization landscape of the s-stress when all pairwise distances are known (Malone and Trosset, 2000; Parhizkar, 2013). It was recently shown that the landscape is not benign when $k=\ell$, and it was conjectured that the landscape becomes benign as soon as $k\ge \ell+1$ (Song et al., 2025; Criscitiello et al., 2026). Here, we show that the complete-graph s-stress has a benign landscape whenever $k\ge 2(\ell+1)$, establishing the conjecture up to a factor of two. A key idea is to view second-order criticality as a containment of two ellipsoids; finding a descent direction then corresponds to finding a separating hyperplane that violates this containment. This dual perspective yields the stated landscape result, and also applies to any measurement operator whose inverse satisfies a simple frame condition.

Disclosure

“cal point is positive semidefinite (Lemma 5.1), a property closely connected to universal rigidity. Perhaps rigidity theory can provide a geometric explanation of the descent mechanism? Acknowledgments AI: The author used GPT-5.5 Pro during the preparation of this work. The descent directions (Sections 5.2), the overall proof strategy, and the proof of the m = 1 case (Section 6) were developed before any AI assistance. AI was subsequently used to help derive severa”

PDF page 31

Classification

Drafting a complete proof for author revision

Multiplier

9

Verified

2026-08-23T05:20:13.241596Z

Structural counts