首页 > 其他分享 >奇异值分解(SVD)原理

奇异值分解(SVD)原理

时间:2024-07-20 14:27:01浏览次数:11  
标签:bf SVD boldsymbol 矩阵 cdots 分解 奇异

0 引子

奇异值分解(singular value decomposition,SVD)是一种矩阵因子分解方法,是线性代数的概念。在机器学习中,矩阵分解是常用的手段,作为矩阵分解的经典方法SVD,不仅是经典的数学问题,在工程应用中许多地方也都有它的身影。SVD被广泛应用在推荐系统、图像处理等领域,是一种数据降维的经典方法。

许多数学对象可以通过将它们分解成多个组成部分或者找到它们的一些属性来更好地理解,这些属性是通用的,而不是由我们选择它们的方式所产生的。对应地,我们也可以通过分解矩阵来发现矩阵表示成数组元素时不明显的函数性质。特征分解是使用最广的矩阵分解之一,在这个分解中,我们将矩阵分解成一组特征向量特征值,这样可以帮助我们分析矩阵的特定性质。

奇异值分解是将矩阵分解为奇异向量奇异值。通过奇异值分解,我们会得到一些与特征分解相同类型的信息,但是奇异值分解有更广泛的应用。每一个实数矩阵都有一个奇异值分解,但不一定都有特征分解(例如非方阵矩阵)。

对于矩阵 A \boldsymbol{A} A,使用特征分解分析矩阵 A \boldsymbol{A} A 时,会得到特征向量构成的矩阵 V \boldsymbol{V} V 和特征值构成的向量 λ \boldsymbol{\lambda} λ,即:

A = V d i a g ( λ ) V − 1 \boldsymbol{A} = \boldsymbol{V} diag(\boldsymbol{\lambda}) \boldsymbol{V}^{-1} A=Vdiag(λ)V−1

奇异值分解于特征分解类似,只是此时将矩阵 A \boldsymbol{A} A 分解为三个矩阵的乘积:

A = U Σ V T \boldsymbol{A} = \boldsymbol{U}\boldsymbol{\Sigma}\boldsymbol{V}^{\boldsymbol{T}} A=UΣVT

其中, U \boldsymbol{U} U 是 m 阶正交矩阵, V \boldsymbol{V} V 是 n 阶正交矩阵, Σ \boldsymbol{\varSigma } Σ 是由降序排列的非负的对角线元素组成的 m × n m\times n m×n 矩形对角矩阵(不一定是方阵),对角线上的元素就叫做奇异值,既是 A T A \boldsymbol{A}^T\boldsymbol{A} ATA 特征值的平方根,也是 A A T \boldsymbol{AA}^T AAT 特征值的平方根。 U Σ V T \boldsymbol{U\varSigma V}^{\boldsymbol{T}} UΣVT 称为矩阵 A \boldsymbol{A} A 的奇异值分解, U \boldsymbol{U} U 的列向量被称为左奇异向量,是 A A T \boldsymbol{AA}^T AAT 的特征向量; V \boldsymbol{V} V 的列向量被称为右奇异向量,是 A T A \boldsymbol{A}^T\boldsymbol{A} ATA 的特征向量。

使用SVD可以很容易得到任意矩阵的满秩分解,用满秩分解可以对数据做降维压缩。可以用SVD来证明对任意 m × n m \times n m×n 的矩阵均存在如下分解:
在这里插入图片描述

以上便是奇异值分解的核心内容了,下面将使用简单的线性知识,来帮助理解 SVD 的原理。

1 正交矩阵

正交矩阵是在欧几里得空间里的叫法,在酉空间里叫酉矩阵,一个正交矩阵对应的变换叫正交变换,这个变换的特点是不改变向量的尺寸和向量间的夹角

在这里插入图片描述

假设二维空间中的一个向量 O A \bf{OA} OA,它在标准坐标系也即 e 1 、 e 2 e1、e2 e1、e2 表示的坐标是中表示为 ( a , b ) T (a,b)^T (a,b)T,现在把它用另一组坐标 e 1 ′ 、 e 2 ′ e1'、e2' e1′、e2′ 表示为 ( a ′ , b ′ ) T (a',b')^T (a′,b′)T,存在矩阵 U \boldsymbol{U} U 使得 ( a ′ , b ′ ) T = U ( a , b ) T (a',b')^T=\boldsymbol{U}(a,b)^T (a′,b′)T=U(a,b)T,则 U \boldsymbol{U} U 即为正交矩阵。

