Escaping Realization Traps in Distance Geometry by Releasing One Edge

Many reconstruction problems come down to placing points in space so that measured pairwise distances are respected. Protein structure from distance restraints, sensor and camera layouts, and keypoint skeletons of rigid robots all have this form. Gradient-based solvers for these problems often settle on a confidently wrong answer: a configuration that fits almost every measurement but is a mirror-folded or flipped version of the truth. We argue that many of these traps are not accidents of a rugged landscape. They are predictable consequences of rigidity theory, and a specific move escapes them that generic tricks such as random restarts, injected noise, or landscape smoothing do not provide. The move is to temporarily delete one distance constraint, follow the single remaining degree of freedom along the resulting flexing motion, and stop wherever the deleted distance is satisfied again.

The underlying fact comes from rigidity theory. A minimally rigid framework is a network of rods that cannot bend, but becomes bendable if any single rod is removed. Even with perfect measurements, such a framework can be assembled in many distinct real configurations, and the number of them can grow exponentially in the number of joints. Each assembly is an exact zero-loss minimum of the usual "stress" objective, the sum of squared distance errors. Once real sensors add noise, or a few redundant noisy measurements are added to pick out the true assembly, all the other assemblies become spurious local minima. Gradient descent cannot tell them apart from the truth, and saddle-escape methods cannot leave them because the curvature there is positive in every direction. Removing one rod turns the trap into a one-dimensional path that leads to the other assemblies, and that path can be traced cheaply.

Core Claim

We make three linked claims, ordered from most to least certain.

First, for sparse distance problems with a minimally rigid core, the number of bad local minima is governed by the number of real realizations (distinct physical assemblies), not by the much larger complex-algebraic bounds. The classical bounds count solutions over the complex numbers. The multihomogeneous Bézout analysis in On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs and the tighter combinatorial and tropical bounds in New Upper Bounds for the Number of Embeddings of Minimally Rigid Graphs and A tropical approach to rigidity: Counting realisations of frameworks all work in this setting. Constructive lower bounds count real assemblies. The modular chains in Algebraic Methods for Counting Euclidean Embeddings of Rigid Graphs reach roughly $2.52^n$ in 3D. The space between the two kinds of count is the "algebraic upper bound gap." Our claim is that, for an optimizer, the real count is the number that matters.

Second, this explains an apparent contradiction in the metric-embedding literature. Multidimensional Scaling: Approximation and Complexity proves that the spring-energy embedding objective is NP-hard. It nevertheless finds that gradient descent with restarts beats its own approximation scheme on the Davis network (energy 0.0478 versus 0.0498) and runs about 100 times faster (4 s versus 453 s on a 50-node Watts–Strogatz graph). That objective uses all pairwise graph distances, so the framework is dense and globally rigid and has essentially one real assembly. We predict that the benign behavior disappears as the measured edge set is thinned toward a minimally rigid core, and that restart success falls roughly in proportion to the real realization count.

Third, an edge-release move escapes these traps where stochastic saddle escape provably cannot. The move is related to the coupler-curve sampling that On the Maximal Number of Real Embeddings of Spatial Minimally Rigid Graphs used to construct graphs with many real assemblies. We repurpose it as an optimization step. The sim-to-real regime enters as the setting where this matters most. Real measurement noise does more than shift minima: it can push the distance vector near a "wall" in distance space where two real assemblies merge and turn complex. Near such a wall, the true basin becomes shallow and nearly degenerate, which is exactly the non-strict-saddle situation where perturbed gradient descent loses its guarantees. Solvers tuned on clean synthetic distances should therefore fail disproportionately on real data close to these walls, and we will test whether proximity to a wall predicts failures.

Research Program

The objective has two parts, a hard-ish core and weak evidence:

$$F(x) = \sum_{(i,j)\in E_c} \big(\|x_i-x_j\|^2 - d_{ij}^2\big)^2 + \lambda \sum_{(i,j)\in E_r} \big(\|x_i-x_j\| - \tilde d_{ij}\big)^2 .$$

Here $x_i$ is the position of point $i$. $E_c$ is a minimally rigid core of edges with lengths $d_{ij}$, and $E_r$ is a small set of redundant noisy measurements $\tilde d_{ij}$, weighted by $\lambda$, that distinguishes the true assembly. In the robotics and structural-biology instances, the core comes from known rigid-body or bond geometry and the redundant set comes from sensors.

The edge-release move works as follows. At a converged point $x^\star$, we select a core edge $e$, either by residual on $E_r$ or by its position in a Henneberg construction order (the step-by-step vertex-adding recipe that builds the graph). Removing $e$ leaves a one-degree-of-freedom mechanism. We trace its configuration curve with a predictor–corrector step. The predictor moves along the null vector of the rigidity matrix of $E_c\setminus\{e\}$, the matrix whose null space contains the instantaneous flexes. The corrector projects back onto the remaining constraints. Along the curve we record the length $\ell_e(t)$. Each crossing $\ell_e(t)=d_e$ is another real assembly, and we polish each one with a few gradient steps and keep the lowest $F$. One loop of the curve costs a few hundred projected steps, which is far cheaper than enumerating all complex roots.

There is also a stochastic variant aimed directly at the constrained-escape gap left open by How to Escape Saddle Points Efficiently. Its perturbed gradient descent adds isotropic noise from a ball, and on a constraint manifold almost all of that noise is infeasible. Projecting the noise back can cancel the useful component. We instead lower the weight on $e$ toward zero, which turns the wrong assembly into the bottom of a one-dimensional valley. We then inject noise only along the flex tangent and restore the weight. This is a continuation in a single edge weight rather than the global Gaussian blur analyzed in A Theoretical Analysis of Optimization by Gaussian Continuation. That paper's bound assumes a minimum path without bifurcations, and global blurring of a distance landscape tends to break this assumption by collapsing distinct assemblies together. In our version the bifurcation is the intended event and happens at a known place.

