线性代数——特征值分解、奇异值分解与 RQ 分解

Three Methods of Matrix Decomposition

 Thistledown    April 12, 2019

特征值分解

1. 特征值与特征向量

在线性代数中,对于 $n$ 阶方阵 $A$,如果存在某个数 $\lambda$ 及某个 $n$ 维非零列向量 $v$,使得

则称 $\lambda$ 是方阵 $A$ 的一个特征值,$v$ 是方阵 $A$ 的属于特征值 $\lambda$ 的一个特征向量。

对上式进行变换:

则称

  • $\lambda E - A$ 为 $A$ 的特征矩阵
  • 行列式 $f(\lambda) = |\lambda E- A|$ 为 $A$ 的特征多项式
  • $|\lambda E - A| = 0$ 是 $A$ 的特征方程
  • $(\lambda E - A)v = \overrightarrow{0}$ 是 $A$ 关于该特征值 $\lambda$ 的齐次线性方程组

$A$ 的主对角线上元素之和称为矩阵的(trace),记为 $tr(A)$,即

迹和特征值有着很重要的联系:

行列式也与特征值有关联:

2. 特征值分解

如果我们求出了方阵 $A$ 的 $n$ 个特征值 $\lambda_1 \leq \lambda_2 \leq … \leq \lambda_n$ 以及这 $n$ 个特征值所对应的特征向量 ${v_1, v_2, …, v_n}$,且这 $n$ 个特征向量线性无关。那么特征值分解,EVDEigen Value Decomposition)就是将方阵 $A$ 用下面的形式表示:

其中,$Q$ 是这 $n$ 个特征向量组成的 $n \times n$ 维矩阵,$\Sigma$ 是以这 $n$ 个特征值为主对角线的 $n \times n$ 维矩阵。

若将矩阵 $Q$ 中的 $n$ 个特征向量标准化,即满足 $||v_i||_2 = 1$,或者说 $v_i^Tv_i = 1$,此时 $Q$ 中的 $n$ 个特征向量为标准正交基,满足 $Q^TQ = I$,即 $Q^T = Q^{-1}$,此时 $Q$ 是一个酉矩阵。这样我们可以把特征分解表达式写作

3. 特征值与特征向量的几何意义

从某种意义上将,一个矩阵就是一个线性变换,因为一个矩阵与一个向量相乘的结果,相当于对这个向量进行了线性变换。比如,对于矩阵

它对应的线性变换如下图所示:

这是因为,矩阵 $M$ 与一个向量 $\begin{bmatrix} x & y \end{bmatrix}^T$ 相乘的结果为

由于矩阵 $M$ 是对称的,所以这个变换是一个对 $x$、$y$ 轴方向的拉伸变换:每一个对角线上的元素将会对一个维度进行拉伸变换,当值 $> 1$ 时为拉长,值 $< 1$ 时缩短。而当矩阵 $M$ 不对称时

它所描述的变换见下图:

如蓝色箭头所示,这其实是在平面上对一个轴进行的拉伸变换。图中,蓝色的剪头是一个最主要的变化方向(注意,变化方向并不唯一)。在描述一个变换时,最重要的就是描述这个变换主要的变化方向。

奇异值分解

奇异值分解,SVD (Singular Value Decomposition) 是线性代数中一种重要的矩阵分解,在信号处理、统计学等领域有重要应用。

1. 奇异值分解

特征值分解能够得到方阵的特征。对于普通的矩阵,可以采用奇异值分解的方法描述其特征:

其中,

  • $A$ 是一个 $M \times N$ 的矩阵
  • $U$ 是一个 $M \times M$ 的方阵($U$ 中的向量称为左奇异向量,都是正交的)
  • $\Sigma$ 是一个 $M \times N$ 的矩阵(除了对角线,其他元素都为 0,对角线上的元素称为奇异值)
  • $V$ 是一个 $N \times N$ 的方阵($V$ 中的向量称为右奇异向量,都是正交的)

2. 奇异值的计算

