ConceptLinear Algebra used inDBISAI-written · not yet proofread

Singular Value Decomposition

Also SVD · Singular Values · Truncated SVD · Reduced SVD · Low-Rank Approximation · Rank-k Approximation · Singulärwertzerlegung

The singular value decomposition factors any matrix A ∈ ℝ^{m×n} of rank r as A = UΣVᵀ with orthogonal U, V and a diagonal Σ holding the singular values σ₁ ≥ … ≥ σ_r > 0; keeping the k largest gives the best rank-k approximation of A.

Know these firstEigenvector Matrix Rank

Definition

Let $A \in \mathbb{R}^{m \times n}$ with $r = \operatorname{rank}(A)$ . A singular value decomposition (SVD) of $A$ is a factorization

A = U \Sigma V^\top

with an orthogonal $U \in \mathbb{R}^{m \times m}$ ( $U^\top U = I_m$ ), an orthogonal $V \in \mathbb{R}^{n \times n}$ ( $V^\top V = I_n$ ) and a rectangular diagonal $\Sigma \in \mathbb{R}^{m \times n}$ with $\Sigma_{ii} = \sigma_i$ and $\Sigma_{ij} = 0$ for $i \neq j$ , where

\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_r > 0 = \sigma_{r+1} = \dots

The $\sigma_i$ are the singular values, the columns $u_i$ of $U$ the left-singular vectors and the columns $v_j$ of $V$ the right-singular vectors. Every real matrix has an SVD (MML Thm. 4.22).

Reduced (compact) SVD. Dropping the zero singular values and the vectors they multiply gives

A = U_r S V_r^\top, \qquad U_r \in \mathbb{R}^{m \times r},\; S = \operatorname{diag}(\sigma_1, \dots, \sigma_r) \in \mathbb{R}^{r \times r},\; V_r \in \mathbb{R}^{n \times r},

where $U_r$ and $V_r$ are column-orthonormal ( $U_r^\top U_r = V_r^\top V_r = I_r$ ) and $S$ is invertible.

Formula#

Construction from eigenvectors (MML §4.5.2). Inserting the SVD into the two Gram matrices:

A^\top A = V\, \Sigma^\top \Sigma\, V^\top, \qquad A A^\top = U\, \Sigma \Sigma^\top\, U^\top.

Both are symmetric and positive semidefinite, so:

the right-singular vectors $v_i$ are orthonormal eigenvectors of $A^\top A$ ,
the left-singular vectors $u_i$ are orthonormal eigenvectors of $A A^\top$ ,
the nonzero eigenvalues of both are $\lambda_i = \sigma_i^2$ , so $\sigma_i = \sqrt{\lambda_i}$ .

The two sides are linked by

u_i = \frac{1}{\sigma_i} A v_i, \qquad v_i = \frac{1}{\sigma_i} A^\top u_i \quad (i \le r), \qquad\text{i.e.}\qquad V_r^\top = S^{-1} U_r^\top A.

Outer-product form:

A = \sum_{i=1}^{r} \sigma_i\, u_i v_i^\top,

a sum of $r$ rank-1 matrices weighted by the singular values (MML (4.91)).

Rank- $k$ approximation (truncated SVD). For $k \le r$ keep the $k$ largest singular values:

A_k = U_k S_k V_k^\top = \sum_{i=1}^{k} \sigma_i\, u_i v_i^\top,

with $U_k$ , $V_k$ the first $k$ columns of $U$ , $V$ and $S_k = \operatorname{diag}(\sigma_1, \dots, \sigma_k)$ . Storing $A_k$ in factored form takes $k(m + n + 1)$ numbers instead of $mn$ .

Properties#

Rank: $\operatorname{rank}(A)$ = number of nonzero singular values (Matrix Rank).
Uniqueness: the singular values are unique. If they are pairwise distinct, each $u_i$ , $v_i$ is unique up to a common sign flip.
$U^\top U$ vs. $U U^\top$ : for the reduced $U_r \in \mathbb{R}^{m \times r}$ , $U_r^\top U_r = I_r$ always holds (orthonormal columns). $U_r U_r^\top \in \mathbb{R}^{m \times m}$ has rank $r$ , so it equals $I_m$ only if $r = m$ . In general $U_r U_r^\top$ is the orthogonal projection onto the column space $\operatorname{im}(A)$ .
Inverting the factorization: since $U_r^\top U_r = I_r$ and $S$ is invertible, $A = U_r S V_r^\top$ gives $V_r^\top = S^{-1} U_r^\top A$ (DBIS notation: $V = S^{-1} U^\top A$ ).
Symmetric PSD matrices: for $A = A^\top \succcurlyeq 0$ the SVD is the eigendecomposition, $U = V$ and $\sigma_i = \lambda_i$ (MML p. 123).
Pseudo inverse: $A^+ = V_r S^{-1} U_r^\top$ (MSI script Def. 10).

Example#

ExampleSVD of a $2 \times 2$ matrix and its rank-1 approximation

A = \begin{pmatrix} 2 & 2 \\ 1 & -1 \end{pmatrix}, \qquad A A^\top = \begin{pmatrix} 8 & 0 \\ 0 & 2 \end{pmatrix}.

Eigenvalues of $AA^\top$ : $8$ and $2$ , so $\sigma_1 = 2\sqrt{2}$ , $\sigma_2 = \sqrt{2}$ . Eigenvectors: $u_1 = e_1$ , $u_2 = e_2$ , so $U = I$ .
$V^\top = S^{-1} U^\top A = \begin{pmatrix} \tfrac{1}{2\sqrt2} & 0 \\ 0 & \tfrac{1}{\sqrt2} \end{pmatrix} \begin{pmatrix} 2 & 2 \\ 1 & -1 \end{pmatrix} = \frac{1}{\sqrt2}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$ , whose rows are orthonormal.
Rank-1 approximation: $A_1 = \sigma_1 u_1 v_1^\top = 2\sqrt2 \cdot e_1 \cdot \tfrac{1}{\sqrt2}(1, 1) = \begin{pmatrix} 2 & 2 \\ 0 & 0 \end{pmatrix}$ .
Error: $A - A_1 = \begin{pmatrix} 0 & 0 \\ 1 & -1 \end{pmatrix}$ has spectral norm $\sqrt2 = \sigma_2$ , as Eckart–Young predicts.

Sources#

MML p. 119 (Thm. 4.22: SVD theorem, singular values and vectors), MML pp. 122–125 (§4.5.2: construction from $A^\top A$ and $AA^\top$ , $\sigma_i^2 = \lambda_i$ , $u_i = Av_i/\sigma_i$ )
MML p. 129 (reduced SVD, truncated SVD, rank-1 matrices $u_i v_i^\top$ ), MML p. 130 (outer-product form (4.91), rank- $k$ approximation), MML pp. 131–132 (spectral norm, Thm. 4.24, Eckart–Young Thm. 4.25)
Use in DBIS: Latent Semantic Indexing (rank- $k$ approximation of the term-document matrix, LSI Ranking); exams WS 16/17 Task 5 (not published), WS 17/18 Task 5 (not published), WS 19/20 Task 5.1 (not published), WS 22/23 Task 5.2 (not published)
Use in MSI: MSI script p. 34 (Def. 9: SVD, Def. 10: Moore–Penrose pseudo inverse)