数学：SVD分解[1]——原理

Preface 前言

SVD (Singular Value Decomposition) 在机器学习等其他领域有着非常广泛的应用，本文主要是受到计算机图像学课和以前看到的材料的启发，希望对SVD有更深入的了解。

相关的pdf资料可以参见我github上的记录。本文行文基本上是对它的翻译和理解。

Preparation

我们先叙述一些名词和涉及到的线性代数中的一些看法。

非齐次线性方程组 ${Ax=b}$ 的计算可以有两种形式，这取决于我们对矩阵具体含义的看法。

如计算：

{ \left[ \begin{matrix} 1 & 3 \\ -3 & 2 \\ \end{matrix} \right] \times \left[ \begin{matrix} 3 \\ 1 \end{matrix} \right] }

我们一般习惯的计算方式是row-way： ${a_{i,j}}$ 是左矩阵的 ${i}$ 行和右矩阵的 ${j}$ 列对应相乘求和，即：

{ \left[ \begin{matrix} 1 & 3 \\ -3 & 2 \\ \end{matrix} \right] \times \left[ \begin{matrix} 3 \\ 1 \end{matrix} \right] = \left[ \begin{matrix} \left[ \begin{matrix} 1 & 3 \end{matrix} \right] \times \left[ \begin{matrix} 3 \\ 1 \end{matrix} \right] \\ \left[ \begin{matrix} -3 & 2 \end{matrix} \right] \times \left[ \begin{matrix} 3 \\ 1 \end{matrix} \right] \end{matrix} \right] = \left[ \begin{matrix} 6 \\ 7 \end{matrix} \right] }

column-way将矩阵看成列向量组，我们得到的结果 ${b}$ 就是列向量组的线性组合，系数为 ${x}$ 。

{ \left[ \begin{matrix} 1 & 3 \\ -3 & 2 \\ \end{matrix} \right] \times \left[ \begin{matrix} 3 \\ 1 \end{matrix} \right] = 3 \times \left[ \begin{matrix} 1 \\ -3 \end{matrix} \right] + 1 \times \left[ \begin{matrix} 3 \\ 1 \end{matrix} \right] = \left[ \begin{matrix} 6 \\ 7 \end{matrix} \right] }

Column-Way使得我们将求解非齐次线性方程组 ${Ax=b}$ 看成用列向量组 ${A}$ 表出 ${b}$ ，如果：

${b}$ 在列向量组张成的空间中，则我们一定可以求得 ${x}$ ，它是表出的系数。
${b}$ 不在列向量组张成的空间中，我们希望求得它的最小二乘解。

Anotations

我们给出四个特殊的名词。

Perpframes(正交标架)

Perpframe一词源于Perpendicular(垂直)和frame(框架)。更好的理解的说法是orthonormal basis(单位正交基)。我们给定一组单位正交基 ${\left[v_{0},v_{1}, \cdots, v_{n}\right]}$ ，它满足:

{ \left\{ \begin{array}{lc} v_{i}^{T}v_{j} = 0 & i \neq j \\ v_{i}^{T}v_{j} = 1 & i = j \end{array} \right. }

以下我们使用一组二维平面的单位正交基 ${[v_{1},v_{2}]}$ 来叙述。

Aligners

上述的单位正交基对应的Aligners 定义为:

{\left[ \begin{matrix} v_{1}^{T} \\ v_{2}^{T} \end{matrix} \right]}

它具有如下的性质：

{ \left[ \begin{matrix} v_{1}^{T} \\ v_{2}^{T} \end{matrix} \right] \cdot v_{1} = \left[ \begin{matrix} v_{1}^{T} \cdot v_{1} \\ v_{2}^{T} \cdot v_{1} \end{matrix} \right] = \left[ \begin{matrix} 1 \\ 0 \end{matrix} \right] \quad \left[ \begin{matrix} v_{1}^{T} \\ v_{2}^{T} \end{matrix} \right] \cdot v_{2} = \left[ \begin{matrix} v_{1}^{T} \cdot v_{2} \\ v_{2}^{T} \cdot v_{2} \end{matrix} \right] = \left[ \begin{matrix} 0 \\ 1 \end{matrix} \right] }

也就是说，Aligners将单位正交基投影到x-y坐标轴(即二维平面的标准正交基 ${\left[e_{1},e_{2} \right]}$ )。

Hangers

上述的单位正交基对应的Hangers定义为：

{\left[ v_{1}, v_{2} \right]}

它具有的性质是：

{ \left[ v_{1}, v_{2} \right] \cdot \left[ \begin{matrix} 0 \\ 1 \end{matrix} \right] = v_{2} \quad \left[ v_{1}, v_{2} \right] \cdot \left[ \begin{matrix} 1 \\ 0 \end{matrix} \right] = v_{1} \quad }

也就是说，Hangers的作用正好和Aligners相反，它把标准正交基投影到我们的单位正交基上。

同时我们注意到：

{ Aligners \cdot Hangers = \left[ \begin{matrix} v_{1}^{T} \\ v_{2}^{T} \end{matrix} \right] \cdot \left[ \begin{matrix} v_{1} & v_{2} \end{matrix} \right] = \left[ \begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix} \right] = E }

