Singular value decomposition

Singular value decomposition (SVD) says that any $n\times m$ matrix can be decomposed into a product of three different matrices, $A=U\Sigma V^T$.

• $U$: some $n\times n$ orthogonal matrix, where the columns are the left-singular vectors.
• $\Sigma$: an $n\times m$ matrix where the first $r=\text{rank}(A)$ diagonal entries are the non-zero singular values ${\sigma }_1,\dots ,{\sigma }_r\ge 0$ of $A$, where all other entries are $0$.
• $V$: some $m\times n$ orthogonal matrix, where the columns are the right-singular vectors.

We can alternatively express SVD in a different way, where $\overrightarrow{u_i}$ and $\overrightarrow{v_i}$ are the columns of $U$ and $V$, respectively. Notice below why it’s useful.

$$A={\sigma }_1\overrightarrow{u_1}{\overrightarrow{v_1}}^T+\dots +{\sigma }_r\overrightarrow{u_r}{\overrightarrow{v_r}}^T$$

We define the singular values of $A$ as the square roots of the eigenvalues of the symmetric $m\times m$ matrix $A^{T}A$. We represent them in decreasing order.

Theorems

Every real matrix has a singular value decomposition, which makes SVD more broadly applicable than eigendecomposition.

Applications

The singular values of $A$ encode some interesting information. For example, a useful application of SVD is to compress data. Since the singular values continue to decrease, and many of the values are small relative to ${\sigma }_1$, we can save (maybe) the first 20 terms of $A$ instead of all the terms (of ${\mathbb{R}}^n$, which can be very large) and still come out with relatively high quality data.

We can also use SVD to compute the pseudoinverse of a non-square matrix, via the Moore-Penrose pseudoinverse algorithm.

Computations

In MATLAB, we have related functions:

• S = svd(A) saves the singular values of A in descending order.
• [U,S,V] = svd(A) performs the singular value decomposition of A and saves the corresponding matrices according to the above.

In NumPy, we can use np.linalg.svd(A), which returns a tuple with the attributes U, S, and Vh.