text: We study Semidefinite Programming, relaxations for Sensor Network Localization, with anchors and with noisy distance information. The main point of the paper is to view as a (nearest) Euclidean Distance Matrix, , completion problem and to show the advantages for using this latter, well studied model. We first show that the current popular relaxation is equivalent to known relaxations in the literature for completions. The existence of anchors in the problem is not special. The set of anchors simply corresponds to a given fixed clique for the graph of the problem. We next propose a method of projection when a large clique or a dense subgraph is identified in the underlying graph. This projection reduces the size, and improves the stability, of the relaxation. In addition, viewing the problem as an completion problem yields better low rank approximations for the low dimensional realizations. And, the projection reduction procedure can be repeated for other given cliques of sensors or for sets of sensors, where many distances are known. Thus, further size reduction can be obtained. Optimality duality conditions and a primal-dual interior-exterior path following algorithm are derived for the relaxations We discuss the relative stability and strength of two formulations and the corresponding algorithms that are used. In particular, we show that the quadratic formulation arising from the relaxation is better conditioned than the linearized form, that is used in the literature and that arises from applying a Schur complement.
  @cite_24: 
  @cite_10: Abstract A partial pre-distance matrix A is a matrix with zero diagonal and with certain elements fixed to given nonnegative values; the other elements are considered free . The Euclidean distance matrix completion problem chooses nonnegative values for the free elements in order to obtain a Euclidean distance matrix, EDM. The nearest (or approximate) Euclidean distance matrix problem is to find a Euclidean distance matrix, EDM, that is nearest in the Frobenius norm to the matrix A , when the free variables are discounted. In this paper we introduce two algorithms: one for the exact completion problem and one for the approximate completion problem. Both use a reformulation of EDM into a semidefinite programming problem, SDP. The first algorithm is based on an implicit equation for the completion that for many instances provides an explicit solution. The other algorithm is based on primal–dual interior-point methods that exploit the structure and sparsity. Included are results on maps that arise that keep the EDM and SDP cones invariant. We briefly discuss numerical tests.
  @cite_22: Abstract A distance matrix D of order n is symmetric with elements − 1 2 d ij 2 , where dii=0. D is Euclidean when the 1 2 n(n−1) quantities dij can be generated as the distances between a set of n points, X (n×p), in a Euclidean space of dimension p. The dimensionality of D is defined as the least value of p=rank(X) of any generating X; in general p+1 and p+2 are also acceptable but may include imaginary coordinates, even when D is Euclidean. Basic properties of Euclidean distance matrices are established; in particular, when ρ=rank(D) it is shown that, depending on whether eTD−e is not or is zero, the generating points lie in either p=ρ−1 dimensions, in which case they lie on a hypersphere, or in p=ρ−2 dimensions, in which case they do not. (The notation e is used for a vector all of whose values are one.) When D is non-Euclidean its dimensionality p=r+s will comprise r real and s imaginary columns of X, and (r, s) are invariant for all generating X of minimal rank. Higher-ranking representations can arise only from p+1=(r+1)+s or p+1=r+ (s+1) or p+2=(r+1)+(s+1), so that not only are r, s invariant, but they are both minimal for all admissible representations X.
  @cite_3: Given a partial symmetric matrix A with only certain elements specified, the Euclidean distance matrix completion problem (EDMCP) is to find the unspecified elements of A that make A a Euclidean distance matrix (EDM). In this paper, we follow the successful approach in [20] and solve the EDMCP by generalizing the completion problem to allow for approximate completions. In particular, we introduce a primal-dual interior-point algorithm that solves an equivalent (quadratic objective function) semidefinite programming problem (SDP). Numerical results are included which illustrate the efficiency and robustness of our approach. Our randomly generated problems consistently resulted in low dimensional solutions when no completion existed.
summary: The geometry of has been extensively studied in the literature, e.g. @cite_22 @cite_24 and more recently in @cite_3 @cite_10 and the references therein. The latter two references studied algorithms based on formulations of the completion problem.