singular value decomposition (SVD)

Jung, Alexander

The singular value decomposition (SVD) factors any matrix into an orthogonal matrix, a matrix that is zero off its main diagonal, and a second orthogonal matrix. For ${\mathbf A} \in \mathbb{R}^{m \times d}$ it reads ${\mathbf A} = \mathbf{V} \boldsymbol{\Lambda} \mathbf{U}^{\top}$, and the nonnegative diagonal entries of $\boldsymbol{\Lambda}$ are the singular values. In contrast to an eigenvalue decomposition (EVD), which only exists for a square diagonalizable matrix, an SVD exists for every matrix. Truncating the SVD after the $k$ largest singular values yields the best approximation by a matrix of rank $k$, which underlies dimensionality reduction. For linear regression, the SVD of the feature matrix splits the objective into one term per singular value plus an irreducible remainder. The solution with the smallest Euclidean norm divides each component of the label vector along a left singular vector by the matching singular value. The SVD delivers the pseudoinverse, the spectral norm, and the condition number of a matrix.

Definition

P-existA grayscale photograph with $m$ rows and $d$ columns of pixels is stored as a matrix of $m \times d$ intensities, that is, $m d$ numbers. Most photographs can be stored with far fewer numbers: keeping only the $k$ largest of the singular values of that matrix, defined below, costs $k (m + d + 1)$ numbers. The SVD of a matrix ${\mathbf A} \in \mathbb{R}^{m \times d}$ is a factorization of the form \[ {\mathbf A} = \mathbf{V} {\boldsymbol \Lambda} \mathbf{U}^{\top} \text{,} \] with orthogonal matrices (Golub and Loan, 2013), whose columns are orthonormal vectors, \[ \mathbf{V} = \big({\mathbf v}^{(1)},\,\ldots,\,{\mathbf v}^{(m)}\big) \in \mathbb{R}^{m \times m}, \qquad \mathbf{U} = \big( {\mathbf u}^{(1)},\,\ldots,\,{\mathbf u}^{(d)} \big) \in \mathbb{R}^{d \times d} \text{.} \] The matrix ${\boldsymbol \Lambda} \in \mathbb{R}^{m \times d}$ is zero off the main diagonal, whose entries $\Lambda_{j,j} = \lambda_{j} \geq 0$ are referred to as singular values and ordered as $\lambda_{1} \geq \lambda_{2} \geq \ldots \geq 0$. The columns ${\mathbf u}^{(j)}$ of $\mathbf{U}$ are the right singular vectors and the columns ${\mathbf v}^{(j)}$ of $\mathbf{V}$ the left singular vectors; both families are orthonormal. Multiplying the factorization by ${\mathbf u}^{(j)}$ gives ${\mathbf A} {\mathbf u}^{(j)} = \lambda_{j} {\mathbf v}^{(j)}$. The matrix ${\mathbf A}$ therefore maps each right singular vector ${\mathbf u}^{(j)}$ to the left singular vector ${\mathbf v}^{(j)}$ scaled by the singular value $\lambda_{j}$ (see Fig. 1).

P-lowrankRetaining only the $k$ largest singular values yields the truncated SVD \[ \widehat{{\mathbf A}} := \sum_{j=1}^{k} \lambda_{j} {\mathbf v}^{(j)} \big({\mathbf u}^{(j)}\big)^{\top} \text{,} \] a matrix of rank at most $k$. Among all matrices ${\mathbf B}$ of rank at most $k$, the truncation $\widehat{{\mathbf A}}$ minimizes the approximation error $\left\lVert {\mathbf A} - {\mathbf B} \right\rVert_{\mathrm{F}}$ (Eckart and Young, 1936).

This property is what makes the truncation useful for storing the photograph of the opening. No matrix of rank at most $k$ is closer to ${\mathbf A}$, so the truncation loses as little as any storage by a rank-$k$ matrix can. It requires only the $k$ largest singular values with their left and right singular vectors, that is, $k (m + d + 1)$ numbers instead of $m d$ (pythondemos/svd.py).

