Introduction to singular value decomposition特異値分解とくいちぶんかいSVD

1Introduction

The key point of this lecture is that singular value decomposition特異値分解とくいちぶんかいSVD decomposes a matrix, not necessarily square, into orthogonal changes of coordinates and stretching along coordinate axes.

eigenvalues固有値こゆうち and diagonalization mainly concern square matrices. In applications, rectangular matrices are common. SVD is the standard decomposition that works for every real or complex matrix.

SVD separates the input-side orthonormal basis基底きてい, the output-side orthonormal basis基底きてい, and the nonnegative scale factors. This lets rank階数かいすう, least squares, pseudoinverses, and low-rank階数かいすう approximation be described in one framework.

2Terms and definitions

For a real $m\times n$m\times n matrix $A$A, a singular value decomposition特異値分解とくいちぶんかい is

where $U$U is an $m\times m$m\times m orthogonal matrix, $V$V is an $n\times n$n\times n orthogonal matrix, and $\mathrm{\Sigma }$\Sigma is an $m\times n$m\times n matrix with nonnegative diagonal entries.

The diagonal entries

are the singular values特異値とくいち of $A$A.

For complex matrices,

with unitary $U$U and $V$V.

3Plan

Study $A^{T}A$A^TA in the real case and $A^{*}A$A^*A in the complex case. These matrices are symmetric or Hermitian and positive semidefinite. Therefore they can be orthogonally or unitarily diagonalized.

The reason for looking at $A^{*}A$A^*A is that, for every $x$x,

Thus $A^{*}A$A^*A is Hermitian and positive semidefinite, so its eigenvalues固有値こゆうち are nonnegative real numbers. In the real case we write

and in the complex case

The singular values特異値とくいち of $A$A are the square roots of these nonnegative eigenvalues:

4Intuitive explanation

SVD decomposes the action of $A$A as

Orthogonal or unitary factors preserve lengths and angles. The matrix $\mathrm{\Sigma }$\Sigma is the only part that changes lengths. Thus singular values特異値とくいち measure how much $A$A stretches each principal input direction.

5Precise explanation

5.11. Right singular vectors from $A^{T}A$A^TA or $A^{*}A$A^*A

In the real case, $A^{T}A$A^TA is symmetric. Choose an orthonormal eigenbasis $v_1,\dots ,v_n$v_1,\ldots,v_n:

These $v_i$v_i are the right singular vectors. In the complex case,

5.22. Constructing left singular vectors

For ${\sigma }_i>0$\sigma_i>0, define

Then the $u_i$u_i are orthonormal:

Using $A^{*}A{v}_i={\sigma }_{i^2}{v}_i$A^*Av_i=\sigma_i^2v_i and the orthonormality of the $v_i$v_i, this equals ${\delta }_{ij}$\delta_{ij}. Extend these $u_i$u_i to an orthonormal basis基底きてい of the output space to obtain $U$U.

The left singular vectors are also eigenvectors固有こゆうベクトル of $A{A}^T$AA^T in the real case:

and of $A{A}^{*}$AA^* in the complex case.

5.33. rank階数かいすう

The rank階数かいすう of $A$A is the number of nonzero singular values特異値とくいち:

Small singular values特異値とくいち indicate directions that are strongly compressed and often contribute to numerical instability.

5.44. Compact SVD and fundamental subspaces

If $\mathrm{rank}\left(A\right)=r$\operatorname{rank}(A)=r, keeping only positive singular values特異値とくいち gives the compact SVD

in the real case, and $A=U_r{\mathrm{\Sigma }}_r{V}_{r^{*}}$A=U_r\Sigma_rV_r^* in the complex case.

The columns of $U_r$U_r form an orthonormal basis基底きてい of $\mathrm{Col}\left(A\right)$\operatorname{Col}(A). The columns of $V_r$V_r form an orthonormal basis基底きてい of the row space行空間ぎょうくうかん. Right singular vectors for ${\sigma }_i=0$\sigma_i=0 span $\ker \left(A\right)$\ker(A), and left singular vectors for zero singular values特異値とくいち span $\ker \left(A^T\right)$\ker(A^T) or $\ker \left(A^{*}\right)$\ker(A^*).

5.55. Low-rank階数かいすう approximation

Keeping only the largest $k$k singular values特異値とくいち gives

in the real case, and $v_{i^{*}}$v_i^* in the complex case. By the Eckart-Young theorem, $A_k$A_k is the closest matrix to $A$A among matrices of rank階数かいすう at most $k$k:

This supports compression and denoising, but discarding small singular values特異値とくいち also discards information. If a small-singular-value direction contains meaningful signal, truncation must be used carefully.

6Concrete examples

For

we may take

The singular values特異値とくいち are $3$3 and $1$1.

For a general matrix, $V^T$V^T first rotates the input space into principal directions, $\mathrm{\Sigma }$\Sigma stretches those directions, and $U$U places the result in the output space.

For a non-diagonal example,

Then

