The Singular Value Decomposition

Definition Let $\mathbb{F}$ be $\mathbb{R}$ or $\mathbb{C}$ and let $A \in \mathbb{F}^{m \times n}$. The Gram operator of $A$ is the $n \times n$ matrix $A^{*}A$, which acts on the input space $\mathbb{F}^n$. Over $\mathbb{R}$ it is $A^{\mathsf{T}}A$. If $a_1, \dots, a_n$ are the columns of $A$, then $(A^{*}A)_{ij} = \langle a_i, a_j \rangle$, so it is the Gram matrix of the columns. For every $x \in \mathbb{F}^n$

The matrix $A^{*}A$ is Hermitian, since $(A^{*}A)^{*} = A^{*}A$, and this identity makes it positive semidefinite. Its eigenvalues are real and nonnegative, since $A^{*}Av = \lambda v$ with $v \ne 0$ gives $\lambda \lVert v \rVert^2 = \lVert Av \rVert^2$. Its kernel equals $\ker A$. If $Ax = 0$, then $A^{*}Ax = 0$. If $A^{*}Ax = 0$, then $\lVert Ax \rVert^2 = x^{*}A^{*}Ax = 0$, so $Ax = 0$. By rank-nullity, $\operatorname{rank}(A^{*}A) = \operatorname{rank} A$. None of this needs $A$ to be square or normal. For a linear map $T \colon V \to W$ between finite-dimensional inner product spaces, the Gram operator is $T^{*}T \colon V \to V$, and the same proofs apply.

Definition Let $A \in \mathbb{F}^{m \times n}$ and $p = \min(m, n)$. List the eigenvalues of $A^{*}A$ with multiplicity in decreasing order, $\lambda_1 \ge \cdots \ge \lambda_n \ge 0$. The singular values of $A$ are the nonnegative square roots

so that $\sigma_1 \ge \cdots \ge \sigma_p \ge 0$. The diagonalizable matrix $A^{*}A$ has as many positive eigenvalues as its rank, which is $\operatorname{rank} A \le p$. So all positive eigenvalues are among $\lambda_1, \dots, \lambda_p$, and the number $r$ of positive singular values equals $\operatorname{rank} A$. When $n > m$, the remaining eigenvalues $\lambda_{p+1}, \dots, \lambda_n$ are therefore all zero. Their eigenvectors lie in $\ker A$, and these zeros are not counted as extra singular values. The singular values depend only on $A$, and they are real and nonnegative even when the eigenvalues of a square $A$ are negative or not real.

Definition Let $A \in \mathbb{F}^{m \times n}$ have rank $r$ and singular values $\sigma_1 \ge \cdots \ge \sigma_r > 0$, all others zero. By the spectral theorem for the Hermitian matrix $A^{*}A$, choose an orthonormal basis $v_1, \dots, v_n$ of $\mathbb{F}^n$ with $A^{*}Av_i = \sigma_i^2 v_i$ for $i \le r$ and $A^{*}Av_i = 0$ for $i > r$. These are right singular vectors. For $i \le r$ the left singular vectors are

which needs $\sigma_i > 0$. They are orthonormal, because

which is $1$ for $i = j$ and $0$ otherwise. Expanding $x = \sum_i \langle v_i, x \rangle v_i$ gives $Ax = \sum_{i \le r} \sigma_i \langle v_i, x \rangle u_i$, so $u_1, \dots, u_r$ span $\operatorname{im} A$. Complete them with an orthonormal basis $u_{r+1}, \dots, u_m$ of $\ker A^{*}$, which is the orthogonal complement of $\operatorname{im} A$, since $\langle Ax, y \rangle = \langle x, A^{*}y \rangle$ vanishes for every $x$ exactly when $A^{*}y = 0$. The two lists satisfy

So $u_1, \dots, u_r$ is an orthonormal basis of $\operatorname{im} A$, $u_{r+1}, \dots, u_m$ of $\ker A^{*}$, $v_1, \dots, v_r$ of $\operatorname{im} A^{*}$, and $v_{r+1}, \dots, v_n$ of $\ker A$.

Definition Let $\mathbb{F}$ be $\mathbb{R}$ or $\mathbb{C}$, $A \in \mathbb{F}^{m \times n}$ and $p = \min(m, n)$. A singular value decomposition of $A$ is a factorization

