Low-rank approximations

We next state a matrix approximation problem that at first seems to have little to do with information retrieval. We describe a solution to this matrix problem using singular-value decompositions, then develop its application to information retrieval.

Given an $\lsinoterms\times \lsinodocs$ matrix $\lsimatrix$ and a positive integer $k$, we wish to find an $\lsinoterms\times \lsinodocs$ matrix $\lsimatrix_k$ of rank at most $k$, so as to minimize the Frobenius norm of the matrix difference $X=\lsimatrix-\lsimatrix_k$, defined to be

$$\Vert X \Vert _F = \sqrt{\sum_{i=1}^\lsinoterms \sum_{j=1}^\lsinodocs X_{ij}^2}.$$ (238)

Thus, the Frobenius norm of $X$ measures the discrepancy between $\lsimatrix_k$ and $\lsimatrix$; our goal is to find a matrix $\lsimatrix_k$ that minimizes this discrepancy, while constraining $\lsimatrix_k$ to have rank at most $k$. If $r$ is the rank of $\lsimatrix$, clearly $\lsimatrix_r=\lsimatrix$ and the Frobenius norm of the discrepancy is zero in this case. When $k$ is far smaller than $r$, we refer to $\lsimatrix_k$ as a low-rank approximation .

The singular value decomposition can be used to solve the low-rank matrix approximation problem. We then derive from it an application to approximating term-document matrices. We invoke the following three-step procedure to this end:

1. Given $\lsimatrix$, construct its SVD in the form shown in (232); thus, $\lsimatrix=U\Sigma V^T$.
2. Derive from $\Sigma$ the matrix $\Sigma_k$ formed by replacing by zeros the $r-k$ smallest singular values on the diagonal of $\Sigma$.
3. Compute and output $\lsimatrix_k=U\Sigma_k V^T$ as the rank-$k$ approximation to $\lsimatrix$.

The rank of $\lsimatrix_k$ is at most $k$: this follows from the fact that $\Sigma_k$ has at most $k$ non-zero values. Next, we recall the intuition of Example 18.1: the effect of small eigenvalues on matrix products is small. Thus, it seems plausible that replacing these small eigenvalues by zero will not substantially alter the product, leaving it ``close'' to $\lsimatrix$. The following theorem due to Eckart and Young tells us that, in fact, this procedure yields the matrix of rank $k$ with the lowest possible Frobenius error.

Theorem.

$$\min_{Z \vert \mbox{ rank}(Z)=k} \Vert\lsimatrix-Z\Vert _F = \Vert\lsimatrix-\lsimatrix_k\Vert _F = \sigma_{k+1}.$$ (239)

End theorem.

Recalling that the singular values are in decreasing order $\sigma_1\geq \sigma_2 \geq \cdots$, we learn from Theorem 18.3 that $\lsimatrix_k$ is the best rank-$k$ approximation to $\lsimatrix$, incurring an error (measured by the Frobenius norm of $\lsimatrix-\lsimatrix_k$) equal to $\sigma_{k+1}$. Thus the larger $k$ is, the smaller this error (and in particular, for $k=r$, the error is zero since $\Sigma_r=\Sigma$; provided $r<M,N$, then $\sigma_{r+1}=0$ and thus $\lsimatrix_r=\lsimatrix$).

To derive further insight into why the process of truncating the smallest $r-k$ singular values in $\Sigma$ helps generate a rank-$k$ approximation of low error, we examine the form of $\lsimatrix_k$:

$$\lsimatrix_k = U\Sigma_k V^T$$ (240)

$$= U \left( \begin{array}{ccccc} \sigma_1 & 0 & 0 & 0 & 0 \\ 0 ... ... 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \cdots \\ \end{array} \right) V^T$$ (241)

$$= \sum_{i=1}^k \sigma_i \vec{u}_i \vec{v}_i^T,$$ (242)

where $\vec{u_i}$ and $\vec{v_i}$ are the $i$th columns of $U$ and $V$, respectively. Thus, $\vec{u}_i \vec{v}_i^T$ is a rank-1 matrix, so that we have just expressed $\lsimatrix_k$ as the sum of $k$ rank-1 matrices each weighted by a singular value. As $i$ increases, the contribution of the rank-1 matrix $\vec{u}_i \vec{v}_i^T$ is weighted by a sequence of shrinking singular values $\sigma_i$.

Exercises.

• Compute a rank 1 approximation $C_1$ to the matrix $\lsimatrix$ in Example 235, using the SVD as in Exercise 236. What is the Frobenius norm of the error of this approximation?

• Consider now the computation in Exercise 18.3 . Following the schematic in Figure 18.2 , notice that for a rank 1 approximation we have $\sigma_1$ being a scalar. Denote by $U_1$ the first column of $U$ and by $V_1$ the first column of $V$. Show that the rank-1 approximation to $\lsimatrix$ can then be written as $U_1\sigma_1V_1^T=\sigma_1U_1V_1^T$.

• reduced can be generalized to rank $k$ approximations: we let $U'_k$ and $V'_k$ denote the ``reduced'' matrices formed by retaining only the first $k$ columns of $U$ and $V$, respectively. Thus $U'_k$ is an $\lsinoterms\times k$ matrix while ${V'}_k^T$ is a $k\times \lsinodocs$ matrix. Then, we have
  

  $$\lsimatrix_k=U'_k\Sigma'_k{V'}_k^T,$$ (243)

  
  
  where $\Sigma'_k$ is the square $k\times k$ submatrix of $\Sigma_k$ with the singular values $\sigma_1,\ldots,\sigma_k$ on the diagonal. The primary advantage of using (243) is to eliminate a lot of redundant columns of zeros in $U$ and $V$, thereby explicitly eliminating multiplication by columns that do not affect the low-rank approximation; this version of the SVD is sometimes known as the reduced SVD or truncated SVD and is a computationally simpler representation from which to compute the low rank approximation.

  For the matrix $\lsimatrix$ in Example 18.2, write down both $\Sigma_2$ and $\Sigma'_2$.