• Interpretation of covariance matrix
• Eigenvalue decomposition
• Positive-definite matrices, ellipsoids
• Least-squares estimation

33.1. Interpretation of covariance matrix

We are given [latex]m[/latex] of points [latex]x_1, \cdots, x_m[/latex] in [latex]\mathbb{R}^n[/latex]. We assume that the average and variance of the data projected along a given direction do 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 [latex]w \in \mathbb{R}^n[/latex] ([latex]||w||_2 =1[/latex]), we associate the line with direction [latex]w[/latex] passing through the origin, [latex]\mathcal{L}(w)=\{tw: t\in \mathbb{R}\}[/latex]. We then consider the projection of the points [latex]x_i[/latex], [latex]i = 1, \cdots, m[/latex], on the line [latex]\mathcal{L}(w)[/latex], and look at the associated coordinates of the points on the line. These projected values are given by

[latex]\begin{align*} t_i(w) & :=\arg\min\limits_t ||tw-x_i||_2, \quad i = 1, \cdots, m. \end{align*}[/latex]

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

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

1. Show that [latex]t_i(w) = x_i^Tw, \quad i = 1,\cdots, m.[/latex]

2. Show that the sample average of the data points

[latex]\begin{align*} \hat{x} & :=\frac{1}{m} \sum\limits_{i=1}^m x_i, \end{align*}[/latex]

is zero.

3. Show that the sample covariance matrix of the data points,

[latex]\begin{align*} \Sigma & := \frac{1}{m} \sum_{i=1}^m (x_i - \hat{x})(x_i -\hat{x})^T, \end{align*}[/latex]

is of the form [latex]\sigma^2 \cdot I[/latex], where [latex]I[/latex] is the identity matrix of order [latex]n[/latex]. (Hint: the largest eigenvalue [latex]\lambda_{\max}[/latex] of the matrix [latex]\sum[/latex] can be written as: [latex]\lambda_{\max} = \max_w \{w^T\sum w: w^Tw=1\}[/latex], and a similar expression holds for the smallest eigenvalue.)

33.2. Eigenvalue decomposition

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

1. Show that [latex]p+q[/latex] and [latex]p-q[/latex] are eigenvectors of [latex]A[/latex], and determine the corresponding eigenvalues.

2. Determine the nullspace and rank of [latex]A[/latex].

3. Find an eigenvalue decomposition of [latex]A[/latex]. Hint: use the previous two parts.

4. What is the answer to the previous part if [latex]p,q[/latex] are not normalized?

33.3. Positive-definite matrices, ellipsoids

1. 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 [latex]x^TAx \leq 1[/latex].

[latex]\begin{align*} A_1 & = \left(\begin{array}{ll} 2 & 1 \\ 1 & 2 \end{array}\right) \\ \vspace{-20pt} A_2 & = \left(\begin{array}{cc} 1 & -1 \\ -1 & 1 \end{array}\right) \\ \vspace{-20pt} A_3 & = \left(\begin{array}{cc} -1 & 0 \\ 0 & -1 \end{array}\right) \end{align*}[/latex]

2. Show that if a square, [latex]n \times n[/latex] symmetric matrix [latex]A[/latex] is positive semi-definite, then for every [latex]n \times k[/latex] matrix [latex]B[/latex], [latex]B^TAB[/latex] is also positive semi-definite. (Here, [latex]k[/latex] is an arbitrary integer.)

3. Drawing an ellipsoid. How would you efficiently draw an ellipsoid in [latex]\mathbb{R}^2[/latex], if the ellipsoid is described by a quadratic inequality of the form

[latex]\begin{align*} {\bf E} & = {x^TAx+2b^Tx+c \leq 0}, \end{align*}[/latex]

where [latex]A[/latex] is [latex]2 \times 2[/latex] and symmetric, positive-definite, [latex]c \in \mathbb{R}^2[/latex], and [latex]b \in \mathbb{R}[/latex]? Describe your algorithm as precisely as possible. (You are welcome to provide code.) Draw the ellipsoid

[latex]\begin{align*} {\bf E} & = {4x_1^2 +2x_2^2 +3x_1x_2+4x_1+5x_2+3\leq 1}. \end{align*}[/latex]

33.4. Least-squares estimation

BLUE property of least-squares. Consider a system of linear equations in vector [latex]x[/latex]

[latex]\begin{align*} Ax & =y+v, \end{align*}[/latex]

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

[latex]\begin{align*} \min\limits_x ||Ax-y||_2 \end{align*}[/latex]

The solution is, when [latex]A[/latex] is full column rank, of the form [latex]x^* = B_{ls}y[/latex], with [latex]B_{ls} = (A^TA)^{-1} A^T[/latex]. We note that [latex]B_{ls}A=I[/latex], which means that the LS estimator is unbiased. In this exercise, we show that [latex]B_{ls}[/latex] 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 [latex]x - \hat{x} = -Bv[/latex].

2. This motivates us to minimize the size of [latex]B[/latex], say using the Frobenius norm:

[latex]\begin{align*} \min\limits_B ||B||_F: BA=I. \end{align*}[/latex]

Show that [latex]B_{ls}[/latex] is the best unbiased linear estimator (BLUE), in the sense that it solves the above problem.

Hint: Show that any unbiased linear estimator [latex]B[/latex] can be written as [latex]B= B_{ls} +Z[/latex] with [latex]ZB_{ls}^T = 0[/latex], and that [latex]BB^T = ZZ^T + B_{ls}B_{ls}^T[/latex]  is positive semi-definite.