Exercises

Interpretation of covariance matrix

We are given of points x_1,ldots,x_m in $mathbf{R}^n$ . We assume that the average and variance of the data projected along a given direction does not change with the direction. In this exercise we will show that the sample covariance matrix is then proportional to the identity.

We formalize this as follows. To a given normalized direction $w in mathbf{R}^n$ ( |w|_2 = 1 ), we associate the line with direction passing through the origin, {cal L}(w) = { t w ::: t in mathbf{R}} . We then consider the projection of the points x_i , i=1,ldots,m , on the line , and look at the associated coordinates of the points on the line. These projected values are given by

t_i(w):= argdisplaystylemin_t : |tw-x_i|_2, ;; i=1,ldots,m.

We assume that for any , the sample average hat{t}(w) of the projected values t_i(w) , i=1,ldots,m , and their sample variance sigma^2(w) , are both constant, independent of the direction (wih |w|_2 = 1 ). Denote by hat{t} and sigma^2 the (constant) sample average and variance.

Justify your answer to the following as carefully as you can.

Show that , .
Show that the sample average of the data points,

$hat{x} := frac{1}{m}sum_{i=1}^m x_i,$

is zero.

Show that the sample covariance matrix of the data points,

$Sigma := frac{1}{m}sum_{i=1}^m (x_i - hat{x})(x_i - hat{x})^T,$

is of the form sigma^2 cdot I , where is the identity matrix of order . (Hint: the largest eigenvalue $lambda_{rm max}$ of the matrix Sigma can be written as: $lambda_{rm max}= max_w :{ w^TSigma w ::: w^Tw = 1 }$ , and a similar expression holds for the smallest eigenvalue.)

Eigenvalue decomposition

Let $p,q in mathbf{R}^n$ be two linearly independent vectors, with unit norm ( |p|_2 = |q|_2 = 1 ). Define the symmetric matrix A:=pq^T+qp^T . In your derivations, it may be useful to use the notation c := p^Tq .

Show that and are eigenvectors of , and determine the corresponding eigenvalues.
Determine the nullspace and rank of .
Find an eigenvalue decomposition of . Hint: use the previous two parts.
What is the answer to the previous part if are not normalized?

Positive-definite matrices, ellipsoids

In this problem we examine the geometrical interpretation of the positive definiteness of a matrix. For each of the following cases determine the shape of the region generated by the constraint $x^{T}Ax leq 1$ .
1. .
2. .
3. .
Show that if a square, symmetric matrix is positive semi-definite, then for every matrix , is also positive semi-definite. (Here, is an arbitrary integer.)
Drawing an ellipsoid. How would you efficiently draw an ellipsoid in $mathbf{R}^2$ , if the ellipsoid is described by a quadratic inequality of the form

$mathbf{E} = left{ x^TAx+2b^Tx+c le 0 right},$

where is 2 times 2 and symmetric, positive-definite, $c in mathbf{R}^2$ , and b in mathbf{R} ? Describe your algorithm as precisely as possible. (You are welcome to provide a matlab code.) Draw the ellipsoid

$mathbf{E} = left{ 4x_1^2 + 2 x_2^2 + 3x_1x_2 + 4 x_1 + 5 x_2 + 3 le 1 right}.$

Least-squares estimation

BLUE property of least-squares. Consider a system of linear equations in vector

where is a noise vector, and the input is $A in mathbf{R}^{m times n}$ , a full rank, tall matrix ( m ge n ), and $y in mathbf{R}^m$ . We do not know anything about , except that it is bounded: |v|_2 le alpha , with alphage 0 a measure of the level of noise. Our goal is to provide an estimate hat{x} of via a linear estimator, that is, a function hat{x} = By with a n times m matrix. We restrict attention to unbiased estimators, which are such that hat{x} = x when v=0 . This implies that should be a left inverse of , that is, BA = I_n . A example of linear estimator is obtained by solving the least-squares problem

The solution is, when is full column rank, of the form $x^ast = B_{rm ls}y$ , with $B_{rm ls} = (A^TA)^{-1}A^T$ . We note that $B_{rm ls}A = I$ , which means that the LS estimator is unbiased. In this exercise, we show that $B_{rm ls}$ is the best unbiased linear estimator. (This is often referred to as the BLUE property.)

1. Show that the estimation error of an unbiased linear estimator is .
2. This motivates us to minimize the size of , say using the Frobenius norm:

Show that $B_{rm ls}$ is the best unbiased linear estimator (BLUE), in the sense that it solves the above problem. Hint: Show that any unbiased linear estimator can be written as $B = B_{rm ls}+Z$ with $ZB_{rm ls}^T = 0$ , and that $BB^T = ZZ^T + B_{rm ls}B_{rm ls}^T$ is positive semi-definite.