您现在的位置是:首页 > 正文

【线性代数/机器学习】矩阵的奇异值与奇异值分解(SVD)

2024-02-01 01:56:10阅读 4

一、引言

我们知道,对于一个 n × n n\times n n×n的矩阵 A A A,如果 A A A n n n个线性无关的特征向量,则 A A A可以相似对角化,即存在可逆矩阵 P P P使得 A = P Λ P − 1 A=P\Lambda P^{-1} A=PΛP1,其中 Λ \Lambda Λ A A A的特征值组成的对角阵。 P P P的列实际上就是 A A A的特征向量。把 A A A分解为 P Λ P − 1 P\Lambda P^{-1} PΛP1的过程称为矩阵的特征值分解(eigendecomposition)。但是,对于 m × n m\times n m×n的矩阵,其中 m ≠ n m\ne n m=n,我们就无能为力了。此时我们应该怎么分解这个矩阵呢?这里我们就引入了奇异值分解(singular value decomposition, SVD)的概念。

二、奇异值

A A A是一个 m × n m\times n m×n矩阵。我们对特征值已经比较熟悉了,所以我们对奇异值的定义也是从特征值出发获得的。什么样的矩阵具有特征值呢?答案是方阵。但 A A A不一定是方阵,不过我们有办法把它变成方阵—— A T A A^TA ATA是一个 n × n n\times n n×n的方阵。我们接下来考察 A T A A^T A ATA的特征值。

引理1 A T A A^T A ATA的每个特征值 λ \lambda λ都大于等于 0 0 0

证明:设 A T A x = λ x A^T A\boldsymbol{x}=\lambda\boldsymbol{x} ATAx=λx,其中 x \boldsymbol{x} x A T A A^T A ATA的一个特征向量。则 x T A T A x = λ x T x ∥ A x ∥ 2 = λ ∥ x ∥ 2 \boldsymbol{x}^T A^TA\boldsymbol{x}=\lambda \boldsymbol{x}^T\boldsymbol{x}\\ \|A\boldsymbol{x}\|^2=\lambda\|\boldsymbol{x}\|^2 xTATAx=λxTxAx2=λx2注意 ∥ A x ∥ 2 \|A\boldsymbol{x}\|^2 Ax2 ∥ x ∥ 2 \|\boldsymbol{x}\|^2 x2都是非负数,故 λ ≥ 0 \lambda\ge 0 λ0。∎

现在我们来定义奇异值(singular value)。

定义2 λ 1 , λ 2 , ⋯   , λ n \lambda_1,\lambda_2,\cdots,\lambda_n λ1,λ2,,λn A T A A^T A ATA的奇异值,满足 λ 1 ≥ λ 2 ≥ ⋯ ≥ λ n ≥ 0 \lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n\ge 0 λ1λ2λn0。定义 σ i = λ i \sigma_i=\sqrt{\lambda_i} σi=λi ,则 σ 1 ≥ σ 2 ≥ ⋯ ≥ σ n ≥ 0 \sigma_1\ge\sigma_2\ge\cdots\ge\sigma_n\ge 0 σ1σ2σn0。这些 σ i \sigma_i σi称为 A A A的奇异值。

命题3 A A A的非零奇异值个数等于 A A A的秩。

证明:即证 r ( A T A ) = r ( A ) r(A^T A)=r(A) r(ATA)=r(A)。考虑齐次线性方程组 A T A x = 0 A^TA\boldsymbol{x}=\boldsymbol{0} ATAx=0,设 ξ \boldsymbol{\xi} ξ为它的一个解,即 A T A ξ = 0 A^T A\boldsymbol{\xi}=\boldsymbol{0} ATAξ=0,则 ξ T A T A ξ = 0 \boldsymbol{\xi}^T A^T A\boldsymbol{\xi}=\boldsymbol{0} ξTATAξ=0,即 ∥ A ξ ∥ 2 = 0 \|A\boldsymbol{\xi}\|^2=0 Aξ2=0,故 A ξ = 0 A\boldsymbol{\xi}=0 Aξ=0。这说明 A T A x = 0 A^T A\boldsymbol{x}=0 ATAx=0的解也是 A x = 0 A\boldsymbol{x}=0 Ax=0的解。同时 A x = 0 A\boldsymbol{x}=0 Ax=0的解显然也是 A T A x = 0 A^T A\boldsymbol{x}=0 ATAx=0的解,因此两个线性方程组同解,这说明 r ( A T A ) = r ( A ) r(A^T A)=r(A) r(ATA)=r(A)。∎

