The Singular Value Decomposition

      Every rectangular matrix with may be factored into the form

where are matrices with orthonormal columns and the diagnoal matrix .The numbers are called the singular values of The columns of are the left singular vectors and the columns of are the right singular vectors of ${\bf A}$.   This is the so-called ``short form" of the Singular Value Decompositon (SVD) of ${\bf A}$.

The relationship (A.5.1) may be manipulated using orthogonality to reveal that

if . Thus selected singular values and the corresponding right singular vectors may be computed by finding eigenvalues and vectors for the $n \times n$ matrix

In many applications, one is iterested in computing a few (say k) of the largest singular values and corresponding vectors. If , denote the leading k-columns of and respectively, and if denotes the leading principal submatrix of then

is the best rank-k approximation to ${\bf A}$ in both the 2-norm and the Frobenius norm. Often a very small k will suffice to approximate important features of the original ${\bf A}$ or to approximately solve least squares problems involving

This partial SVD may be computed efficiently using ARPACK subroutine _saupd in mode = 1 with which = 'LA' and taking

Of course, the action of should be computed with the steps

1.

Matrix-vector multiply

2.

Matrix-vector multiply

Also, note that if the matrix ${\bf A}$ is huge and must be stored on a peripheral device, then ${\bf A}$ may be read in by blocks to achieve the action of using the fact that

where to obtain the loop shown in Figure A.2.

  

Figure A.2: Compute w <--- A^TA by Blocks

Initialize ${\bf w} \leftarrow 0$;
For $j=1,2,3,... \ell$,

${\bf C} \leftarrow {\bf A}_j;$ (Read next block of $\bf A$)
${\bf z} \leftarrow {\bf C} {\bf v}$;
${\bf w} \leftarrow {\bf w} + {\bf C}^T {\bf z}$;

End_For

The drivers illustrate how to compute the leading k terms of the SVD as just described. The left singular vectors are recovered   from the right singular vectors. As long as the largest singular values are not multiple or tightly clusterd, there should be no problem in obtaining numerically orthogonal left singular vectors from the computed right singular vectors. However, there is a way to get the both the left and right singular vectors directly. This is to define

and utilize the fact that

to extract the columns of from the first m components of the converged eigenvectors of OP and the columns of from the remaining n components. If this scheme is used, it is important to set which = 'LA' because the blocked matrix OP will have both and as eigenvalues for .

We only provide the first approach in the ARPACK drivers. We also should mention that in case you have a matrix ${\bf A}$ with m < n then replace ${\bf A}$ with in the above discussion and reverse the roles of and .