这说明：同一组单位正交基的Aligners和Hangers是互逆的。

Stretchers(伸缩)

Stretchers比较好理解，它是对角阵：

{ Stretchers = diagnal(\lambda_{0}, \lambda_{1}, \cdots, \lambda_{n}) }

如 ${\textbf{R}^{2}}$ 上的一个Stretchers定义为:

{\left[ \begin{matrix} a & 0 \\ 0 & b \end{matrix} \right]}

对任意二位平面内的向量 ${\left[ x,y \right]^{T}}$ ，Stretchers对它进行变换有：

{ \left[ \begin{matrix} a & 0 \\ 0 & b \end{matrix} \right] \cdot \left[ \begin{matrix} x \\ y \end{matrix} \right] = \left[ \begin{matrix} ax \\ by \end{matrix} \right] = x \cdot \left[ \begin{matrix} a \\ 0 \end{matrix} \right] + y \cdot \left[ \begin{matrix} 0 \\ b \end{matrix} \right] }

{ \left[ \begin{matrix} a \\ 0 \end{matrix} \right] = a \cdot \left[ \begin{matrix} 1 \\ 0 \end{matrix} \right] = a \cdot e_{1} \quad \left[ \begin{matrix} 0 \\ b \end{matrix} \right] = b \cdot \left[ \begin{matrix} 0 \\ 1 \end{matrix} \right] = b \cdot e_{2} }

即Stretchers对应位置上的值对对应维度上的单位正交基进行了放缩。

Coordinate(坐标)

对任意二维平面上的向量 ${p=\left[ x_{1}, x_{2} \right]^{T}}$ ，首先我们要理解这里给出的坐标实际是 ${p}$ 在标准正交基下的坐标，如果我们想求它在单位正交基 ${\left[ v_{1},v_{2} \right]}$ 下的坐标：

{ p = av_{1} + bv_{2} = \left[ v_{1}, v_{2} \right] \cdot \left[ \begin{matrix} a \\ b \end{matrix} \right] = \left[ e_{1}, e_{2} \right] \cdot \left[ \begin{matrix} x_{1} \\ x_{2} \end{matrix} \right] }

我们用Aligners左乘上面的式子得到：

{ Aligners \cdot p = \left[ \begin{matrix} v_{1}^{T} \\ v_{2}^{T} \end{matrix} \right] \left[ v_{1}, v_{2} \right] \cdot \left[ \begin{matrix} a \\ b \end{matrix} \right] = \left[ \begin{matrix} a \\ b \end{matrix} \right] }

上面的式子里 ${\left[ v_{1}, v_{2} \right] = Hangers}$ ，则：

{ \left[ v_{1}, v_{2} \right] \cdot \left[ \begin{matrix} a \\ b \end{matrix} \right] = \left[ \begin{matrix} x_{1} \\ x_{2} \end{matrix} \right] = p }

我们从以上可以看出：

Aligners将向量在标准正交基上的坐标变换到它的单位正交基上的坐标。
Hangers将向量在它的单位正交基上的坐标变换到标准正交基上的坐标。

Example (例子)

给定二维平面上的一组单位正交基:

{ \left\{ \begin{array}{l} v_{1} = \left[ \frac{\sqrt{2}}{2}, \frac{\sqrt{2}}{2} \right]^T \\ v_{2} = \left[ -\frac{\sqrt{2}}{2}, \frac{\sqrt{2}}{2} \right]^T \end{array} \right. }

求向量 ${p=\left[ 3,5 \right]^{T}}$ 到 ${v_{1}}$ 的垂足。

解：
${p}$ 在x-y轴上对于x轴上的垂足我们很容易得到是 ${\left[ 3,0 \right]}$ ，我们只需要令y轴的坐标为0，也就是说我们将一个Stretchers作用于 ${p}$ ：

{ \left[ \begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix} \right] \cdot p = \left[ \begin{matrix} 3 \\ 0 \end{matrix} \right] }

这个Stretchers保持 ${p}$ 在x轴的伸缩尺度为1，在y轴的伸缩尺度为0。

那我们的思路可以是：将 ${p}$ 变换到给定的单位正交基上，用该Stretchers作用它，得到垂足在单位正交基上的坐标，再将其变换回x-y坐标系，一系列的变换矩阵 ${A}$ 为：

{ A \cdot p = (Hangers) \cdot (Stretchers) \cdot (Aligners) \cdot p = \left[ \begin{matrix} \frac{\sqrt{2}}{2} & - \frac{\sqrt{2}}{2} \\ \frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} \end{matrix} \right] \cdot \left[ \begin{matrix} 1 & 0 \\ 0 & 0 \end{matrix} \right] \cdot \left[ \begin{matrix} \frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} \\ -\frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} \end{matrix} \right] \cdot \left[ \begin{matrix} 3 \\ 5 \end{matrix} \right] = \left[ \begin{matrix} 4 \\ 4 \end{matrix} \right] }

这就是整个的变换过程，也是计算机图像学中几个变换矩阵连续变换的理论，将复杂的变换分解有利于计算。

Singular Value Decomposition (SVD分解)

SVD分解就是这样一个命题：对任意一个 ${m \times n}$ 的矩阵 ${A}$ ，存在以下的分解形式：

{A = (Hangers) \cdot (Stretchers) \cdot (Aligners) }

SVD的精妙之处在于：它对任意的矩阵都成立，任意的矩阵都有如上的分解形式。

问题是我们如何找到这样的 ${(Hangers) (Stretchers) (Aligners)}$ 。

构造

首先，对任意一个 ${m \times n}$ 的矩阵 ${A}$ ，我们可以将它看成是 ${\textbf{R}^{n} \rightarrow \textbf{R}^{m}}$ 的变换(线性映射)。我们可以在 ${\textbf{R}^{n}}$ 里找到一组单位正交基 ${\left[ a_{1}, a_{2}, \cdots, a_{n} \right]}$ ，而且这样的单位正交基有任意多个。

我们将这组单位正交基通过 ${A}$ 投影到另一组向量 ${\left[ d_{1}, d_{2}, \cdots, d_{n} \right]}$ (注意该向量组共有n个元素，每个元素是m维)。

我们定义标量 ${s_{i} = \vert\vert d_{i} \vert\vert = \vert\vert Aa_{i} \vert\vert}$ 。

由此我们定义另一组向量 ${\left[ h_{1}, h_{2}, \cdots, h_{n}\right]}$ ，它们满足：

