Chapter 8 Basis and Change of Basis

When we think of coordinate pairs, or coordinate triplets, we tend to think of them as points on a grid where each axis represents one of the coordinate directions:

Figure 8.1: The Coordinate Plane

We may not have previously formalized it, but even in this elementary setting, we are considering these points (vectors) as linear combinations of the elementary basis vectors $${\mathbf{\text{e}}}_1=\left(\begin{array}{c}1\\ 0\end{array}\right)\text{ and }{\mathbf{\text{e}}}_2=\left(\begin{array}{c}0\\ 1\end{array}\right).$$ For example, the point $(2,3)$ can be written as $$\begin{array}{}\text{(8.1)}& \left(\begin{array}{c}2\\ 3\end{array}\right)=2\left(\begin{array}{c}1\\ 0\end{array}\right)+3\left(\begin{array}{c}0\\ 1\end{array}\right)=2{\mathbf{\text{e}}}_1+3{\mathbf{\text{e}}}_2.\end{array}$$

We consider the coefficients (the scalars 2 and 3) in this linear combination as coordinates in the basis ${\mathcal{B}}_1=\{{\mathbf{\text{e}}}_1,{\mathbf{\text{e}}}_2\}$. The coordinates, in essence, tell us how much “information” from the vector/point $(2,3)$ lies along each basis direction: to create this point, we must travel 2 units along the direction of ${\mathbf{\text{e}}}_1$ and then 3 units along the direction of ${\mathbf{\text{e}}}_2$.

We can also view Equation (8.1) as a way to separate the vector $(2,3)$ into orthogonal components. Each component is an orthogonal projection of the vector onto the span of the corresponding basis vector. The orthogonal projection of vector $\mathbf{a}$ onto the span another vector $\mathbf{\text{v}}$ is simply the closest point to $\mathbf{a}$ contained on the span($\mathbf{\text{v}}$), found by projecting $\mathbf{a}$ onto $\mathbf{\text{v}}$ at a ${90}^{\circ }$ angle. Figure 8.2 shows this explicitly for $\mathbf{a}=(2,3)$.

Figure 8.2: Orthogonal Projections onto basis vectors

Definition 8.1 (Elementary Basis) For any vector $\mathbf{\text{a}}=(a_1,a_2,\dots ,a_n)$, the basis $\mathcal{B}=\{{\mathbf{\text{e}}}_1,{\mathbf{\text{e}}}_2,\dots ,{\mathbf{\text{e}}}_n\}$ (recall ${\mathbf{\text{e}}}_i$ is the $i^{th}$ column of the identity matrix ${\mathbf{I}}_n$) is the elementary basis and $\mathbf{\text{a}}$ can be written in this basis using the coordinates $a_1,a_2,\dots ,a_n$ as follows: $$\mathbf{\text{a}}=a_1{\mathbf{\text{e}}}_1+a_2{\mathbf{\text{e}}}_2+\dots a_n{\mathbf{\text{e}}}_n.$$

The elementary basis ${\mathcal{B}}_1$ is convenient for many reasons, one being its orthonormality: $$\begin{array}{rcl}{\mathbf{\text{e}}}_1^T{\mathbf{\text{e}}}_1& =& {\mathbf{\text{e}}}_2^T{\mathbf{\text{e}}}_2=1\\ {\mathbf{\text{e}}}_1^T{\mathbf{\text{e}}}_2& =& {\mathbf{\text{e}}}_2^T{\mathbf{\text{e}}}_1=0\end{array}$$

However, there are many (infinitely many, in fact) ways to represent the data points on different axes. If I wanted to view this data in a different way, I could use a different basis. Let’s consider, for example, the following orthonormal basis, drawn in green over the original grid in Figure 8.3: $${\mathcal{B}}_2=\{{\mathbf{\text{v}}}_1,{\mathbf{\text{v}}}_2\}=\{\frac{\sqrt{2}}{2}\left(\begin{array}{c}1\\ 1\end{array}\right),\frac{\sqrt{2}}{2}\left(\begin{array}{c}1\\ -1\end{array}\right)\}$$

Figure 8.3: New basis vectors, ${\mathbf{\text{v}}}_1$ and ${\mathbf{\text{v}}}_2$, shown on original plane