Principal component analysis (PCA) is the same truncation applied to a centered feature matrix ${\mathbf X} \in \mathbb{R}^{m \times d}$: a linear dimensionality reduction that replaces each feature vector by its coordinates along the $k$ directions of largest variance. The right singular vectors ${\mathbf u}^{(j)}$ of ${\mathbf X}$ are the eigenvectors of the sample covariance matrix $\frac{1}{m} {\mathbf X}^{\top} {\mathbf X}$, whose eigenvalues are $\lambda_{j}^{2}/m$. PCA therefore projects each data point onto the leading ${\mathbf u}^{(1)},\,\ldots,\,{\mathbf u}^{(k)}$.

The SVD can also be used to analyze and to implement linear regression methods. Consider a feature matrix ${\mathbf X} \in \mathbb{R}^{m \times d}$, whose $r$-th row is the feature vector of the $r$-th data point, and a label vector ${\mathbf y} \in \mathbb{R}^{m}$. Linear regression minimizes the squared Euclidean norm $\left\lVert {\mathbf X} {\mathbf w} - {\mathbf y} \right\rVert_{2}^{2}$ of the residual over the model parameters ${\mathbf w}$. That is the empirical risk minimization (ERM) objective for the squared error loss, the least squares problem.

Let $p$ be the number of nonzero singular values of ${\mathbf X}$, its rank. A component of ${\mathbf w}$ along a right singular vector ${\mathbf u}^{(j)}$ with $j > p$ leaves ${\mathbf X} {\mathbf w}$ unchanged, so expanding ${\mathbf w} = \sum_{j=1}^{p} \widetilde{w}^{(j)} {\mathbf u}^{(j)}$ in the leading right singular vectors loses nothing. With ${\mathbf X} {\mathbf u}^{(j)} = \lambda_{j}{\mathbf v}^{(j)}$ and the orthonormality of the left singular vectors ${\mathbf v}^{(j)}$, the objective of linear regression reads \[ \begin{aligned} \left\lVert {\mathbf X} {\mathbf w} - {\mathbf y} \right\rVert_{2}^{2} &= \left\lVert \textstyle\sum_{j=1}^{p} \lambda_{j}\widetilde{w}^{(j)} {\mathbf v}^{(j)} - {\mathbf y} \right\rVert_{2}^{2} \\ &= \sum_{j=1}^{p} \big(\lambda_{j}\widetilde{w}^{(j)} - ({\mathbf v}^{(j)})^{\top}{\mathbf y}\big)^{2} + \sum_{j=p+1}^{m} \big(({\mathbf v}^{(j)})^{\top}{\mathbf y}\big)^{2} \text{.} \end{aligned} \]

P-pinvThe objective of linear regression depends on ${\mathbf y}$ only through its components $({\mathbf v}^{(j)})^{\top}{\mathbf y}$ along the left singular vectors. The second sum is the constant, irreducible error from the part of ${\mathbf y}$ outside the column space of ${\mathbf X}$. The first sum is minimized termwise at $\widehat{w}^{(j)} = ({\mathbf v}^{(j)})^{\top}{\mathbf y} / \lambda_{j}$ for $j \leq p$. In matrix form, this is $\widehat{{\mathbf w}} = {{\mathbf X}}^{+} {\mathbf y}$ with the pseudoinverse ${{\mathbf X}}^{+} = \mathbf{U} {{\boldsymbol \Lambda}}^{+} \mathbf{V}^{\top}$, where ${{\boldsymbol \Lambda}}^{+}$ inverts the nonzero singular values. The vector $\widehat{{\mathbf w}}$ is the solution of linear regression with the smallest Euclidean norm. A small singular value divides the corresponding component of ${\mathbf y}$ by a small number, which is why the condition number of ${\mathbf X}$ determines how noise in ${\mathbf y}$ enters $\widehat{{\mathbf w}}$. That matters because the least squares objective is a proxy: the goal is a small squared error on data points outside the training set (see generalization), and noise amplified into $\widehat{{\mathbf w}}$ is carried to every such data point.

singular value decomposition (SVD)

Definition

References

Cite this entry