奇异值分解 Singular Value Decomposition,SVD

用矩阵A乘以向量x,将获得一个新的向量y。其中,矩阵A对向量x可以进行两种变换:

  1. 旋转
  2. 伸缩

例如:

matrixtransformationofvectors

(a)中即旋转又伸缩,(b)中仅仅进行旋转,(c)中仅仅进行伸缩。

奇异值分解是对矩阵的一种因素分解,将一个矩阵分解成若干个各有其应用意义的成分。


以一个几何例子来讨论奇异值分解。

280px-Singular_value_decomposition

一个单位球在任何一个{m}times{n}矩阵下的投影都是一个超椭圆:

mathbb{R}^m下的超椭圆可以被看做是将mathbb{R}^m下的单位球沿着正交方向{u}_{1},{u}_{2},...,{u}_{m}inmathbb{R}^m进行以{sigma}_{1},{sigma}_{2},...,{sigma}_{m}inmathbb{R}^m为系数的伸缩后得到的结果。

为了方便讨论,假设{u}_{j}为单位向量,即{| {u}_{j} |}_{2}=1。则{sigma}_{j}{u}_{j}是超椭圆的主要半轴(principal semiaxes),而{sigma}_{j}为长度。

下图是一个mathbb{R}^2中的例子:

geometric example

通过矩阵A将单位圆Sinmathbb{R}^2变换为椭圆ASinmathbb{R}^2

其中{sigma}_{1},{sigma}_{2}为矩阵A的奇异值(singular values)。

注意:

  1. 如果矩阵A秩(rank)为r,则r个长度{sigma}_{j}不为0
  2. 如果矩阵Am times n矩阵,并且有m data-recalc-dims=n" />,则至多有n个长度{sigma}_{j}不为0
  3. 如果矩阵A满秩(full rank),则矩阵An个奇异值为矩阵AS中主要半轴的长度{sigma}_{j}
    通常将奇异值按照递减顺序排列,即{sigma}_{1}geq{sigma}_{2}geqldotsgeq{sigma}_{n} data-recalc-dims=0" />

一般地,在mathbb{R}^n中的该变换表示为:

A{v}_{j}={sigma}_{j}{u}_{j},1leq j leq n

一共有n个向量被A进行了变换。

更加紧凑的表达形式为:

AV=hat{U}hat{Sigma}

其中:

  1. A{m}times{n}
  2. V{n}times{n}的酉矩阵(unitary matrix)。
  3. hat{U}{m}times{n},其中列是标准正交(orthonormal)的。
  4. hat{Sigma}{n}times{n}的对角线矩阵(diagonal matrix )。如果A满秩,则 hat{Sigma}对角线值均为正。

因为V是酉矩阵,在上式两边同时乘以共轭矩阵(conjugate){V}^{*}获得:

A=hat{U}hat{Sigma}V^{*}

这个公式被称为简化奇异值分解(reduced SVD)

下图揭示了各个矩阵的维度:

dimension


通常对简化奇异值分解进行如下改进将其变为标准的奇异值分解:

  1. hat{U}矩阵中增加额外的m-nhat{U}中原有的列呈标准正交的列,构成矩阵U
    构建好的U{m}times{m},并且为酉矩阵
  2. hat{Sigma}矩阵中增加额外的m-n行0

上述过程是针对满秩矩阵而言的,对于秩亏矩阵,只需要将上述过程中的n用矩阵秩r代替即可。

得到的标准奇异值分解公式为:

A=U{Sigma}V^{*}

其中:

  1. Uinmathbb{C}^{{m}times{m}}为酉矩阵
  2. Vinmathbb{C}^{{n}times{n}}为酉矩阵
  3. Sigmainmathbb{R}^{{m}times{n}}为对角线矩阵

并且:

  • Sigma矩阵对角线上的值为非负且按照递减顺序排列
    {sigma}_{1}geq{sigma}_{2}geqldotsgeq{sigma}_{p}geq 0,p=min(m,n)

下图揭示了各个矩阵的维度:

dimension2

结合几何例子,将矩阵A的奇异值分解理解为:

  1. 首先,通过V^{*}矩阵进行酉变换,对例子中的单位球而言,该变换的效果只是旋转
  2. 然后,通过Sigma矩阵进行伸缩变换,本例中为将旋转后的单位球进行伸缩变换,形成超椭圆
  3. 最后,通过U矩阵进行酉变换,本例中为将上面形成的超椭圆进一步旋转

即,通过矩阵A进行的变换,可以视为上述3个变换的组合。


重要的定理:

  • 任何矩阵A{in}mathbb{C}^{{m}times{n}}均有一个奇异值分解,并且,奇异值{sigma}_{j}有唯一确定值。

计算奇异值分解

上面的定理确定了奇异值分解的存在,但是其值仍需要计算。

考虑如下矩阵乘法:

{A}^{T}{A} = {(U{Sigma}V^{*})}^{T}{(U{Sigma}V^{*})} ={V{Sigma}{U}^{*}}{U{Sigma}{V}^{*}} ={V}{Sigma}^{2}{V}^{*}

{A}{A}^{T} = {(U{Sigma}V^{*})}{(U{Sigma}V^{*})}^{T} ={U{Sigma}{V}^{*}}{V{Sigma}{U}^{*}} ={U}{Sigma}^{2}{U}^{*}

对上述两式分别在两边同时乘以VU有:

{A}^{T}AV = V{Sigma}^{2}

A{A}^{T}U = U{Sigma}^{2}

这样便将奇异值分解转换成了特征值的求解问题。

如果能针对这两个公式找到标准化的特征向量,则特征值的平方根即为奇异值。

在Matlab中,奇异值分解的语句为:[U,S,V]=svd(A)

Reference:

Nathan, Kutz. Computational Methods for Data Analysis Lecture Notes. 

Leave a Reply

Your email address will not be published. Required fields are marked *