An Inquiry-Based Introduction to Linear Algebra and Applications

Subsection Application: Search Engines and Semantics

Effective search engines search for more than just words. Language is complex and search engines must deal with the fact that there are often many ways to express a given concept (this is called synonymy, that multiple words can have the same meaning), and that a single word can have multiple meanings (polysemy). As a consequence, a search on a word may provide irrelevant matches (e.g., searching for derivative could provide pages on mathematics or financial securities) or you might search for articles on cats but the paper you really want uses the word felines. A better search engine will not necessarily try to match terms, but instead retrieve information based on concept or intent. Latent Semantic Indexing (LSI) (or Latent Semantic Analysis), developed in the late 1980s, helps search engines determine concept and intent in order to provide more accurate and relevant results. LSI essentially works by providing underlying (latent) relationships between words (semantics) that search engines need to provide context and understanding (indexing). LSI provides a mapping of both words and documents into a lower dimensional “concept” space, and makes the search in this new space. The mapping is provided by the singular value decomposition.

Subsection Introduction

The singular value decomposition (SVD) of a matrix is an important and useful matrix decomposition. Unlike other matrix decompositions, every matrix has a singular value decomposition. The SVD is used in a variety of applications including scientific computing, digital signal processing, image compression, principal component analysis, web searching through latent semantic indexing, and seismology. Recall that the eigenvector decomposition of an \(n \times n\) diagonalizable matrix \(M\) has the form \(P^{-1}MP\text{,}\) where the columns of the matrix \(P\) are \(n\) linearly independent eigenvectors of \(M\) and the diagonal entries of the diagonal matrix \(P^{-1}MP\) are the eigenvalues of \(M\text{.}\) The singular value decomposition does something similar for any matrix of any size. One of the keys to the SVD is that the matrix \(A^{\tr}A\) is symmetric for any matrix \(A\text{.}\)

Subsection The Operator Norm of a Matrix

Before we introduce the Singular Value Decomposition, let us work through some preliminaries to motivate the idea. The first is to provide an answer to the question “How ‘big’ is a matrix?” There are many ways to interpret and answer this question, but a substantial (and useful) answer should involve more than just the dimensions of the matrix. A good measure of the size of a matrix, which we will refer to as the norm of the matrix, should take into account the action of the linear transformation defined by the matrix on vectors. This then will lead to questions about how difficult or easy is it to solve a matrix equation \(A \vx = \vb\text{.}\)

If we want to incorporate the action of a matrix \(A\) into a calculation of the norm of \(A\text{,}\) we might think of measuring how much \(A\) can change a vector \(\vx\text{.}\) This could lead us to using \(||A\vx||\) as some sort of measure of a norm of \(A\text{.}\) However, since \(||A (c\vx)|| = |c| \ ||A\vx||\) for any scalar \(c\text{,}\) scaling \(\vx\) by a large scalar will produce a large norm, so this is not a viable definition of a norm. We could instead measure the relative effect that \(A\) has on a vector \(\vx\) as \(\ds \frac{||A\vx||}{||\vx||}\text{,}\) since this ratio does not change when \(\vx\) is multiplied by a scalar. The largest of all of these ratios would provide a good sense of how much \(A\) can change vectors. Thus, we define the operator norm of a matrix \(A\) as follows.

Due to the linearity of matrix multiplication, we can restrict ourselves to unit vectors for an equivalent definition of the operator norm of the matrix \(A\) as

The operator norm of a matrix tells us that how big the action of an \(m \times n\) matrix is can be determined by its action on the unit sphere in \(\R^n\) (the unit sphere is the set of terminal point of unit vectors). Let us consider two examples.

Example 29.2.

Let \(A = \left[ \begin{array}{cc} 2\amp 1 \\ 2\amp 5 \end{array} \right]\text{.}\) We can draw a graph to see the action of \(A\) on the unit circle. A picture of the set \(\{A\vx \ : \ ||\vx|| = 1\}\) is shown in Figure 29.3.

It appears that \(A\) transforms the unit circle into an ellipse. To find \(||A||\) we want to maximize \(||A\vx||\) for \(\vx\) on the unit circle. This is the same as maximizing

