Index (Exam Spring 2001, Question 3)

Usage notes

Assume we are given n data points x₁,...,x_n with x_k=(x_1k,...,x_mk), we want to compute an index for each data point. For our purpose, an index is a function in x, i. e.

A good index is one which spreads the data points as much as possible. That is, if we make a histogram of the values of index(x) for every point x, a good index will look like

while a bad index will cluster around its center

let's define the optimal index as the index which maximizes the variance of

with respect to all data points for

Let X be the random variable taking the value

for a randomly chosen k. Then the problem can be expressed as follows

1: optimal

___________________ )

The variance of X can be expressed in terms of the covariance matrix C of the vectors x₁,...,x_n.
To do this compute the variance of X and write it as an expression in

and x_i.

___________________ )

Let e_i, i=1..k be the eigenvectors of C,

, i=1..k the respective eigenvalues and

the eigenvalue-decomposition of C where U is an orthonormal matrix and

the diagonal matrix.

Given

write

, or an expression in

and

___________________

where

We proved that the largest variance is obtained with an

, which is the ___________________ with the ___________________ eigenvalue of the covariance matrix C.

Home

Feedback to quiz developers, problem reports...please use it!!!

Name:
	Restore previous session, if applicable Start blank quiz
Note:	If you wish to ask for a hint or a solution, or if you want your answers checked, you have to log in. Your answers, or the fact that you asked for a hint or solution, may be recorded.