## Subsection11.2.1Computing the SVD from the Spectral Decomposition

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

###### Homework11.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.

###### Homework11.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.

###### Homework11.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 Subsection 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?

###### Homework11.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*}