很多时候我们会遇到这样一个问题: ∥ x ∥ \|\boldsymbol{x}\| x ∥ A x ∥ \|A\boldsymbol{x}\| Ax的大小有怎样的关系呢?把矩阵 A A A看作一个线性变换,它作用于 x \boldsymbol{x} x上可以改变其长度,那么长度最多变化多少倍呢?有了奇异值,我们就可以很方便地解决这个问题。

命题4 A A A是一个 m × n m\times n m×n矩阵, x \boldsymbol{x} x是一个 n × 1 n\times 1 n×1向量。则 ∥ A x ∥ ≤ σ 1 ∥ x ∥ \|A\boldsymbol{x}\|\le\sigma_1\|\boldsymbol{x}\| Axσ1x,其中 σ 1 \sigma_1 σ1 A A A最大的奇异值,且取等条件为 x \boldsymbol{x} x A T A A^T A ATA对应于特征值 σ 1 2 \sigma_1^2 σ12的特征向量。

证明:注意 A T A A^T A ATA是实对称矩阵,所以它存在单位正交特征向量组 v 1 , v 2 , ⋯   , v n \boldsymbol{v}_1,\boldsymbol{v}_2,\cdots,\boldsymbol{v}_n v1,v2,,vn。若 x ∈ R n \boldsymbol{x}\in\mathbb{R}^n xRn,则可以把 x \boldsymbol{x} x表示为 x = c 1 v 1 + c 2 v 2 + ⋯ + c n v n \boldsymbol{x}=c_1\boldsymbol{v}_1+c_2\boldsymbol{v}_2+\cdots+c_n\boldsymbol{v}_n x=c1v1+c2v2++cnvn其中 c 1 , c 2 , ⋯   , c n c_1,c_2,\cdots,c_n c1,c2,,cn是标量,满足 c 1 2 + c 2 2 + ⋯ + c n 2 = ∥ x ∥ 2 c_1^2+c_2^2+\cdots+c_n^2=\|\boldsymbol{x}\|^2 c12+c22++cn2=x2。再考察 ∥ A x ∥ 2 \|A\boldsymbol{x}\|^2 Ax2 ∥ A x ∥ 2 = x T A T A x = ⟨ x , A T A x ⟩ = ⟨ ∑ i = 1 n c i v i , ∑ i = 1 n c i A T A v i ⟩ \|A\boldsymbol{x}\|^2=\boldsymbol{x}^T A^T A\boldsymbol{x}=\langle\boldsymbol{x},A^T A \boldsymbol{x}\rangle=\left\langle\sum\limits_{i=1}^n c_i\boldsymbol{v}_i,\sum\limits_{i=1}^n c_i A^T A \boldsymbol{v}_i\right\rangle Ax2=xTATAx=x,ATAx=i=1ncivi,i=1nciATAvi注意 v i \boldsymbol{v}_i vi A T A A^T A ATA对应于特征值 σ i 2 \sigma_i^2 σi2的特征向量,故 A T A v i = σ i 2 v i A^T A\boldsymbol{v}_i=\sigma_i^2\boldsymbol{v}_i ATAvi=σi2vi。因此 ∥ A x ∥ 2 = ⟨ ∑ i = 1 n c i v i , ∑ i = 1 n c i σ i 2 v i ⟩ = ∑ i = 1 n c i 2 σ i 2 ≤ ∑ i = 1 n c i 2 σ 1 2 = σ 1 2 ∥ x ∥ 2 \|A\boldsymbol{x}\|^2=\left\langle\sum\limits_{i=1}^n c_i\boldsymbol{v}_i,\sum\limits_{i=1}^n c_i \sigma_i^2 \boldsymbol{v}_i\right\rangle= \sum\limits_{i=1}^n c_i^2\sigma_i^2\le\sum\limits_{i=1}^n c_i^2\sigma_1^2=\sigma_1^2\|\boldsymbol{x}\|^2 Ax2=i=1ncivi,i=1nciσi2vi=i=1nci2σi2i=1nci2σ12=σ12x2取等条件为 c 1 2 = ∥ x ∥ 2 c_1^2=\|\boldsymbol{x}\|^2 c12=x2 c 2 = c 3 = ⋯ = c n = 0 c_2=c_3=\cdots=c_n=0 c2=c3==cn=0,此时 x = c 1 v \boldsymbol{x}=c_1\boldsymbol{v} x=c1v,故 x \boldsymbol{x} x A T A A^T A ATA对应于特征值 σ 1 2 \sigma_1^2 σ12的特征向量。证毕。∎

