SVD: Singular Value Decomposition

Yao Yao on September 13, 2018

这次我们从结论出发反推。

SVD 即任意 matrix $A$ 都可以分解为:

其中:

  • $U_{m \times m}$ is orthogonal
    • $UU^T = I_{m \times m}$
  • $D_{m \times n}$ is diagonal
    • 因为 $D$ 不一定是 square,所以不一定有 $D = D^T$
  • $V_{n \times n}$ is orthogonal
    • $VV^T = I_{n \times n}$

当 $m = n$ 时,你可以把 eigen-decomposition 看成是 SVD 的特殊情况。

注意到可以有如下两式:

这个很像是 eigen-decomposition 啊……对的,它其实就是 eigen-decomposition!

所以我们先 eigen-decompose $AA^T$ 得到 $U$,然后 eigen-decompose $A^TA$ 得到 $V$。但是如何从 $DD^T$ 和 $D^TD$ 中确定 $D$?下面详细说。

1. Gram matrix

A Gram matrix of vectors $\mathbf{a}_1, \dots, \mathbf{a}_n$ is a matrix $G$ whose $G_{ij} = \mathbf{a}_i^T \mathbf{a}_j$.

If matrix $A_{m \times n} = [\mathbf{a}_1 \, \dots \, \mathbf{a}_n]$, then $G_{n \times n}=A^TA$

A Gram matrix is positive definite and symmetric.

2. Rank–nullity theorem

我们在 Kernel in Linear Algebra / Inner Product Space / Hyperplane / SVM / Kernel Function / Normed vector space / Metric Space 里其实讲到了这个 Rank–nullity theorem,但是我当时还不知道它可以和 eigen-decomposition 联系起来。

假设有一个线性变换 $L: V \to W$,那么 rank-nullity theorem 说:

我们把 matrix $A_{m \times n}$ 看成一个线性变换 $A: \mathbb{R}^n \to \mathbb{R}^m$,那么 rank-nullity theorem 可以表示为:

然后关键来了:

  • The nullity is the dimension of the kernel of the matrix.
  • 然后 kernel 可以看成什么?kernel 其实就是 eigenvalue $\lambda = 0$ 的 eigenspace 呀
  • 所以 $\operatorname{rank}(A) = n - \dim(E_{\lambda=0; A})$

3. Rank of $AA^T$ and $A^TA$

首先一点:$\operatorname{rank}(A) = \operatorname{rank}(A^T)$。证明就不细说了,思路是:

  1. $\operatorname{rank}(A) = \operatorname{ColumnRank}(A) = \operatorname{RowRank}(A)$
  2. 然后 $\operatorname{ColumnRank}(A) = \operatorname{RowRank}(A^T)$。

所以必定有 $\operatorname{rank}(AA^T) = \operatorname{rank}(A^TA)$

我们可以进一步证明 $\operatorname{rank}(AA^T) = \operatorname{rank}(A^TA) = \operatorname{rank}(A)$,参考 Prove rank $AA^T$ = rank A for any $A_{m \times n}$

根据 rank-nullity theorem:

假设 $m > n$,那么 $m - n = \operatorname{nullity}(AA^T) - \operatorname{nullity}(A^TA)$,这个值说明什么?说明针对同一个 eigenvalue $\lambda=0$,$AA^T$ 比 $A^TA$ 多了 $m-n$ 个 eigenvectors。

问题来了:

  • 如果不考虑 uniqueness 的话,能否说明 $AA^T$ 比 $A^TA$ 多 $m-n$ 个值为 0 的 eigenvalues?
    • 答案是可以,但是你不能用 “针对同一个 eigenvalue $\lambda=0$,$AA^T$ 比 $A^TA$ 多了 $m-n$ 个 eigenvectors” 这个理由,因为 eigenvector 的数量是 geometric multiplicity
    • 而 eigenvalue 的数量是 algebraic multiplicity
  • 那么其他 $\neq 0$ 的 eigenvalues 的情况如何?

看下一节

4. Sylvester’s determinant identity

If $A$ and $B$ are matrices of size $m \times n$ and $n \times m$ respectively, then

我们借此研究一下 characteristic polynomial of $AA^T$:

Amazing!我们可以推论 (记得我们仍然在 $m > n$ 的大前提下):

  • 如果 $\lambda \neq 0$ 是 $A^T A$ ($n \times n$) 的 eigenvalue $\rightarrow$ 那它也一定是 $AA^T$ ($m \times m$) 的 eigenvalue
    • 且 algebraic multiplicity 相同
  • $A^T A$ ($n \times n$) 不一定有 $\lambda=0$ 的 eigenvalue
  • 假设 $A^T A$ ($n \times n$) 中 eigenvalue $\lambda=0$ 的 algebraic multiplicity 为 $m_0$ ($m_0 = 0$ 表示 no such eigenvalue) $\rightarrow$ $AA^T$ ($m \times m$) 中 eigenvalue $\lambda=0$ 的 algebraic multiplicity 为 $m_0 + m - n$
  • 换言之,$A^T A$ and $AA^T$ share the same non-zero eigenvalues!

5. SVD

我们回头看 $DD^T$ 和 $D^TD$。它俩都是 diagonal 因为 $D$ 本身是 diagonal。考虑到

  • $DD^T$ 对角线上是 $AA^T$ 的 eigenvalues (且按惯例是降序排列,下同)
  • $D^TD$ 对角线上是 $A^TA$ 的 eigenvalues

所以 $DD^T$ 和 $D^TD$ 虽然维度不同,但也只是 “对角线上有 0 / 无 0” 和 “对角线上 0 多 / 0 少” 的区别。

考虑到 $D_{m \times n}$ 是 diagonal,所以它应该只需要 $A^T A$ 的 $n$ 个 eigenvalue 就可以确定了。那么它的对角线上的值到底是多少呢?

  • 考虑 general 的情况,sigular value 的个数应该是 $\min(m, n)$

考虑到 $A^T A$ 是 positive definite,所以它的 non-zero eigenvalues 必定为 positive。所以我们定义 singular value $\sigma_i = \sqrt{\lambda_i}$ with $D_{ii} = \sigma_i$ and $D^TD = \operatorname{diag}(\lambda_1, \dots, \lambda_n)$ being $A^T A$’s eigenvalue matrix

然后有:

  • $AA^T$ 的 eigenvectors (即 $U$ 的 columns) 称为 $A$ 的 left singular vectors
  • $A^TA$ 的 eigenvectors (即 $V$ 的 columns) 称为 $A$ 的 right singular vectors

一个题外话:Theorem: If $\mathbf{q}$ is an eigenvector of $AA^T$, then $A^T \mathbf{q}$ is an eigenvector of $A^TA$.

Proof:



blog comments powered by Disqus