The scalar multipliers $\frac{\sqrt{2}}{2}$ are simply normalizing factors so that the basis vectors have unit length. You can convince yourself that this is an orthonormal basis by confirming that $$\begin{array}{rcl}{\mathbf{\text{v}}}_1^T{\mathbf{\text{v}}}_1& =& {\mathbf{\text{v}}}_2^T{\mathbf{\text{v}}}_2=1\\ {\mathbf{\text{v}}}_1^T{\mathbf{\text{v}}}_2& =& {\mathbf{\text{v}}}_2^T{\mathbf{\text{v}}}_1=0\end{array}$$

If we want to change the basis from the elementary ${\mathcal{B}}_1$ to the new green basis vectors in ${\mathcal{B}}_2$, we need to determine a new set of coordinates that direct us to the point using the green basis vectors as a frame of reference. In other words we need to determine $({\alpha }_1,{\alpha }_2)$ such that travelling ${\alpha }_1$ units along the direction ${\mathbf{\text{v}}}_1$ and then ${\alpha }_2$ units along the direction ${\mathbf{\text{v}}}_2$ will lead us to the point in question. For the point $(2,3)$ that means $$\left(\begin{array}{c}2\\ 3\end{array}\right)={\alpha }_1{\mathbf{\text{v}}}_1+{\alpha }_2{\mathbf{\text{v}}}_2={\alpha }_1\left(\begin{array}{c}\frac{\sqrt{2}}{2}\\ \frac{\sqrt{2}}{2}\end{array}\right)+{\alpha }_2\left(\begin{array}{c}\frac{\sqrt{2}}{2}\\ -\frac{\sqrt{2}}{2}\end{array}\right).$$

This is merely a system of equations $\mathbf{V}\mathbf{a}=\mathbf{\text{b}}$: $$\frac{\sqrt{2}}{2}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)\left(\begin{array}{c}{\alpha }_1\\ {\alpha }_2\end{array}\right)=\left(\begin{array}{c}2\\ 3\end{array}\right)$$

The $2\times 2$ matrix $\mathbf{\text{V}}$ on the left-hand side has linearly independent columns and thus has an inverse. In fact, $\mathbf{\text{V}}$ is an orthonormal matrix which means its inverse is its transpose. Multiplying both sides of the equation by ${\mathbf{\text{V}}}^{-1}={\mathbf{\text{V}}}^T$ yields the solution $$\mathbf{a}=\left(\begin{array}{c}{\alpha }_1\\ {\alpha }_2\end{array}\right)={\mathbf{\text{V}}}^T\mathbf{\text{b}}=\left(\begin{array}{c}\frac{5\sqrt{2}}{2}\\ -\frac{\sqrt{2}}{2}\end{array}\right)$$

This result tells us that in order to reach the red point (formerly known as (2,3) in our previous basis), we should travel $\frac{5\sqrt{2}}{2}$ units along the direction of ${\mathbf{\text{v}}}_1$ and then $-\frac{\sqrt{2}}{2}$ units along the direction ${\mathbf{\text{v}}}_2$ (Note that ${\mathbf{\text{v}}}_2$ points toward the southeast corner and we want to move northwest, hence the coordinate is negative). Another way (a more mathematical way) to say this is that the length of the orthogonal projection of $\mathbf{a}$ onto the span of ${\mathbf{\text{v}}}_1$ is $\frac{5\sqrt{2}}{2}$, and the length of the orthogonal projection of $\mathbf{a}$ onto the span of ${\mathbf{\text{v}}}_2$ is $-\frac{\sqrt{2}}{2}$. While it may seem that these are difficult distances to plot, they work out quite well if we examine our drawing in Figure 8.3, because the diagonal of each square is $\sqrt{2}$.

In the same fashion, we can re-write all 3 of the red points on our graph in the new basis by solving the same system simultaneously for all the points. Let $\mathbf{\text{B}}$ be a matrix containing the original coordinates of the points and let $\mathbf{\text{A}}$ be a matrix containing the new coordinates: $$\mathbf{\text{B}}=\left(\begin{array}{ccc}-4& 2& 5\\ -2& 3& 2\end{array}\right)\mathbf{\text{A}}=\left(\begin{array}{ccc}{\alpha }_{11}& {\alpha }_{12}& {\alpha }_{13}\\ {\alpha }_{21}& {\alpha }_{22}& {\alpha }_{23}\end{array}\right)$$

Then the new data coordinates on the rotated plane can be found by solving: $$\mathbf{\text{V}}\mathbf{\text{A}}=\mathbf{\text{B}}$$ And thus $$\mathbf{\text{A}}={\mathbf{\text{V}}}^T\mathbf{\text{B}}=\frac{\sqrt{2}}{2}\left(\begin{array}{ccc}-6& 5& 7\\ -2& -1& 3\end{array}\right)$$

