05. Can distances reveal a map?

Correlation completion showed how PSD constraints control unknown inner products. Does that geometry transfer to a problem with a completely different surface story?

A collection of sensors may know distances to nearby sensors without knowing its own coordinates. This appears in wireless localization and more generally in graph realization. SDP-based methods have been developed for incomplete and noisy distance measurements. Biswas and Ye, 2004

This chapter uses a deliberately small, exact instance. Its purpose is to expose the Gram-matrix representation before dealing with missing or noisy ranges.

Five sensor nodes are connected by dashed lines labeled with measured distances.

Five sensors connected by measured pairwise ranges.

Go further: localization

The motivating method is developed in Biswas and Ye’s primary paper, Semidefinite Programming for Ad Hoc Wireless Sensor Network Localization. The paper includes anchors, incomplete measurements, and algorithmic issues that our exact five-sensor experiment deliberately omits.

Can squared distances become linear?

If the unknown position of sensor $i$ is $p_i$ and $G_{ij}=p_i^Tp_j$, then

\[ \lVert p_i-p_j\rVert_2^2=G_{ii}+G_{jj}-2G_{ij}. \]

The distance equation is linear in $G$. Requiring $G\succeq0$ guarantees that it describes some Euclidean vectors.

Distances alone cannot locate an absolute origin: adding the same translation to every sensor leaves every pairwise distance unchanged. We choose one representative by centering the positions,

\[ \sum_i p_i=0. \]

If the position vectors are the rows of $P$ and $G=PP^T$, centering implies

\[ G\mathbf1=P(P^T\mathbf1)=0. \]

We therefore require every row sum of $G$ to be zero. This removes translation; rotation and reflection will remain.

using JuMP
using Clarabel
using LinearAlgebra

points = [
     0.0  0.2
     1.5  0.0
     2.4  1.0
     1.8  2.1
     0.3  1.8
]
points .-= sum(points; dims = 1) ./ size(points, 1)
n = size(points, 1)
d² = [(sum(abs2, points[i, :] - points[j, :])) for i in 1:n, j in 1:n]

5×5 Matrix{Float64}:
 0.0   2.29  6.4   6.85  2.65
 2.29  0.0   1.81  4.5   4.68
 6.4   1.81  0.0   1.57  5.05
 6.85  4.5   1.57  0.0   2.34
 2.65  4.68  5.05  2.34  0.0

In this first localization model every pairwise range is available. That makes the centered Gram matrix unique and lets us check the entire pipeline against known coordinates.

model = Model(Clarabel.Optimizer)
set_silent(model)
@variable(model, G[1:n, 1:n], PSD)
@constraint(model, [i in 1:n], sum(G[i, j] for j in 1:n) == 0)
@constraint(
    model,
    [i in 1:n, j in (i + 1):n],
    G[i, i] + G[j, j] - 2G[i, j] == d²[i, j],
)
@objective(model, Min, 0)
optimize!(model)

Ĝ = Matrix(value.(G))
(status = termination_status(model),
 minimum_eigenvalue = eigmin(Symmetric(Ĝ)),
 eigenvalues = round.(eigvals(Symmetric(Ĝ)); digits = 7))

(status = OPTIMAL, minimum_eigenvalue = -1.070784122775967e-14, eigenvalues = [-0.0, 0.0, 0.0, 3.1311559, 4.4968441])

Can we recover the hidden map?

Only two eigenvalues should be meaningfully positive because the sensors live in the plane. Take the two leading eigenpairs to obtain coordinates.

decomposition = eigen(Symmetric(Ĝ))
order = sortperm(decomposition.values; rev = true)
keep = order[1:2]
recovered = decomposition.vectors[:, keep] *
            Diagonal(sqrt.(max.(decomposition.values[keep], 0)))

recovered_d² = [sum(abs2, recovered[i, :] - recovered[j, :])
                for i in 1:n, j in 1:n]

(maximum_distance_error = maximum(abs.(recovered_d² - d²)),
 recovered_coordinates = round.(recovered; digits = 4))

(maximum_distance_error = 1.509903313490213e-14, recovered_coordinates = [1.4505 -0.0914; 0.2635 -1.03; … ; -1.0677 0.6215; 0.3748 1.1304])

The recovered coordinates need not match the original coordinate columns. Rotation and reflection change coordinates but preserve the Gram geometry and all pairwise distances.

What exactly did feasibility establish?

The objective is zero, so this is a feasibility problem: every matrix satisfying the constraints is equally optimal. Complete exact distances plus centering make the Gram matrix unique in this instance. The coordinates are still not unique because rotation and reflection preserve that matrix.

With incomplete ranges, distinguish three questions:

Feasibility: does any Euclidean configuration match the measurements?
Uniqueness: do the constraints determine one Gram matrix?
Identifiability: after accounting for rigid motions, do they determine the physical configuration of interest?

A solver returning one feasible matrix answers only the first question unless additional structure proves the others.

What breaks with real measurements?

With only some ranges, many PSD completions may fit. With noisy ranges, exact equalities may be inconsistent. Practical formulations introduce residuals, weights, anchors, or objectives that choose among approximate realizations. The small feasibility problem above establishes the representation those models extend; it is not a deployment-ready localization system.

This detour has tested the Gram-matrix idea on physical geometry. We can now return to schedules and ask whether binary signs can be replaced by the same kind of vectors.

Try it yourself

