I imagine there's a known algorithm for this, but am not totally sure what to search for, and so my search didn't turn up much.
Basically, I have have a set of $N$ nodes $\hat x_i $ in a graph $\hat G$, where each node is a 2D location $\hat x_i \in \Re^2$. Each edge of the graph $\hat e_{ij}$ is tagged with the length of the edge, namely $\lvert\hat x_i$ - $\hat x_j\rvert$. This is a complete, undirected graph.
What I would like to do is produce an estimate $G^*$ of $\hat G$ based on some well-known and some observed information about the graph.
In particular, $M$ of the nodes' locations (and thus the edges between them) are known a priori and fixed. In addition, I have noisy estimates for $K$ of the remaining edge lengths $\tilde e_{ij}$, which are taken from $\mathcal N(\hat e_{ij}, \sigma)$ (where $\sigma$ is fixed).
My inclination is to define an energy function $E(G)$ on the differences between the edge lengths in $G$ and the observed lengths, e.g.:
$$ E(G) = \sum_{i=0}^N {\sum_{j=0}^N {(\tilde e_{ij}- e_{ij})^2}} $$
And then solve for $G^*$, the graph with minimum energy:
$$G^* = {argmin}_{G} [E(G)] $$
Subject to the known constraints.
But I'm not sure how to solve this problem... normally to solve the argmin I'd want to take the gradient with respect to $G$ and find its zeros.. but what does it mean to take a gradient with respect to a graph?
It is obvious that there are certain situations which do not have a unique solution. At a minimum, it would seem that 3 nodes' locations must be known (and not co-linear), and all nodes must have at least 3 observed edge lengths.
My hope is that there's some way of solving this in closed form, but I suspect solutions may need to be approached iteratively.
How might I estimate $\hat G$?