Using our new basis vectors, our alternative view of the data is that in Figure 8.4.

Figure 8.4: Points plotted in the new basis, $\mathcal{B}$

In the above example, we changed our basis from the original elementary basis to a new orthogonal basis which provides a different view of the data. All of this amounts to a rotation of the data around the origin. No real information has been lost - the points maintain their distances from each other in nearly every distance metric. Our new variables, ${\mathbf{\text{v}}}_1$ and ${\mathbf{\text{v}}}_2$ are linear combinations of our original variables ${\mathbf{\text{e}}}_1$ and ${\mathbf{\text{e}}}_2$, thus we can transform the data back to its original coordinate system by again solving a linear system (in this example, we’d simply multiply the new coordinates again by $\mathbf{\text{V}}$).

In general, we can change bases using the procedure outlined in Theorem 8.1.

Theorem 8.1 (Changing Bases) Given a matrix of coordinates (in columns), $\mathbf{\text{A}}$, in some basis, ${\mathcal{B}}_1=\{{\mathbf{x}}_1,{\mathbf{x}}_2,\dots ,{\mathbf{x}}_n\}$, we can change the basis to ${\mathcal{B}}_2=\{{\mathbf{\text{v}}}_1,{\mathbf{\text{v}}}_2,\dots ,{\mathbf{\text{v}}}_n\}$ with the new set of coordinates in a matrix $\mathbf{\text{B}}$ by solving the system $$\mathbf{\text{X}}\mathbf{\text{A}}=\mathbf{\text{V}}\mathbf{\text{B}}$$ where $\mathbf{\text{X}}$ and $\mathbf{\text{V}}$ are matrices containing (as columns) the basis vectors from ${\mathcal{B}}_1$ and ${\mathcal{B}}_2$ respectively.

Note that when our original basis is the elementary basis, $\mathbf{\text{X}}=\mathbf{I}$, our system reduces to $$\mathbf{\text{A}}=\mathbf{\text{V}}\mathbf{\text{B}}.$$

When our new basis vectors are orthonormal, the solution to this system is simply $$\mathbf{\text{B}}={\mathbf{\text{V}}}^T\mathbf{\text{A}}.$$

Definition 8.2 (Basis) A basis for an arbitrary vector space $\mathcal{V}$ is any set of linearly independent vectors $\{{\mathcal{B}}_1,\dots ,{\mathcal{B}}_r\}$ such that $$span(\{{\mathcal{B}}_1,\dots ,{\mathcal{B}}_r\})=\mathbf{V}.$$ $r$ is said to be the dimension of the vector space ${\mathbb{R}}^n$.

A basis for the vector space ${\mathbb{R}}^n$ is then any set of $n$ linearly independent vectors in ${\mathbb{R}}^n$; $n$ is said to be the dimension of the vector space ${\mathbb{R}}^n$. When the basis vectors are orthonormal (as in our prior examples), the set is called an orthonormal basis.

The preceding discussion dealt entirely with bases for ${\mathbb{R}}^n$ (our example was for points in ${\mathbb{R}}^2$). However, we will need to consider bases for subspaces of ${\mathbb{R}}^n$. Recall that the span of two linearly independent vectors in ${\mathbb{R}}^3$ is a plane. This plane is a 2-dimensional subspace of ${\mathbb{R}}^3$. Its dimension is 2 because 2 basis vectors are required to represent this space. However, not all points from ${\mathbb{R}}^3$ can be written in this basis - only those points which exist on the plane. In Chapter 10 we discuss how to proceed in a situation where the point we’d like to represent does not actually belong to the subspace we are interested in. This is the foundation for Least Squares.

8.1 Vector Space Models

The knowledge of coordinates and bases in data science allows us to explore the data using a vector space model. In a vector space model, the objects/observations of interest are considered vectors in a vector space and then often the dimensionality of that vector space is reduced in some way - yielding a new set of basis vectors (a smaller set) and coordinates of the data along those new basis vectors. Let’s take a look at such a model using some text data as an example. The finer details of the text-mining process can be found in Chapter 16. Figure 8.5 shows 4 short “documents.” The words highlighted in red are the words that appear in at least two documents. We’ll use those red-highlighted words as the variables in our analysis, and the documents as the observations.

Figure 8.5: Four Short Documents