如果 x ⊥ v 1 \boldsymbol{x}\perp\boldsymbol{v}_1 xv1,即 c 1 = 0 c_1=0 c1=0,那么同理可证 ∥ A x ∥ ≤ σ 2 ∥ x ∥ 2 \|A\boldsymbol{x}\|\le\sigma_2\|\boldsymbol{x}\|^2 Axσ2x2;如果 x ⊥ v 1 \boldsymbol{x}\perp\boldsymbol{v}_1 xv1 x ⊥ v 2 \boldsymbol{x}\perp\boldsymbol{v}_2 xv2,即 c 1 = c 2 = 0 c_1=c_2=0 c1=c2=0,则 ∥ A x ∥ ≤ σ 3 ∥ x ∥ 2 \|A\boldsymbol{x}\|\le\sigma_3\|\boldsymbol{x}\|^2 Axσ3x2;依此类推。

三、奇异值分解的定义

上面介绍了奇异值,下面介绍如何利用奇异值对矩阵进行分解。

A A A是一个 m × n m\times n m×n矩阵, σ 1 ≥ σ 2 ≥ ⋯ ≥ σ n ≥ 0 \sigma_1\ge\sigma_2\ge\cdots\ge\sigma_n\ge 0 σ1σ2σn0是它的奇异值。令 r r r A A A的秩,也就是 A A A非零奇异值的个数。

定义5 A A A的一个奇异值分解是具有如下形式的分解: A = U Σ V T A=U\Sigma V^T A=UΣVT其中

  • U U U是一个 m × m m\times m m×m正交矩阵;
  • V V V是一个 n × n n\times n n×n正交矩阵;
  • Σ \Sigma Σ是一个 m × n m\times n m×n矩阵,它非常类似于一个对角矩阵:其第 i i i个对角元是 σ i \sigma_i σi,对于 i = 1 , 2 , ⋯   , r i=1,2,\cdots,r i=1,2,,r Σ \Sigma Σ的其他元素都是 0 0 0

例如,当 A A A是对称方阵时,它的奇异值实际上就是特征值的绝对值。

四、如何进行奇异值分解

引理6
(1) ∥ A v i ∥ = σ i \|A\boldsymbol{v}_i\|=\sigma_i Avi=σi
(2) 若 i ≠ j i\ne j i=j,则 A v i A\boldsymbol{v}_i Avi A v j A\boldsymbol{v}_j Avj正交。

证明 ⟨ A v i , A v j ⟩ = v i T A T A v j = v i T σ j 2 v j = σ j 2 ⟨ v i , v j ⟩ \langle A\boldsymbol{v}_i,A\boldsymbol{v}_j\rangle=\boldsymbol{v}_i^T A^T A\boldsymbol{v}_j=\boldsymbol{v}_i^T\sigma_j^2\boldsymbol{v}_j=\sigma_j^2\langle\boldsymbol{v}_i,\boldsymbol{v}_j\rangle Avi,Avj=viTATAvj=viTσj2vj=σj2vi,vj

  • i = j i=j i=j,由 ∥ v i ∥ = 1 \|\boldsymbol{v}_i\|=1 vi=1 ∥ A v i ∥ 2 = σ i 2 \|A\boldsymbol{v}_i\|^2=\sigma_i^2 Avi2=σi2
  • i ≠ j i\ne j i=j,由 v i ⊥ v j \boldsymbol{v}_i\perp \boldsymbol{v}_j vivj A v i ⊥ A v j A\boldsymbol{v}_i\perp A\boldsymbol{v}_j AviAvj

定理7 A A A是一个 m × n m\times n m×n矩阵。则我们可以这样构造一个 A A A的奇异值分解 A = U Σ V T A=U\Sigma V^T A=UΣVT,其中:

  • V V V A T A A^T A ATA的单位正交特征向量组 v 1 , v 2 , ⋯   , v n \boldsymbol{v}_1,\boldsymbol{v}_2,\cdots,\boldsymbol{v}_n v1,v2,,vn,满足 A T A v i = σ i 2 v i A^T A\boldsymbol{v}_i=\sigma_i^2 \boldsymbol{v}_i ATAvi=σi2vi
  • i ≤ r i\le r ir(此时 σ i ≠ 0 \sigma_i\ne 0 σi=0),则 U U U的第 i i i列是 1 σ 1 A v i \frac{1}{\sigma_1}A\boldsymbol{v}_i σ11Avi。根据引理6,这些列是单位正交的,其他列可以通过任意地扩充 R m \mathbb{R}^m Rm的单位正交基得到。

