当前位置：首页 > news >正文

线性代数重要知识点和理论(下)

news 来源：原创 2024/9/18 3:54:05

奇异值分解

奇异值分解非常重要且有趣。首先对于 $n\times n$ 对称矩阵 $A$ ，可以通过对角化得到其对角化形式 $A=PDP^{-1}$ ，但是如果 $A$ 不是对称矩阵或者不是方阵，则不能进行对角化，但是可以通过奇异值分解得到类似形式。对于对角化，利用的重要性质是 $A\bold{v_1}=\lambda \bold{v_1}$ 以及对称矩阵的特征向量互相正交。对于任意 $m\times n$ 矩阵，可以看做是 $\Bbb R^m$ 到 $\Bbb R^n$ 空间的一个映射，是否也存在一些 $A\bold{v_1}=\sigma_1\bold{u_1}$ 的形式呢？
定理：奇异值分解
设 $A$ 是秩为 $r$ 的 $m\times n$ 矩阵，那么存在一个 $m\times n$ 矩阵 $\Sigma$ ， $D$ 是一个 $r\times r$ 非零对角矩阵，其对角线元素是A的前 $r$ 个奇异值， $\sigma_1\ge\sigma_2\ge...\ge\sigma_r\gt0$ ，并且存在一个 $m\times m$ 正交矩阵 $U$ 和 $n\times n$ 正交矩阵 $V$ ，满足 $A=U\Sigma V^T$ ，这个分解叫做 $A$ 的一个奇异值分解，矩阵 $U$ 和 $V$ 不是由 $A$ 唯一确定的(只确定了部分 $U 和 V$ 正交基，其余满足单位正交条件即可)，但 $\Sigma$ 对角线必须是 $A$ 的奇异值。
$\Sigma=\left[ \begin{aligned} D \ \ & 0\\ 0 \ \ & 0\\ \end{aligned} \right]$

引入的过程
奇异值分解基于一般的矩阵对角化性质可以被长方形矩阵模仿：一个对称矩阵 $A$ 的特征值的绝对值，表示度量 $A$ 拉长或者压缩一个向量(特征向量)的程度，如果 $Ax=\lambda x$ ，且 $∣∣ x ∣∣ = 1$ ，那么 $||Ax||=||\lambda x||=|\lambda|||x||=|\lambda|$
如果 $\lambda_1$ 是具有最大数值的特征值，那么对应的单位特征向量 $\bold{v_1}$ ，确定一个有 $A$ 拉长影响最大的方向，也就是 $\bold{x}=\bold{v_1}$ 时， $||A\bold{x}||$ 长度最大化, $||A\bold{v_1}||=|\lambda_1|$ 。其中的原因在特征值部分已经做了介绍，任何向量都可以分解成特征向量的线性组合，选取最大特征值对应的特征向量方向，对向量的拉长自然是最大的。这里为什么要通过研究拉长最大的方向来引入奇异值，后面会做分析。
以一个矩阵 $A$ 为例，求 $||\bold{x}||=1$ 的条件下 $||A\bold{x}||$ 的最大长度和此时的 $\bold{x}$
$A=\left[ \begin{aligned} 4&&11&&14\\ 8&&7&&-2\\ \end{aligned} \right]$
求 $||A\bold{x}||$ 的最大值，等价于求 $||A\bold{x}||^2$ 的最大值，
$||A\bold{x}||^2=(A\bold{x})^T(A\bold{x})=\bold{x}^TA^TA\bold{x}=\bold{x}^T(A^TA)\bold{x}$
而 $A^TA)^T=A^TA^{TT}=A^TA$ ， $A^TA$ 转置等于自身，是对称矩阵。根据前面对二次型的介绍，最大值的模是 $A^TA$ 的最大特征值 $\lambda_1$ ，此时 $\bold{x}$ 为最大特征值 $\lambda_1$ 对应的特征向量 $\bold{v_1}$ ，令 $\sigma_i=\sqrt{\lambda_i}$ ，叫做作矩阵 $A$ 的奇异值，故 $||A\bold{x}||$ 的最大值为 $\sigma_1=\sqrt{\lambda_1}$ .
考虑到 $\bold{v_1}$ 是 $m\times 1$ ,令 $\bold{u_1}$ 是 $\Bbb R^n$ 空间的单位基，则 $A\bold{v_1}=\sigma_1 \bold{u_1}$ ，进而推广 $A\bold{v_i}=\sigma_i \bold{u_i}$ ，这个推广是可行的，因为 $A^TA$ 是对称矩阵，所以 $v_i$ 之间相互正交(特征值一节已经证明，且证明比较简单)。幸运的是，在 $\Bbb R^n$ 空间中， $\bold{u_i}$ 在奇异值不同的情况下也是相互正交的，因为：
设 $\bold{u_i}$ 和 $\bold{u_j}$ 对应不同奇异值 $\sigma_i$ 和 $\sigma_j$ ，则
$\sigma_i\sigma_j\bold{u_i}\cdot\bold{u_j}=(\sigma_i\bold{u_i})^T(\sigma_j\bold{u_j})\\ =(A\bold{v_i})^T(A\bold{v_j})=\bold{v_i}^T(A^TA)\bold{v_j}=\bold{v_i}^T\lambda_j\bold{v_j}=0$
下面来讨论，为什么要通过研究 $||A\bold{x}||$ 的最大值、次大值来引入奇异值的分析。首先当然是出于类比的原因，因为特征值和特征向量就是对单位向量拉长最大、次大。。的数值和方向。如果不加最大值这个限制，还能不能分解 $A$ 呢？此时仍旧可以分解 $A = QM V$ ， $Q, V$ 分别是 $m\times m, n\times n$ 的单位正交基，问题就在于，此时M就不是奇异值构成的对角阵了，且计算是比较复杂的，其实对称矩阵也可以写成非特征向量构成的P满足 $A=PMP^{-1}$ 的形式，但是此时只是换了一组正交基，不能发现矩阵的本质特性，不能简化运算。按照这种分解方式，研究的是矩阵在椭圆的长轴、次长轴…一个分解的性质，具有明确的几何意义和物理意义。也正是因为奇异值分解有求取 $||A\bold{x}||$ 最大值的含义，使其可以用于主成分分析法，拉长最大的方向，是将原像数据映射到像空间导致差别最大的数据，含有最多的分类信息量。