将 $A$ 的转置与 $A$ 相乘,那么对于 $N \times N$ 的方阵 $A^TA$,其特征值及特征向量满足

其中的 $v_i$ 即右奇异向量,$n$ 个特征向量 $v$ 组成了矩阵 $V$。

同理,对于 $M \times M$ 的矩阵 $AA^T$,其特征值和特征向量满足

其中的 $u_i$ 即左奇异向量,$m$ 个特征向量 $u$ 组成了矩阵 $U$。

推导可得:

这样可以求得所有的奇异值 $\sigma$,进而求出奇异值矩阵 $\Sigma$ 。此外还有

奇异值 $\sigma_i$ 也可以通过求出 $A^TA$ 的特征值取平方根得到。

3. SVD 的性质

奇异值 $\sigma$ 与特征值类似,在矩阵 $\Sigma$ 中也是从大到小降序排列,而且 $\sigma$ 减少得特别快,在很多情况下,前 10% 甚至 1% 的奇异值的和就占全部奇异值之和的 99% 以上了。也就是说,我们也可以用前 $r$ 个奇异值来近似描述矩阵,即部分奇异值分解

由于 $r$ 比 $n$ 小很多,存储矩阵和矩阵计算的花费也大大减少。当然,$r$ 越接近于 $n$,相乘的结果也越接近于 $A$ 。

根据这个性质,SVD 可以用于 PCA(Principal Component Analysis,主成分分析)降维,来做数据压缩和去噪。也可以用于推荐算法,将用户和用户喜好对应的矩阵做特征分解,进而得到隐含的用户需求来做推荐,事实上 Netflix 等公司的推荐算法都采用了 SVD。同时奇异值分解也可以用于 NLP(Natural Language Processing,自然语言处理),比如 LSI(Latent Semantic Indexing,潜在语义索引)等。

RQ 分解

1. QR 分解

了解 RQ 分解之前,先要掌握 QR 分解。QR 分解将矩阵 $A$ 分解为一个正交矩阵 $Q$ 与上三角矩阵 $R$ 的积,即

使用 Householder 变换可以对其进行求解,此处不再赘述,可参考文末链接。

2. RQ 分解

对矩阵 $A$ 进行 RQ 分解即将其分解为一个上三角阵 $R$ 与一个正交矩阵(Orthogonal Matrix)$Q$ 的乘积,要求矩阵 $A$ 满秩。

对于 $n \times n$ 的矩阵 $A$,若给定矩阵 $P$,满足

则 $AP$ 会倒置 $A$ 中列的顺序,$PA$ 会倒置 $A$ 中行的顺序。且 $P^T = P$,$PP = I$,于是 $P^{-1} = P = P^T$,$P$ 为正交矩阵。进行以下步骤的计算:

  • 计算 $\tilde{A} = PA$,即倒置 $A$ 中行的顺序
  • 计算 QR 分解:$\tilde{A}^T = \tilde{Q}\tilde{R}$
  • 令 $Q = P \tilde{Q}^T$,即倒置 $\tilde{Q}^T$ 中行的顺序($Q$ 是正交矩阵)
  • 令 $R = P\tilde{R}^TP$

在最后一步中,上三角矩阵 $\tilde{R}$ 通过两次矩阵 $P$ 相乘变成一个下三角矩阵

由上面的 $R$ 和 $Q$ 可以得到


参考:
$1$. 奇异值分解 - 维基百科,自由的百科全书
$2$. 机器学习中的数学(5)-强大的矩阵奇异值分解(SVD)及其应用 - LeftNotEasy - 博客园
$3$. AMS :: Feature Column from the AMS
$4$. 奇异值分解(SVD)原理与在降维中的应用 - 刘建平Pinard - 博客园
$5$. 奇异值分解(SVD)原理 - JackGao的博客 - CSDN博客
$6$. QR分解 - 维基百科,自由的百科全书
$7$. G. H. Golub, C. Reinsch, Singular Value Decomposition and Least Squares Solutions.
$8$. D. Kalman, A Singularly Valuable Decomposition: The SVD of a Matrix.

Thistledown