从上面的图中可以看到,正交变换只是将需要变换的向量使用另一组正交基表示,在这个过程中,并没有对向量做拉伸处理,也没有改变向量的空间位置(暂且这么说吧)。那么如果对两个向量同时做相同的正交变换,变换前后这两个向量的夹角不会变化。从上面的图中可以看到,可以把坐标系 e 1 ′ , e 2 ′ e1', e2' e1′,e2′ 看作是坐标系 e 1 , e 2 e1, e2 e1,e2 旋转 θ \theta θ 角度得到,也这里的正交变换时旋转变换。假设 X = [ a b ] \boldsymbol{X} = \left[ \begin{matrix} a \\ b \end{matrix} \right] X=[ab​],那么,
a ′ = X e 1 ′ = e 1 ′ T X b ′ = X e 2 ′ = e 2 ′ T X a' = \boldsymbol{X} e1'=e1'^T \boldsymbol{X} \\ b' = \boldsymbol{X} e2'=e2'^T \boldsymbol{X} a′=Xe1′=e1′TXb′=Xe2′=e2′TX

a ′ , b ′ a', b' a′,b′ 实际上是 X \boldsymbol{X} X 在 e 1 ′ , e 2 ′ e1', e2' e1′,e2′ 上的投影大小,那么计算内积可以得到,
[ a ′ b ′ ] = [ e 1 T e 2 T ] X \left[ \begin{matrix} a' \\ b' \end{matrix}\right] = \left[ \begin{matrix} e1^T \\ e2^T \end{matrix} \right] \boldsymbol{X} [a′b′​]=[e1Te2T​]X

从上面的图上可以看出来, e 1 , e 2 e1, e2 e1,e2 是一组正交基,坐标分别为 ( 1 , 0 ) , ( 0 , 1 ) (1, 0), (0, 1) (1,0),(0,1),把这一对基投影到新的坐标轴上得到另一组正交基 e 1 ′ , e 2 ′ e1', e2' e1′,e2′,
e 1 ′ = [ ∣ e 1 ∣ cos ⁡ θ ∣ e 1 ∣ sin ⁡ θ ] e 2 ′ = [ − ∣ e 2 ∣ sin ⁡ θ ∣ e 2 ∣ cos ⁡ θ ] e1' = \left[ \begin{matrix} |e1| \cos \theta \\ |e1| \sin \theta \end{matrix} \right] \\ e2' = \left[ \begin{matrix} -|e2| \sin \theta \\ |e2| \cos \theta \end{matrix} \right] e1′=[∣e1∣cosθ∣e1∣sinθ​]e2′=[−∣e2∣sinθ∣e2∣cosθ​]
即,
U = [ cos ⁡ θ sin ⁡ θ − sin ⁡ θ cos ⁡ θ ] \boldsymbol{U} = \left[ \begin{matrix} \cos \theta & \sin \theta \\ -\sin \theta & \cos \theta \end{matrix} \right] U=[cosθ−sinθ​sinθcosθ​]

正交阵 U \boldsymbol{U} U 行(列)向量之间都是正交单位向量,上面求得的是一个旋转矩阵,它对向量做旋转变换。前文说到旋转变换没有改变向量的空间位置,这个实际上如下图:
在这里插入图片描述