\begin{equation*} ||A\vx||^2 = (A\vx)^{\tr}(A\vx) = \vx^{\tr}A^{\tr}A\vx\text{.} \end{equation*}

Now \(A^{\tr}A = \left[ \begin{array}{cc} 8\amp 12 \\ 12\amp 26 \end{array} \right]\) is a symmetric matrix, so we can orthogonally diagonalize \(A^{\tr}A\text{.}\) The eigenvalues of \(A^{\tr}A\) are 32 and 2. Let \(P = [\vu_1 \ \vu_2]\text{,}\) where \(\vu_1=\left[ \frac{\sqrt{5}}{5} \ \frac{2\sqrt{5}}{5} \right]^{\tr}\) is a unit eigenvector of \(A^{\tr}A\) with eigenvalue 32 and \(\vu_2=\left[ -\frac{2\sqrt{5}}{5} \ \frac{\sqrt{5}}{5} \right]^{\tr}\) is a unit eigenvector of \(A^{\tr}A\) with eigenvalue 2. Then \(P\) is an orthogonal matrix such that \(P^{\tr}(A^{\tr}A)P = \left[ \begin{array}{cc} 32\amp 0 \\ 0\amp 2 \end{array} \right] = D\text{.}\) It follows that

\begin{equation*} \vx^{\tr} (A^{\tr}A) \vx = \vx^{\tr} PDP^{\tr} \vx = (P^{\tr}\vx)^{\tr} D (P^{\tr}\vx)\text{.} \end{equation*}

Now \(P^{\tr}\) is orthogonal, so \(||P^{\tr}\vx|| = ||\vx||\) and \(P^{\tr}\) maps the unit circle to the unit circle. Moreover, if \(\vx\) is on the unit circle, then \(\vy = P\vx\) is also on the unit circle and \(P^{\tr}\vy = P^{\tr}P\vx = \vx\text{.}\) So every point \(\vx\) on the unit circle corresponds to a point \(P\vx\) on the unit circle. Thus, the forms \(\vx^{\tr} (A^{\tr}A) \vx\) and \((P^{\tr}\vx)^{\tr} D (P^{\tr}\vx)\) take on exactly the same values over all points on the unit circle. Now we just need to find the maximum value of \((P^{\tr}\vx)^{\tr} D (P^{\tr}\vx)\text{.}\) This turns out to be relatively easy since \(D\) is a diagonal matrix.

Let's simplify the notation. Let \(\vy = P^{\tr}\vx\text{.}\) Then our job is to maximize \(\vy^{\tr}D\vy\text{.}\) If \(\vy = [y_1 \ y_2]^{\tr}\text{,}\) then

\begin{equation*} \vy^{\tr} D \vy = 32y_1^2 + 2y_2^2\text{.} \end{equation*}

We want to find the maximum value of this expression for \(\vy\) on the unit circle. Note that \(2y_2^2 \leq 32y_2^2\) and so

\begin{equation*} 32y_1^2 + 2y_2^2 \leq 32y_1^2 + 32y_2^2 = 32(y_1^2+y_2^2) = 32||\vy||^2 = 32\text{.} \end{equation*}

Since \([1 \ 0]^{\tr}\) is on the unit circle, the expression \(32y_1^2 + 2y_2^2\) attains the value 32 at some point on the unit circle, so 32 is the maximum value of \(\vy^{\tr} D \vy\) over all \(\vy\) on the unit circle. While we are at it, we can similarly find the minimum value of \(\vy^{\tr} D \vy\) for \(\vy\) on the unit circle. Since \(2y_1^2 \leq 32y_1^2\) we see that

\begin{equation*} 32y_1^2 + 2y_2^2 \geq 2y_1^2 + 2y_2^2 = 2(y_1^2+y_2^2) = 2||\vy||^2 = 2\text{.} \end{equation*}

Since the expression \(\vy^{\tr} D \vy\) attains the value 2 at \([0 \ 1]^{\tr}\) on the unit circle, we can see that \(\vy^{\tr} D \vy\) attains the minimum value of 2 on the unit circle.