We’ll create a matrix, called a term-document matrix, where the $(i,j{)}^{th}$ entry is the number of times that term $i$ appeared in document $j$. Why put our documents/observations along the columns? Simply because we’re exposing the linear combinations involved in our interpretation and we want that intuition to come easily from the animation in Figure 2.7, which might be helpful to revisit at this time. Everything works the same if we put the documents on the columns, the translation is simply a linear combination of rows, which is too wide for print.

$$\begin{array}{cc}& \begin{array}{cccc}do{c}_1& do{c}_2& do{c}_3& do{c}_4\end{array}\\ \begin{array}{c}\text{cat}\\ \text{dog}\\ \text{tired}\\ \text{injured}\\ \text{ankle}\\ \text{sprained}\end{array}& \left(\begin{array}{cccc}1& 2& 0& 0\\ 2& 3& 0& 0\\ 0& 1& 0& 1\\ 0& 0& 1& 1\\ 0& 0& 1& 1\\ 0& 0& 1& 1\end{array}\right)\end{array}$$

These documents, upon formulation of the term-document matrix above, live in the 6-dimensional term space. We could expand each document in a coordinate-basis representation where each of the elementary axes represents a single term, for instance:

$$do{c}_1=1\begin{array}{c}dog\\ \left(\begin{array}{c}1\\ 0\\ 0\\ 0\\ 0\\ 0\end{array}\right)\end{array}+2\begin{array}{c}cat\\ \left(\begin{array}{c}0\\ 1\\ 0\\ 0\\ 0\\ 0\end{array}\right)\end{array}$$

Now, we will change the basis and create new basis vectors that attempt to approximate this data in only 2 dimensions using a matrix factorization. Matrix factorizations are extremely powerful for data analysis, but we are not presently concerned with how they are created or chosen to solve a problem. Our goal in this section is merely to interpret the output and catch a glimpse of their utility. Below we examine one such matrix factorization, which was created using a Nonnegative Matrix Factorization (NMF) algorithm [55].

$$\begin{array}{cc}& \begin{array}{cc}facto{r}_1& facto{r}_2\end{array}\\ \begin{array}{c}\text{cat}\\ \text{dog}\\ \text{tired}\\ \text{injured}\\ \text{ankle}\\ \text{sprained}\end{array}& \left(\begin{array}{cc}1.0& 0\\ 1.6& 0\\ 0.4& 0.4\\ 0& 0.8\\ 0& 0.8\\ 0& 0.8\end{array}\right)\end{array}\begin{array}{c}\begin{array}{cccc}do{c}_1& do{c}_2& do{c}_3& do{c}_4\end{array}\\ \left(\begin{array}{cccc}1.0& 1.7& 0& 0\\ 0& 0.1& 0.9& 1.1\end{array}\right)\end{array}$$

The “factors” in the left matrix live in the term space. The factors can be considered as linear combinations of our original term vectors:

$$\begin{array}{rcl}facto{r}_1& =& 1\begin{array}{c}dog\\ \left(\begin{array}{c}1\\ 0\\ 0\\ 0\\ 0\\ 0\end{array}\right)\end{array}+1.6\begin{array}{c}cat\\ \left(\begin{array}{c}0\\ 1\\ 0\\ 0\\ 0\\ 0\end{array}\right)\end{array}+0.4\begin{array}{c}tired\\ \left(\begin{array}{c}0\\ 0\\ 1\\ 0\\ 0\\ 0\end{array}\right)\end{array}+0\begin{array}{c}injured\\ \left(\begin{array}{c}0\\ 0\\ 1\\ 0\\ 0\\ 0\end{array}\right)\end{array}+0\begin{array}{c}ankle\\ \left(\begin{array}{c}0\\ 0\\ 1\\ 0\\ 0\\ 0\end{array}\right)\end{array}+0\begin{array}{c}sprained\\ \left(\begin{array}{c}0\\ 0\\ 1\\ 0\\ 0\\ 0\end{array}\right)\end{array}\\ facto{r}_2& =& 0\begin{array}{c}dog\\ \left(\begin{array}{c}1\\ 0\\ 0\\ 0\\ 0\\ 0\end{array}\right)\end{array}+0\begin{array}{c}cat\\ \left(\begin{array}{c}0\\ 1\\ 0\\ 0\\ 0\\ 0\end{array}\right)\end{array}+0.4\begin{array}{c}tired\\ \left(\begin{array}{c}0\\ 0\\ 1\\ 0\\ 0\\ 0\end{array}\right)\end{array}+0.8\begin{array}{c}injured\\ \left(\begin{array}{c}0\\ 0\\ 1\\ 0\\ 0\\ 0\end{array}\right)\end{array}+0.8\begin{array}{c}ankle\\ \left(\begin{array}{c}0\\ 0\\ 1\\ 0\\ 0\\ 0\end{array}\right)\end{array}+0.8\begin{array}{c}sprained\\ \left(\begin{array}{c}0\\ 0\\ 1\\ 0\\ 0\\ 0\end{array}\right)\end{array}\end{array}$$

