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

这篇具有很好参考价值的文章主要介绍了【线性代数/机器学习】矩阵的奇异值与奇异值分解(SVD)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、引言

我们知道,对于一个 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)中发挥着重要作用。文章来源地址https://www.toymoban.com/news/detail-689062.html

参考资料

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

到了这里,关于【线性代数/机器学习】矩阵的奇异值与奇异值分解(SVD)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【机器学习线性代数】03 再论矩阵:空间映射关系的描述

    目录 1.利用矩阵表示空间映射 2.矮胖矩阵对空间的降维压缩 2.1.空间降维的原理 2.2.实

    2024年03月13日
    浏览(40)
  • 数值线性代数:奇异值分解SVD

    本文记录计算矩阵奇异值分解SVD的原理与流程。 注1:限于研究水平,分析难免不当,欢迎批评指正。 设列满秩矩阵,若的特征值为,则称为矩阵的奇异值。 设,则存在正交矩阵与,使得 其中,,,即为矩阵的奇异值。 考虑下述两种情形: 情形1: 其中, 由此可以看出,

    2024年02月15日
    浏览(53)
  • 线性代数:增广矩阵学习笔记

    定义 对于一个 n × m ntimes m n × m 的矩阵 A = [ a i j ] A=[a_{ij}] A = [ a ij ​ ] ,我们可以在它的右边加上一个 n × 1 ntimes1 n × 1 的列向量 b b b ,得到一个 n × ( m + 1 ) ntimes(m+1) n × ( m + 1 ) 的矩阵 [ A ∣ b ] begin{bmatrix} A bigl| bend{bmatrix} [ A ​ ​ ​ b ​ ] ,这个矩阵被称为 A A A 的

    2024年02月05日
    浏览(61)
  • 机器学习-线性代数

    二维空间-Singular 平行的线是 linear dependence 的,singular的,相交的线是Non-singular的,交点就是二元方程解   在机器学习的计算过程中,等式右边的常数全部转化为0,确保每条线都经过(0,0) 三维空间-singular 平面相交于一条线或者重叠,则为singular 线性相关 有唯一解的方程

    2024年03月20日
    浏览(51)
  • 机器学习线性代数基础

    本文是斯坦福大学CS 229机器学习课程的基础材料,原始文件下载 原文作者:Zico Kolter,修改:Chuong Do, Tengyu Ma 翻译:黄海广 备注:请关注github的更新,线性代数和概率论已经更新完毕。 1. 基础概念和符号 线性代数提供了一种紧凑地表示和操作线性方程组的方法。 例如,以

    2024年02月13日
    浏览(48)
  • 【学习笔记】(数学)线性代数-矩阵的概念和特殊矩阵

    由 m × n mtimes n m × n 个数按一定的次序排成的 m m m 行 n n n 列的矩形数表成为 m × n mtimes n m × n 的矩阵,简称 矩阵 (matrix)。 横的各排称为矩阵的 行 ,竖的各列称为矩阵的 列 。 元素为实数的称为 实矩阵 ,一般情况下我们所讨论的矩阵均为实矩阵。 1 行 n n n 列的矩阵称为

    2024年02月09日
    浏览(45)
  • 线性代数 | 机器学习数学基础

    前言 线性代数 (linear algebra)是关于向量空间和线性映射的一个数学分支。它包括对线、面和子空间的研究,同时也涉及到所有的向量空间的一般性质。 本文主要介绍 机器学习 中所用到的线性代数 核心基础概念 ,供读者学习阶段查漏补缺或是 快速学习参考 。 线性代数

    2024年01月21日
    浏览(68)
  • 线性代数与机器学习的紧密关系

    线性代数和机器学习之间的关系是非常紧密的。线性代数是一门数学分支,它研究的是如何解决系统中的线性方程组问题。机器学习则是一门跨学科的研究领域,它旨在让计算机程序能够从数据中自动发现模式、关系和规律,并利用这些发现来进行预测、分类和决策。 在过去

    2024年01月16日
    浏览(42)
  • 线性代数的学习和整理13: 函数与向量/矩阵

    目录 1 函数与 向量/矩阵 2 初等数学的函数 2.1 函数 2.2 函数的定义:定义域  →映射→  值域 3  高等数学里的函数:定义域和陪域/到达域(非值域)的映射关系 3.1 函数 3.2 单射,满射,双射等都是针对定义域 和 陪域的 3.3 易错地方:值域较小且是被决定的 3.4 单射,满射,

    2024年02月11日
    浏览(66)
  • 机器学习-线性代数-逆映射与向量空间

    矩阵的本质是映射。对于一个 m × n m × n m × n 的矩阵,乘法 y = A x y = Ax y = A x 的作用就是将向量从 n n n 维原空间中的 x x x 坐标位置,映射到 m m m 维目标空间的 y y y 坐标位置,这是正向映射的过程。那么,如果已知结果向量的坐标 y y y 去反推原向量的坐标 x x x ,这个过程就

    2024年02月09日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包