Singular Value Decomposition

Extra note · SVD Lecture Notes · page 1

Supplement supplied separately; wording and calculations retained as written.

Singular Value Decomposition (SVD)

For a real $m\times n$ matrix $\mA$, the product $\mA^T\mA$ is symmetric and positive semi-definite, so it can be diagonalized by an orthogonal matrix: \[\mA^T\mA=\mV\mLambda\mV^T\quad\text{where }\mV^T\mV=\mI_n,\quad\mLambda=\operatorname{diag}(\sigma_1^2,\ldots,\sigma_n^2),\quad\sigma_1\ge\sigma_2\ge\cdots\ge\sigma_n\ge0.\]

Now look at what $\mA\mA^T$ does to the vector $\mA\vv_k$: \[(\mA\mA^T)\mA\vv_k=\mA(\mA^T\mA\vv_k)=\sigma_k^2\,\mA\vv_k.\] Thus $\mA\vv_k$ is an eigenvector of the symmetric positive semi-definite matrix $\mA\mA^T$ with eigenvalue $\sigma_k^2$, provided $\mA\vv_k\ne\nul$. Write $\mA\vv_k=\alpha_k\uu_k$ with $\|\uu_k\|=1$. Taking norms, \[\|\mA\vv_k\|^2=|\alpha_k|^2\ \Rightarrow\ \vv_k^T\underbrace{\mA^T\mA\vv_k}_{\sigma_k^2\vv_k}=|\alpha_k|^2\ \Rightarrow\ \alpha_k=\sigma_k\text{ is a solution}.\]

So $\mA\vv_k=\sigma_k\uu_k$ for every $k$. Putting all $n$ of these equations side by side, \[\mA[\vv_1\ \cdots\ \vv_n]=[\uu_1\sigma_1\ \uu_2\sigma_2\ \cdots\ \uu_n\sigma_n]=[\uu_1\ \cdots\ \uu_n]\underbrace{\mSigma}_{\operatorname{diag}(\sigma_1,\ldots,\sigma_n)}\] \[\Rightarrow\mA\mV=\mU\mSigma\ \Rightarrow\ \mA=\mU\mSigma\mV^T.\] If $\sigma_k=0$, then $\mA\vv_k=\nul$ and the formula $\uu_k=\mA\vv_k/\sigma_k$ does not define $\uu_k$. Such columns can be completed with any orthonormal vectors, or simply dropped, as in the final form below.

For the non-zero singular values the vectors $\uu_k$ are automatically orthonormal. Indeed, for $\sigma_k>0$ and $\sigma_i>0$, \begin{align*} \uu_k^T\uu_i&=\frac1{\sigma_k}\vv_k^T\mA^T\mA\frac1{\sigma_i}\vv_i=\frac1{\sigma_k\sigma_i}\vv_k^T\underbrace{(\mA^T\mA)\vv_i}_{\sigma_i^2\vv_i}\\ &=\frac{\sigma_i}{\sigma_k}\vv_k^T\vv_i=\begin{cases}1&\text{if }k=i\\0&\text{if }k\ne i.\end{cases} \end{align*} Final form. Keeping only the $r$ non-zero singular values, the matrix is a sum of $r$ rank-one pieces:

The SVD in its final form

\[\mA=\sum_{i=1}^r\sigma_i\uu_i\vv_i^T,\quad\text{where $r$ is the number of non-zero singular values $\sigma_i$.}\] \[\mA=\mU_r\mSigma_r\mV_r^T,\quad\mU_r=[\uu_1\ \cdots\ \uu_r],\quad\mSigma_r=\operatorname{diag}(\sigma_1,\ldots,\sigma_r),\quad\mV_r=[\vv_1,\ldots,\vv_r].\]

Extra note · SVD SUMMARY · page 1

Supplement supplied separately; wording and calculations retained as written.

SVD (Singular Value Decomposition)

Definition. A real $m\times n$ matrix $\mA$ of rank $r$ can be written in the “reduced” form

Reduced SVD

\[\mA_{m\times n}=\mU\mSigma\mV^T,\qquad\mSigma=\col{\sigma_1&0&\cdots&0\\0&\sigma_2&&\vdots\\\vdots&&\sigma_3&\vdots\\0&\cdots&0&\sigma_r}_{r\times r}.\]

The numbers $\sigma_i$ are the singular values of $\mA$, ordered as $\sigma_1\ge\sigma_2\ge\sigma_3\ge\cdots\ge\sigma_r>0$. The columns of $\mU$ and $\mV$ are orthonormal bases of the column space and the row space: \[\mU_{m\times r}=[\uu_1\ \cdots\ \uu_r],\quad\text{where $\{\uu_1,\uu_2,\ldots,\uu_r\}$ is an ON basis for }\operatorname{Col}(\mA),\] \[\mV_{n\times r}=[\vv_1\ \cdots\ \vv_r],\quad\text{where $\{\vv_1,\vv_2,\ldots,\vv_r\}$ is an ON basis for }\operatorname{Row}(\mA).\]