Thus, these “factors” can be thought of almost like documents: they are merely a collection of terms. In particular, it seems as though $facto{r}_1$ is a generic document about pets and $facto{r}_2$ is a generic document about injuries. Thus we might choose call these factors “topics” and give them names based upon the interpretation of their loadings, which are the coefficients in the above coordinate-basis expansion.

Furthermore, the “scores” in the right matrix provide information about how each document relates to each of these topics:

$$\begin{array}{rcl}do{c}_2& =& 1.7facto{r}_1+0.1facto{r}_2\\ do{c}_4& =& 0.0facto{r}_1+1.1facto{r}_2\end{array}$$

The above representation allows us to conclude that document 2 is mostly about factor/topic 1 (“pets”) and document 4 is mostly about factor/topic 2 (“injuries”) just by identifying the largest coordinate for each document.

A matrix factorization gives us information about both the rows and columns of the matrix of interest. Here, we saw both the terms and documents collected into two topics according to the loadings (left matrix) and the scores (right matrix).

We strongly encourage the reader to convince themselves of our conclusions and to replicate this analysis by completing the related question in the exercises.

8.2 Exercises

1. What are the coordinates of the vector $\mathbf{x}=\left(\begin{array}{c}4\\ 3\end{array}\right)$ in the basis $\{\left(\begin{array}{c}-1\\ -1\end{array}\right),\left(\begin{array}{c}1\\ -1\end{array}\right)\}$? Draw a picture to make sure your answer lines up with intuition.
2. In the following picture what would be the signs (+/-) of the coordinates of the green point in the basis $\{{\mathbf{\text{v}}}_1,{\mathbf{\text{v}}}_2\}$? Pick another point at random and answer the same question for that point.
3. Write the orthonormal basis vectors from exercise 1 as linear combinations of the original elementary basis vectors.

4. What is the length of the orthogonal projection of ${\mathbf{\text{a}}}_1$ onto ${\mathbf{\text{v}}}_1$?

5. Interpret the following Nonnegative Factor Output for a term-document matrix of a small collection of text documents, answering the following questions:
   1. What meaning (theme/topic) would you give to each of the three factors?
   2. What is the dominant factor (theme/topic) for each document?
   3. What is the loading of the word baseball on Factor 2?
   4. What is the coordinate/score of document 5 along Factor 3?

   $$\begin{array}{rc}& \begin{array}{ccc}Factor1& Factor2& Factor3\end{array}\\ \begin{array}{c}baseball\\ pitcher\\ mound\\ player\\ coach\\ soccer\\ world\\ fifa\\ cup\\ canada\\ womens\\ USA\\ olympics\\ medal\\ gold\\ phelps\end{array}& \left(\begin{array}{ccc}1.9& 0& 0\\ 2.6& 0& 0.1\\ 1.1& 0.0& 0\\ 1.5& 0.1& 0\\ 1.3& 0.8& 0.8\\ 0& 2.2& 0\\ 0.1& 1.7& 0.5\\ 0& 2.3& 0\\ 0& 1.6& 0.1\\ 0.2& 1.9& 0.5\\ 0& 1.8& 0.7\\ 0.1& 2.0& 2.3\\ 0& 0.2& 2.8\\ 0& 0.1& 2.2\\ 0& 0& 1.8\\ 0& 0& 1.6\end{array}\right)\end{array}\begin{array}{c}\begin{array}{ccccc}doc1& doc2& doc3& doc4& doc5\end{array}\\ \left(\begin{array}{ccccc}3.2& 2.7& 0& 0.2& 0.1\\ 0.1& 0.1& 2.5& 2.1& 0.3\\ 0.2& 0& 0.2& 0.1& 2.9\end{array}\right)\end{array}$$

List of Key Terms

• basis vectors
• orthonormal basis
• coordinates in different bases

References

[55]

D. D. Lee and H. S. Seung, “Learning the parts of objects by non-negative matrix factorization,” Nature, vol. 401, no. 6755, pp. 788–91, 1999.