Now we can return to the expression \(\vx^{\tr} (A^{\tr}A) \vx\text{.}\) Since \(\vy^{\tr} D \vy\) assumes the same values as \(\vx^{\tr} (A^{\tr}A) \vx\text{,}\) we can say that the maximum value of \(\vx^{\tr} (A^{\tr}A) \vx\) for \(\vx\) on the unit circle is 32 (and the minimum value is 2). Moreover, the quadratic form \((P^{\tr}\vx)^{\tr} D (P^{\tr}\vx)\) assumes its maximum value when \(P^{\tr}\vx = [1 \ 0]^{\tr}\) or \([-1 \ 0]^{\tr}\text{.}\) Thus, the form \(\vx^{\tr} (A^{\tr}A) \vx\) assumes its maximum value at the vector \(\vx = P[1 \ 0 ]^{\tr} = \vu_1\) or \(-\vu_1\text{.}\) Similarly, the quadratic form \(\vx^{\tr} (A^{\tr}A) \vx\) attains its minimum value at \(P[0 \ 1]^{\tr} = \vu_2\) or \(-\vu_2\text{.}\) We conclude that \(||A|| = \sqrt{32}\text{.}\)

Figure 29.4 shows the image of the unit circle under the action of \(A\) and the images of \(A\vu_1\) and \(A\vu_2\) where \(\vu_1, \vu_2\) are the two unit eigenvectors of \(A^{\tr}A\text{.}\) The image also supports that \(A\vx\) assumes its maximum and minimum values for points on the unit circle at \(\vu_1\) and \(\vu_2\text{.}\)

Example 29.5.

This same process works for matrices other than \(2 \times 2\) ones. For example, consider \(A = \left[ \begin{array}{rrr} -2\amp 8\amp 20 \\ 14\amp 19\amp 10 \end{array} \right]\text{.}\) In this case \(A\) maps \(\R^3\) to \(\R^2\text{.}\) The image of the unit sphere \(\{\vx \in \R^3 : ||\vx|| = 1\}\) under left multiplication by \(A\) is a filled ellipse as shown in Figure 29.6.

As with the previous example, the norm of \(A\) is the square root of the maximum value of \(\vx^{\tr} (A^{\tr}A) \vx\) and this maximum value is the dominant eigenvalue of \(A^{\tr}A = \left[ \begin{array}{ccc} 200\amp 250\amp 100\\ 250\amp 425\amp 350\\ 100\amp 350\amp 500 \end{array} \right]\text{.}\) The eigenvalues of \(A\) are \(\lambda_1 = 900\text{,}\) \(\lambda_2 = 225\text{,}\) and \(\lambda_3 = 0\) with corresponding unit eigenvectors \(\vu_1=\left[ \frac{1}{3} \ \frac{2}{3} \ \frac{2}{3} \right]^{\tr}\text{,}\) \(\vu_1=\left[ -\frac{2}{3} \ -\frac{1}{3} \ \frac{2}{3} \right]^{\tr}\text{,}\) and \(\vu_3=\left[ \frac{2}{3} \ -\frac{2}{3} \ \frac{1}{3} \right]^{\tr}\text{.}\) So in this case we have \(||A|| = \sqrt{900} = 30\text{.}\) The transformation defined by matrix multiplication by \(A\) from \(\R^3\) to \(\R^2\) has a one-dimensional kernel which is spanned by the eigenvector corresponding to \(\lambda_3\text{.}\) The image of the transformation is 2-dimensional and the image of the unit circle is an ellipse where \(A\vu_1\) gives the major axis of the ellipse and \(A\vu_2\) gives the minor axis. Essentially, the square roots of the eigenvalues of \(A^{\tr}A\) tell us how \(A\) stretches the image space in each direction.

Subsection The SVD

The Singular Value Decomposition (SVD) is essentially a concise statement of what we saw in the previous section that works for any matrix. We will uncover the SVD in this section.