The analysis has two parts. On families whose real count is known, such as Henneberg vertex-addition chains (each addition doubles the count by reflection) and the Emiris-type modular chains, we will prove that every real assembly on the same component of the released-edge curve is reachable in one move. We will also characterize the assemblies that are not reachable this way, namely those on other curve components, which require releasing a different edge. Empirically, we will test the wall hypothesis by computing, for each failed instance, the smallest distance perturbation that merges two real assemblies. Small instances will use homotopy continuation, as in On the maximal number of real embeddings of minimally rigid graphs in $\mathbb{R}^2$, $\mathbb{R}^3$ and $\mathbb{S}^2$, and larger ones will use a local Jacobian-determinant proxy.

Baselines

The naive reference point is plain gradient descent (and Levenberg–Marquardt) on $F$ from a single random initialization. It tells us how often the trap occurs at all.

The strongest existing competitor is gradient descent with many random restarts. Multidimensional Scaling: Approximation and Complexity shows this beats a provable approximation scheme on dense embeddings (energy 0.0478 on the Davis network versus 0.0498, 4 s versus 453 s). We will first reproduce that number on the full Davis objective, so that our implementation is shown to be competitive in the dense regime. We then give restarts exactly the same budget of gradient and projection evaluations that edge-release hopping consumes, counting curve-tracing steps as evaluations. We tune the step size and restart count on held-out synthetic instances. On sparse frameworks there is no reported result found on Lacuna for restarts, so we establish that baseline ourselves. Beating it means a higher rate of recovering the true assembly, measured as aligned RMSD below threshold, at equal evaluations. The gain should grow with the real realization count.

The second competitor is perturbed gradient descent with feasibility projection, following How to Escape Saddle Points Efficiently, together with its momentum variant from Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent. They are run at matched evaluations with the noise radius tuned. We expect them to fix saddles but not realization traps, and that separation is itself a result.

The third is generic barrier crossing: random-direction basin hopping and contour stochastic gradient Langevin dynamics from A Contour Stochastic Gradient Langevin Dynamics Algorithm for Simulations of Multi-modal Distributions, with temperatures tuned on the same budget.

The fourth is recursive decomposition, RDIS from Recursive Decomposition for Nonconvex Optimization - IJCAI-15 Distinguished Paper. It reports lower error than restarted LM on Ladybug and proteins, but the file gives no reported numbers, so we rerun it.

The key ablation replaces the flex direction with a random feasible tangent direction of the same step length, and replaces residual-guided edge choice with uniform edge choice. If random-tangent hopping matches the flex move, the rigidity structure is not what is helping.

Why not just…?

Why not just use many random restarts? On dense problems this is the right answer, and Demaine et al.'s numbers show it. On sparse rigid cores, restarts are the most serious threat to this proposal, because the true assembly's basin may simply be large. The evidence against them is indirect: RDIS reports restarted LM getting trapped on Ladybug and protein landscapes. Our census experiment settles the question directly. If restart success does not fall as real realization counts grow from tens to thousands, the core claim is wrong, and we will report that.

Why not just enumerate all solutions with an exact algebraic or homotopy solver? This is exact and we use it as ground truth for small instances. However, it must track every complex root, and the complex bounds exceed the real counts by large factors. The file notes that enumeration becomes impractical beyond roughly 10–12 vertices. Edge-release tracing visits only real assemblies on one curve component, so its cost scales with the curve length rather than the complex root count. We will plot wall-clock time against $n$ for both methods.

Why not just smooth the landscape or decompose it, as in Gaussian continuation or RDIS? Global smoothing merges distinct assemblies, which is the bifurcation failure that Mobahi and Fisher's analysis excludes by assumption. Decomposition helps when the problem splits into nearly independent pieces, but a minimally rigid core is by definition a non-decomposable block, which is exactly where RDIS falls back on a local solver. We include both as baselines rather than arguing the point. We expect RDIS to win on loosely coupled proteins and to lose on cores built from Henneberg and modular chains.

Decisive Experiments

The synthetic testbed uses Henneberg and Emiris-style chains in 2D and 3D, together with the high-density graphs from Bartzos et al.'s coupler-curve search, with $n$ from 6 to about 200. We generate distances in two noise regimes. The "sim" regime uses clean distances with small Gaussian noise. The "real-like" regime adds outliers, dropped edges, and a systematic scale bias of the kind seen in calibrated sensors.

The first decisive check is a restart census on noise-free cores. If the number of distinct converged minima tracks the real count and not the complex bound, the first claim holds.

The second check is recovery rate at matched budget against all baselines. We also measure the shift between regimes: the drop in recovery from sim to real-like noise, and whether the distance to the nearest merging wall predicts which instances fail. A predictive area under the curve clearly above chance would support the sim-to-real mechanism. Chance-level prediction would refute it.

The third check tests the dense-to-sparse transition. We take the Davis and Watts–Strogatz graphs from Demaine et al., reproduce the 0.0478 restart energy, and then thin the measured pairs toward a rigid core. Edge-release hopping should begin to beat restarts at the point where the real realization count grows.

The fourth check uses real data. One set is backbone fragments from the 21-protein Protein Data Bank suite used by RDIS, with bond-geometry cores and sparse long-range restraints. The other is Ladybug structure-from-motion, using camera-to-point distance subproblems extracted from the bundle adjustment. In both, success is RMSD to the deposited or reference structure at equal evaluations.

The proposal fails cleanly if the random-tangent ablation matches the flex move, or if restarts keep pace as real counts grow. Either outcome would show that realization structure, while mathematically present, is not what limits practical solvers.