Skip to main content

Unit 11.2.1 Computing the SVD from the Spectral Decomposition

Let's see if we can turn the discussion from Unit 11.1.1 around: Given the Spectral Decomposition of \(A^H A \text{,}\) how can we extract the SVD of \(A\text{?}\)

Homework 11.2.1.1.

Let \(A \in \mathbb C^{m \times m} \) be nonsingular and \(A^H A = Q D Q^H \text{,}\) the Spectral Decomposition of \(A^H A \text{.}\) Give a formula for \(U \text{,}\) \(V \text{,}\) and \(\Sigma \) so that \(A = U \Sigma V^H \) is the SVD of \(A \text{.}\) (Notice that \(A \) is square.)

Solution

Since \(A \) is nonsingular, so is \(A^H A \) and hence \(D \) has positive real values on its diagonal. If we take \(V = Q \) and \(\Sigma = D^{1/2} \) then

\begin{equation*} A = U \Sigma V^H = U D^{1/2} Q^H. \end{equation*}

This suggests that we choose

\begin{equation*} U = A V \Sigma^{-1} = A Q D^{-1/2}. \end{equation*}

We can easily verify that \(U \) is unitary:

\begin{equation*} \begin{array}{l} U^H U \\ ~~~=~~~~\\ (A Q D^{-1/2})^H ( A Q D^{-1/2} ) \\ ~~~=~~~~\\ D^{-1/2} Q^H A^H A Q D^{-1/2}\\ ~~~=~~~~\\ D^{-1/2} D D^{-1/2} \\ ~~~=~~~~\\ I . \end{array} \end{equation*}

The final detail is that the Spectral Decomposition does not require the diagonal elements of \(D \) to be ordered from largest to smallest. This can be easily fixed by permuting the columns of \(Q \) and, correspondingly, the diagonal elements of \(D \text{.}\)

Not all matrices are square and nonsingular. In particular, we are typically interested in the SVD of matrices where \(m \gt n \text{.}\) Let's examine how to extract the SVD from the Spectral Decomposition of \(A^H A\) for such matrices.

Homework 11.2.1.2.

Let \(A \in \mathbb C^{m \times n} \) have full column rank and let \(A^H A = Q D Q^H \text{,}\) the Spectral Decomposition of \(A^H A \text{.}\) Give a formula for the Reduced SVD of \(A \text{.}\)

Solution

We notice that if \(A \) has full column rank, then its Reduced Singular Value Decomposition is given by \(A = U_L \Sigma V^H \text{,}\) where \(U_L \in \Cmxn\text{,}\) \(\Sigma \in \mathbb R^{n \times n} \text{,}\) and \(V \in \mathbb C^{n \times n} \text{.}\) Importantly, \(A^H A \) is nonsingular, and \(D \) has positive real values on its diagonal. If we take \(V = Q \) and \(\Sigma = D^{1/2} \) then

\begin{equation*} A = U_L \Sigma V^H = U_L D^{1/2} Q^H. \end{equation*}

This suggests that we choose

\begin{equation*} U_L = A V \Sigma^{-1} = A Q D^{-1/2}, \end{equation*}

where, clearly, \(\Sigma = D^{1/2} \) is nonsingular. We can easily verify that \(U_L \) has orthonormal columns:

\begin{equation*} \begin{array}{l} U_L^H U_L \\ ~~~=~~~~\\ (A Q D^{-1/2})^H ( A Q D^{-1/2} ) \\ ~~~=~~~~\\ D^{-1/2} Q^H A^H A Q D^{-1/2}\\ ~~~=~~~~\\ D^{-1/2} D D^{-1/2} \\ ~~~=~~~~\\ I . \end{array} \end{equation*}

As before, the final detail is that the Spectral Decomposition does not require the diagonal elements of \(D \) to be ordered from largest to smallest. This can be easily fixed by permuting the columns of \(Q \) and, correspondingly, the diagonal elements of \(D \text{.}\)

