Regarding orthonormality vs. Spanning (or my slightly botched up example about slanting axes in 2-D)

[Subbarao Kambhampati <rao@asu.edu>]

Folks:

 If my discussion and retraction of the 2-D example meant to convey the importance of orthonormal dimensions left you confused, here is a more elaborate answer (which might require a bit more understanding of linear algebra). 

========
We say that a space is spanned by a set of vectors v1...vn (called "basis vectors"; normally you consider that v1..vn are unit vectors) if every other vector in that space can be written as some linear combination of these vectors.

I.e. for every vector u in the space

 u = a1*v1+a2*v2....+an*vn   for some arbitrary real numbers (a1, a2... an)

In this case, the tuple (a1, a2,..an) is considered the *coordinates* of u in the space. 

Note that this definition does not say anything about the inter-relation between the basis vectors v1... vn . In particular, nothing in the definition says that 
v1...vn must all be pairwise orthogonal (independent). [ *By the way, an easy way to check if two vectors are orthogonal is to take their dot product and see if it is zero. Because of this, if 
you make a matrix M which has as its columns the n orthogonal vectors, then both M'*M and M*M' will be  diagonal matrixces. If the original vectors are all unit vectors, then the result is the 
Identity matrix..]. 


The *rank* of a space is the minimum number of vectors needed to span that space. 

The whole issue of dimensionality reduction is that the space I want to span is really a (linear) manifold in a higher dimensional space, and thus doesn't really need all those dimensions.
(Suppose your entire data/documents fall on a plane--oriented in some funny way--in the 3-D space; then although all the datapoints on the plane have three cordinates, they really don't
need all three; they only need 2! If all your data falls on a line in 3 D, then you only need 1 cooridnate..)

Thus the worry is that I might give you a set of basis vectors that do span the space, but are more in number than  the minimum needed. 

If this happens, then it must be the case that some of the basis vectors are themselves writable as the linear combination of the other basis vectors (and are thus
are essentially redundant). For example, suppose all our data is on the plane  3x+4y+2z=7 (where the vector 3,4,2 is orthogonal to the plane 
see http://local.wasp.uwa.edu.au/~pbourke/geometry/planeeq/ ), then knowing X and Y coordinates of a point allows us to figure out its z coordinate...


=========

Now, coming back to orthonormality, it is easy to show that  *IF*  we are starting with more basis vectors than is required  by the rank of the space, then the basis vectors
cannot all be pairwise independent (at least some of them should be linearly dependent on others, which means their dot product with those basis vectors will be non-zero).

The converse, however, is not true--it is possible to span a space with a minimum number of non-orthogonal vectors. 
In particular, you can span 2-d space with *any* two vectors in that space whose dot product is not 1. 

And if you span the space with minimum number of non-orthogonal vectors, then none of them can be written as a linear combination of the others (and thus you cannot guess any
coordinate even when given all other coordinates)

====What does this have to do with the class 2-D example=======

What I was purportedly trying to show was that if your basis vectors are orthogonal, then you cannot guess the nth coordinate even if you are given all other coordinates.
This  is said assuming implicitly that the basis vectors (in addition to being orthogonal) also span the space you are interested in.

Conversely, if your basis vectors are not minimal--i.e., they are more than the number needed to span your space, then you can guess some coordiante given other coordinates. 

==

Let me know/post on blog if you have any questions.

regards
Rao