singular value decomposition

Data

subject:: Matrix Analysis
parent:: Chapter 7
theme:: math notes

[[dg-publish]]

Definitions

Theorem (Matrix Analysis 1)

Singular Value Decomposition

Let $A \in M_{m, n}$ such that $m \leq n$ . Then there exists $U \in M_{n}$ unitary, $Σ \in M_{m}$ diagonal, and $W \in M_{m, n}$ with orthonormal rows such that

A = U Σ W

WLOG, we assume the diagonal elements of $Σ$ are nonnegative and ordered in a non-increasing.

Proof

Note that $A A^{*}$ is hermitian and therefore positive semidefinite. So there exists $U \in M_{n}$ unitary and $D \in M_{n}$ diagonal such that $A A^{*} = U D U^{*}$ by the spectral theorem for hermitian matrices. Call the columns of $U = [u_{1} | u_{2} | \dots | u_{m}]$

Say each of the elements in $D$ are called $σ_{i i}^{2} \geq 0$ (we can do this because each eigenvector of $A A^{*}$ is real).

Say $A$ is rank $k$ . Then let $σ_{k} > 0, σ_{k + 1} = 0$ and define $Σ$ to be the $m \times m$ matrix containing the ordered $σ_{i}$ s.

For $i = 1, \dots, k$ , define the $i$ th row of $W$ to be $\frac{1}{σ_{i}} u_{i}^{*} A$ . These are orthonormal since for all $i, j$ we have $\frac{(}{1} σ_{i} u_{i}^{*} A) \frac{1}{σ_{j} u_{j}^{*} A} = u_{i}^{*} A A^{*} u_{j} = \frac{1}{σ_{i} σ_{j}} D_{i j}$ and this is $1$ if $i = j$ and $0$ otherwise.

For $i = k + 1, \dots, m$ , define the rows of $W$ any way you like, so long as they are orthonormal and orthogonal to the first $k$ rows of $W$ . And thus we are done! We have

U^{*} A = Σ W ⟹ A = U Σ W

For rows $1, \dots, k$ equality holds by construction. For rows $k + 1, \dots, m$ , we have $A A^{*} u_{i} = 0$ since each $u_{i}$ is an eigenvector with eigenvalues $0$ for $A A^{*}$ . Thus we have $u_{i}^{*} A A^{*} u_{i} = 0 = | | u_{i}^{*} A | |_{2}^{2} ⟹ u_{i}^{*} A = 0 =$ the $i$ th row of $W$ . So LHS = RHS = 0.

Note that if $A$ is real, we can take $U, Σ, W$ real.

Theorem (Matrix Analysis 2)

Theorem (Singular Value Decomposition)

For any $A \in M_{m, n}$ , there exists $U \in M_{m}$ , $V \in M_{n}$ both unitary and $Σ \in M_{m, n}$ "diagonal" with $min {m, n}$ real, nonnegative, nonincreasing, entries such that

A = U Σ V^{*}

Further, if $A$ is real-valued, we can take each of $U, Σ, V$ to be real.

(we take "diagonal" to mean that the only entries that can be nonzero have the same row and column index)

Note

We can think of this as a generalization of diagonalization/spectral decomposition, but where the loss is that $U$ and $V$ are distinct.
if $A$ is positive semidefinite, then the diagonalization is the singular value decomposition since we have that $A = U Σ U^{*}$ for some unitary $U$ and nonnegative $Σ$ all real.

Proof

If $m \leq n$ , then by the previous definition here we have $A = U Σ W$ where $U \in M_{n}$ unitary, $Σ \in M_{m}$ diagonal, and $W \in M_{m, n}$ with orthogonal columns. Since $m \leq n$ , we add $n - m$ columns of zeros to $Σ$ to make it size $m \times n$ . Then we can append $n - m$ orthogonal rows to $W$ with Gram-Schmidt to get a $V^{*}$

If $n > m$ , then $A^{*} = U Σ V^{*}$ is SVD by the above case. But then $A = V Σ^{T} U^{*}$ is an SVD of $A$ !

Another Definition (Data Science)

Singular Value Decomposition

The Singular Value Decomposition of a matrix $X \in C^{n \times m}$ is the unique factorization such that

X = U Σ V^{*}

Where $U \in C^{n \times n}, V \in C^{m \times m}$ are unitary and orthonormal. A unitary matrix $U$ is one such that $U^{*} U = U U^{*} = I$ . The columns of $U$ are called the left singular vectors of $X$ , and the columns of $V$ are called the right singular vectors. The entries of $Σ$ are called the singular values

the columns of $U$ are the same "shape" as the columns of $X$ . They give me a basis where I can represent the columns of my data matrix $X$

This means that the columns of $U$ can be reshaped into "eigen"representations of instances of the data

The columns of $V^{*}$ are the "mixtures" of the columns of $U$ that we need in order to reproduce each of the instances of the dataset

Notes on SVD

Say $A \in M_{m, n}$ and $A \in U Σ V^{*}$ its SVD. Suppose there are $k$ non-negative singular values call them $σ_{1}, \dots, σ_{k}$ . Denote $u_{1}, \dots u_{m}$ the columns of $U$ and $v_{1}^{*}, \dots, v_{n}^{*}$ the rows of $V^{*}$ . Then

$A = U Σ V^{*} = \sum_{i = 1}^{k} σ_{i} u_{i} v_{i}^{*}$
$rank (A) = rank (Σ) = k$
$range (A) = span {u_{1}, \dots, u_{k}}$ - easy to see from (1)
$null (A) = span (v_{k + 1}, \dots, v_{n})$ - easy to see from (1)
$range (A^{*}) = span {v_{1}, \dots, v_{k}}$
$null (A^{*}) = span {u_{k + 1}, \dots, u_{m}}$
For any $A \in M_{m, n}$ , we have $| | A | |_{2, 2} := max_{x \in C^{n} \neq 0} \frac{| | A x | |_{2}}{| | x | |_{2}} = σ_{1}$
$| | A | |_{F}^{2} = | | U Σ V^{*} | |_{F}^{2} = | | Σ | |_{F}^{2} = \sum_{i = 1}^{k} σ_{i}$

To see (5) and (6) , recall that $A^{*} = V Σ^{T} U^{*}$ and we simply apply (3) and (4) in this case.

To see (7), note that

| | A | |_{2, 2}^{2} = max_{x \neq 0} \frac{| | A x | |_{2}}{| | x | |_{2}} = max \frac{x^{*} A^{*} A x}{x^{*} x} =^{*, * *} σ_{1}^{2}

Note $*$ is by Rayleigh-Ritz that this equals the largest eigenvalue of $A^{*} A$ .
Then $* *$ is by the fact that the eigenvalues of $A^{*} A = (U Σ V^{*})^{*} (U Σ V^{*}) = V Σ Σ^{*} V^{*}$ - ie the eigenvalues are the squared singular values of $A$ .

Mentions

File
Moore-Penrose inverse
Notes on SVD - from Brunton and Kutz
Procrustes Notes
polar decomposition
singular value decomposition
the psuedoinverse gives the least norm solution to the least squares problem
Lecture 19
Lecture 20
Lecture 21
Lecture 22
Lecture 26
Lecture 36
Section 09
my obsidian vault