选择 e 1 ′ , e 2 ′ e1', e2' e1′,e2′ 作为新的标准坐标系,那么向量 O A \bf{OA} OA 在原坐标系 e 1 , e 2 e1, e2 e1,e2 中就变成了 O A ′ \bf{OA'} OA′,这样看起来就是向量 O A \bf{OA} OA 顺时针旋转了 θ \theta θ 角度。旋转变换是正交变换的一种,正交变换也可以做反射变换。

2 特征值分解(EVD)

对称阵,在酉空间中称作厄米阵。对称阵一定可以相似对角化,并且对称阵的不同特征值对应的特征向量两两正交。一个矩阵能够相似对角化说明其特征子空间就是其列向量空间,若不能对角化那么其特征子空间是其列向量空间的子空间。

假设矩阵 A \boldsymbol{A} A 是 m × m m \times m m×m 的满秩对称矩阵,那么它又 m m m 个不同的特征值,如果特征值 λ i \lambda _i λi​ 对应的特征向量为 x i \bf{x_i} xi​,那么有,
A x i = λ i x i \boldsymbol{A} \bf{x_i} = \lambda _i \bf{x_i} Axi​=λi​xi​

那么有
A U = U Λ \boldsymbol{A} \boldsymbol{U} = \boldsymbol{U} \boldsymbol{\Lambda} AU=UΛ

其中,
U = [ x 1 x 2 ⋯ x m ] \boldsymbol{U} = \left[ \begin{matrix} \bf{x_1} & \bf{x_2} & \cdots & \bf{x_m} \end{matrix} \right] U=[x1​​x2​​⋯​xm​​]

Λ = [ λ 1 ⋯ 0 ⋮ ⋱ ⋮ 0 ⋯ λ m ] \Lambda = \left[ \begin{matrix} \lambda _1 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & \lambda _m \end{matrix} \right] Λ= ​λ1​⋮0​⋯⋱⋯​0⋮λm​​

此时便得到了 A \boldsymbol{A} A 的特征值分解,由于对称阵的特征向量两两正交,因此 U \boldsymbol{U} U 是正交阵。考虑到正交阵的逆矩阵即是其转置,那么
A = U Λ U − 1 = U Λ U T \boldsymbol{A} = \boldsymbol{U} \boldsymbol{\Lambda} \boldsymbol{U} ^{-1} = \boldsymbol{U} \boldsymbol{\Lambda} \boldsymbol{U} ^{T} A=UΛU−1=UΛUT

假设有向量 x \bf{x} x,

A x = U Λ U T x \boldsymbol{A} \bf{x} = \boldsymbol{U} \boldsymbol{\Lambda} \boldsymbol{U^T} \bf{x} Ax=UΛUTx

易知, U T \boldsymbol{U^T} UT 是正交矩阵,因此 U T \boldsymbol{U^T} UT 对 x \bf{x} x 的变换是正交变换,并且这个正交变换是把 x \bf{x} x 用新的坐标系来表示,这个新的坐标系是 A \boldsymbol{A} A 的所有正交的特征向量构成的。那么 x \bf{x} x 可以使用 A \boldsymbol{A} A 的所有正交的特征向量来表示,
x = a 1 x 1 + a 2 x 2 + ⋯ + a m x m \bf{x} = a_1 \bf{x_1} + a_2 \bf{x_2} + \cdots + a_m \bf{x_m} x=a1​x1​+a2​x2​+⋯+am​xm​

那么向量 x \bf{x} x 经过这样的正交变换之后,其坐标为 [ a 1 , a 2 , ⋯   , a m ] T \left[a_1, a_2, \cdots , a_m \right] ^T [a1​,a2​,⋯,am​]T,那么前面的方程可以写成
U Λ U T x = U Λ [ x 1 T x 2 T ⋮ x m T ] ( a 1 x 1 + a 2 x 2 + ⋯ + a m x m ) = U Λ [ a 1 a 2 ⋮ a m ] \boldsymbol{U} \boldsymbol{\Lambda} \boldsymbol{U^T} \bf{x} = \boldsymbol{U} \boldsymbol{\Lambda} \left[ \begin{matrix} \bf{x}_1^T \\ \bf{x}_2^T \\ \vdots \\ \bf{x}_m^T \end{matrix} \right] (a_1 \bf{x_1} + a_2 \bf{x_2} + \cdots + a_m \bf{x_m}) = \boldsymbol{U} \boldsymbol{\Lambda} \left[ \begin{matrix} a_1 \\ a_2 \\ \vdots \\ a_m \end{matrix} \right] UΛUTx=UΛ ​x1T​x2T​⋮xmT​​ ​(a1​x1​+a2​x2​+⋯+am​xm​)=UΛ ​a1​a2​⋮am​​

从上面的等式可以看出,如果 A \boldsymbol{A} A 不是满秩的话,那么就是说对角阵的对角线上元素存在 0,这时候就会导致维度退化, 这样就可以降维了,这样就会使映射后的向量落入 m 维空间的子空间中。

由于 U \boldsymbol{U} U 和 U T \boldsymbol{U_T} UT​ 互为逆矩阵,所以 U \boldsymbol{U} U 变换是 U T \boldsymbol{U_T} UT​ 变换的逆变换。因此,从对称阵的分解对应的映射分解来分析一个矩阵的变换特点是非常直观的。假设对称阵特征值全为1那么显然它就是单位阵,如果对称阵的特征值有个别是0其他全是1,那么它就是一个正交投影矩阵,它将 m 维向量投影到它的列空间中。

根据对称阵 A \boldsymbol{A} A 的特征向量,如果 A \boldsymbol{A} A 是 2 ∗ 2 2*2 2∗2 的,那么就可以在二维平面中找到这样一个矩形,这个矩形经过 A \boldsymbol{A} A 变换后还是矩形:
在这里插入图片描述

这个矩形的选择就是让其边都落在 A \boldsymbol{A} A 的特征向量方向上,如果选择其他矩形的话变换后的图形就不是矩形了。

特征值分解的对象是对称矩阵 A \boldsymbol{A} A,根据特征值分解可以找到一个超矩形,使其变换之后依然是超矩形,即对称阵 A \boldsymbol{A} A 可以将一组正交基映射到零一组正交基。

3 奇异值分解(SVD)

特征值分解针对的是对称矩阵,那么对于任意 m × n m \times n m×n 的矩阵,找到一组正交基使得它经过变换之后依然是正交基,这便是奇异值分解的核心了。SVD 针对的不限于 m × m m \times m m×m 的满秩对称矩阵,而是针对任意非零实矩阵 A \boldsymbol{A} A。

矩阵的奇异值分解是指将一个非零的实矩阵 A \boldsymbol{A} A, A ∈ B m × n A \in \boldsymbol{B}^{m \times n} A∈Bm×n,表示为以下三个实矩阵乘积形式的运算,即进行矩阵的因子分解:
A = U Σ V T \boldsymbol{A} = \boldsymbol{U} \boldsymbol{\Sigma} \boldsymbol{V} ^T A=UΣVT

其中, U \boldsymbol{U} U 是 m 阶正交矩阵, V \boldsymbol{V} V 是 n 阶正交矩阵, Σ \boldsymbol{\Sigma} Σ 是由降序排列的非负的对角线元素组成的 m × n m \times n m×n 矩形对角矩阵,对角线上的元素就叫做奇异值,满足:

U U T = I V V T = I Σ = d i a g ( σ 1 , σ 2 , ⋯   , σ p ) / / σ 1 ≥ σ 2 ≥ ⋯ ≥ σ p ≥ 0 p = min ⁡ ( m , n ) \boldsymbol{U} \boldsymbol{U} ^T = \boldsymbol{I} \\ \boldsymbol{V} \boldsymbol{V} ^T = \boldsymbol{I} \\ \boldsymbol{\Sigma} = diag(\sigma _1, \sigma _2, \cdots, \sigma _p) // \sigma _1 \ge \sigma _2 \ge \cdots \ge \sigma _p \ge 0 \\ p = \min(m, n) UUT=IVVT=IΣ=diag(σ1​,σ2​,⋯,σp​)//σ1​≥σ2​≥⋯≥σp​≥0p=min(m,n)

U Σ V T \boldsymbol{U} \boldsymbol{\Sigma} \boldsymbol{V} ^T UΣVT 称为矩阵 A \boldsymbol{A} A 的奇异值分解, σ i \sigma _i σi​ 称为矩阵 A \boldsymbol{A} A 的奇异值, U \boldsymbol{U} U 的列向量被称为左奇异向量, b o l d s y m b o l V boldsymbol{V} boldsymbolV 的列向量被称为右奇异向量。

任意给定一个实矩阵,其奇异值分解一定存在,但不唯一,这就是奇异值分解的基本定理

现在假设存在 m × n m \times n m×n 矩阵 A \boldsymbol{A} A,将 n 维空间中的向量映射到 k( k = R a n k ( A ) , k ≤ m k = Rank(A), k \le m k=Rank(A),k≤m) 维空间中。现在的目标就是:在 n 维空间中找一组正交基,使得经过 A \boldsymbol{A} A 变换后还是正交的。假设已经找到这样一组正交基:
v 1 , v 2 , ⋯   , v n {\bf{v_1}, \bf{v_2}, \cdots, \bf{v_n}} v1​,v2​,⋯,vn​

那么这组基经过 A \boldsymbol{A} A 变换之后依然是正交基,那么这组基经过 A \boldsymbol{A} A 变换:
A v 1 , A v 2 , ⋯   , A v n {\boldsymbol{A} \bf{v_1}, \boldsymbol{A} \bf{v_2}, \cdots, \boldsymbol{A} \bf{v_n}} Av1​,Av2​,⋯,Avn​

由于经过 A \boldsymbol{A} A 变换之后依然两两正交,那么:
A v i ⋅ A v j = ( A v i ) T ⋅ A v j = v i T A T A v j = 0 \boldsymbol{A} \bf{v_i} \cdot \boldsymbol{A} \bf{v_j} = (\boldsymbol{A} \bf{v_i})^T \cdot \boldsymbol{A} \bf{v_j} = \bf{v_i}^T \boldsymbol{A} ^T \boldsymbol{A} \bf{v_j} = 0 Avi​⋅Avj​=(Avi​)T⋅Avj​=vi​TATAvj​=0

考虑到前面假设 v i \bf{v_i} vi​ 是一组正交基,那么,
v i T ⋅ v j = v i ⋅ v j = 0 \bf{v_i}^T \cdot \bf{v_j} = \bf{v_i} \cdot \bf{v_j} = 0 vi​T⋅vj​=vi​⋅vj​=0

如果正交基 v \bf{v} v 选择为 A T A \boldsymbol{A} ^T \boldsymbol{A} ATA 的特征向量,即 A T A v i = λ i v i \boldsymbol{A}^T \boldsymbol{A} \bf{v_i} = \lambda _i \bf{v_i} ATAvi​=λi​vi​。由于 A T A \boldsymbol{A}^T \boldsymbol{A} ATA 是对称阵,那么 v i \bf{v_i} vi​ 两两正交,
v i T A T A v j = v i T λ i v j = λ i v i T v j = λ i v i v j = 0 \bf{v_i}^T \boldsymbol{A}^T \boldsymbol{A} \bf{v_j} = \bf{v_i}^T \lambda _i \bf{v_j} = \lambda _i \bf{v_i}^T \bf{v_j} = \lambda _i \bf{v_i} \bf{v_j} = 0 vi​TATAvj​=vi​Tλi​vj​=λi​vi​Tvj​=λi​vi​vj​=0

至此,就找到了经过经过映射之后仍然为正交基的正交基,将映射后的正交基单位化,由于
A v i ⋅ A v i = λ i ⋅ v i ⋅ v i = λ i \boldsymbol{A} \bf{v_i} \cdot \boldsymbol{A} \bf{v_i} = \lambda _i \cdot \bf{v_i} \cdot \bf{v_i} = \lambda _i Avi​⋅Avi​=λi​⋅vi​⋅vi​=λi​

即,
∣ A v i ∣ 2 = λ i ≥ 0 |\boldsymbol{A} \bf{v_i}|^2 = \lambda _i \ge 0 ∣Avi​∣2=λi​≥0

那么对 A v i \boldsymbol{A} \bf{v_i} Avi​ 单位化得到:
u i = A v i ∣ A v i ∣ = 1 λ i A v i \bf{u_i} = \frac{\boldsymbol{A} \bf{v_i}}{|\boldsymbol{A} \bf{v_i}|} = \frac{1}{\sqrt{\lambda _i}} \boldsymbol{A} \bf{v_i} ui​=∣Avi​∣Avi​​=λi​ ​1​Avi​

那么有
A v i = σ i u i , 奇异值, σ i = λ i , 0 ≤ i ≤ k , k = R a n k ( A ) \boldsymbol{A} \bf{v_i} = \sigma _i \bf{u_i}, 奇异值,\sigma _i = \sqrt{\lambda _i}, 0 \le i \le k, k = Rank(\boldsymbol{A}) Avi​=σi​ui​,奇异值,σi​=λi​ ​,0≤i≤k,k=Rank(A)

当 0 ≤ i ≤ m 0 \le i \le m 0≤i≤m 时对 u 1 , u 2 , ⋯   , u k \bf{u_1}, \bf{u_2}, \cdots, \bf{u_k} u1​,u2​,⋯,uk​ 进行拓展 u k + 1 , ⋯   , u m \bf{u_{k+1}}, \cdots, \bf{u_m} uk+1​,⋯,um​,使得 u 1 , u 2 , ⋯   , u m \bf{u_1}, \bf{u_2}, \cdots, \bf{u_m} u1​,u2​,⋯,um​ 为 m m m 维空间中的一组正交基。同样地,对 v 1 , v 2 , ⋯   , v k \bf{v_1}, \bf{v_2}, \cdots, \bf{v_k} v1​,v2​,⋯,vk​ 进行拓展 v k + 1 , ⋯   , v n \bf{v_{k+1}}, \cdots, \bf{v_n} vk+1​,⋯,vn​,使得 v 1 , v 2 , ⋯   , v v \bf{v_1}, \bf{v_2}, \cdots, \bf{v_v} v1​,v2​,⋯,vv​ 为 n n n 维空间中的一组正交基(其中, v k + 1 , ⋯   , v n \bf{v_{k+1}}, \cdots, \bf{v_n} vk+1​,⋯,vn​ 存在于 A \boldsymbol{A} A 地零空间中,即 A x = 0 \boldsymbol{A} \bf{x} = 0 Ax=0 的解),那么有,
A [ v 1 , v 2 , ⋯   , v k ∣ v k + 1 , ⋯   , v n ] = [ u 1 , u 2 , ⋯   , u k ∣ u k + 1 , ⋯   , u m ] [ σ 1 0 ⋯ 0 0 0 σ 2 ⋯ 0 0 ⋮ ⋮ ⋱ ⋮ ⋮ 0 0 ⋯ σ k 0 0 0 ⋯ 0 0 ] \boldsymbol{A} [\bf{v_1}, \bf{v_2}, \cdots, \bf{v_k} | \bf{v_{k+1}}, \cdots, \bf{v_n}] = [\bf{u_1}, \bf{u_2}, \cdots, \bf{u_k} | \bf{u_{k+1}}, \cdots, \bf{u_m}] \left[ \begin{array}{cccc|c} \sigma _1 & 0 & \cdots & 0 & 0 \\ 0 & \sigma _2 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & \sigma _k & 0 \\ \hline 0 & 0 & \cdots & 0 & 0 \end{array} \right] A[v1​,v2​,⋯,vk​∣vk+1​,⋯,vn​]=[u1​,u2​,⋯,uk​∣uk+1​,⋯,um​] ​σ1​0⋮00​0σ2​⋮00​⋯⋯⋱⋯⋯​00⋮σk​0​00⋮00​​

从而便得到了矩阵 A \boldsymbol{A} A 的奇异值分解
A = U Σ V T \boldsymbol{A} = \boldsymbol{U} \boldsymbol{\Sigma} \boldsymbol{V}^T A=UΣVT

其中, V \boldsymbol{V} V 是 n × n n \times n n×n 的正交矩阵, U \boldsymbol{U} U 是 m × m m \times m m×m 的正交矩阵, Σ \Sigma Σ 是 m × n m \times n m×n 的对角阵。

对 A \boldsymbol{A} A 矩阵映射过程分析:
如果在 n 维空间中找到一个超矩形,使其边都落在 A T A \boldsymbol{A^T A} ATA 的特征向量方向上,那么在经过 A \boldsymbol{A} A 变换之后仍然为超矩形。 v i \bf{v_i} vi​ 为矩阵 A T A \boldsymbol{A^T A} ATA 的特征向量,称作 A \boldsymbol{A} A 的右奇异向量。 u i = A v i \bf{u_i} = \boldsymbol{A} \bf{v_i} ui​=Avi​,为 A A T \boldsymbol{A A^T} AAT 的特征向量,称作 A \boldsymbol{A} A 的左奇异向量。

下面证明前面提到的,任意 m × n m \times n m×n 矩阵,都存在满秩分解:

A = [ u 1 , u 2 , ⋯   , u k ∣ u k + 1 , ⋯   , u m ] [ σ 1 0 ⋯ 0 0 0 σ 2 ⋯ 0 0 ⋮ ⋮ ⋱ ⋮ ⋮ 0 0 ⋯ σ k 0 0 0 ⋯ 0 0 ] [ v 1 T ⋮ v k T v k + 1 T ⋮ v n T ] \boldsymbol{A} = [\bf{u_1}, \bf{u_2}, \cdots, \bf{u_k} | \bf{u_{k+1}}, \cdots, \bf{u_m}] \left[ \begin{array}{cccc|c} \sigma _1 & 0 & \cdots & 0 & 0 \\ 0 & \sigma _2 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & \sigma _k & 0 \\ \hline 0 & 0 & \cdots & 0 & 0 \end{array} \right] \left[ \begin{array}{c} \bf{v_1}^T \\ \vdots \\ \bf{v_k}^T \\ \hline \bf{v_{k+1}}^T \\ \vdots \\ \bf{v_n}^T \end{array} \right] A=[u1​,u2​,⋯,uk​∣uk+1​,⋯,um​] ​σ1​0⋮00​0σ2​⋮00​⋯⋯⋱⋯⋯​00⋮σk​0​00⋮00​​ ​v1​T⋮vk​Tvk+1​T⋮vn​T​​

根据矩阵分块乘法的规则,
A = [ u 1 , u 2 , ⋯   , u k ] [ σ 1 ⋱ σ k ] [ v 1 T ⋮ v k T ] + [ u k + 1 , ⋯   , u m ] [ 0 ] [ v k + 1 T ⋮ v n T ] \boldsymbol{A} = [\bf{u_1}, \bf{u_2}, \cdots, \bf{u_k}] \left[ \begin{matrix} \sigma _1 & & \\ & \ddots & \\ & & \sigma _k \\ \end{matrix} \right] \left[ \begin{matrix} \bf{v_1}^T \\ \vdots \\ \bf{v_k}^T \end{matrix} \right] + [\bf{u_{k+1}}, \cdots, \bf{u_m}] \left[ \begin{matrix} 0 \end{matrix} \right] \left[ \begin{matrix} \bf{v_{k+1}}^T \\ \vdots \\ \bf{v_n}^T \end{matrix} \right] A=[u1​,u2​,⋯,uk​] ​σ1​​⋱​σk​​ ​v1​T⋮vk​T​ ​+[uk+1​,⋯,um​][0​] ​vk+1​T⋮vn​T​

由于第二项为 0,那么有,
A = [ u 1 , u 2 , ⋯   , u k ] [ σ 1 ⋱ σ k ] [ v 1 T ⋮ v k T ] \boldsymbol{A} = [\bf{u_1}, \bf{u_2}, \cdots, \bf{u_k}] \left[ \begin{matrix} \sigma _1 & & \\ & \ddots & \\ & & \sigma _k \\ \end{matrix} \right] \left[ \begin{matrix} \bf{v_1}^T \\ \vdots \\ \bf{v_k}^T \end{matrix} \right] A=[u1​,u2​,⋯,uk​] ​σ1​​⋱​σk​​ ​v1​T⋮vk​T​

令,
X = [ u 1 , u 2 , ⋯   , u k ] [ σ 1 ⋱ σ k ] = [ σ 1 u 1 , σ 2 u 2 , ⋯   , σ k u k ] \boldsymbol{X} = [\bf{u_1}, \bf{u_2}, \cdots, \bf{u_k}] \left[ \begin{matrix} \sigma _1 & & \\ & \ddots & \\ & & \sigma _k \\ \end{matrix} \right] = \left[ \sigma _1 \bf{u_1}, \sigma _2 \bf{u_2}, \cdots, \sigma _k \bf{u_k} \right] X=[u1​,u2​,⋯,uk​] ​σ1​​⋱​σk​​ ​=[σ1​u1​,σ2​u2​,⋯,σk​uk​]

Y = [ v 1 T ⋮ v k T ] \boldsymbol{Y} = \left[ \begin{matrix} \bf{v_1}^T \\ \vdots \\ \bf{v_k}^T \end{matrix} \right] Y= ​v1​T⋮vk​T​

那么, A = X Y \boldsymbol{A} = \boldsymbol{XY} A=XY 即是 A \boldsymbol{A} A 的满秩分解。

4 紧奇异值分解和截断奇异值分解

在前面给出的奇异值分解被称为矩阵的完全奇异值分解。实际上常用的是奇异值分解的紧凑形式截断形式紧奇异值分解是与原始矩阵等秩的奇异值分解,截断奇异值分解是比原始矩阵低秩的奇异值分解

4.1 紧奇异值分解

对于 m × n m \times n m×n 实矩阵 A \boldsymbol{A} A,其秩 R a n k ( A ) = r , r ≤ min ⁡ ( m , n ) Rank(\boldsymbol{A}) = r, r \le \min(m, n) Rank(A)=r,r≤min(m,n),则称 U r Σ r V r T \boldsymbol{U_r \Sigma _r V_r ^T} Ur​Σr​VrT​ 为 A \boldsymbol{A} A 的紧奇异值分解(compact singular valus decomposition),即
A = U r Σ r V r T \boldsymbol{A} = \boldsymbol{U_r \Sigma _r V_r ^T} A=Ur​Σr​VrT​

其中 U r \boldsymbol{U_r} Ur​ 是 m × r m \times r m×r 矩阵,由完全奇异值分解中 U \boldsymbol{U} U 的前 r 列得到, V r \boldsymbol{V_r} Vr​ 是 n × r n \times r n×r 矩阵,由完全奇异值分解中 V \boldsymbol{V} V 的前 r 列得到, Σ r \Sigma _r Σr​ 是 r 阶对角矩阵,由完全奇异值分解中 Σ \Sigma Σ 的前 r 个对角元素得到,其秩与 A \boldsymbol{A} A 的秩相等。

4.1 截断奇异值分解

在矩阵的奇异值分解中,只取最大的 k 个奇异值( k > r k>r k>r, r 为矩阵的秩)对应的部分,就得到矩阵的截断奇异值分解。实际应用中提到矩阵的奇异值分解时,通常指截断奇异值分解。

对于 m × n m \times n m×n 实矩阵 A \boldsymbol{A} A,其秩 R a n k ( A ) = r Rank(\boldsymbol{A}) = r Rank(A)=r,且 0 < k < r 0 < k < r 0<k<r,则称 U k Σ k V k T \boldsymbol{U_k \Sigma _k V_k ^T} Uk​Σk​VkT​ 为 A \boldsymbol{A} A 的截断奇异值分解(truncated singular valus decomposition),即
A ≈ U k Σ k V k T \boldsymbol{A} \approx \boldsymbol{U_k \Sigma _k V_k ^T} A≈Uk​Σk​VkT​

其中 U k \boldsymbol{U_k} Uk​ 是 m × k m \times k m×k 矩阵,由完全奇异值分解中 U \boldsymbol{U} U 的前 k 列得到, V k \boldsymbol{V_k} Vk​ 是 n × k n \times k n×k 矩阵,由完全奇异值分解中 V \boldsymbol{V} V 的前 k 列得到, Σ k \Sigma _k Σk​ 是 k 阶对角矩阵,由完全奇异值分解中 Σ \Sigma Σ 的前 k 个对角元素得到,其秩比 A \boldsymbol{A} A 的秩低。

实际上,紧奇异值分解就是截断奇异值分解的一种特殊表现形式。实际应用中,常常需要对矩阵的数据进行压缩,将其近似表示,奇异值分解提供了一种方法。奇异值分解是在平方损失意义下对矩阵的最优近似。紧奇异值分解对应无损压缩,截断奇异值分解对应有损压缩。

5 奇异值分解的外积展开式

A \boldsymbol{A} A 的奇异值分解可以写成外积的形式,
A = ∑ k = 1 n A k = ∑ k = 1 n σ k u k v k T \boldsymbol{A} = \sum _{k=1} ^{n} \boldsymbol{A} _k = \sum _{k=1} ^{n} \sigma _k \bf{u} _k \bf{v} _k ^T A=k=1∑n​Ak​=k=1∑n​σk​uk​vkT​

其中 A k = σ k u k v k T \boldsymbol{A} _k = \sigma _k \bf{u} _k \bf{v} _k ^T Ak​=σk​uk​vkT​,是 m × n m \times n m×n 矩阵,上式将 A \boldsymbol{A} A 分解为矩阵的有序加权和,展开可以得到,
A = σ 1 u 1 v 1 T + σ 2 u 2 v 2 T + ⋯ + σ n u n v n T \boldsymbol{A}=\sigma _1\boldsymbol{u}_1\boldsymbol{v}_{1}^{T}+\sigma _2\boldsymbol{u}_2\boldsymbol{v}_{2}^{T}+\cdots +\sigma _n\boldsymbol{u}_n\boldsymbol{v}_{n}^{T} A=σ1​u1​v1T​+σ2​u2​v2T​+⋯+σn​un​vnT​

当 n = k n=k n=k 时,矩阵 A \boldsymbol{A} A 的秩为 k,并且 A k \boldsymbol{A}_k Ak​ 是秩为 k 的矩阵中在弗罗贝尼乌斯范数意义下 A \boldsymbol{A} A 的最优近似矩阵。矩阵 A k \boldsymbol{A}_k Ak​ 就是 A \boldsymbol{A} A 的截断奇异值分解。

通常奇异值 σ i \sigma _i σi​ 递减的很快,因此 k 取很小值时, A k \boldsymbol{A}_k Ak​ 也可以对 A \boldsymbol{A} A 有很好地近似。

标签:bf,SVD,boldsymbol,矩阵,cdots,分解,奇异
From: https://blog.csdn.net/qq_38342510/article/details/140570809

相关文章

  • Camera 冷启动阶段分解
    目录一、Camxtrace调试开关设置1.设置camxoverridesettingstrace开关2.重启后设置开启camxtrace开关二、Camera冷启动阶段分解分析1.从TouchUp到ActivityStart耗时2.从ActivityStart到App层OpenCamera耗时1.App开始执行MainActivity一系列onCreate,onStar......
  • 【CEEMDAN-VMD-Transformer-LSTM】双重分解+Transformer-LSTM多变量时序预测
    双重分解+Transformer-LSTM是一种用于多变量时序预测的方法,结合了双重分解(CEEMDAN-VMD)、Transformer和LSTM模型。这种方法可以用于分析和预测具有多个变量的时间序列数据。下面是一个更详细的步骤,演示如何使用双重分解+Transformer-LSTM进行多变量时序预测:数据准备:收集多......
  • C++(3) 3D-3D ICP SVD RANSCE
    CMakeLists.txtcmake_minimum_required(VERSION3.5)project(ICP_SVD_example)#SetC++standardtoC++11set(CMAKE_CXX_STANDARD11)set(CMAKE_CXX_STANDARD_REQUIREDON)#FindEigenlibraryfind_package(Eigen3REQUIRED)#IncludedirectoriesforEigeni......
  • CEEMDAN-VMD-CNN-LSTM二次分解结合卷积双向长短期记忆神经网络多变量时序预测(Matlab完
    CEEMDAN-VMD-CNN-LSTM二次分解结合卷积长短期记忆神经网络多变量时序预测(Matlab完整源码和数据)CEEMDAN分解,计算样本熵,根据样本熵进行kmeans聚类,调用VMD对高频分量Co-IMF1二次分解,VMD分解的高频分量与Co_IMF2;Co_IMF3分量作为卷积长短期记忆神经网络模型的目标输出分别预测......
  • CEEMDAN-VMD-CNN-GRU二次分解结合卷积门控循环单元多变量时序预测(Matlab完整源码和数
    CEEMDAN-VMD-CNN-GRU二次分解结合卷积门控循环单元多变量时序预测(Matlab完整源码和数据)CEEMDAN分解,计算样本熵,根据样本熵进行kmeans聚类,调用VMD对高频分量Co-IMF1二次分解,VMD分解的高频分量与Co_IMF2;Co_IMF3分量作为卷积门控循环单元网络模型的目标输出分别预测后相加。......
  • 关于SVD-LLM的应用-基于SVD量化
    关于SVD-LLM的应用-基于SVD量化一背景论文连接:https://arxiv.org/pdf/2403.07378这是论文github:https://github.com/AIoT-MLSys-Lab/SVD-LLM 二什么是SVD SVD可能是可以把矩阵向量转化到另外一个空间角度,以方便数据处理。2.1概念SVD(Singular......
  • 奇异值分解以及matlab实现
    奇异值分解(SingularValueDecomposition)是线性代数中一种重要的矩阵分解,具有压缩矩阵信息的作用目录一、奇异值分解的理论介绍1.奇异值分解的例子2.U的计算3.V的计算4.Σ的计算5.利用SVD对数据进行"降维"(1)对U与V进行分块,得到分块矩阵(2)去除奇异值后得到压缩后的矩阵(3)保留原矩阵的......
  • 高创新 | CEEMDAN-VMD-GRU-Attention双重分解+门控循环单元+注意力机制多元时间序列预
    目录效果一览基本介绍模型设计程序设计参考资料效果一览基本介绍高创新|CEEMDAN-VMD-GRU-Attention双重分解+门控循环单元+注意力机制多元时间序列预测本文提出一种基于CEEMDAN的二次分解方法,通过样本熵重构CEEMDAN分解后的序列,复杂序列通过VMD分解......
  • 牛客周赛 Round 50 D[小红的因式分解] 超级无敌大暴力
    牛客周赛Round50D小红的因式分解超级无敌大暴力首先拿到这个题,真的是一头雾水,本蒟蒻今天才想出来。。。首先拆开式子,我们可以得到a1a2==a;a1b2+a2b1==b;b1b2==c;那么,我们只需要求解一对a1与b1即可得到本题答案,因为剩下的一对a2b2由a/a1和b/b1得到所以我们可以运用......
  • 时间序列分析专题——时间序列分解
    接下来的几章我们会介绍时间序列分析模型,本章我们先来对时间序列概念进行介绍,并进行最初步的时间序列分解时间序列分析大致可分成三大部分,分别是描述过去、分析规律和预测未来目录一、基础名词解释1.时间序列数据2.时间序列的要素与类别(1)时间要素(2)数值要素(3)时期序列与时点序列二......