Preview Activity 29.3 contains the basic ideas behind the Singular Value Decomposition. Let \(A\) be an \(m \times n\) matrix with real entries. Note that \(A^{\tr}A\) is a symmetric \(n \times n\) matrix and, hence, it can be orthogonally diagonalized. Let \(V = [\vv_1 \ \vv_2 \ \vv_3 \ \cdots \ \vv_n ]\) be an \(n \times n\) orthogonal matrix whose columns form an orthonormal set of eigenvectors for \(A^{\tr}A\text{.}\) For each \(i\text{,}\) let \((A^{\tr}A)\vv_i = \lambda_i \vv_i\text{.}\) We know

Now notice that for each \(i\) we have

so \(\lambda_i \geq 0\text{.}\) Thus, the matrix \(A^{\tr}A\) has no negative eigenvalues. We can always arrange the eigenvectors and eigenvalues of \(A^{\tr}A\) so that

Also note that

if \(i \neq j\text{.}\) So the set \(\{A\vv_1, A\vv_2, \ldots, A\vv_n\}\) is an orthogonal set in \(\R^m\text{.}\) Each of the vectors \(A\vv_i\) is in \(\Col A\text{,}\) and so \(\{A\vv_1, A\vv_2, \ldots, A\vv_n\}\) is an orthogonal subset of \(\Col A\text{.}\) It is possible that \(A\vv_i = \vzero\) for some of the \(\vv_i\) (if \(A^{\tr}A\) has 0 as an eigenvalue). Let \(\vv_1\text{,}\) \(\vv_2\text{,}\) \(\ldots\text{,}\) \(\vv_r\) be the eigenvectors corresponding to the nonzero eigenvalues. Then the set

is a linearly independent set of nonzero orthogonal vectors in \(\Col A\text{.}\) Now we will show that \(\CB\) is a basis for \(\Col A\text{.}\) Let \(\vy\) be a vector in \(\Col A\text{.}\) Then \(\vy = A\vx\) for some vector \(\vx\) in \(\R^n\text{.}\) Recall that the vectors \(\vv_1\text{,}\) \(\vv_2\text{,}\) \(\ldots\text{,}\) \(\vv_n\) form an orthonormal basis of \(\R^n\text{,}\) so

for some scalars \(x_1\text{,}\) \(x_2\text{,}\) \(\ldots\text{,}\) \(x_n\text{.}\) Since \(A\vv_j = \vzero\) for \(r+1 \leq j \leq n\) we have

So \(\Span \ \CB = \Col A\) and \(\CB\) is an orthogonal basis for \(\Col A\text{.}\)

Now we are ready to find the Singular Value Decomposition of \(A\text{.}\) First we create an orthonormal basis \(\{\vu_1, \vu_2, \ldots, \vu_r\}\) for \(\Col A\) by normalizing the vectors \(A\vv_i\text{.}\) So we let

for \(i\) from 1 to \(r\text{.}\)

Remember from (29.1) that \(||A\vv_i||^2 = \lambda_i\text{,}\) so if we let \(\sigma_i = \sqrt{\lambda_i}\text{,}\) then we have

We ordered the \(\lambda_i\) so that \(\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n\text{,}\) so we also have

The scalars \(\sigma_1\text{,}\) \(\sigma_2\text{,}\) \(\ldots\text{,}\) \(\sigma_n\) are called the singular values of \(A\text{.}\)

The vectors \(\vu_1\text{,}\) \(\vu_2\text{,}\) \(\ldots\text{,}\) \(\vu_r\) are \(r\) orthonormal vectors in \(\R^m\text{.}\) We can extend the set \(\{\vu_1\text{,}\) \(\vu_2\text{,}\) \(\ldots\text{,}\) \(\vu_r\}\) to an orthonormal basis \(\CC = \{\vu_1, \vu_2, \ldots, \vu_r, \vu_{r+1} \vu_{r+2}, \ldots, \vu_m\}\) of \(\R^m\text{.}\) Recall that \(A \vv_i = \sigma_i \vu_i\) for \(1 \leq i \leq r\) and \(A \vv_j = \vzero\) for \(r+1 \leq j \leq n\text{,}\) so