证明:我们只需证明,如果 U U U V V V按照上面的方式定义,则 A = U Σ V T A=U\Sigma V^T A=UΣVT。我们无法直接证明 A = U Σ V T A=U\Sigma V^T A=UΣVT,但是我们可以证明 ∀ x ∈ R n \forall\boldsymbol{x}\in\mathbb{R}^n xRn U Σ V T x = A x U\Sigma V^T\boldsymbol{x}=A\boldsymbol{x} UΣVTx=Ax。这就可以说明 A = U Σ V T A=U\Sigma V^T A=UΣVT(因为若 ∀ x ∈ R n \forall\boldsymbol{x}\in\mathbb{R}^n xRn都有 A x = B x A\boldsymbol{x}=B\boldsymbol{x} Ax=Bx,则 ∀ x ∈ R n \forall\boldsymbol{x}\in\mathbb{R}^n xRn都有 ( A − B ) x = 0 (A-B)\boldsymbol{x}=0 (AB)x=0,即该线性方程组的基础解系的秩为 n n n r ( A − B ) = 0 r(A-B)=0 r(AB)=0 A − B = O A-B=O AB=O A = B A=B A=B)。考虑 V T x = [ v 1 T v 2 T ⋮ v n T ] x = [ v 1 T x v 2 T x ⋮ v n T x ] V^T\boldsymbol{x}=\begin{bmatrix}\boldsymbol{v}_1^T\\\boldsymbol{v}_2^T\\\vdots\\\boldsymbol{v}_n^T\end{bmatrix}\boldsymbol{x}=\begin{bmatrix}\boldsymbol{v}_1^T\boldsymbol{x}\\\boldsymbol{v}_2^T\boldsymbol{x}\\\vdots\\\boldsymbol{v}_n^T\boldsymbol{x}\end{bmatrix} VTx= v1Tv2TvnT x= v1Txv2TxvnTx Σ V T x = [ σ 1 v 1 T x σ 2 v 2 T x ⋮ σ r v r T x 0 ⋮ 0 ] \Sigma V^T\boldsymbol{x}=\begin{bmatrix}\sigma_1\boldsymbol{v}_1^T\boldsymbol{x}\\\sigma_2\boldsymbol{v}_2^T\boldsymbol{x}\\\vdots\\\sigma_r\boldsymbol{v}_r^T\boldsymbol{x}\\0\\\vdots\\0\end{bmatrix} ΣVTx= σ1v1Txσ2v2TxσrvrTx00 左乘 U U U U Σ V T x = ( σ 1 v 1 T x ) 1 σ 1 A v 1 + ( σ 2 v 2 T x ) 1 σ 2 A v 2 + ⋯ + ( σ r v r T x ) 1 σ r A v r = A v 1 v 1 T x + A v 2 v 2 T x + ⋯ + A v r v r T x = A v 1 v 1 T x + A v 2 v 2 T x + ⋯ + A v r v r T x + ⋯ + A v n v n T x = A ( v 1 v 1 T + v 2 v 2 T + ⋯ + v n v n T ) x = A V T V x = A x \begin{aligned} U\Sigma V^T\boldsymbol{x}&=(\sigma_1\boldsymbol{v}_1^T\boldsymbol{x})\frac{1}{\sigma_1}A\boldsymbol{v}_1+(\sigma_2\boldsymbol{v}_2^T\boldsymbol{x})\frac{1}{\sigma_2}A\boldsymbol{v}_2+\cdots+(\sigma_r\boldsymbol{v}_r^T\boldsymbol{x})\frac{1}{\sigma_r}A\boldsymbol{v}_r\\ &=A\boldsymbol{v}_1\boldsymbol{v}_1^T\boldsymbol{x}+A\boldsymbol{v}_2\boldsymbol{v}_2^T\boldsymbol{x}+\cdots+A\boldsymbol{v}_r\boldsymbol{v}_r^T\boldsymbol{x}\\ &=A\boldsymbol{v}_1\boldsymbol{v}_1^T\boldsymbol{x}+A\boldsymbol{v}_2\boldsymbol{v}_2^T\boldsymbol{x}+\cdots+A\boldsymbol{v}_r\boldsymbol{v}_r^T\boldsymbol{x}+\cdots+A\boldsymbol{v}_n\boldsymbol{v}_n^T\boldsymbol{x}\\ &=A(\boldsymbol{v}_1\boldsymbol{v}_1^T+\boldsymbol{v}_2\boldsymbol{v}_2^T+\cdots+\boldsymbol{v}_n\boldsymbol{v}_n^T)\boldsymbol{x}\\ &=AV^T V\boldsymbol{x}\\ &=A\boldsymbol{x} \end{aligned} UΣVTx=(σ1v1Tx)σ11Av1+(σ2v2Tx)σ21Av2++(σrvrTx)σr1Avr=Av1v1Tx+Av2v2Tx++AvrvrTx=Av1v1Tx+Av2v2Tx++AvrvrTx++AvnvnTx=A(v1v1T+v2v2T++vnvnT)x=AVTVx=Ax注意这里用到了当 i > r i>r i>r A v i = σ i = 0 A\boldsymbol{v}_i=\sigma_i=0 Avi=σi=0。这样就证明了 A = U Σ V T A=U\Sigma V^T A=UΣVT。∎

