Well, if this is useful, I can also point to several PhD theses on the EDM completion problem
Bruce Hendrickson, Cornell, 1991 Haw-ren Fang, Maryland, 2006 Pratik Biswas, Stanford, 2007 Anthony Man-Cho So, Stanford, 2007 Nathan Krislock, Waterloo, 2010 which are all available on the web. Probably there are other dissertations on the topic. Finally, let me say sorry for misspelling Dattorro's name in my previous posting (the correct spelling is easier to google!) -- Steve On Friday, October 23, 2015 at 10:53:40 AM UTC-4, Spencer Russell wrote: > > Thanks for this great pointers! I’ve been browsing a couple sensor > localization papers (that’s the area I’m coming from) but hadn’t seen it in > terms of Euclidean Distance Matrix Completion. Also, Dattorro’s book looks > great and super relevant. I’ll keep digging into the literature. > > -s > > > On Oct 22, 2015, at 11:10 PM, vav...@uwaterloo.ca <javascript:> 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 > > >
