Computing an SVD in Full, Economy and Compact Forms

Definition Let $A$ be a real $m \times n$ matrix and $q = \min(m, n)$. The $n \times n$ matrix $A^{\top}A$ is symmetric with $\mathbf{x}^{\top}A^{\top}A\mathbf{x} = \lVert A\mathbf{x} \rVert^2 \ge 0$, so by the spectral theorem it has an orthonormal basis of eigenvectors $\mathbf{v}_1, \dots, \mathbf{v}_n$ with eigenvalues $\lambda_1 \ge \cdots \ge \lambda_n \ge 0$. The computation runs as follows. Find these eigenvalues and orthonormal eigenvectors in decreasing order of eigenvalue, and take the singular values $\sigma_i = \sqrt{\lambda_i}$ for $i = 1, \dots, q$. Then, for every $i$ with $\sigma_i > 0$, set

These vectors are automatically orthonormal, since $\mathbf{u}_i \cdot \mathbf{u}_j = \sigma_j^2\,(\mathbf{v}_i \cdot \mathbf{v}_j) / (\sigma_i\sigma_j)$, which is $1$ for $i = j$ and $0$ otherwise. One may start from the $m \times m$ matrix $AA^{\top}$ instead, which has the same positive eigenvalues with the same multiplicities and is smaller when $m < n$. Its orthonormal eigenvectors for those eigenvalues give the $\mathbf{u}_i$, the partners are $\mathbf{v}_i = A^{\top}\mathbf{u}_i / \sigma_i$, and the remaining right singular vectors come from an orthonormal basis of $\operatorname{Null} A$. Either way, the second vector of each pair is computed from the first, never found separately.

Definition Let $A$ be a real $m \times n$ matrix of rank $r$. The formula $A\mathbf{v}_i / \sigma_i$ produces left singular vectors only for the $r$ positive singular values, and it cannot be used when $\sigma_i = 0$, because division by zero is undefined and the image $A\mathbf{v}_i = \mathbf{0}$ points in no direction. A full SVD needs $m$ left singular vectors. Completing the basis means extending $\mathbf{u}_1, \dots, \mathbf{u}_r$ to an orthonormal basis $\mathbf{u}_1, \dots, \mathbf{u}_m$ of $\mathbb{R}^m$, for instance by finding a basis of the orthogonal complement and applying Gram-Schmidt. The added vectors are perpendicular to $\operatorname{span}\{\mathbf{u}_1, \dots, \mathbf{u}_r\} = \operatorname{Col} A$, so they form an orthonormal basis of the left null space $\operatorname{Null} A^{\top}$, which has dimension $m - r$. Any such choice works. On the input side nothing extra is needed, because the eigenvectors of $A^{\top}A$ for the eigenvalue $0$ already give an orthonormal basis $\mathbf{v}_{r+1}, \dots, \mathbf{v}_n$ of $\operatorname{Null} A^{\top}A = \operatorname{Null} A$.

Definition A full SVD of a real $m \times n$ matrix $A$ is a factorization $A = U\Sigma V^{\top}$ with $U$ an $m \times m$ orthogonal matrix, $\Sigma$ an $m \times n$ rectangular diagonal matrix with diagonal entries $\sigma_1 \ge \cdots \ge \sigma_q \ge 0$ where $q = \min(m, n)$, and $V$ an $n \times n$ orthogonal matrix. To build one, take the $\mathbf{v}_i$ and $\sigma_i$ from $A^{\top}A$, form $\mathbf{u}_i = A\mathbf{v}_i / \sigma_i$ for the positive singular values, complete the left singular vectors to an orthonormal basis of $\mathbb{R}^m$, and place the columns of $U$ and $V$ in the same order as the singular values on the diagonal of $\Sigma$. Because it keeps complete bases of both spaces, a full SVD of a matrix of rank $r$ displays all four fundamental subspaces. The vectors $\mathbf{u}_1, \dots, \mathbf{u}_r$ span $\operatorname{Col} A$, the vectors $\mathbf{u}_{r+1}, \dots, \mathbf{u}_m$ span $\operatorname{Null} A^{\top}$, the vectors $\mathbf{v}_1, \dots, \mathbf{v}_r$ span $\operatorname{Row} A$, and the vectors $\mathbf{v}_{r+1}, \dots, \mathbf{v}_n$ span $\operatorname{Null} A$.

