Outer Products and Low-Rank Approximation

Definition Let $\mathbf{x}$ be a vector in $\mathbb{R}^m$ and $\mathbf{y}$ a vector in $\mathbb{R}^n$. Their outer product is the $m \times n$ matrix $\mathbf{x}\mathbf{y}^{\top}$, the product of an $m \times 1$ column and a $1 \times n$ row. Its entries are $(\mathbf{x}\mathbf{y}^{\top})_{ij} = x_i y_j$, its $j$th column is $y_j\mathbf{x}$, and its $i$th row is $x_i\mathbf{y}^{\top}$. For every $\mathbf{z}$ in $\mathbb{R}^n$, associativity of the matrix product gives

The order of the factors matters. When $m = n \ge 2$, the product $\mathbf{y}^{\top}\mathbf{x}$ in the other order is a $1 \times 1$ matrix, the inner product $\mathbf{y} \cdot \mathbf{x}$, which is a number rather than an $n \times n$ matrix.

Definition An $m \times n$ matrix has rank one when its column space has dimension $1$. If $\mathbf{x} \ne \mathbf{0}$ in $\mathbb{R}^m$ and $\mathbf{y} \ne \mathbf{0}$ in $\mathbb{R}^n$, the outer product $\mathbf{x}\mathbf{y}^{\top}$ has rank one, with

Every output is a multiple of $\mathbf{x}$, and every multiple $c\mathbf{x}$ is reached, for instance by the input $c\,\mathbf{y}/(\mathbf{y} \cdot \mathbf{y})$. Since $\mathbf{x} \ne \mathbf{0}$, the output $(\mathbf{y} \cdot \mathbf{z})\,\mathbf{x}$ is zero exactly when $\mathbf{y} \cdot \mathbf{z} = 0$, so the null space consists of the inputs perpendicular to $\mathbf{y}$ and has dimension $n - 1$. Conversely, every $m \times n$ matrix of rank one equals $\mathbf{x}\mathbf{y}^{\top}$ for some nonzero vectors $\mathbf{x}$ in $\mathbb{R}^m$ and $\mathbf{y}$ in $\mathbb{R}^n$. Indeed, if $\mathbf{x}$ spans the column space, each column is a multiple $y_j\mathbf{x}$, and the coefficients $y_j$ form a nonzero vector $\mathbf{y}$. The pair is not unique, since $(c\mathbf{x})(\mathbf{y}/c)^{\top} = \mathbf{x}\mathbf{y}^{\top}$ for every $c \ne 0$. If $\mathbf{x} = \mathbf{0}$ or $\mathbf{y} = \mathbf{0}$, the outer product is the zero matrix, which has rank zero.

Definition Let $A$ be a real $m \times n$ matrix of rank $r \ge 1$ with compact singular value decomposition $A = U_r\Sigma_r V_r^{\top}$. Here $\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_r > 0$ are the positive singular values, and $\mathbf{u}_1, \dots, \mathbf{u}_r$ in $\mathbb{R}^m$ and $\mathbf{v}_1, \dots, \mathbf{v}_r$ in $\mathbb{R}^n$ are orthonormal left and right singular vectors with $A\mathbf{v}_i = \sigma_i\mathbf{u}_i$. Multiplying the factors column by row gives

Each term $\sigma_i\mathbf{u}_i\mathbf{v}_i^{\top}$ is a rank-one matrix, here called a singular layer. Applied to an input $\mathbf{z}$ in $\mathbb{R}^n$, the expansion reads

The zero matrix, of rank $0$, is the empty sum.

Definition Let $A$ have the expansion of the previous card, with singular values in decreasing order, and let $k$ be an integer with $0 \le k \le r$. The truncated SVD of rank $k$ keeps the first $k$ layers,

where $U_k$ and $V_k$ hold the first $k$ left and right singular vectors as columns and $\Sigma_k = \operatorname{diag}(\sigma_1, \dots, \sigma_k)$. It has rank exactly $k$. The truncation $A_0$ is the zero matrix, $A_r = A$, and for $k > r$ one sets $A_k = A$. The discarded part is

