From bahendr@sandia.gov Sat Jan 29 15:08:18 2005 Date: Sat, 29 Jan 2005 08:38:34 -0700 (MST) From: Bruce Hendrickson To: Henry Wolkowicz Subject: Re: referee report on So/Ye paper? (fwd) Hi Henry. I'm so sorry. I wrote up a report in early December, but I must have erred in sending it to you. I'm attaching it below. - Bruce On Sat, 29 Jan 2005, Henry Wolkowicz wrote: > > Dear Bruce, > Just a quick reminder about the paper to referee > > Theory of Semidefinite Programming for Sensor Network Localization > by So and Ye. > > Do you know when you can provide a report? > > best regards > > Henry > > > > > Prof. Henry Wolkowicz |USE Email: hwolkowicz AT uwaterloo.ca > Univ. of Waterloo |URL http://orion.math.uwaterloo.ca/~hwolkowi > Dept of Comb and Opt |Tel (519) 888-4567, x5589, office MC6065 > Waterloo, Ont. CANADA N2L 3G1 |Fax (519) 725-5441 > > This is my report on "Theory of Semidefinite Programming for Sensor Network Localization" which is being considered for publication. This paper is concerned with the "sensor network localization problem". Given a set of objects in R^d, some at known locations, and knowledge about some of the pairwise distances between objects, can we determine the location of all the objects? This is a variant of a problem that has been well studied by several communities. This particular variant is distinguished by the presence of some objects with known locations. Note that the data in a problem instance can be thought of as a graph. The principle contribution of this paper is the identification of a class of graphs for which a semi-definite programming algorithm is guaranteed to find the unique solution. The graph class is interesting - it is graphs that have a solution in 2D, but no different solutions in higher dimensions. Although not remarked in the paper, I don't think this property is purely graph theoretic, but also depends upon the set of distances (or alternatively, on the locations of vertices in the solution). Perhaps there is some convexity property in the placement of vertices and anchors. It would be nice to have a graph and geometric understanding of strong localizability. The authors draw connections to the rigidity literature, and to the results on unique realizability in particular. Although these prior results are closely related to the current paper, to my knowledge the current results are new. And I find them interesting and intriguing. I can't help but wonder if there are connections to Connelly's work on tensegrity frameworks ... Although the paper is generally well written, I have a few suggestions for improving the presentation. Most are not substantive. Page 2, Line 13: "there has been" should be "there have been". P 2, L -16 (also P 7, L -6): "close to be" should be "close to being". P 2, L -16 (also P 7, L -6): It's not clear to me why you can argue that your result is nearly the best possible. There could be a larger class of graphs that are solvable. The fact that the general problem is hard doesn't ensure that a particular solvable class is nearly the best possible. P 8, L 16: "are couple ways" should be "are several ways". Section 5: You mention early in this section that you assume the embeddings are generic. But this is an important assumption and should probably be included in some of the theorem statements. P 10, L -5: "an useful" should be "a useful". Definition 5: Is it possible to reinterpret this condition in a manner that doesn't depend on SDP duality? P 12, L 4 and L 5: What is "w."? P 13, L 8: I think you mean to reflect the subgraph induced by a_1, x_2 and a_3 (not a_2).