We can write the matrix \([\sigma_1 \vv_1 \ \sigma_2 \vv_2 \ \cdots \ \sigma_r \vv_r \ \vzero \ \vzero \ \cdots \ \vzero]\) in another way. Let \(\Sigma\) be the \(m\times n\) matrix defined as

Now

So if \(U = [\vu_1 \ \vu_2 \ \cdots \ \vu_m]\text{,}\) then

Since \(V\) is an orthogonal matrix, we have that

This is the Singular Value Decomposition of \(A\text{.}\)

There is another way we can write this SVD of \(A\text{.}\) Let the \(m \times n\) matrix \(A\) have a singular value decomposition \(U \Sigma V^{\tr}\text{,}\) where

Since \(A = U \Sigma V^{\tr}\) we see that

This is called an outer product decomposition of \(A\) and tells us everything we learned above about the action of the matrix \(A\) as a linear transformation. Each of the products \(\vu_i\vv_i^{\tr}\) is a rank 1 matrix (see Exercise 9), and \(||A\vv_1|| = \sigma_1\) is the largest value \(A\) takes on the unit \(n\)-sphere, \(||A\vv_2|| = \sigma_2\) is the next largest dilation of the unit \(n\)-sphere, and so on. An outer product decomposition allows us to approximate \(A\) with smaller rank matrices. For example, the matrix \(\sigma_1 \vu_1\vv_1^{\tr}\) is the best rank 1 approximation to \(A\text{,}\) \(\sigma_1 \vu_1\vv_1^{\tr} + \sigma_2 \vu_2\vv_2^{\tr}\) is the best rank 2 approximation, and so on. This will be very useful in applications, as we will see in the next section.

Subsection SVD and the Null, Column, and Row Spaces of a Matrix

We conclude this section with a short discussion of how a singular value decomposition relates fundamental subspaces of a matrix. We have seen that the vectors \(\vu_1\text{,}\) \(\vu_2\text{,}\) \(\ldots\text{,}\) \(\vu_r\) in an SVD for an \(m \times n\) matrix \(A\) form a basis for \(\Col A\text{.}\) Recall also that \(A \vv_j = \vzero\) for \(r+1 \leq j \leq n\text{.}\) Since \(\dim(\Nul A) + \dim(\Col A) = n\text{,}\) it follows that the vectors \(\vv_{r+1}\text{,}\) \(\vv_{r+2}\text{,}\) \(\ldots\text{,}\) \(\vv_n\) form a basis for \(\Nul A\text{.}\) As you will show in the exercises, the set \(\{\vv_1, \vv_2, \ldots, \vv_r\}\) is a basis for \(\Row A\text{.}\) Thus, an SVD for a matrix \(A\) tells us about three fundamental vector spaces related to \(A\text{.}\)

Subsection Examples

What follows are worked examples that use the concepts from this section.

Subsection Summary

We learned about the singular value decomposition of a matrix.

• The operator norm of an \(m \times n\) matrix \(A\) is

  \begin{equation*} ||A|| = \max_{||\vx|| \neq 0} \frac{||A\vx||}{||\vx||} = \max_{||\vx||=1} ||A\vx||\text{.} \end{equation*}

  The operator norm of a matrix tells us that how big the action of an \(m \times n\) matrix is can be determined by its action on the unit sphere in \(\R^n\text{.}\)