Remove one distance constraint and determine whether the recovered missing distance is still unique.
Change one measured squared distance by 0.2. Inspect the termination status rather than attempting to read nonexistent variable values.
Generate points in three dimensions and predict the numerical rank of G.
Complete learner/05_geometry_from_distances.jl.

--- title: "05. Can distances reveal a map?" engine: julia julia: exeflags: ["--project=@."] --- Correlation completion showed how PSD constraints control unknown inner products. Does that geometry transfer to a problem with a completely different surface story? A collection of sensors may know distances to nearby sensors without knowing its own coordinates. This appears in wireless localization and more generally in graph realization. SDP-based methods have been developed for incomplete and noisy distance measurements. [Biswas and Ye, 2004](https://doi.org/10.1109/IPSN.2004.1307322) This chapter uses a deliberately small, exact instance. Its purpose is to expose the Gram-matrix representation before dealing with missing or noisy ranges. ![Five sensors connected by measured pairwise ranges.](../assets/sensor-network.svg){fig-alt="Five sensor nodes are connected by dashed lines labeled with measured distances."} ::: {.callout-note title="Go further: localization"} The motivating method is developed in Biswas and Ye's primary paper, [Semidefinite Programming for Ad Hoc Wireless Sensor Network Localization](https://doi.org/10.1109/IPSN.2004.1307322). The paper includes anchors, incomplete measurements, and algorithmic issues that our exact five-sensor experiment deliberately omits. ::: ## Can squared distances become linear? If the unknown position of sensor $i$ is $p_i$ and $G_{ij}=p_i^Tp_j$, then $$ \lVert p_i-p_j\rVert_2^2=G_{ii}+G_{jj}-2G_{ij}. $$ The distance equation is linear in $G$. Requiring $G\succeq0$ guarantees that it describes some Euclidean vectors. Distances alone cannot locate an absolute origin: adding the same translation to every sensor leaves every pairwise distance unchanged. We choose one representative by centering the positions, $$ \sum_i p_i=0. $$ If the position vectors are the rows of $P$ and $G=PP^T$, centering implies $$ G\mathbf1=P(P^T\mathbf1)=0. $$ We therefore require every row sum of $G$ to be zero. This removes translation; rotation and reflection will remain. ```{julia} #| label: make-range-data using JuMP using Clarabel using LinearAlgebra points = [ 0.0 0.2 1.5 0.0 2.4 1.0 1.8 2.1 0.3 1.8 ] points .-= sum(points; dims = 1) ./ size(points, 1) n = size(points, 1) d² = [(sum(abs2, points[i, :] - points[j, :])) for i in 1:n, j in 1:n] ``` In this first localization model every pairwise range is available. That makes the centered Gram matrix unique and lets us check the entire pipeline against known coordinates. ```{julia} #| label: localization-sdp model = Model(Clarabel.Optimizer) set_silent(model) @variable(model, G[1:n, 1:n], PSD) @constraint(model, [i in 1:n], sum(G[i, j] for j in 1:n) == 0) @constraint( model, [i in 1:n, j in (i + 1):n], G[i, i] + G[j, j] - 2G[i, j] == d²[i, j], ) @objective(model, Min, 0) optimize!(model) Ĝ = Matrix(value.(G)) (status = termination_status(model), minimum_eigenvalue = eigmin(Symmetric(Ĝ)), eigenvalues = round.(eigvals(Symmetric(Ĝ)); digits = 7)) ``` ## Can we recover the hidden map? Only two eigenvalues should be meaningfully positive because the sensors live in the plane. Take the two leading eigenpairs to obtain coordinates. ```{julia} #| label: recover-sensors decomposition = eigen(Symmetric(Ĝ)) order = sortperm(decomposition.values; rev = true) keep = order[1:2] recovered = decomposition.vectors[:, keep] * Diagonal(sqrt.(max.(decomposition.values[keep], 0))) recovered_d² = [sum(abs2, recovered[i, :] - recovered[j, :]) for i in 1:n, j in 1:n] (maximum_distance_error = maximum(abs.(recovered_d² - d²)), recovered_coordinates = round.(recovered; digits = 4)) ``` The recovered coordinates need not match the original coordinate columns. Rotation and reflection change coordinates but preserve the Gram geometry and all pairwise distances. ## What exactly did feasibility establish? The objective is zero, so this is a feasibility problem: every matrix satisfying the constraints is equally optimal. Complete exact distances plus centering make the Gram matrix unique in this instance. The coordinates are still not unique because rotation and reflection preserve that matrix. With incomplete ranges, distinguish three questions: 1. **Feasibility:** does any Euclidean configuration match the measurements? 2. **Uniqueness:** do the constraints determine one Gram matrix? 3. **Identifiability:** after accounting for rigid motions, do they determine the physical configuration of interest? A solver returning one feasible matrix answers only the first question unless additional structure proves the others. ## What breaks with real measurements? With only some ranges, many PSD completions may fit. With noisy ranges, exact equalities may be inconsistent. Practical formulations introduce residuals, weights, anchors, or objectives that choose among approximate realizations. The small feasibility problem above establishes the representation those models extend; it is not a deployment-ready localization system. This detour has tested the Gram-matrix idea on physical geometry. We can now return to schedules and ask whether binary signs can be replaced by the same kind of vectors. ## Try it yourself 1. Remove one distance constraint and determine whether the recovered missing distance is still unique. 2. Change one measured squared distance by `0.2`. Inspect the termination status rather than attempting to read nonexistent variable values. 3. Generate points in three dimensions and predict the numerical rank of `G`. 4. Complete `learner/05_geometry_from_distances.jl`.