举个例子
求取 $A=\left[ \begin{aligned} 1&&-1\\ -2&&2\\ 2&&-2 \end{aligned} \right]$
第一步：先求 $A^TA=\left[\begin{aligned}9&&-9\\-9&&9\end{aligned}\right]$
第二步：求 $A^TA$ 的特征值 $\lambda_1=18,\lambda_2=0$ 和特征向量
$\bold{v_1}=\left[\begin{aligned}\frac{\sqrt{2}}{2} \\ -\frac{\sqrt{2}}{2}\end{aligned}\right] \bold{v_2}=\left[\begin{aligned}\frac{\sqrt{2}}{2} \\ \frac{\sqrt{2}}{2}\end{aligned}\right]$
第三步：求 $U$ . 只能求得一个非零向量 $\bold{u_1}=\frac{1}{\sigma_1}A\bold{v_1}=\left[\begin{aligned} \frac{1}{3} \\ -\frac{2}{3} \\ \frac{2}{3} \\ \end{aligned}\right]$
使用格拉姆施密特方法补齐U的单位正交基。 $x_1-2x_2+2x_3=0$ ，分别取 $x_2=0,x_3=1, 则x_1=-2$ 和 $x_1=0,x_2=1, 则x_3=1$ ，此时后两个向量都和 $\bold{u_1}$ 正交，有格拉姆施密特方法，求得 $\bold{u_2}=\left[\begin{aligned} -\frac{2\sqrt{2}}{3} \\ -\frac{\sqrt{2}}{6} \\ \frac{\sqrt{2}}{6} \\ \end{aligned}\right] \bold{u_3}=\left[\begin{aligned} 0 \\ \frac{\sqrt{2}}{2} \\ \frac{\sqrt{2}}{2} \\ \end{aligned}\right]$
求得A的奇异值分解为 $A=U\Sigma V^T=\left[ \begin{aligned} \frac{1}{3} &&-\frac{2\sqrt{2}}{3}&&0 \\ -\frac{2}{3} &&-\frac{\sqrt{2}}{6}&&\frac{\sqrt{2}}{2} \\ \frac{2}{3} &&\frac{\sqrt{2}}{6}&&\frac{\sqrt{2}}{2} \\ \end{aligned} \right] \left[ \begin{aligned} 3\sqrt{2} &&0 \\ 0&&0 \\ 0&&0 \\ \end{aligned} \right] \left[ \begin{aligned} \frac{\sqrt{2}}{2} &&-\frac{\sqrt{2}}{2} \\ \frac{\sqrt{2}}{2}&&\frac{\sqrt{2}}{2} \\ \end{aligned} \right]$
对于非0奇异值 $3\sqrt{2}$ 实际上只有一个非零向量 $\bold{v_1}$ 和 $\bold{u_1}$ ， $U, V$ 其余的正交基是为了满秩补齐的，实际上，在分解和计算A的时候，完全可以使用0进行填充，对与计算A没有任何影响。另外，对于 $U$ 因为只有一个正交基，所以另外的两个单位正交基实际上并不是唯一的(补齐它们，实际对计算A没有任何影响，因为在计算矩阵的时候，他们将和 $\Sigma$ 里的0值相乘)
对于奇异值分解若 $A=U\Sigma V^T$ ，则 $A^T=V\Sigma U^T$ 。对于 $A$ 的奇异值分解，若 $\lambda_i, \bold{v_i}$ 分别是 $A^TA$ 的一个特征值和特征向量， $\sigma_i=\sqrt{\lambda_i}$ 是对应的奇异值，则有 $A\bold{v_i}=\sigma_i\bold{u_i}$ ， $\sigma_iA^T\bold{u_i}=A^TA\bold{v_i}=\lambda_i\bold{v_i}$ ，所以 $A^T\bold{u_i}=\frac{\lambda_i}{\sigma_i}\bold{v_i}=\sigma_i\bold{v_i}$ ，所以，如果 $V$ 的某一列是 $A$ 原像空间的单位正交基， $U$ 的对应列是 $A$ 的像空间的单位正交基，则 $U$ 的该列是 $A^T$ 原像空间的单位正交基， $V$ 的对应列是 $A^T$ 的像空间的单位正交基。所以 $A^T$ 的奇异值分解有上述形式。此处没有证明 $A^TA$ 和 $AA^T$ 具有相同的非零特征值。
基于这个原因对于求 $A_{m\times n}$ 的奇异值分解(m<<n)，可以通过求 $A^T$ 的奇异值分解来实现，则计算复杂度降低：计算 $A^TA$ 复杂度从 $2mn^2$ 下降到 $2m^n$ ，计算行列式的时间复杂度由 $n!$ 下降到 $m!$
因此，如果上面计算 $A^T$ 的奇异值分解，可以立即得到 $A^T=(U\Sigma V^T)^T=V\Sigma U^T$ ，而上述矩阵均为已知。