The truncation agrees with $A$ on $\operatorname{span}\{\mathbf{v}_1, \dots, \mathbf{v}_k\}$ and on $\operatorname{Null} A$, and it sends $\mathbf{v}_{k+1}, \dots, \mathbf{v}_r$ to $\mathbf{0}$. Storing $U_k$, $\Sigma_k$ and $V_k$ takes $k(m + n + 1)$ numbers instead of $mn$, and applying $A_k$ to a vector takes $k$ dot products, $k$ scalings and one combination of $k$ vectors. When $\sigma_k = \sigma_{k+1}$, the matrix $A_k$ depends on which singular vectors were chosen, a case treated in the last card.

Definition For a real $m \times n$ matrix $A$ with entries $a_{ij}$, the Frobenius norm and the spectral norm are

The Frobenius norm is the length of $A$ viewed as a list of $mn$ numbers, and $\lVert A \rVert_F^2 = \operatorname{tr}(A^{\top}A)$. The spectral norm is the induced Euclidean norm, the largest stretch of a unit input. If $A$ has positive singular values $\sigma_1 \ge \cdots \ge \sigma_r$, then

and both norms of the zero matrix are $0$. The Frobenius formula holds because the entrywise inner product $\langle B, C \rangle = \sum_{i,j} b_{ij}c_{ij}$ of two outer products is $\langle \mathbf{p}\mathbf{q}^{\top}, \mathbf{s}\mathbf{t}^{\top} \rangle = (\mathbf{p} \cdot \mathbf{s})(\mathbf{q} \cdot \mathbf{t})$. Distinct layers $\mathbf{u}_i\mathbf{v}_i^{\top}$ of an SVD are therefore perpendicular, each has Frobenius norm $1$, and the Pythagorean theorem adds the numbers $\sigma_i^2$. The spectral formula holds because for a unit input $\mathbf{z}$ the coordinates $c_i = \mathbf{v}_i \cdot \mathbf{z}$ satisfy $\sum_i c_i^2 \le 1$, so $\lVert A\mathbf{z} \rVert^2 = \sum_i \sigma_i^2 c_i^2 \le \sigma_1^2$, with equality at $\mathbf{z} = \mathbf{v}_1$. In particular $\lVert A \rVert_2 \le \lVert A \rVert_F \le \sqrt{r}\,\lVert A \rVert_2$.

Definition Let $A$ be a real $m \times n$ matrix of rank $r$ with singular values $\sigma_1 \ge \cdots \ge \sigma_r > 0$, and let $k$ be an integer with $0 \le k < r$. For every real $m \times n$ matrix $B$ with $\operatorname{rank} B \le k$,

So the truncated SVD $A_k$ is a best approximation of rank at most $k$ in both norms, a result often called the Eckart-Young theorem. When $k \ge r$, the matrix $A$ itself has rank at most $k$ and the error is $0$. The equalities on the right come from the previous card, because $A - A_k$ has singular values $\sigma_{k+1}, \dots, \sigma_r$. The spectral inequality has a short proof. The subspace $\operatorname{span}\{\mathbf{v}_1, \dots, \mathbf{v}_{k+1}\}$ has dimension $k + 1$ and $\operatorname{Null} B$ has dimension at least $n - k$, so the two subspaces share a unit vector $\mathbf{z}$. Then $(A - B)\mathbf{z} = A\mathbf{z}$, and $\lVert A\mathbf{z} \rVert \ge \sigma_{k+1}$ because $\mathbf{z}$ is a unit combination of $\mathbf{v}_1, \dots, \mathbf{v}_{k+1}$. The Frobenius inequality needs a longer argument.

Uniqueness depends on the cutoff. Let $1 \le k < r$. If $\sigma_k > \sigma_{k+1}$, the truncation $A_k$ is the only best approximation in the Frobenius norm. If $\sigma_k = \sigma_{k+1}$, the singular values are tied at the cutoff. The cutoff then splits a group of equal singular values whose singular vectors can be chosen in many ways, and different choices give different truncations, all best approximations with the same errors. The spectral norm is less selective. Its best approximations are never unique for these $k$, because each kept $\sigma_i$ may be replaced by any number within $\sigma_{k+1}$ of it without raising the spectral error.