Target Sampling as a Built-In Saddle Escape for Anchor Placement

Indoor radio positioning systems such as ultra-wideband (UWB) locate a tag by measuring its distances, or differences of distances, to fixed reference radios called anchors. The accuracy they can reach depends heavily on where those anchors sit. The usual summary of this effect is geometric dilution of precision (GDOP): a number that says how much the anchor layout amplifies ranging noise at each point in the room. Anchors that are bunched together or nearly collinear make GDOP blow up, and so does any target outside the region the anchors enclose. Choosing anchor positions to minimize GDOP averaged over a room is therefore a non-convex optimization over the anchor coordinates. Today it is solved with candidate grids and convex relaxations, with coordinate descent restricted to the walls, or with genetic algorithms. None of these methods asks what the continuous landscape looks like, or whether gradient methods stall on it.

This note proposes treating the room-averaged placement objective the way machine learning treats a training loss, and making one specific bet. The room average is a sum over target locations, much as a training loss is a sum over examples. Sampling target locations to estimate the gradient therefore produces stochastic-gradient noise. We hypothesize that this noise points along exactly the directions that let a stuck anchor layout escape. At a symmetric or degenerate layout, such as two anchors stacked together or anchors spaced evenly along a corridor, the room-averaged gradient for pulling the anchors apart cancels to zero. Individual targets, however, pull hard and in opposite directions. If this holds, plain stochastic gradient descent over sampled targets escapes saddle points (stationary points with a downhill direction) where full-quadrature gradient descent and coordinate descent sit still. It would also do so without the artificial noise or Hessian computations that saddle-escape theory usually relies on.

Core Claim

Let $A \in \mathbb{R}^{3K}$ stack the coordinates of $K$ anchors, constrained to a feasible set $\mathcal{C}$ made of room walls, ceiling, and obstacle exclusion zones. Let $p$ be a target location drawn uniformly from the region of interest $R$. The objective is

$$ J(A) = \mathbb{E}_{p \sim R}\big[\, j(p, A) \,\big], \qquad j(p,A) = \operatorname{tr}\!\big( F(p,A)^{-1} \big), $$

where $F(p,A)$ is the Fisher information matrix at target $p$, which measures how much information the anchors carry about the target's position. It is built from the unit vectors pointing from each anchor to $p$, weighted by a distance-dependent noise variance. The distance-dependent variance follows the path-loss model of Sparsity-exploiting anchor placement for localization in sensor networks and keeps the problem well posed. The term $j$ is the per-target squared GDOP; in the NLOS variant we replace it with the per-target mean-squared error of Finding the Right Place.

The escape mechanism comes from Escaping Saddles with Stochastic Gradients. That paper shows plain SGD escapes strict saddles whenever its gradient noise satisfies a correlated negative curvature (CNC) condition. In our notation the condition reads

$$ \mathbb{E}_{p}\big[\, (v^\top \nabla_A j(p,A))^2 \,\big] \;\ge\; \eta > 0, $$

where $v$ is the eigenvector of the Hessian of $J$ with the most negative eigenvalue and $\eta$ is a constant. In words, the per-target gradients must have non-vanishing spread along the downhill direction.

That paper also shows that isotropic injected noise has only $O(1/d)$ of its variance along $v$, where $d$ is the dimension. Isotropic noise is spread evenly over all $d$ directions, so only a $1/d$ share lands on any one of them. Our claim has three parts:

  1. At the stationary points that structured initializations actually reach, namely symmetric perimeter layouts, corridor-collinear layouts, and coincident drops, target-sampling noise satisfies CNC with an $\eta$ that does not shrink as $K$ grows.
  2. Plain stochastic gradient descent over target samples therefore escapes, while full-quadrature methods stall.
  3. This advantage over isotropic perturbation widens as the number of anchors grows.

The research file confirms that no prior work applies saddle-escape methods to anchor placement. It also frames the problem as having "no mini-batch" to supply intrinsic noise. The reframing that target sampling is the mini-batch is the new part.

Research Program

The first stage is a landscape census, and it decides whether the project continues. We take three benchmark geometries:

  1. synthetic rectangular and L-shaped rooms;
  2. a cluttered room whose NLOS bias model is fitted from the Loco Positioning System measurements used in Finding the Right Place;
  3. a long-corridor exploration scenario mirroring On-Line Optimal Ranging Sensor Deployment for Robotic Exploration.

In each geometry we run full-quadrature projected gradient descent from many structured and random initializations, for $K$ from 4 to about 200. At each terminal point we compute the exact Hessian, projected onto the tangent space of the active constraints, which is cheap at these sizes. We record how often runs end at strict saddles, the size of the negative eigenvalue, and what the escape direction looks like physically: separating, rotating out of a line, or lifting off a wall.