Definition Let $A$ be a nonzero real $m \times n$ matrix of rank $r$ with full SVD $A = U\Sigma V^{\top}$, and let $q = \min(m, n)$. The economy SVD keeps the first $q$ columns of $U$ and of $V$,

with $U_q$ of size $m \times q$, $\Sigma_q = \operatorname{diag}(\sigma_1, \dots, \sigma_q)$ of size $q \times q$ including any zero singular values, and $V_q$ of size $n \times q$. The compact SVD keeps only the positive singular values,

with $U_r$ of size $m \times r$, $\Sigma_r = \operatorname{diag}(\sigma_1, \dots, \sigma_r)$ of size $r \times r$, and $V_r$ of size $n \times r$. Both products equal $A$ exactly, because the dropped columns of $U$ and $V$ meet only zero rows or zero columns of $\Sigma$. The rectangular factors have orthonormal columns, so $U_q^{\top}U_q = I_q$ and $V_r^{\top}V_r = I_r$, but $U_qU_q^{\top}$ is not the identity when $q < m$. Books and software use these names differently, and some call one of the two forms reduced or thin, so check the sizes and whether zero singular values are kept.

Definition A proposed full SVD $(U, \Sigma, V)$ of a real $m \times n$ matrix $A$ is correct exactly when four things hold. The sizes are $m \times m$, $m \times n$ and $n \times n$. The equations $U^{\top}U = I_m$ and $V^{\top}V = I_n$ hold. The matrix $\Sigma$ is rectangular diagonal with entries $\sigma_1 \ge \cdots \ge \sigma_q \ge 0$. Finally, the product $U\Sigma V^{\top}$ equals $A$. Since $V$ is invertible, the last condition is equivalent to $AV = U\Sigma$, that is,

Two matrices that agree on a basis agree everywhere, so checking these $n$ products is enough. For an economy or compact form, make the same checks with the smaller sizes. The rectangular factors need orthonormal columns, and in the compact form every diagonal entry of $\Sigma$ must be positive. When the kept $V$ has fewer than $n$ columns, those columns are not a basis of $\mathbb{R}^n$, so agreement on them is not enough and the product has to be multiplied out. For the $2 \times 3$ matrix $A$ of the first card, taking $U = \Sigma = I_2$ and the columns $\mathbf{e}_1$ and $\mathbf{e}_2$ for $V$ satisfies $A\mathbf{v}_i = \sigma_i\mathbf{u}_i$ for both columns, yet $U\Sigma V^{\top}$ has rows $(1, 0, 0)$ and $(0, 1, 0)$ and is not $A$.

Definition The singular values of a matrix are determined by the matrix, but its singular vectors are not. Replacing a pair $(\mathbf{u}_i, \mathbf{v}_i)$ by $(-\mathbf{u}_i, -\mathbf{v}_i)$ always gives another SVD. If a positive singular value $\sigma$ occurs $k > 1$ times, the matching right singular vectors may be any orthonormal basis of the eigenspace of $A^{\top}A$ for $\sigma^2$, with partners $\mathbf{u}_i = A\mathbf{v}_i / \sigma$. In a full SVD of a matrix of rank $r$, the vectors $\mathbf{v}_{r+1}, \dots, \mathbf{v}_n$ may be any orthonormal basis of $\operatorname{Null} A$, and $\mathbf{u}_{r+1}, \dots, \mathbf{u}_m$ any orthonormal basis of $\operatorname{Null} A^{\top}$. What stays fixed is, for each distinct positive singular value, the subspace spanned by its right singular vectors and the subspace spanned by its left ones, together with the two kernels. When the positive singular values are distinct, each pair $(\mathbf{u}_i, \mathbf{v}_i)$ with $\sigma_i > 0$ is unique up to one common sign.