whose eigenvalues固有値こゆうち are

Therefore the singular values特異値とくいち are

Although $A$A has only the eigenvalue固有値こゆうち $1$1, its singular values特異値とくいち record how lengths are stretched by $A$A. SVD is not a replacement for eigenvalues固有値こゆうち; it measures a different and often more stable geometric quantity.

7Another viewpoint

Singular value decompositionSVD特異値分解とくいちぶんかい is the basis of the least squares method最小二乗法さいしょうにじょうほう and the pseudoinverse matrix擬似逆行列ぎじぎゃくぎょうれつ. Even when $A$A is not invertible, one can invert only the directions with nonzero singular values and thereby define the minimum-norm solution.

8Criteria

• Singular values特異値とくいち are the square roots of the eigenvalues固有値こゆうち of $A^{T}A$A^TA or $A^{*}A$A^*A.
• The number of nonzero singular values is the rank階数かいすう.
• SVD applies to rectangular matrices as well as square matrices.
• Small singular values特異値とくいち are related to compression and numerical instability.
• Compact SVD simultaneously describes the column space列空間れつくうかん, row space行空間ぎょうくうかん, and kernel核かく.

9Scope

SVD holds for every real or complex matrix. Unlike eigendecomposition, it does not require the matrix to be square or diagonalizable.

10Existence theorem and proof outline

For every real $m\times n$m\times n matrix $A$A, there exist orthogonal matrices直交行列ちょっこうぎょうれつ $U,V$U,V and an $m\times n$m\times n matrix $\mathrm{\Sigma }$\Sigma with nonnegative diagonal entries such that

For a complex matrix,

The proof is based on the spectral theorem for $A^{T}A$A^TA or $A^{*}A$A^*A. The matrix $A^{*}A$A^*A is Hermitianエルミート and

so it is positive semidefinite. Hence it has an orthonormal eigenbasis $v_i$v_i with nonnegative eigenvalues固有値こゆうち ${\lambda }_i$\lambda_i. Set ${\sigma }_i=\sqrt{{\lambda }_i}$\sigma_i=\sqrt{\lambda_i}, and for ${\sigma }_i>0$\sigma_i>0 define

Then

so the $u_i$u_i are mutually orthogonal直交ちょっこう and have length $1$1. Completing the remaining $u_i$u_i gives $U$U. This construction explains the existence of the SVD.

11Correspondence of fundamental subspaces

SVD organizes the four fundamental subspaces基本部分空間きほんぶぶんくうかん at the same time.

Therefore SVD describes not only the rank階数かいすう, but also the directions in which solutions are lost, the projection射影しゃえい onto the column space列空間れつくうかん, and least-squares solutions最小二乗解さいしょうにじょうかい.

12Another viewpoint

SVD is the foundation of the least squares method最小二乗法さいしょうにじょうほう and the pseudoinverse matrix擬似逆行列ぎじぎゃくぎょうれつ. Even when $A$A is not invertible可逆かぎゃく, nonzero singular directions can be inverted while zero singular directions are treated as lost information.

13Calculation example: a non-diagonal $$2\times 2$$2\times2 matrix

Consider

Then

and the eigenvalues固有値こゆうち are

Therefore the singular values特異値とくいち are

Here the eigenvalue固有値こゆうち of $A$A itself is $1$1 with multiplicity two, but the singular values特異値とくいち measure a different quantity as square roots of the eigenvalues of $A^{T}A$A^TA. In other words, SVD is not a substitute for eigenvalues固有値こゆうち; it is a decomposition分解ぶんかい that measures how much lengths in input directions are stretched.

14Criteria

• singular values特異値とくいち are square roots of eigenvalues固有値こゆうち of $A^{T}A$A^TA or $A^{*}A$A^*A.
• The number of nonzero singular values特異値とくいち is the rank階数かいすう.
• SVD applies to rectangular matrices.
• Small singular values特異値とくいち indicate compression and possible numerical instability.
• Compact SVD describes column space列空間れつくうかん, row space行空間ぎょうくうかん, and kernels simultaneously.

15Meaning and cautions of low-rank approximation

The Eckart-Young theorem定理ていり states that

obtained by keeping only the top $k$k singular values特異値とくいち is the closest matrix to $A$A among all matrices of rank階数かいすう at most $k$k. However, cutting off small singular values特異値とくいち also means throwing away information. This is useful for denoising and compression, but caution is necessary when the directions of small singular values特異値とくいち contain meaningful signal.

16Scope and limitations

SVD exists for every real or complex matrix. Unlike eigenvalue decomposition固有値分解こゆうちぶんかい, it does not assume squareness or diagonalizability. However, the singular values特異値とくいち alone do not capture sign, phase, or eigenvector固有こゆうベクトル behavior; they describe length stretching.

17Final forms

18In one sentence

Singular value decomposition特異値分解とくいちぶんかいSVD is the standard form that decomposes any matrix into orthogonal coordinate changes and axis-wise stretching.

19Exercise link

20Related links