矩阵的奇异值分解在机器学习中有广泛应用,比如在主成分分析(Principal Component Analysis, PCA)中发挥着重要作用。

参考资料

  1. https://en.wikipedia.org/wiki/Eigendecomposition_of_a_matrix
  2. https://math.berkeley.edu/~hutching/teach/54-2017/svd-notes.pdf

网站文章

  • C++项目中如何实现一个栈计算器?

    C++项目中如何实现一个栈计算器?

    写一个栈计算器写一个栈计算器,设计如下:支持 +、-、*、/运算支持后缀输入例如:23+输出:5堆操作可以总结如下:push:将一个元素添加到栈顶部pop:从栈顶部移除该元素top: 获取栈顶部元素的...

    2024-02-01 01:55:42
  • 真的太刺激了,蚂蚁金服难忘的四面经历:Linxu+数据库+数据结构+算法+计算机网络

    真的太刺激了,蚂蚁金服难忘的四面经历:Linxu+数据库+数据结构+算法+计算机网络

    前言 前段时间,蚂蚁金服的热度可不小,互联网圈人人都在讨论它上市的事情,实际上蚂蚁金服上市是迟早的事情。这一下,蚂蚁的员工含金量上升了不少,那我之前蚂蚁提前批这波面经,也是时候分享了。 这次面试,可以...

    2024-02-01 01:55:36
  • Python虚拟环境管理之 pipenv

    Python虚拟环境管理之 pipenv

    创建虚拟环境需要一些工具,本文将会介绍这些工具。 pipenv 是Kenneth Reitz大神的作品,提供Python的各个版本间的管理,各种包管理。

    2024-02-01 01:55:29
  • hua图软件 mac_新入手Mac系统需要做的两件事

    hua图软件 mac_新入手Mac系统需要做的两件事

    最近有小伙伴们提问,新买的Mac 电脑,想要下载点软件,要么下载了软件提示:“xxx”因为出现问题而无法打开。请与开发者联系,还有的小伙伴是这样的提示“xxx.app已损坏,打不开。您应该将它移到废纸...

    2024-02-01 01:55:03
  • Git实操大全(最全操作)

    Git实操大全(最全操作)

    目录1.git常用命令1.1用户签名在此文件中查看(全局的)1.2 git init初始化本地库1.3 git status查看本地库1.4 git add 添加到暂存区1.5 添加到本地库 git ...

    2024-02-01 01:54:56
  • Liunx安装MySQL解压版

    liunx安装解压版教程;

    2024-02-01 01:54:49
  • 【C++】类与类之间的 5 种关系

    【C++】类与类之间的 5 种关系

    该文章就是简要的总结一下面向对象的:类与类之间的关系,熟悉类与类之间的关系,能够帮助我们更好的设计出合理的类;: A继承B,说明A is B;

    2024-02-01 01:54:20
  • vue中element-ui下拉框数据改变后,页面不刷新问题

    vue中element-ui下拉框数据改变后,页面不刷新问题

    vue中element-ui下拉框数据改变后,页面不刷新问题

    2024-02-01 01:54:14
  • css多张图片一行显示居中,【CSS技巧】多图片的垂直居中排版

    css多张图片一行显示居中,【CSS技巧】多图片的垂直居中排版

    多图片的垂直居中排版,比如相册中相片的缩略图展示页,如图所示:先看效果:代码如下:============================-//W3C//DTD XHTML 1.0 Transitional//EN” “http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd“>无标题文档.box{ width:232px; height...

    2024-02-01 01:54:08
  • merge改写update

    1.OLD:需求将HH2中的data_object_id同步至HH中。UPDATEHHASETDATA_OBJECT_ID=(SE...

    2024-02-01 01:54:04