University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Tutte seminar - Henry WolkowiczExport this event to calendar

Friday, July 31, 2009 — 3:30 PM to 4:30 PM EDT

Sensor Network Localization, Euclidean Distance Matrix Completions, and Graph Realization

Speaker: Henry Wolkowicz
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

The sensor network localization (SNL) problem consists of locating the positions of ad hoc wireless sensors, given only the distances between sensors that are within radio range and the positions of a subset of the sensors (called anchors). One main point is to view SNL as a (nearest) Euclidean Distance Matrix (EDM), completion problem that does not distinguish between the anchors and the sensors. We show that there are advantages for using the well-studied EDM model. This problem can be relaxed to a weighted, nearest, (positive) semidefinite programming (SDP), completion problem. This relaxation is ill-conditioned in two ways. First, it is, implicitly, highly degenerate in the sense that the feasible set is restricted to a low dimensional face of the SDP cone. This means that the Slater constraint qualification fails. Second, nonuniqueness of the optimal solution results in large sensitivity to small perturbations in the data. 

The degeneracy in the SDP arises from cliques in the graph of the SNL problem. We take advantage of the absence of the Slater constraint qualification and derive a preprocessing technique that solves the SNL problem. With exact data, we explicitly solve the corresponding SDP problem without using any SDP solver. We do this by finding explicit representations of the faces of the SDP cone corresponding to intersections of cliques of the SNL problem. For problems with noise, we first solve nearest matrix problems to get best EDM approximations. 

This is joint work with Nathan Krislock.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
  1. 2020 (33)
    1. March (11)
    2. February (11)
    3. January (11)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (138)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)