AA: Transformation of Random Vectors for Decorrelation

Assignment Summary

If your last (family) name begins with A-N, please complete the "Appl. Assignment 4 Quiz" on WebCT after finishing work on this assignment. If your last (family) name begins with O-Z, please complete the "Appl. Assignment 4 Quiz" on WebCT PRIOR TO STARTING work on this assignment. The quiz is found in the "Assessments" tab of the WebCT page.

Last Name Begins With When To Take the Quiz
A-N After completing the assignment
O-Z BEFORE STARTING the assignment

In this assignment, you will de-correlate the measured RSS stream at each node. This will produce vectors with uncorrelated elements.

  1. Compute the covariance matrix for the measured RSS data vectors over time. Turn in: An image plot of the covariance matrix.
  2. Compute the KLT for your measured RSS data. Turn in: Plots of the first 9 eigenvectors.
  3. Transform the RSS data vectors using the KLT into an uncorrelated matrix. Turn in: An image plot of the new covariance matrix.
  4. Compare a few components at nodes a and b. Turn in: A brief description of which components are best to use in secret key generation.

You will need Matlab, a text file from an RSS measurement experiment, and some way to produce a document (eg., Word, OpenOffice). Create one PDF containing the outputs of your assignment, and the Matlab code you used to generate them. Turn it into the WebCT assignment drop box, by midnight on the due date.

Assignment Description

Load the data as you did in Application Assignment 2. This involves loading, separating, and interpolating the data so that you have data vectors "interpa" and "interpb" in memory. Also, correct for the mean in each vector as you did previously.

0. Prepare to consider temporal vectors

In application assignment 3, we considered the covariance between measurements on the two directions of the link. The main difference in this application assignment is that instead, we will consider the covariance of one direction of the link, but over time. Assignment 3 studied "spatial" covariance; this assignment studies "temporal" covariance.

We will study small segments of your measurements. Each radio made about 50 measurements per second. So we will study one-second segments by looking at each 50-length vector of those measurements. This is


for any valid integer i. For your own benefit, set i to be equal to some number between 1 and length(interpa)-49. Then:

plot(1:50, interpa(i:i+49),'-o')

Try it a few times with different i. (Don't turn anything in). Hopefully, it is clear that the fading signal is highly correlated over time.

The real-world problem this causes in secret key generation is that correlation makes a bad secret. If we were to use an encoding scheme to convert each sample into a bit (one or zero) subsequent bits would be likely to be the same. They would be predictable -- an eavesdropper who guessed one bit correctly would be able to guess other subsequent bits. The decorrelation transform presented here produces samples which have zero covariance with other samples.

Our scheme looks like this:

In past assignments, we've taken $X_i$ directly and quantized it to one bit each. In this assignment, we introduce the above transform on vectors of $\mathbf{X}$ prior to quantization.

We will take interpa (or interpb) and take from it a vector of length N=50. Then, we'll transform that data vector using a matrix we design in this assignment. Then, we'll use the tranformed vector's components to generate the secret key bits.

1. Compute the mean vector and covariance matrix

The mean vector and covariance matrix are calculated as
$$ \mu_\mathbf{X} = \frac{1}{K} \sum_{i=1}^K \mathbf{X}_i $$
$$ C_\mathbf{X} = \frac{1}{K-1} \sum_{i=1}^K [\mathbf{X}_i-\mu_\mathbf{X}] [\mathbf{X}_i-\mu_\mathbf{X}]^T $$
where $\mathbf{X}_i$ is the ith measured realization of $\mathbf{X}$, and $K$ is the total number of realizations. Here, a "realization" $\mathbf{X}_i$ just is the ith possible vector of length N which is taken from interpa (or interpb). So the same as before -- let $\mathbf{X}_i$ be equal to interpa(i:i+49) in Matlab. Note that two subsequent realizations will overlap, that's fine.

In Matlab, $\mu_\mathbf{X}$ is calculated as

len = length(interpa);
mu = zeros(50,1);
K = len - 49;
for i=1:K,
mu = mu + interpa(i:i+49)';
mu = mu ./ K;

Then $C_\mathbf{X}$ is calculated as

C_X = zeros(50);
for i=1:K,
C_X = C_X + (interpa(i:i+49)' - mu)*(interpa(i:i+49)' - mu)';
C_X = C_X ./ (K-1);

Compute C_X and plot it (Turn in this plot). You can plot a matrix using imagesc:


2. Compute the eigenfunctions of your measured RSS data.

Compute the SVD of the covariance matrix.

[U, Lambda, V] = svd(C_X)

The ith column of U is the ith eigenvector, and Lambda(i,i) is its eigenvalue. By default, Matlab sorts the columns of U so that the eigenvalues are in decreasing order. Plot the nine highest-eigenvalued eigenvectors by calling my function plotNineColumns.m with U as the argument. Turn in this plot.

3. Transform the RSS data vectors using the KLT

Your new vectors $\mathbf{Y}$ are computed as $\mathbf{Y} = U^T \mathbf{X}$. What is the covariance matrix of $\mathbf{Y}$, that is, $C_\mathbf{Y}$? Turn in a plot of the new covariance matrix $C_\mathbf{Y}$.

4. Compare a few components at nodes a and b.

Assume that U is known at both node a and node b, and they both compute the KLT of their data at a particular time i:

decorra = U' * interpa(i:i+49)';
decorrb = U' * interpb(i:i+49)';
disp{[decorra, decorrb])

Pick a few different times i and try the above procedure to see what $\mathbf{Y}$ would be calculated at nodes a and b.

Pay attention to how close the values are in different components (rows). We must decide which components are most reliably similar at nodes a and b, and should be used in bit generation. In a real secret key generation system, we perform this KLT and then pick the components with high correlation between nodes a and b. Those are the only components which are then coded with bits. Other, unreliable, components are not encoded into bits.

Turn in: Describe which components are most reliably similar (correlated) at nodes a and b. You can probably see from several different values of i which components are best. This does not need to be quantitative, but if you feel necessary, you can compute the correlation coefficient as you did in assignment 2, for each component. This is essentially an answer to a system design question, of what components would be included in the secret key generation system.


Submit your results as described above.

If your last (family) name begins with A-N, please complete the "Appl. Assignment 4 Quiz" on WebCT now.