Scaling Effect of $\Sigma$

The matrix of singular values acts as a pure scaling: it stretches or shrinks each coordinate separately. To see this, start from $\mA\xx=\yy$ with $\xx\in\R^n$ and $\yy\in\R^m$, and multiply by $\mU^T$: \[\mA_{m\times n}\underbrace{\xx}_{\in\R^n}=\underbrace{\yy}_{\in\R^m}\quad\xrightarrow{\times\mU^T}\quad\mU^T\mA\xx=\mU^T\yy\] \[\Rightarrow\underbrace{\mU^T\mU}_{\mI}\mSigma\mV^T\xx=\mU^T\yy\] \[\Rightarrow\mSigma\underbrace{\mV^T\xx}_{\widetilde{\xx}}=\underbrace{\mU^T\yy}_{\widetilde{\yy}}\ \Rightarrow\ \mSigma\widetilde{\xx}=\widetilde{\yy}.\] In the rotated coordinates $\widetilde{\xx}=\mV^T\xx$ and $\widetilde{\yy}=\mU^T\yy$ the map is diagonal:

Scaling effect, componentwise

\[\sigma_i\widetilde{x}_i=\widetilde{y}_i.\]

So the directions $\vv_i$ in the input space are sent to the directions $\uu_i$ in the output space, and a singular value $\sigma_i>1$ stretches along that direction while $\sigma_i<1$ shrinks it.

The Matrix as a Sum of Rank-One Pieces

Multiplying out the three factors, \[\mA=[\uu_1\ \cdots\ \uu_r]\col{\sigma_1&\cdots&0\\&\sigma_2&\\0&\cdots&\sigma_r}\col{\vv_1^T\\\vdots\\\vv_r^T}=\sum_{i=1}^r\sigma_i\uu_i\vv_i^T.\] Each term $\sigma_i\uu_i\vv_i^T$ is a rank-one matrix, and together they add up to a matrix of rank $r$. Keeping only the terms with the largest $\sigma_i$ gives the best low-rank approximation of $\mA$.

Extra note · SVD SUMMARY · page 2

Supplement supplied separately; wording and calculations retained as written.

Derivation of the Singular Vectors

Let $\mW=\mA^T\mA$. Then $\mW\in\R^{n\times n}$ and $\mW=\mW^T$.

1) The vectors $\vv_i$ (row space)

Start from $\mA=\mU\mSigma\mV^T$, which gives $\mA^T=\mV\mSigma^T\mU^T$. Multiplying, \[\begin{gathered}\mA=\mU\mSigma\mV^T\\\mA^T=\mV\mSigma^T\mU^T\end{gathered}\quad\Rightarrow\quad\mA^T\mA=\mV\underbrace{\mSigma^T}_{=\mSigma}\underbrace{\mU^T\mU}_{\mI}\mSigma\mV^T.\]

\[\mA^T\mA=\mV\mSigma^2\mV^T.\] Multiplying on the right by $\mV$ and using $\mV^T\mV=\mI$ (the $\vv_i$’s are orthonormal), \[\Rightarrow\mA^T\mA\mV=\mV\mSigma^2\underbrace{\mV^T\mV}_{\mI}=\mV\mSigma^2.\] Reading this column by column, \[(\mA^T\mA)\vv_i=\vv_i\lambda_i,\qquad\lambda_i=\sigma_i^2.\] So the eigenvalues of $\mA^T\mA$ are the squares of the singular values, and the columns $\vv_i$ of $\mV$ are the corresponding eigenvectors of $\mA^T\mA$. We order them by eigenvalue: if $\lambda_1\ge\lambda_2\ge\lambda_3\ge\cdots\ge\lambda_n$, then $\vv_1$ is the eigenvector for $\lambda_1$, and so on.

2) The vectors $\uu_i$ (column space)

From $\mA=\mU\mSigma\mV^T$ we get $\mA\mV=\mU\mSigma$, and column by column $\mA\vv_i=\uu_i\sigma_i$. Hence

The left singular vectors

\[\uu_i=\frac{\mA\vv_i}{\sigma_i},\]

and these form an orthonormal basis for $\operatorname{Col}(\mA)$. Each $\uu_i$ must be listed in the same order as its partner $\vv_i$, so that the pairs $(\uu_i,\vv_i)$ share the singular value $\sigma_i$.

Blog