{ h_{i} = \left\{ \begin{array}{cl} \vec{0} & if \quad s_{i} = 0 \\ \frac{1}{s_{i}} A a_{i} & if \quad s_{i} \neq 0 \end{array} \right. }

我们可以发现以下的式子成立：

{ \begin{aligned} H \cdot S \cdot A' &= \left[ h_{1}, h_{2}, \cdots, h_{n}\right] \cdot \left[ \begin{matrix} s_{1} & & & \\ & s_{2} & & \\ & & \ddots & \\ & & & s_{n} \\ \end{matrix} \right] \cdot \left[ \begin{matrix} a_{1}^{T} \\ \vdots \\ a_{n}^{T} \end{matrix} \right] \\ & = \left[ Aa_{1}, Aa_{2}, \cdots, Aa_{n}\right] \cdot \left[ \begin{matrix} a_{1}^{T} \\ \vdots \\ a_{n}^{T} \end{matrix} \right] \\ & = A \left[ a_{1}, a_{2} \cdots, a_{n} \right] \left[ \begin{matrix} a_{1}^{T} \\ a_{2}^{T} \\ \vdots \\ a_{n}^{T} \end{matrix} \right] \\ & = A \end{aligned} }

特别注意的是以上的矩阵的大小：

${H}$ 的大小为 ${m \times n}$ ， ${S}$ 的大小为 ${n \times n}$ ，是一个对角阵，同时是一个 ${Stretchers}$ ； ${A'}$ 的大小为 ${n \times n}$ ，同时是一个 ${Aligner}$ 。只有 ${H}$ 不一定是 ${Hanger}$ 。

基于以上的构造方法，我们发现现在的问题是：寻找合适的 ${\textbf{R}^{n}}$ 空间的单位正交基 ${\left[ a_{1}, a_{2}, \cdots, a_{n} \right]}$ 使得通过以上构造方法得到的 ${H}$ 为 ${Hanger}$ ，那我们就得到了对一个矩阵进行SVD分解的三个矩阵，同时证明了任意一个矩阵有SVD分解。

构造Hanger

得到单位正交向量组

要使得向量组 ${\left[ h_{1}, h_{2}, \cdots, h_{n} \right]}$ 构成 ${Hanger}$ ，当且仅当该向量组也是一组单位正交基。

对任意 ${h_{i}}$ ，根据之前的 ${s_{i}}$ 的定义，只要 ${s_{i}\neq 0}$ ，我们有：

{ h_{i} \cdot h_{i} = \frac{1}{s_{i}^2} || Aa_{i} ||^{2} = 1 }

剩下的关键就是如何使得 ${h_{i}}$ 正交，即

{ h_{i} \cdot h_{j} = 0 \quad if \quad (i \neq j) }

我们如下推导：

{ \begin{aligned} h_{i} \cdot h_{j} &= Aa_{i} \cdot Aa_{j} &= (Aa_{i})^{T}Aa_{j} &= 0 \\ &= a_{i}^{T} (A^{T} Aa_{j}) \end{aligned} }

我们只要令:

{ A^{T}Aa_{j} = \lambda a_{j} }

就可以使得:

{a_{i}^{T}(A^{T} Aa_{j}) = a_{i}^{T}\lambda a_{j} = 0 = h_{i}h_{j} \quad if \quad (i \neq j)}

通过上面的推导，我们发现这唯一的一组正交基正是 ${A^{T}A}$ 的特征向量 ${\left[ a_{1}, a_{2}, \cdots, a_{n} \right]}$ 。而且由于 ${A^{T}A}$ 是实对称阵， ${\left[ a_{1}, a_{2}, \cdots, a_{n} \right]}$ 一定存在，通过它得到的向量组 ${\left[ h_{1}, h_{2}, \cdots, h_{n} \right]}$ 一定是正交的。

这里我们还有最后一个问题，向量组 ${\left[ h_{1}, h_{2}, \cdots, h_{n} \right]}$ 是否是 ${\textbf{R}^{m}}$ 的基。

基的讨论

首先，由矩阵秩的不等式：

{rank(A^{T}A) \leq min(rank(A^T), rank(A)) = rank(A) \leq min(m,n)}

如果 ${m \neq n}$ ，矩阵 ${A^{T}A}$ 一定不是满秩，则它一定存在 ${\lambda = 0}$ 的特征值，且由于矩阵 ${A^{T}A}$ 可分解，它的特征值的几何重数等于代数重数，该特征值对应的特征向量的个数等于 ${n-rank(A^{T}A)}$ 。我们把这些特征向量记作 ${c_{i}}$ ，其中 ${i=1,\cdots,n-rank(A^{T}A)}$ 。

对 ${c_{i}}$ ，我们有：

{A^{T}Ac_{i}=0}

则

{c_{i}^{T}A^{T}Ac_{i} = 0 = ||Ac_{i}||}

又根据 ${s_{i}}$ 的定义，我们知道这些 ${c_{i}}$ 对应的 ${h_{i}=Ac_{i}}$ 都是零向量。也就是说向量组 ${\left[ h_{1},h_{2},\cdots,h_{n} \right]}$ 中必定存在至少 ${n-rank(A^{T}A)}$ 个零向量。

又

{n-rank(A^{T}A) \geq n-rank(A) \geq n - min(m,n)}

我们下面分析 ${m,n}$ 的大小的两种情况：

${m < n}$

此时矩阵 ${A}$ 就是高维空间向低维空间的映射，它完成了降维的功能。

如果 ${m < n}$ ，那么向量组 ${\left[ h_{1},h_{2},\cdots,h_{n} \right]}$ 中必定存在至少 ${n-m}$ 个零向量，我们把这些零向量去除，得到至多包含 ${m}$ 个向量的向量组 ${\left[ h_{1}, h_{2}, \cdots, h_{m} \right]}$ 。

如果 ${A}$ 的秩为m，那么向量组 ${\left[ h_{1}, h_{2}, \cdots, h_{m} \right]}$ 中就不再包含零向量。该向量组包含m个向量，每个向量又是m维的，那么该向量组一定是 ${\textbf{R}^{m}}$ 的基。

如果 ${A}$ 的秩小于m，那么向量组 ${\left[ h_{1}, h_{2}, \cdots, h_{m} \right]}$ 中仍有零向量，我们仍将他们去除，变成 ${\left[ h_{1}, h_{2}, \cdots, h_{k} \right]}$ ，我们将该向量组扩充，向该向量组添加 ${m-k}$ 个互相正交的向量，得到的新的向量组 ${\left[ h_{1}, h_{2}, \cdots, h_{m} \right]}$ 就构成 ${\textbf{R}^{m}}$ 的基。
${m \geq n}$

此时矩阵 ${A}$ 是升维功能。

此时的分析过程大致和上面的情况相同，向量组 ${\left[ h_{1},h_{2},\cdots,h_{n} \right]}$ 中必定包含至少0个零向量，如果 ${A}$ 的秩小于n，我们仍然将对应的零向量去除。无论是否去除零向量，如果向量组中向量的个数小于m，我们仍添加正交的向量使整个向量组包含m个正交向量，这样得到 ${\textbf{R}^{m}}$ 的基。

总结一下就是：使用之前的构造方法必然得到至多 ${m}$ 个正交向量 ${h_{i}}$ ，如果向量组个数小于 ${m}$ ，我们就扩充该向量组，这样必然可以得到 ${\textbf{R}^{m}}$ 的基。

而且，因为这些扩充的向量对应的 ${s_{i}}$ 是0，所以这样的 ${H}$ 和 ${S,A'}$ 相乘时仍然可以还原成 ${A}$ 。

这里还有一个比较值得我们注意的是在SVD分解中三个矩阵的大小，在我们最初的构造过程中我们得到的分解模式

{A = H \cdot S \cdot A'}

${H}$ 的大小为 ${m \times n}$ ， ${S}$ 的大小为 ${n \times n}$ ， ${A'}$ 的大小是 ${n \times n}$ 。

如果我们去掉 ${H}$ 列向量组中的零向量，对应的我们去除 ${S}$ 中对应的行，我们得到的矩阵大小现在是： ${H}$ 的大小为 ${m \times k}$ ， ${S}$ 的大小为 ${k \times n}$ 。

我们按照前述的得到 ${\textbf{R}^{m}}$ 的基的方法，如果 ${k < m}$ 就添加正交向量将 ${H}$ 列向量组扩充为m个，并在 ${S}$ 的相应位置添加全零行。我们现在得到的矩阵大小是： ${H}$ 的大小为 ${m \times m}$ ， ${S}$ 的大小为 ${m \times n}$ ， ${A'}$ 的大小是 ${n \times n}$ 。这就得到了我们想要的满足SVD定义的标准分解。

关于SVD最后想说的几点

${Stretcher}$ 矩阵的大小和矩阵 ${A}$ 大小相等。

The dimensions of the stretcher matrix will always match the dimensions of A.

对应关系： ${Hanger}$ 矩阵的第 ${\textbf{i}}$ 列，对应 ${Stretcher}$ 矩阵的第 ${\textbf{i}}$ 行。 ${Stretcher}$ 矩阵的第 ${\textbf{i}}$ 列，对应 ${Aligner}$ 矩阵的第 ${\textbf{i}}$ 行。（废话）也就是如果要删去行列，要遵守这一规则，这将在PCA中有用。