0.2 Simulation procedure

Simulation procedure

For our project, we applied these new matrix completion techniques to the sensor network localization problem. More explicitly, our idea was to take an incomplete matrix of distances between sensors and use the OptSpace algorithm mentioned previously to fill in the missing entries, whereupon the network may be reconstructed using multidimensional scaling methods. Because a matrix of Euclidean distances between random points is, in general, full rank, it cannotbe completed directly; however, the matrix of the squares of the distances between the points has a fixed maximum rank depending on the dimension of the space in which the points are embedded. To see this, suppose that we are given $N$ points $x_1,...,x_n$ in ${\mathbb{R}}^n$ , and let $D_2$ be the $N$ -by- $N$ matrix of their squared distances; that is, the $ij$ -entry of $D_2$ is equal to $\parallel x_i-x_j{\parallel }^2$ for $i,j=1,...,n$ . Denote the $k^{\mathrm{th}}$ coordinate of $x_i$ by $x_i^{\left(k\right)}$ . Because $\parallel x_i-x_j{\parallel }^2=\parallel x_i{\parallel }^2-2(x_i•x_j)+{\parallel x_j\parallel }^2$ (where $•$ denotes the usual dot product on ${\mathbb{R}}^n$ ), we have

and so $D_2$ may be written as the product of a matrix with $n+2$ columns and a matrix with $n+2$ rows. The rank of $D_2$ may therefore not exceed $n+2$ . For our particular project, we restricted our attention to sensors embedded in a plane (in which case the rank of $D_2$ is at most 4 for any number of sensors $N$ ), but this property of the matrix $D_2$ offers a simple way to extend our work to higher dimensions.

To try out our ideas, we designed and executed several different MATLAB simulations, each of which proceded according to the following general outline:

1. Generate $N=200$ uniformly distributed random points inside the unit square $[0,1]\times [0,1]$ .
2. Form the matrix $D$ of pairwise distances between the points. Add noise if necessary.
3. Form the matrix $D_2$ of the squares of the (possibly noisy) distances between the points.
4. Knock out pairs of distances in $D_2$ according one of two procedures (described below) to form the partially observed matrix $R$ .
5. Complete the matrix $R$ using OptSpace to get $\widehat{D_2}$ .
6. Form the matrix $\widehat{D}$ , which is the element-wise square-root of $\widehat{D_2}$ .
7. Compare the completed matrix $\widehat{D}$ to the original $D$ by measuring the relative Frobenius-norm error $e=\parallel \widehat{D}{-D\parallel }_F/{\parallel D\parallel }_F$ .
8. Repeat the above steps for 25 trials, and compute the average relative Frobenius-norm error at the end.

We used two different methods for determining which entries in the matrix to eliminate, which we call “random" and “realistic" knock-out, respectively. By random knock-out, we mean that distance pairs were selected at random to be knocked-out according to a fixed probability. In constrast, realistic knock-out involves removing all entries of the matrix that exceed a certain threshold distance. The idea is that in a realistic setting, sensors which are far apartfrom each other may not be able to construct an estimate of the distance between themselves.

To simulate noise in the trials that required it, we randomly generated values from zero-mean Gaussian distributions and added them to the entries in the matrix of distances. In order to understand what effect the noise amplitude would have on the results, we used five different values for the standard deviations of these distributions: 0.01, 0.05, 0.1, 0.2, and 0.5.

A copy of the MATLAB code we wrote for the simulations is available here . The OptSpace code must be downloaded separately and may be found at the OptSpace website listed in this project's References module.