• A singular value decomposition of an \(m \times n\) matrix is of the form \(A = U \Sigma V^{\tr}\text{,}\) where

  • \(V= [\vv_1 \ \vv_2 \ \vv_3 \ \cdots \ \vv_n ]\) where \(\{\vv_1, \vv_2, \vv_3, \ldots, \vv_n\}\) is an orthonormal basis of eigenvectors of \(A^{\tr}A\) such that \((A^{\tr}A) \vv_i = \lambda_i \vv_i\) for \(i\) from 1 to \(n\) with \(\lambda_1 \geq \lambda_{2} \geq \cdots \geq \lambda_n \geq 0\text{,}\)

  • \(U = [\vu_1 \ \vu_2 \ \cdots \ \vu_m]\) where \(\vu_i = \frac{A\vv_i}{||A\vv_i||}\) for \(i\) from 1 to \(r\text{,}\) and this orthonormal basis of \(\Col A\) is extended to an orthonormal basis \(\{\vu_1, \vu_2, \ldots, \vu_r, \vu_{r+1} \vu_{r+2}, \ldots, \vu_m\}\) of \(\R^m\text{,}\)

  • \(\Sigma = \left[ \begin{array}{ccccc|c} \sigma_1\amp \amp \amp \amp 0\amp \\ \amp \sigma_2\amp \amp \amp \amp 0 \\ \amp \amp \sigma_3\amp \amp \amp \\ \amp \amp \amp \ddots \amp \amp \\ 0\amp \amp \amp \amp \sigma_r \\ \hline \amp \amp 0\amp \amp \amp 0 \end{array} \right]\text{,}\) where \(\sigma_i = \sqrt{\lambda_i} > 0\) for \(i\) from 1 to \(r\text{.}\)

    A singular value decomposition is important in that every matrix has a singular value decomposition, and a singular value decomposition has a variety of applications including scientific computing and digital signal processing, image compression, principal component analysis, web searching through latent semantic indexing, and seismology.

• The vectors \(\vu_1\text{,}\) \(\vu_2\text{,}\) \(\ldots\text{,}\) \(\vu_r\) in an SVD for an \(m \times n\) matrix \(A\) form a basis for \(\Col A\) while the vectors \(\vv_{r+1}\text{,}\) \(\vv_{r+2}\text{,}\) \(\ldots\text{,}\) \(\vv_n\) form a basis for \(\Nul A\text{.}\) Also, the set \(\{\vv_1, \vv_2, \ldots, \vv_r\}\) is a basis for \(\Row A\text{.}\)

• Let \(A\) have an SVD as in the second bullet. Decomposing \(A\) as

  \begin{equation*} A =\sigma_1 \vu_1\vv_1^{\tr} + \sigma_2 \vu_2\vv_2^{\tr} + \sigma_3 \vu_3\vv_3^{\tr} + \cdots + \sigma_r \vu_r\vv_r^{\tr} \end{equation*}

  is an outer product decomposition of \(A\text{.}\) An outer product decomposition allows us to approximate \(A\) with smaller rank matrices. For example, the matrix \(\sigma_1 \vu_1\vv_1^{\tr}\) is the best rank 1 approximation to \(A\text{,}\) \(\sigma_1 \vu_1\vv_1^{\tr} + \sigma_2 \vu_2\vv_2^{\tr}\) is the best rank 2 approximation, and so on.

Subsection Project: Latent Semantic Indexing

As an elementary example to illustrate the idea behind Latent Semantic Indexing (LSI), consider the problem of creating a program to search a collection of documents for words, or words related to a given word. Document collections are usually very large, but we use a small example for illustrative purposes. A standard example that is given in several publications⁵¹ is the following. Suppose we have nine documents \(c_1\) through \(c_5\) (titles of documents about human-computer interaction) and \(m_1\) through \(m_4\) (titles of graph theory papers) that make up our library:

• \(c_1\text{:}\) Human machine interface for ABC computer applications

• \(c_2\text{:}\) A survey of user opinion of computer system response time

• \(c_3\text{:}\) The EPS user interface management system

• \(c_4\text{:}\) System and human system engineering testing of EPS

• \(c_5\text{:}\) Relation of user perceived response time to error measurement

• \(m_1\text{:}\) The generation of random, binary, ordered trees

• \(m_2\text{:}\) The intersection graph of paths in trees

• \(m_3\text{:}\) Graph minors IV: Widths of trees and well-quasi-ordering

• \(m_4\text{:}\) Graph minors: A survey

To make a searchable database, one might start by creating a list of key terms that appear in the documents (generally removing common words such as “a”, “the”, “of”, etc., called stop words — these words contribute little, if any, context). In our documents we identify the key words that are shown in italics. (Note that we are just selecting key words to make our example manageable, not necessarily identifying the most important words.) Using the key words we create a term-document matrix. The term-document matrix is the matrix in which the terms form the rows and the documents the columns. If \(A = [a_{ij}]\) is the term-document matrix, then \(a_{ij}\) counts the number of times word \(i\) appears in document \(j\text{.}\) The term-document matrix \(A\) for our library is

