It is also similar to (metric) multi-dimensional scaling (MDS): the problem of finding coordinates that best explain a distance matrix (it is often a full matrix, but most of the algorithms should also work with a partial one). Your approximate coordinates would be used as an initial guess for the search.
On Friday, 23 October 2015 11:10:35 UTC+8, vav...@uwaterloo.ca wrote: > > The problem of recovering (x,y,z) coordinates given partial pairwise > distance information is a famous problem in the optimization community and > has attracted the attention of many top people. It is sometimes called the > 'Euclidean distance matrix completion' problem by mathematicians and the > 'sensor localization' problem by engineers. If you search in google > scholar on either of these terms, you'll find many papers. Jon Dattorio > wrote an entire book on the problem. > > -- Steve Vavasis > > > On Tuesday, October 20, 2015 at 11:12:44 PM UTC-4, Spencer Russell wrote: >> >> I have a bunch of points in 3D whose positions I know approximately, with >> low-noise distance measurements between them (not necessarily fully >> connected). I want to improve my estimate of their 3D coordinates. This >> smells like an optimization problem so I’m thinking of using it as an >> excuse to learn JuMP. The model variables (coordinates) and objective >> function seem pretty straightforward (probably sum of squared distance >> errors for the objective?) but I don’t know enough about the various >> solvers to know which one to use. I know a tiny bit about optimization >> (I’ve implemented simplex, L-M, and conjugate GD for a class) but get >> quickly outside my depth when it gets theoretical. >> >> Without any known positions the system is underconstrained because the >> whole collection could can translate, rotate, and reflect, but if I set 3 >> non-colinear points at known positions it should be solvable. I can also >> supply pretty good guesses for initial values on locations, at least close >> enough that the closest minima is the one I want (I think). >> >> so in short my questions boil down to: >> >> 1. What solver is appropriate for this sort of problem? (or should I just >> go with a spring-force algorithm like in GraphLayout.jl?) >> 2. (JuMP Specific) - Should I specify my known positions as model >> variables with equality constraints, or just normal julia variables that >> show up in my objective function? >> >> Thanks! >> >> -s > >