The last two homeworks gives us a first glimpse at a practical procedure for computing the (Reduced) SVD from the Spectral Decomposition, for the simpler case where \(A \) has full column rank.

  • Form \(B = A^H A \text{.}\)

  • Compute the Spectral Decomposition \(B = Q D Q^H \) via, for example, the QR algorithm.

  • Permute the columns of \(Q \) and diagonal elements of \(D \) so that the diagonal elements are ordered from largest to smallest. If \(P \) is the permutation matrix such that \(P D P^T \) reorders the diagonal of \(D \) appropriately, then

    \begin{equation*} \begin{array}{l} A^H A \\ ~~~=~~~~ \lt \mbox{ Spectral Decomposition } \gt \\ Q D Q^H\\ ~~~=~~~~ \lt \mbox{ insert identities } \gt \\ = Q \begin{array}[t]{c} \underbrace{P^T P} \\ I \end{array} D \begin{array}[t]{c} \underbrace{P^T P} \\ I \end{array} Q^H \\ ~~~=~~~~ \lt \mbox{ associativity } \gt \\ (Q P^T) ( P D P^T ) ( P Q^H ) \\ ~~~=~~~~ \lt ( B C )^H = C^H B^HH \gt \\ (Q P^T) ( P D P^T ) ( Q P^T )^H \end{array} \end{equation*}
  • Let \(V = Q P^T \text{,}\) \(\Sigma = ( P D P^T)^{1/2}\) (which is diagonal), and \(U_L = A V \Sigma^{-1} \text{.}\)

With these insights, we find the Reduced SVD of a matrix with linearly independent columns. If in addition \(A \) is square (and hence nonsingular), then \(U = U_L \) and \(A = U \Sigma V^H \) is its SVD.

x Let us now treat the problem in full generality.

Homework 11.2.1.3.

Let \(A \in \mathbb C^{m \times n} \) be of rank \(r\) and

\begin{equation*} A^H A = \left( \begin{array}{c | c} Q_L \amp Q_R \end{array} \right) \left( \begin{array}{c | c} D_{TL} \amp 0_{r\times (n-r)} \\ \hline 0_{(n-r) \times r} \amp 0_{(n-r) \times (n-r)} \end{array} \right) \left( \begin{array}{c | c} Q_L \amp Q_R \end{array} \right)^H \end{equation*}

be the Spectral Decomposition of \(A^H A \text{,}\) where \(Q_L \in \mathbb C^{n \times r} \) and, for simplicity, we assume the diagonal elements of \(D_{TL} \) are ordered from largest to smallest. Give a formula for the Reduced SVD of \(A \text{.}\)

Solution

The Reduced SVD of \(A \) is given by \(A = U_L \Sigma_{TL} V_L^H \text{,}\) where \(\Sigma_{TL} \) is \(r \times r \) is diagonal with positive real values along its diagonal, ordered from largest to smallest. If we take \(V_L = Q_L \) and \(\Sigma_{TL} = D_{TL}^{1/2} \) then

\begin{equation*} A = U_L \Sigma_{TL} V_L^H = U_L D^{1/2} Q_L^H. \end{equation*}

This suggests that we choose

\begin{equation*} U_L = A V_L \Sigma_{TL}^{-1} = A Q_L D_{TL}^{-1/2}. \end{equation*}

We can easily verify that \(U_L \) has orthonormal columns:

\begin{equation*} \begin{array}{l} U_L^H U_L \\ ~~~=~~~~\\ (A Q_L D_{TL}^{-1/2})^H ( A Q_L D_{TL}^{-1/2} ) \\ ~~~=~~~~\\ D_{TL}^{-1/2} Q_L^H A^H A Q_L D_{TL}^{-1/2}\\ ~~~=~~~~\\ D_{TL}^{-1/2} Q_L^H \left( \begin{array}{c | c} Q_L \amp Q_R \end{array} \right) \left( \begin{array}{c | c} D_{TL} \amp 0_{r\times (n-r)} \\ \hline 0_{(n-r) \times r} \amp 0_{(n-r) \times (n-r)} \end{array} \right) \left( \begin{array}{c | c} Q_L \amp Q_R \end{array} \right)^H Q_L D_{TL}^{-1/2}\\ ~~~=~~~~\\ D_{TL}^{-1/2} \left( \begin{array}{c | c} I \amp 0 \end{array} \right) \left( \begin{array}{c | c} D_{TL} \amp 0_{r\times (n-r)} \\ \hline 0_{(n-r) \times r} \amp 0_{(n-r) \times (n-r)} \end{array} \right) \left( \begin{array}{c | c} I \amp 0 \end{array} \right)^H D_{TL}^{-1/2}\\ ~~~=~~~~\\ D_{TL}^{-1/2} D_{TL} D_{TL}^{-1/2} \\ ~~~=~~~~\\ I . \end{array} \end{equation*}

