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_29: A growth inhibitor for cariogenic bacteria which comprises containing therein l- alpha -cadinol as an active ingredient. In particular, the effect of growth inhibition to Streptococcus mutans IPCR 1009 strain can be produced at a concentration of 1 50,000.
  @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 relaxations solve a closest matrix problem and generally use the @math norm. The @math norm is used in @cite_29 , where the noise in the radio signal is assumed to come from a multivariate normal distribution with mean @math and variance-covariance matrix @math , i.e. from a spherical normal distribution so that the least squares estimates are the maximum likelihood estimates. (We use the @math norm as well in this paper. Our approach follows that in @cite_3 for completion without anchors.)