One of our goals is to rate the pages in our library for relevance if we search for a query. For example, suppose we want to rate the pages for the query survey, computer. This query can be represented by the vector \(\vq= [0 \ 0 \ 1 \ 0 \ 0 \ 0 \ 0 \ 0 \ 1 \ 0 \ 0 \ 0 ]^{\tr}\text{.}\)

Though we were able to rate the documents in Project Activity 29.5 using the cosine distance, the result is less than satisfying. Documents \(c_3\text{,}\) \(c_4\text{,}\) and \(c_5\) are all related to computers but do not appear at all in or results. This is a problem with language searches — we don't want to compare just words, but we also need to compare the concepts the words represent. The fact that words can represent different things implies that a random choice of word by different authors can introduce noise into the word-concept relationship. To filter out this noise, we can apply the singular value decomposition to find a smaller set of concepts to better represent the relationships. Before we do so, we examine some useful properties of the term-document matrix.

The nature of the term-term and document-document matrices makes it realistic to think about a SVD.

As we will see, the connection of the matrices \(U\) and \(V\) to documents and terms that we saw in Project Activity 29.7 will be very useful when we use the SVD of the term-document matrix to reduce dimensions to a “concept” space. We will be able to interpret the rows of the matrices \(U\) and \(V\) as providing coordinates for terms and documents in this space.

Once we have our term-document matrix, there are three basic comparisons to make: comparing terms, comparing documents, and comparing terms and documents. Term-document matrices are usually very large, with dimension being the number of terms. By using a reduced SVD we can create a much smaller approximation. In our example, the matrix \(A_k\) in Project Activity 29.8 reduces our problem to a \(k\)-dimensional space. Intuitively, we can think of LSI as representing terms as averages of all of the documents in which they appear and documents as averages of all of the terms they contain. Through this process, LSI attempts to combine the surface information in our library into a deeper abstraction (the “concept” space) that captures the mutual relationships between terms and documents.

We now need to understand how we can represent documents and terms in this smaller space where \(A_k = U_k \Sigma_k V_k^{\tr}\text{.}\) Informally, we can consider the rows of \(U_k\) as representing the coordinates of each term in the lower dimensional concept space and the columns of \(V_k^{\tr}\) as the coordinates of the documents, while the entries of \(\Sigma_k\) tell us how important each semantic dimension is. The dot product of two row vectors of \(A_k\) indicates how terms compare across documents. This product is \(A_kA_k^{\tr}\text{.}\) Just as in Project Activity 29.7, we have \(A_kA_k^{\tr} = \left(U_k \Sigma_k\right) \left(U_k\Sigma_k\right)^{\tr}\text{.}\) In other words, if we consider the rows of \(U_k\Sigma_k\) as coordinates for terms, then the dot products of these rows give us term to term comparisons. (Note that multiplying \(U\) by \(\Sigma\) just stretches the rows of \(U\) by the singular values according to the importance of the concept represented by that singular value.) Similarly, the dot product between columns of \(A\) provide a comparison of documents. This comparison is given by \(A_k^{\tr}A_k^ = \left(V_k \Sigma_k^{\tr}\right) \left(V_k\Sigma_k^{\tr}\right)^{\tr}\) (again by Project Activity 29.7). So we can consider the rows of \(V\Sigma^{\tr}\) as providing coordinates for documents.

To work in this smaller concept space, it is important to be able to find appropriate comparisons to objects that appeared in the original search. For example, to complete the latent structure view of the system, we must also convert the original query to a representation within the new term-document system represented by \(A_k\text{.}\) This new representation is called a pseudo-document.

As we can see from Project Activity 29.10, the original query had no match at all with any documents except \(c_1\text{,}\) \(c_2\text{,}\) and \(m_4\text{.}\) In the new concept space, the query now has some connection to every document,. So LSI has made semantic connections between the terms and documents that were not present in the original term-document matrix, which gives us better results for our search.