Although the discussed approaches give us a means by which to compute the (Reduced) SVD that is mathematically sound, the Achilles heel of these is that it hinges on forming \(A^H A\text{.}\) While beyond the scope of this course, the conditioning of computing a Spectral Decomposition of a Hermitian matrix is dictated by the condition number of the matrix, much like solving a linear system is. We recall from Unit 4.2.5 that we avoid using the Method of Normal Equations to solve the linear least squares problem when a matrix is ill-conditioned. Similarly, we try to avoid computing the SVD from \(A^H A \text{.}\) The problem here is even more acute: it is often the case that \(A \) is (nearly) rank deficient (for example, in situations where we desire a low rank approximation of a given matrix) and hence it is frequently the case that the condition number of \(A \) is very unfavorable. The question thus becomes, how can we avoid computing \(A^H A\) while still benefiting from the insights in this unit?

Homework 11.2.1.4.

Compute the SVD of

\begin{equation*} A = \left( \begin{array}{c c} \sqrt{2} \amp 1 \\ 0 \amp \sqrt{2} \end{array} \right). \end{equation*}
Hint

Start by computing the Spectral Decomposition of \(A^T A \text{.}\)

Solution

The strategy is to observe that if \(A = U \Sigma V^T \text{,}\) then \(A^T A = V \Sigma^2 V^T \text{.}\) Thus, if we compute the Spectral decomposition of \(A^T A \text{,}\) we have determined \(V \) and \(\Sigma \text{.}\) From these, we can then compute \(U \text{.}\)

Note that

\begin{equation*} B = A^T A = \left( \begin{array}{c c} \sqrt{2} \amp 1 \\ 0 \amp \sqrt{2} \end{array} \right)^T \left( \begin{array}{c c} \sqrt{2} \amp 1 \\ 0 \amp \sqrt{2} \end{array} \right) = \left( \begin{array}{c c} 2 \amp \sqrt{2} \\ \sqrt{2} \amp 3 \end{array} \right). \end{equation*}

If we now form the characteristic polynomial of \(B \) we find that

\begin{equation*} \begin{array}{rcl} \mbox{det}(\lambda I - B ) \amp = \amp \mbox{det}( \left( \begin{array}{c c} \lambda - 2 \amp -\sqrt{2} \\ -\sqrt{2} \amp \lambda - 3 \end{array} \right) ) = ( \lambda - 2 )( \lambda - 3 ) - 2 \\ \amp=\amp \lambda^2 - 5 \lambda + 4 = ( \lambda - 4 ) ( \lambda - 1). \end{array} \end{equation*}

Thus, the eigenvalues of \(B \) equal \(4 \) and \(1 \text{.}\)

Now, let's compute eigenvectors associated with these eigenvalues:

  • \(\lambda = 4 \text{:}\)

    \begin{equation*} \left( \begin{array}{c c} \lambda - 2 \amp -\sqrt{2} \\ -\sqrt{2} \amp \lambda - 3 \end{array} \right) = \left( \begin{array}{c c} 4 - 2 \amp -\sqrt{2} \\ -\sqrt{2} \amp 4 - 3 \end{array} \right) = \left( \begin{array}{c c} 2 \amp -\sqrt{2} \\ - \sqrt{2} \amp 1 \end{array} \right). \end{equation*}

    We want a vector in the null space of this matrix:

    \begin{equation*} \left( \begin{array}{c c} 2 \amp - \sqrt{2} \\ - \sqrt{2} \amp 1 \end{array} \right) \left( \begin{array}{c} \chi_0 \\ \chi_1 \end{array} \right) = \left( \begin{array}{c} 0 \\ 0 \end{array} \right). \end{equation*}

    By examination,

    \begin{equation*} \tilde v_0 = \left( \begin{array}{c} 1 \\ \sqrt{2} \end{array} \right) \end{equation*}

    is an eigenvector. However, we would like it to have length one:

    \begin{equation*} v_0 = \tilde v_0 / \| \tilde v_0 \|_2 = \tilde v_0 / \sqrt{3} = \frac{1}{\sqrt{3}} \left( \begin{array}{c} 1 \\ \sqrt{2} \end{array} \right) = \left( \begin{array}{c} \sqrt{3}/3 \\ \sqrt{6}/3 \end{array} \right). \end{equation*}
  • \(\lambda = 1 \text{:}\)

    \begin{equation*} \left( \begin{array}{c c} \lambda - 2 \amp -\sqrt{2} \\ -\sqrt{2} \amp \lambda - 3 \end{array} \right) = \left( \begin{array}{c c} 1 - 2 \amp -\sqrt{2} \\ -\sqrt{2} \amp 1 - 3 \end{array} \right) = \left( \begin{array}{c c} -1 \amp -\sqrt{2} \\ -\sqrt{2} \amp -2 \end{array} \right). \end{equation*}

    We want a vector in the null space of this matrix:

    \begin{equation*} \left( \begin{array}{c c} -1 \amp -\sqrt{2} \\ -\sqrt{2} \amp -2 \end{array} \right) \left( \begin{array}{c} \chi_0 \\ \chi_1 \end{array} \right) = \left( \begin{array}{c} 0 \\ 0 \end{array} \right). \end{equation*}

    By examination,

    \begin{equation*} \tilde v_1 = \left( \begin{array}{c} -\sqrt{2} \\ 1 \end{array} \right) \end{equation*}

    is an eigenvector. However, we would like it to have length one:

    \begin{equation*} v_1 = \tilde v_1 / \| \tilde v_1 \|_2 = \tilde v_0 / \sqrt{3} = \frac{1}{\sqrt{3}} \left( \begin{array}{c} -\sqrt{2} \\ 1 \end{array} \right) = \left( \begin{array}{c} -\sqrt{6}/3\\ \sqrt{3}/3 \end{array} \right). \end{equation*}

