singular value decomposition

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

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

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$ .

References

singular value decomposition

Definitions

Theorem (Matrix Analysis 1)

Theorem (Matrix Analysis 2)

Another Definition (Data Science)

References

See Also

Mentions