Section5.5The Singular Value Decomposition
Our overarching goal of this section is to discuss an analogue to the
eigenvalue-eigenvector problem for non-square matrices. That is, we would like to take a
matrix A that is m \times n and find vectors are values that behave similarly to how
eigenvectors and eigenvalues behave for square matrices. The key to this discussion is
the matrix A^T A, so let's start there.
Let \(A\) be an \(m \times n\) matrix. What is the size of \(A^T A\)? Prove that \(A^T A\)
must be a symmetric matrix (a matrix \(B\) is symmetric if \(B_{ij} = B_{ji}\)). Finally, what bearing
does the next Theorem have on the matrix \(A^T A\)?
Theorem5.5.2
An n \times n matrix A has n orthogonal eigenvectors if and only if A is a
symmetric matrix.
Definition5.5.3
The singular values of an m \times n matrix A are the square roots of the
eigenvalues of A^T A.
They are typically denoted as \sigma_1, \sigma_2, \dots, \sigma_n where \sigma_j =
\sqrt{\lambda_j} and \lambda_j is an eigenvalue of A^T A.
Definition5.5.4
The singular value decomposition of an m \times n matrix A with rank r is
a factorization of A into the product of three matrices, U, \Sigma, and V,
such that
\begin{equation*}
A = U \Sigma V^T.
\end{equation*}
In the singular value decomposition, U (m \times m) and V (n \times n) have
orthogonal columns and \Sigma (m \times n)
is a block diagonal matrix
\begin{equation*}
\Sigma = \begin{pmatrix}D \amp 0 \\ 0 \amp 0
\end{pmatrix}
\end{equation*}
where D is an r \times r diagonal matrix containing the r singular values of
A in rank order (largest to smallest).
To build the singular value decomposition:
Form A^TA and find the eigenvalues and eigenvectors (guaranteed to exist
by Theorem 5.5.2).
Form \Sigma
The columns of V are the eigenvectors of A^T A.
The columns of U are the normalized vectors obtained by
\begin{equation*}
\bu_1 = \frac{1}{\sigma_1} A \bv_1\, , \, \bu_2 = \frac{1}{\sigma_2} A
\bv_2 \, , \, \dots, \, \bu_m = \frac{1}{\sigma_m} A \bv_m
\end{equation*}
Use MATLAB to find the singular value decomposition of
\begin{equation*}
A = \begin{pmatrix}4 \amp 11 \amp 14 \\ 8 \amp 7 \amp -2
\end{pmatrix}
\end{equation*}
Some practical MATLAB tips follow:
Define \(A\)
Define the sizes: m=size(A,1); n=size(A,2)
Find the rank of \(A\): r = rank(A);
Define the matrices Sigma and U to be zero matrices with
the right size.
Have MATLAB calculate the eigenvectors and eigenvalues of \(A^T A\):
[vectors,values]=eig(A'A,'vector');
The 'vector' command spits out the eigenvalues as a vector instead of
a diagonal matrix. This will be helpful in the next step.
Have MATLAB sort the eigenvalues and strip any negative approximate
zero eigenvalues that arise from numerical approximation of zero.
values = abs(values);
[values,indices] = sort(values,'descend')
Sort the columns of \(V\) using the indices coming out of the sort command:
V = vectors(:,indices);
Build the singular values from the eigenvalues of \(A^TA\) (remember the
square root!):
singularvalues=...
Build non-zero diagonal entries of the \(\Sigma\) matrix with a loop. Also build a
temporary matrix \(B\) the same size as \(\Sigma\) but with the diagonal entries
\(1/\sigma_j\). We'll need \(B\) in the next step.
B=zeros(size(Sigma));
for j=1:r
Sigma(j,j) = ...
B(j,j) = ...
end
Observe that since \(V\) has orthonormal columns we can write \(AV = U \Sigma\).
Now, \(\Sigma\) is not square, but we know that it has diagonal entries only so
we have a pseudo-inverse \(B^T\) already built. Hence, \(U = A V B^T\).
Build \(U\).
Check that \(A = U \Sigma V^T\)
Create a MATLAB function that accepts a matrix \(A\) and outputs the three matrices for
the singular value decomposition. Test your function on a large random rectangular
matrix.
A = rand(500,300);
[U,S,V] = MySVD(A);
error = norm(A - U*S*V')