We conclude that \(V = \left( \begin{array}{c c} v_0 \amp v_1 \end{array} \right) \) and

\begin{equation*} A^T A = V \Sigma^2 V^T = \left( \begin{array}{c c} \sqrt{3}/3 \amp -\sqrt{6}/3 \\ \sqrt{6}/3 \amp \sqrt{3}/3 \end{array} \right) \left( \begin{array}{c c} 2 \amp 0 \\ 0 \amp 1 \end{array} \right)^2 \left( \begin{array}{c c} \sqrt{3}/3 \amp -\sqrt{6}/3 \\ \sqrt{6}/3 \amp \sqrt{3}/3 \end{array} \right)^T \end{equation*}

is the Spectral Decomposition of \(A \text{.}\) (Recall that the eigenvectors corresponding to distinct eigenvalues of a symmetric matrix are orthogonal and we have chosen the eigenvectors to have length one. Hence, \(V \) is a unitary matrix.) We thus now know \(V \) and \(\Sigma \text{.}\)

Since \(A = U \Sigma V^T \) we know that

\begin{equation*} \begin{array}{rcl} U = A V \Sigma^{-1} \amp= \amp \left( \begin{array}{c c} \sqrt{2} \amp 1 \\ 0 \amp \sqrt{2} \end{array} \right) \left( \begin{array}{c c} \sqrt{3}/3 \amp -\sqrt{6}/3 \\ \sqrt{6}/3 \amp \sqrt{3}/3 \end{array} \right) \left( \begin{array}{c c} 1/2 \amp 0 \\ 0 \amp 1 \end{array} \right) \\ \amp= \amp \left( \begin{array}{c c} 2\sqrt{6}/3 \amp -\sqrt{3}/3 \\ 2 \sqrt{3}/3 \amp \sqrt{6}/3 \end{array} \right) \left( \begin{array}{c c} 1/2 \amp 0 \\ 0 \amp 1 \end{array} \right) \\ \amp= \amp \left( \begin{array}{c c} \sqrt{6}/3 \amp -\sqrt{3}/3\\ \sqrt{3}/3 \amp \sqrt{6}/3 \end{array} \right) \end{array} \end{equation*}

so that

\begin{equation*} \begin{array}[t]{c} \underbrace{ \left( \begin{array}{c c} \sqrt{2} \amp 1 \\ 0 \amp \sqrt{2} \end{array} \right)} \\ A \end{array} = \begin{array}[t]{c} \underbrace{ \left( \begin{array}{c c} \sqrt{6}/3 \amp -\sqrt{3}/3\\ \sqrt{3}/3 \amp \sqrt{6}/3 \end{array} \right) } \\ U \end{array} \begin{array}[t]{c} \underbrace{ \left( \begin{array}{c c} 2 \amp 0 \\ 0 \amp 1 \end{array} \right) } \\ \Sigma \end{array} \begin{array}[t]{c} \underbrace{ \left( \begin{array}{c c} \sqrt{3}/3 \amp -\sqrt{6}/3 \\ \sqrt{6}/3 \amp \sqrt{3}/3 \end{array} \right)^T.} \\ V^T \end{array} \end{equation*}