with $U \in \mathbb{F}^{m \times m}$ and $V \in \mathbb{F}^{n \times n}$ unitary and $\Sigma \in \mathbb{R}^{m \times n}$ rectangular diagonal, with $\Sigma_{ii} = \sigma_i$ for $i \le p$, $\sigma_1 \ge \cdots \ge \sigma_p \ge 0$, and every other entry $0$. The theorem says that every $A \in \mathbb{F}^{m \times n}$ has a singular value decomposition and that the diagonal of $\Sigma$ is always the list of singular values of $A$. When $A$ is real, $U$ and $V$ can be chosen real orthogonal, giving $A = U\Sigma V^{\mathsf{T}}$. For existence, put the vectors constructed above into $U = [u_1 \ \cdots \ u_m]$ and $V = [v_1 \ \cdots \ v_n]$. Then

and multiplying on the right by $V^{*} = V^{-1}$ gives $A = U\Sigma V^{*}$. If $r = 0$, then $A = 0$, $\Sigma = 0$ and any unitary $U$ and $V$ work. Conversely, any such factorization gives $A^{*}A = V(\Sigma^{\mathsf{T}}\Sigma)V^{*}$, so the squared diagonal entries of $\Sigma$ are eigenvalues of $A^{*}A$ and the diagonal is forced. Multiplying out gives a sum of rank-one matrices,

Also $A^{*} = V\Sigma^{\mathsf{T}}U^{*}$ is a singular value decomposition of $A^{*}$, so $A$ and $A^{*}$ have the same singular values.

Definition Let $A = U\Sigma V^{*}$ be a full singular value decomposition of $A \in \mathbb{F}^{m \times n}$, with rank $r$ and $p = \min(m, n)$. Write $U_k$ and $V_k$ for the first $k$ columns of $U$ and $V$, and $\Sigma_k = \operatorname{diag}(\sigma_1, \dots, \sigma_k)$. In each of the three forms $A$ is the product of the left factor, the middle factor and the adjoint of the right factor.

The thin SVD $A = U_p\Sigma_pV_p^{*}$ holds because the columns it drops meet only zero rows or columns of $\Sigma$, and it still contains zero singular values when $r < p$. The compact SVD

keeps only the positive singular values, so $\Sigma_r$ is invertible when $r \ge 1$. When $r = 0$ its factors are empty and the product is read as the zero matrix. The narrow factors have orthonormal columns, so $U_r^{*}U_r = I_r$ and $V_r^{*}V_r = I_r$, but $U_rU_r^{*}$ is the orthogonal projector onto $\operatorname{im} A$ and equals $I_m$ only when $r = m$. Books use the words reduced, thin and economy in different ways, so it is safest to state the shapes.

Definition Let $A = U\Sigma V^{*}$ be a singular value decomposition of $A \in \mathbb{F}^{m \times n}$ of rank $r$. Let $\sigma > 0$ be a singular value that occurs exactly $k$ times, and let $U_\sigma \in \mathbb{F}^{m \times k}$ and $V_\sigma \in \mathbb{F}^{n \times k}$ hold the matching columns of $U$ and $V$. For every unitary $Q \in \mathbb{F}^{k \times k}$, real orthogonal if the decomposition is to stay real, replacing $U_\sigma$ by $U_\sigma Q$ and $V_\sigma$ by $V_\sigma Q$ gives another singular value decomposition, because

For $k = 1$ this multiplies $u_i$ and $v_i$ by the same scalar $c$ with $\lvert c \rvert = 1$, which is a sign $\pm 1$ in a real decomposition. Separately, the last $m - r$ columns of $U$ may be replaced by any orthonormal basis of $\ker A^{*}$, and the last $n - r$ columns of $V$ by any orthonormal basis of $\ker A$, chosen independently. Every singular value decomposition of $A$ arises from a given one by these changes. What $A$ does determine are the singular values, the subspaces $\ker(A^{*}A - \sigma^2 I)$ and $\ker(AA^{*} - \sigma^2 I)$ for each $\sigma > 0$, and each block $\sigma U_\sigma V_\sigma^{*}$.