How to evaluate dimension reduction from n-space to d-space?

Question

I'm performing dimension reduction on some data sets and would like to evaluate how has a particular dimension reduction algorithm performed in terms of how much data is lost. If we are given 1000 dimensions, and we reduce it to 2, then how effective is it? I'm trying to figure till what should you do DR such that your results don't go bad? Is there a metric which does this? I'm using PCA.

Edit:

Can I use some distance metric to do the evaulation?

Answer 1

Let's say you have principal components $v_1$ through $v_n$. Any vector in $n$-space can be translated into the basis of those principal vectors:

$x = x_1v_1 + \dots + x_nv_n $

When you reduce a vector in $n$-space to $d$-space, you are projecting onto the first $d$ principal components and zero-ing out all the rest:

$\hat x = x_1v_1 + \dots + x_dv_d + 0v_{d+1} + \dots + 0v_n$

So if you want to know the error, that would be all the zeroed out parts. I suspect the easiest way to do this is:

given $x$ and precomputed principal components $v_1 \dots v_n$.

$x_1 \dots x_d := $ projection of $x$ onto first $d$ principal components

$\hat x := x_1v_1 + \dots + x_dv_d $

$\|x-\hat x\|^2$ is the squared error of dimensionality reduction

Answer 2

In fact their is a deep lemma about dimension reduction, the Johnson-Lindenstrauss lemma, which asserts that given a set $A = \{a_1,\dots,a_n \}$, a map $f : \mathbb{R}^D \rightarrow \mathbb{R}^d$ is an $\epsilon$-isometry if for every pair $a,a^{'} \in A$ we have $$ ( 1 - \epsilon) || a - a^{'} ||^2 \leq || f(a) - f(a^{'}) ||^2 \leq ( 1 + \epsilon) || a - a^{'} ||^2 $$ and the Johnson-Lindenstrauss lemma asserts that there exists a linear $\epsilon$-isometry whenever $d \geq k \epsilon^{-2} \log ( n )$ where $k$ is an absolute constant. You can realize such a map with an i.i.d. gaussian entries matrix.

Edit : oh sorry i wasnt clear enough about how i think it relates to the question (maybe i am wrong) for dimension reduction (at least in a context where only the distance between points is important like clustering for example) i would calculate how much my mapping (PCA here i think) is changing the distance between points and compare the upper bound of that distorsion to the bound given by JL for example if you go to dimension 2 i would compare it to $\sqrt(\frac{\log(n)}{2})$ if i have n points (of course here 2 is much too low to get a non trivial bound). It gives me a way to assert that my algorithm has the best behavior possible (even if usually i guess you think the other way around setting first an $\epsilon$ and getting a $d$). Another thing the result gives me is a way to construct the best algorithm for dimension reduction which is to use a matrix whose entries are normal random variables as my "projection".