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')