If strict saddles are rare outside contrived starting points, the escape story is moot and the project reduces to a negative result about the landscape. That result is still worth publishing.

The second stage measures the CNC constant. At each saddle we compare $\eta$ for target-sampling noise against the projection of matched-variance isotropic noise. We also derive $\eta$ in closed form for two cases: two coincident anchors, and $K$ anchors evenly spaced on a line with targets uniform in a disc. This should show why $\eta$ scales with the spread of per-target pulls rather than with $1/K$.

The third stage handles constraints. How to Escape Saddle Points Efficiently proves fast escape for perturbed gradient descent and names constrained domains as open. Anchors live on walls and around obstacles. We study projected SGD in which the target-sampling noise is projected onto the tangent space of the active constraints. We test empirically whether escape survives when the downhill direction leaves the feasible set. We expect this to happen most often at saddles pinned against a wall. We borrow the manifold view of perturbed Riemannian stochastic recursive gradient for anchors constrained to wall surfaces.

Baselines

The naive reference is the "trivial" placement from Finding the Right Place: anchors spread uniformly on the room boundary. That paper reports that its optimized placement reduces average RMSE relative to trivial placement by 46.77% in 2D and 75.67% in 3D experiments. Our method must at least reproduce gains of this size in matched simulated rooms before any further claim means anything.

The strongest domain-specific competitor is that paper's block coordinate-wise minimization (BCM) on the MSE objective. It is the only method in the file that optimizes continuous anchor positions under NLOS bias and was validated on hardware. We run it on identical rooms and bias models. We run it both under its original boundary restriction and with that restriction lifted to full 3D free space, so the comparison isolates the optimizer rather than the search space.

The strongest generic competitor is multistart L-BFGS on full-quadrature $J$, with restarts budgeted to the same number of per-target gradient evaluations as our method. Also given the matched evaluation budget are:

For $K \le 13$ we also include the grid-based SDP of Sparsity-exploiting anchor placement, which is reported to keep localization error within 4–5 cm with 95% probability in its own setting.

Every method gets the same tuning budget of 20 configurations, chosen on held-out rooms. Beating a baseline means a lower final $J$ and lower simulated RMSE at equal evaluation count, across at least 50 seeds, with non-overlapping 95% intervals. For the corridor scenario, the target is maintaining the PDoP threshold of 1.5 reported in On-Line Optimal Ranging Sensor Deployment using fewer anchors or less onboard compute. The file has no reported result for continuous free-space GDOP placement, so absolute objective values have no prior reference.

The decisive ablation keeps target-sampling SGD unchanged except that, at each step, we remove the noise component along the current most-negative Hessian eigenvector, recomputed every few steps. If escape rates collapse, the CNC component is the active ingredient. If they do not, our explanation is wrong even if the method works. A second ablation replaces target-sampling noise with isotropic noise of equal total variance.

Why not just…?

Why not just use multistart L-BFGS? With few anchors this is a real threat. The problem has only a few dozen dimensions, and random restarts may simply avoid saddles. We expect the gap to appear only at large $K$, building-scale deployments with hundreds of anchors, and with structured initializations that practitioners actually use, where restarts land in the same symmetric basins. The matched-budget comparison over $K$ will show where, if anywhere, the crossover lies. If no crossover appears up to $K=200$, we will report that multistart suffices.

Why not just compute the Hessian and follow its negative eigenvector? At small $K$ this is cheap and will likely match us, and we include it as a baseline. Its weakness is the NLOS-MSE objective, where every per-target term is a Monte Carlo estimate. A Hessian assembled from noisy estimates can misjudge the sign of a small eigenvalue. The cost also grows with the square of $3K$ times the number of target samples. Stochastic gradients get the escape direction from samples already being drawn. The experiment that settles this is Hessian-step success versus our method as the per-target Monte Carlo noise grows.

Why not just keep discretizing and use convex relaxation or BCM? Grid SDP faces combinatorial blow-up: choosing 13 anchors from 80 sites already exceeds $10^{17}$ combinations (Sparsity-exploiting anchor placement). Convex underestimators also degrade when targets leave the anchors' enclosed region, a breakdown documented in STRONG for localization. BCM moves one block of coordinates at a time, so it cannot follow a downhill direction that couples several anchors. The landscape census tests this directly by checking whether BCM's terminal points have negative Hessian eigenvalues that mix several anchors' coordinates.

Decisive Checks

The project hinges on three measurements:

  1. whether strict saddles occur at practical rates from realistic initializations;
  2. whether target-sampling noise has a measurable, $K$-independent component along the downhill direction;
  3. whether removing that component removes the escape.

If all three hold, we validate the resulting layouts with LPS-calibrated NLOS simulation and a small hardware deployment, reporting RMSE against BCM placements.