精华内容
下载资源
问答
  • 7.1 奇异值分解SVD和对称矩阵谱分解 矩阵 Amn,rankA=r<(m,n)A_{mn},rank A=r < (m, n)Amn​,rankA=r<(m,n) 是亏秩矩阵时,虽然高斯消元法可以求得方程 Ax=bA\mathbf{x}=\mathbf{b}Ax=b 的解,很可惜的是,...

    7.1 奇异值分解SVD和对称矩阵谱分解

    矩阵 A m n , r a n k A = r < ( m , n ) A_{mn},rank A=r < (m, n) Amn,rankA=r<(m,n) 是亏秩矩阵时,虽然高斯消元法可以求得方程 A x = b A\mathbf{x}=\mathbf{b} Ax=b 的解,很可惜的是,采用高斯消元法,有两个缺点:第一是,当方程不存在精确解时,高斯消元法无法得到最小二乘解;第二是,当方程存在精确解时,其解的结构是特解加零解。当选择不同的矩阵 A A A 列空间的极大无关组时,可以求得不同的特解,理论上存在无穷多特解满足方程 A x = b A\mathbf{x}=\mathbf{b} Ax=b ,一般情况下,我们希望获得最特殊的特解--最小范数解,即所有特解中,内积最小特解 min ⁡ ∥ x p ∥ \min\| \mathbf{x}_p \| minxp

    由于矩阵 A A A 是亏秩矩阵,其列向量不是 R m R^m Rm 空间的基,故不是任意 b \mathbf{b} b 都有精确解,只有当 b \mathbf{b} b 位于矩阵 A A A 列空间时,才存在精确解,否则只能获得最小二乘解。令向量 b \mathbf{b} b 向矩阵 A A A 列空间的投影向量为 b p \mathbf{b}_p bp ,则方程 A x = b p A\mathbf{x} = \mathbf{b}_p Ax=bp 有精确解,称为最小二乘解,由于矩阵 A A A 不是列满秩矩阵,故不能采用第五章方法获得最小二乘解。同时由于矩阵 A A A 列向量组是相关组,故方程 A x = b p A\mathbf{x} = \mathbf{b}_p Ax=bp 有无穷多解,其解的结构是特解加零解,我们希望获得最小范数特解。综上,对于方程 A x = b A\mathbf{x}=\mathbf{b} Ax=b ,对任意向量 b \mathbf{b} b,我们希望获得最小范数最小二乘解和零解。

    方程 A x = b A\mathbf{x}=\mathbf{b} Ax=b 的解空间为 R n R^n Rn 空间,令向量组 v i , i = 1 , ⋯   , n \mathbf{v}_i,i=1,\cdots,n vi,i=1,,n R n R^n Rn 空间中任意 n n n 个线性无关的单位向量,则向量组 A v i , i = 1 , ⋯   , n A\mathbf{v}_i,i=1,\cdots,n Avi,i=1,,n R m R^m Rm 空间中向量,对其进行单位化,得 A v i = σ i u i , u i 是 单 位 向 量 , σ i ≥ 0 是 向 量 A v i 的 长 度 A\mathbf{v}_i = \sigma_i\mathbf{u}_i,\mathbf{u}_i是单位向量,\sigma_i \ge 0是向量A\mathbf{v}_i的长度 Avi=σiui,uiσi0Avi 。向量 A T u i A^T\mathbf{u}_i ATui n n n 维,所以位于 R n R^n Rn 空间,故其能被该空间的基表示,向量组 v i , i = 1 , ⋯   , n \mathbf{v}_i,i=1,\cdots,n vi,i=1,,n R n R^n Rn 空间的基,故 A T u i A^T\mathbf{u}_i ATui 能被向量组 v i , i = 1 , ⋯   , n \mathbf{v}_i,i=1,\cdots,n vi,i=1,,n 线性表示,所以令 A T u i = ∑ j = 1 n k i j v j A^T\mathbf{u}_i = \sum^n_{j=1}k_{ij}\mathbf{v}_j ATui=j=1nkijvj 。令矩阵 V = [ v 1 , ⋯   , v n ] V=[\mathbf{v}_1,\cdots,\mathbf{v}_n] V=[v1,,vn] ,则
    A T A v i = A T ( A v i ) = A T σ i u i = σ i ∑ j = 1 n k i j v j = V Λ i 其 中 向 量 Λ i = ( σ i k i 1 , σ i k i 2 , ⋯   , σ i k i n ) A^TA\mathbf{v}_i = A^T(A\mathbf{v}_i)=A^T\sigma_i\mathbf{u}_i=\sigma_i\sum^n_{j=1}k_{ij}\mathbf{v}_j=V\Lambda_i \\ 其中向量 \Lambda_i=(\sigma_ik_{i1},\sigma_ik_{i2},\cdots,\sigma_ik_{in}) ATAvi=AT(Avi)=ATσiui=σij=1nkijvj=VΛiΛi=(σiki1,σiki2,,σikin)


    A T A [ v 1 , ⋯   , v n ] = V [ Λ 1 , ⋯   , Λ n ] A T A V = V Λ A T A = V Λ V − 1 A^TA[\mathbf{v}_1,\cdots,\mathbf{v}_n] = V[\Lambda_1,\cdots,\Lambda_n]\\ A^TAV=V\Lambda\\ A^TA = V\Lambda V^{-1} ATA[v1,,vn]=V[Λ1,,Λn]ATAV=VΛATA=VΛV1

    V V V R n R^n Rn 空间中的任意基,如何选择该基,能使 V Λ V − 1 V\Lambda V^{-1} VΛV1 最简洁?表达式涉及矩阵 V V V 的逆,故希望求逆简单。能直接获得矩阵逆的矩阵有正交矩阵,对角阵,单位阵,矩阵 V V V 为对角阵或单位阵,则会造成矩阵 Λ \Lambda Λ 复杂。矩阵 V V V 为正交矩阵时,能使矩阵 Λ \Lambda Λ 为对角阵!该性质就是对称矩阵谱分解定理。

    对称矩阵谱分解定理 任意对称矩阵 S S S 能分解为正交矩阵 Q Q Q 和对角阵 Λ \Lambda Λ ,且满足 S = Q Λ Q T S=Q\Lambda Q^T S=QΛQT

    Q = [ q 1 , ⋯   , q n ] Q=[\mathbf{q}_1,\cdots,\mathbf{q}_n] Q=[q1,,qn] Λ = d i a g ( λ 1 , ⋯   , λ n ) \Lambda=diag(\lambda_1,\cdots,\lambda_n) Λ=diag(λ1,,λn)

    S = Q Λ Q T = [ q 1 , ⋯   , q n ] d i a g ( λ 1 , ⋯   , λ n ) [ q 1 , ⋯   , q n ] T = [ q 1 , ⋯   , q n ] [ λ 1 q 1 T ⋮ λ n T q n T ] = λ 1 q 1 q 1 T + ⋯ + λ n q n q n T = ∑ i = 1 n λ i q i q i T S=Q\Lambda Q^T = [\mathbf{q}_1,\cdots,\mathbf{q}_n]diag(\lambda_1,\cdots,\lambda_n)[\mathbf{q}_1,\cdots,\mathbf{q}_n]^T=[\mathbf{q}_1,\cdots,\mathbf{q}_n]\left[ \begin{matrix} \lambda_1\mathbf{q}^T_1 \\ \vdots \\ \lambda^T_n\mathbf{q}^T_n \end{matrix} \right]\\ =\lambda_1\mathbf{q}_1\mathbf{q}^T_1 + \cdots + \lambda_n\mathbf{q}_n\mathbf{q}^T_n\\ = \sum^n_{i=1}\lambda_i\mathbf{q}_i\mathbf{q}^T_i S=QΛQT=[q1,,qn]diag(λ1,,λn)[q1,,qn]T=[q1,,qn]λ1q1TλnTqnT=λ1q1q1T++λnqnqnT=i=1nλiqiqiT

    注意 u v T \mathbf{u}\mathbf{v}^T uvT 是矩阵,称为向量外积,需要与向量内积区分。因为 r a n k ( q i q i T ) = 1 rank (\mathbf{q}_i\mathbf{q}^T_i) = 1 rank(qiqiT)=1 S = Q Λ Q T = λ 1 q 1 q 1 T + ⋯ + λ n q n q n T S = Q\Lambda Q^T = \lambda_1\mathbf{q}_1\mathbf{q}^T_1 + \cdots + \lambda_n\mathbf{q}_n\mathbf{q}^T_n S=QΛQT=λ1q1q1T++λnqnqnT ,这表明对称矩阵可分解为 n n n 个简单矩阵(秩为 1 1 1 q i q i T \mathbf{q}_i\mathbf{q}^T_i qiqiT 之和,其系数为 λ i \lambda_i λi 。因为 q i \mathbf{q}_i qi 都是单位向量,故 λ i \lambda_i λi 绝对值大的分量更重要,是主成分。

    因为 Q Q Q 是正交矩阵,故 q i q i T = 1 , q i q j T = 0 f o r i ≠ j \mathbf{q}_i\mathbf{q}^T_i=1 ,\mathbf{q}_i\mathbf{q}^T_j = 0 \quad for \quad i \ne j qiqiT=1,qiqjT=0fori=j,所以 S q i = ( λ 1 q 1 q 1 T + ⋯ + λ n q n q n T ) q i = λ 1 q 1 ( q 1 T q i ) + ⋯ + λ n q n ( q n T q i ) = λ i q i S \mathbf{q}_i = (\lambda_1\mathbf{q}_1\mathbf{q}^T_1 + \cdots + \lambda_n\mathbf{q}_n\mathbf{q}^T_n)\mathbf{q}_i = \lambda_1\mathbf{q}_1(\mathbf{q}^T_1\mathbf{q}_i) + \cdots + \lambda_n\mathbf{q}_n(\mathbf{q}^T_n\mathbf{q}_i) = \lambda_i\mathbf{q}_i Sqi=(λ1q1q1T++λnqnqnT)qi=λ1q1(q1Tqi)++λnqn(qnTqi)λiqi S q i = λ i q i S \mathbf{q}_i = \lambda_i\mathbf{q}_i Sqi=λiqi ,我们称 λ i \lambda_i λi 为矩阵 S S S 的特征值, q i \mathbf{q}_i qi 为对应的特征向量。

    r a n k S = r a n k ( Q Λ Q T ) = r a n k ( Λ Q T ) = r a n k Λ rank S = rank (Q\Lambda Q^T) = rank (\Lambda Q^T) = rank \Lambda rankS=rank(QΛQT)=rank(ΛQT)=rankΛ
    所以对角元素 λ i \lambda_i λi 非零数目等于矩阵 S S S 的秩。

    后面证明该定理。

    因为矩阵 A T A A^TA ATA 是对称矩阵,故能分解为 A T A = V Λ V T A^TA=V\Lambda V^T ATA=VΛVT ,得到正交矩阵 V = [ v 1 , ⋯   , v n ] V =[\mathbf{v}_1,\cdots,\mathbf{v}_n] V=[v1,,vn] 和 对角阵 Λ \Lambda Λ 的对角元素 λ i \lambda_i λi 值,且对角阵 Λ \Lambda Λ 的对角元素 λ i \lambda_i λi 非负。因为对任意向量 x \mathbf{x} x ,有 x T A T A x = ( A x ) T ( A x ) ≥ 0 \mathbf{x}^TA^TA\mathbf{x}=(A\mathbf{x})^T(A\mathbf{x}) \ge 0 xTATAx=(Ax)T(Ax)0 ,故 x T V Λ V T x = ( V T x ) T Λ ( V T x ) = y T Λ y = λ 1 y 1 2 + λ 2 y 2 2 + ⋯ + λ n y n 2 ≥ 0 \mathbf{x}^TV\Lambda V^T\mathbf{x} = (V^T\mathbf{x})^T\Lambda (V^T\mathbf{x}) = \mathbf{y}^T\Lambda \mathbf{y} = \lambda_1 y^2_1 + \lambda_2 y^2_2 + \cdots + \lambda_n y^2_n \ge 0 xTVΛVTx=(VTx)TΛ(VTx)=yTΛy=λ1y12+λ2y22++λnyn20 成立,所以 λ i ≥ 0 \lambda_i \ge 0 λi0

    根据对称矩阵性质 S q i = λ i q i S \mathbf{q}_i = \lambda_i\mathbf{q}_i Sqi=λiqi ,故 A T A v i = λ i v i A^TA\mathbf{v}_i = \lambda_i\mathbf{v}_i ATAvi=λivi 成立,矩阵 A T A A^TA ATA 特征值为 λ i \lambda_i λi 且非负,我们习惯把特征值按降序排列,即 λ 1 ≥ λ 2 ≥ ⋯ λ n ≥ 0 \lambda_1 \ge \lambda_2 \ge \cdots \lambda_n \ge 0 λ1λ2λn0

    根据对称矩阵性质 S = λ 1 q 1 q 1 T + ⋯ + λ n q n q n T S = \lambda_1\mathbf{q}_1\mathbf{q}^T_1 + \cdots + \lambda_n\mathbf{q}_n\mathbf{q}^T_n S=λ1q1q1T++λnqnqnT ,故 A T A = λ 1 v 1 v 1 T + ⋯ + λ n v n v n T A^TA = \lambda_1\mathbf{v}_1\mathbf{v}^T_1 + \cdots + \lambda_n\mathbf{v}_n\mathbf{v}^T_n ATA=λ1v1v1T++λnvnvnT ,由于 λ i \lambda_i λi 非负且按降序排列,故靠前的 λ i v i v i T \lambda_i\mathbf{v}_i\mathbf{v}^T_i λiviviT 占矩阵 A T A A^TA ATA 比例更大,是主成分。

    r = r a n k A = r a n k ( A T A ) = r a n k Λ r = rank A = rank (A^TA) = rank \Lambda r=rankA=rank(ATA)=rankΛ ,所以对角元素 λ i \lambda_i λi 非零数目等于矩阵 A A A 的秩!

    现在证明向量组 U = [ u 1 , ⋯   , u n ] U=[\mathbf{u}_1,\cdots,\mathbf{u}_n] U=[u1,,un] 两两正交。
    ( u i T u j ) ( σ i σ j ) = ( A v i ) T ( A v j ) = v i T A T A v j = v i T ( A T A v j ) = v i T λ j v j = λ j v i T v j (\mathbf{u}^T_i\mathbf{u}_j)(\sigma_i\sigma_j) = (A\mathbf{v}_i)^T(A\mathbf{v}_j) = \mathbf{v}^T_iA^TA\mathbf{v}_j=\mathbf{v}^T_i(A^TA\mathbf{v}_j)=\mathbf{v}^T_i\lambda_j\mathbf{v}_j=\lambda_j\mathbf{v}^T_i\mathbf{v}_j (uiTuj)(σiσj)=(Avi)T(Avj)=viTATAvj=viT(ATAvj)=viTλjvj=λjviTvj
    因为向量组 V = [ v 1 , ⋯   , v n ] V=[\mathbf{v}_1,\cdots,\mathbf{v}_n] V=[v1,,vn] 两两正交,故得证。

    i = j i=j i=j ( u i T u i ) ( σ i σ i ) = λ i ( v i T v i ) (\mathbf{u}^T_i\mathbf{u}_i)(\sigma_i\sigma_i) = \lambda_i(\mathbf{v}^T_i\mathbf{v}_i) (uiTui)(σiσi)=λi(viTvi),因为 u i , v i \mathbf{u}_i,\mathbf{v}_i ui,vi 是单位向量,故 λ i = σ i 2 \lambda_i = \sigma^2_i λi=σi2

    又根据 A T A v i = σ i ∑ j = 1 n k i j v j = λ i v i A^TA\mathbf{v}_i =\sigma_i\sum^n_{j=1}k_{ij}\mathbf{v}_j=\lambda_i\mathbf{v}_i ATAvi=σij=1nkijvj=λivi k i j = 0 f o r j ≠ i k_{ij}=0 \quad for \quad j \ne i kij=0forj=i λ i = σ i k i i \lambda_i = \sigma_ik_{ii} λi=σikii ,得 k i i = σ i k_{ii} = \sigma_i kii=σi,所以 A T u i = ∑ j = 1 n k i j v j = k i i v i = σ i v i A^T\mathbf{u}_i = \sum^n_{j=1}k_{ij}\mathbf{v}_j = k_{ii}\mathbf{v}_i = \sigma_i\mathbf{v}_i ATui=j=1nkijvj=kiivi=σivi

    A A T u i = A σ i v i = σ i A v i = σ i σ i u i = λ i u i AA^T\mathbf{u}_i=A\sigma_i\mathbf{v}_i=\sigma_iA\mathbf{v}_i=\sigma_i\sigma_i\mathbf{u}_i=\lambda_i\mathbf{u}_i AATui=Aσivi=σiAvi=σiσiui=λiui ,所以对称矩阵 A A T AA^T AAT 特征值为 λ i \lambda_i λi ,对应特征向量为 u i \mathbf{u}_i ui

    综合上面结论可得矩阵的奇异值分解定理
    1、首先根据对称矩阵谱分解定理,可得 A T A = V Λ V T = λ 1 v 1 v 1 T + ⋯ + λ n v n v n T A^TA=V\Lambda V^T = \lambda_1\mathbf{v}_1\mathbf{v}^T_1 + \cdots + \lambda_n\mathbf{v}_n\mathbf{v}^T_n ATA=VΛVT=λ1v1v1T++λnvnvnT,矩阵 V = [ v 1 , ⋯   , v n ] V=[\mathbf{v}_1,\cdots,\mathbf{v}_n] V=[v1,,vn] 是正交矩阵,矩阵 Λ \Lambda Λ 是对角阵,对角元素 λ i ≥ 0 \lambda_i \ge 0 λi0 按降序排列,非零数目等于 r a n k A rank A rankA
    2、满足如下性质
    A v i = σ i u i A T u i = σ i v i A T A v i = λ i v i A A T u i = λ i u i σ i = λ i 称 为 奇 异 值 , v i 称 为 右 奇 异 向 量 , u i 称 为 左 奇 异 向 量 . A\mathbf{v}_i = \sigma_i\mathbf{u}_i \\ A^T\mathbf{u}_i = \sigma_i\mathbf{v}_i \\ A^TA\mathbf{v}_i = \lambda_i\mathbf{v}_i \\ AA^T\mathbf{u}_i = \lambda_i\mathbf{u}_i \\ \sigma_i = \sqrt{\lambda_i} 称为奇异值,\mathbf{v}_i称为右奇异向量,\mathbf{u}_i称为左奇异向量. Avi=σiuiATui=σiviATAvi=λiviAATui=λiuiσi=λi viui.

    几点说明:
    1、正交矩阵 V = [ v 1 , ⋯   , v n ] V=[\mathbf{v}_1,\cdots,\mathbf{v}_n] V=[v1,,vn] 和对角阵 Λ \Lambda Λ 如何获得呢?理论上可通过解方程 A T A v i = λ i v i A^TA\mathbf{v}_i = \lambda_i\mathbf{v}_i ATAvi=λivi 获得,具体如何解后面介绍,非零奇异值 σ i = λ i , i = 1 , ⋯   , r = r a n k A \sigma_i = \sqrt{\lambda_i},i=1,\cdots,r=rank A σi=λi ,i=1,,r=rankA σ i \sigma_i σi 是向量 A v i A\mathbf{v}_i Avi 的长度和向量 A T u i A^T\mathbf{u}_i ATui 的长度;
    2、根据非零奇异值计算得到 u i = A v i / σ i , i = 1 , ⋯   , r = r a n k A \mathbf{u}_i = A\mathbf{v}_i/\sigma_i,i=1,\cdots,r=rank A ui=Avi/σi,i=1,,r=rankA
    3、由于向量组 u i , i = 1 , ⋯   , r = r a n k A \mathbf{u}_i,i=1,\cdots,r=rank A uii=1,,r=rankA 两两正交,根据基的扩充定理,可扩充 m − r m-r mr 个单位向量 u i , i = r + 1 , ⋯   , m \mathbf{u}_i,i=r+1,\cdots,m uii=r+1,,m ,使矩阵 U = [ u 1 , ⋯   , u m ] U = [\mathbf{u}_1,\cdots,\mathbf{u}_m] U=[u1,um] 为正交矩阵,并满足对称矩阵谱分解定理即 A A T = U Λ U T = λ 1 u 1 u 1 T + ⋯ + λ m u m u m T AA^T=U\Lambda U^T = \lambda_1\mathbf{u}_1\mathbf{u}^T_1 + \cdots + \lambda_m\mathbf{u}_m\mathbf{u}^T_m AAT=UΛUT=λ1u1u1T++λmumumT

    根据 A v i = σ i u i A\mathbf{v}_i = \sigma_i\mathbf{u}_i Avi=σiui A v 1 = σ 1 u 1 A\mathbf{v}_1 = \sigma_1\mathbf{u}_1 Av1=σ1u1 A v 2 = σ 2 u 2 A\mathbf{v}_2 = \sigma_2\mathbf{u}_2 Av2=σ2u2 ⋯ \cdots A v r = σ r u r A\mathbf{v}_r = \sigma_r\mathbf{u}_r Avr=σrur ,故 A [ v 1 , ⋯   , v r ] = [ u 1 , ⋯   , u r ] d i a g ( σ 1 , ⋯   , σ r ) A[\mathbf{v}_1,\cdots,\mathbf{v}_r] = [\mathbf{u}_1,\cdots,\mathbf{u}_r]diag(\sigma_1,\cdots,\sigma_r) A[v1,,vr]=[u1,,ur]diag(σ1,,σr)写成矩阵形式 A V r = U r Σ r AV_r=U_r\Sigma_r AVr=UrΣr ,其中矩阵 V r = [ v 1 , ⋯   , v r ] , U r = [ u 1 , ⋯   , u r ] , Σ r = d i a g ( σ 1 , ⋯   , σ r ) V_r=[\mathbf{v}_1,\cdots,\mathbf{v}_r],U_r=[\mathbf{u}_1,\cdots,\mathbf{u}_r],\Sigma_r=diag(\sigma_1,\cdots,\sigma_r) Vr=[v1,,vr],Ur=[u1,,ur],Σr=diag(σ1,,σr) 满足 V r T V r = E r , U r T U r = E r V^T_rV_r=E_r,U^T_rU_r=E_r VrTVr=Er,UrTUr=Er ,注意 V r V r T ≠ E r , U r U r T ≠ E r V_rV^T_r\ne E_r,U_rU^T_r\ne E_r VrVrT=Er,UrUrT=Er

    A V r = U r Σ r AV_r=U_r\Sigma_r AVr=UrΣr 可进行扩充即 A [ v 1 , ⋯   , v r , ⋯   , v n ] = [ u 1 , ⋯   , u r ⋯   , u m ] d i a g ( σ 1 , ⋯   , σ r , 0 , ⋯   , 0 ) A[\mathbf{v}_1,\cdots,\mathbf{v}_r,\cdots,\mathbf{v}_n] = [\mathbf{u}_1,\cdots,\mathbf{u}_r\cdots,\mathbf{u}_m]diag(\sigma_1,\cdots,\sigma_r,0,\cdots,0) A[v1,,vr,,vn]=[u1,,ur,um]diag(σ1,,σr,0,,0) 写成矩阵形式 A V = U Σ AV=U\Sigma AV=UΣ,此时矩阵 V , U V,U V,U 均是正交矩阵,故 A = U Σ V T = σ 1 u 1 v 1 T + ⋯ + σ r u r v r T A = U\Sigma V^T = \sigma_1\mathbf{u}_1\mathbf{v}^T_1+\cdots+\sigma_r\mathbf{u}_r\mathbf{v}^T_r A=UΣVT=σ1u1v1T++σrurvrT,这表明秩为 r r r 的任意矩阵 A A A 可分解为 r r r 个简单矩阵(秩为 1 1 1)的矩阵 σ i u i v i T \sigma_i\mathbf{u}_i\mathbf{v}^T_i σiuiviT 之和,且 σ 1 ≥ σ 2 ≥ ⋯ σ r > 0 \sigma_1\ge \sigma_2 \ge \cdots \sigma_r > 0 σ1σ2σr>0,按重要性排序。这就是奇异值分解的核心。注意矩阵 Σ \Sigma Σ 尺寸为 ( m , n ) (m,n) (m,n),并不是对角阵,但其前 ( r , r ) (r,r) (r,r) 子矩阵 Σ r \Sigma_r Σr 是对角阵,对角元素为 σ i > 0 \sigma_i>0 σi>0 ,矩阵其它元素均为 0 0 0

    根据 A = U Σ V T = σ 1 u 1 v 1 T + ⋯ + σ r u r v r T A = U\Sigma V^T = \sigma_1\mathbf{u}_1\mathbf{v}^T_1+\cdots+\sigma_r\mathbf{u}_r\mathbf{v}^T_r A=UΣVT=σ1u1v1T++σrurvrT 可得 A T = V Σ U T = σ 1 v 1 u 1 T + ⋯ + σ r v r u r T A^T = V\Sigma U^T = \sigma_1\mathbf{v}_1\mathbf{u}^T_1+\cdots+\sigma_r\mathbf{v}_r\mathbf{u}^T_r AT=VΣUT=σ1v1u1T++σrvrurT

    A T A = V Λ V T = λ 1 v 1 v 1 T + ⋯ + λ r v r v r T A^TA = V\Lambda V^T = \lambda_1\mathbf{v}_1\mathbf{v}^T_1 + \cdots + \lambda_r\mathbf{v}_r\mathbf{v}^T_r ATA=VΛVT=λ1v1v1T++λrvrvrT A A T = U Λ U T = λ 1 u 1 u 1 T + ⋯ + λ r u r u r T AA^T = U\Lambda U^T = \lambda_1\mathbf{u}_1\mathbf{u}^T_1 + \cdots + \lambda_r\mathbf{u}_r\mathbf{u}^T_r AAT=UΛUT=λ1u1u1T++λrururT

    举几个特殊例子说明奇异值分解。
    1、对单位矩阵 A = E A=E A=E 进行奇异值分解。根据 A T A v i = λ i v i A^TA\mathbf{v}_i = \lambda_i\mathbf{v}_i ATAvi=λivi E T E v i = λ i v i E^TE\mathbf{v}_i = \lambda_i\mathbf{v}_i ETEvi=λivi v i = λ i v i \mathbf{v}_i = \lambda_i\mathbf{v}_i vi=λivi ,所以所有特征值 λ i = 1 \lambda_i=1 λi=1 Σ = E \Sigma = E Σ=E。任意单位向量 v i \mathbf{v}_i vi 均满足方程 A T A v i = λ i v i A^TA\mathbf{v}_i = \lambda_i\mathbf{v}_i ATAvi=λivi,故可取任意正交矩阵 V V V ,它们均是特征值 1 1 1 对应的特征向量。根据 A v i = σ i u i A\mathbf{v}_i = \sigma_i\mathbf{u}_i Avi=σiui u i = v i \mathbf{u}_i=\mathbf{v}_i ui=vi, 故单位矩阵的奇异值分解为 E = V E V T E=VEV^T E=VEVT V V V 是任意正交矩阵。通过这个例子可以得出,矩阵的奇异值分解不唯一,只有当矩阵 A A A 是方阵且奇异值均不相等时,分解才唯一。同一个奇异值可以对应多个奇异向量,甚至全部,奇异值对应奇异向量的数目称为几何重数。

    2、对正交矩阵 A = Q A=Q A=Q 进行奇异值分解。根据 A T A v i = λ i v i A^TA\mathbf{v}_i = \lambda_i\mathbf{v}_i ATAvi=λivi Q T Q v i = λ i v i Q^TQ\mathbf{v}_i = \lambda_i\mathbf{v}_i QTQvi=λivi v i = λ i v i \mathbf{v}_i = \lambda_i\mathbf{v}_i vi=λivi ,所以所有特征值 λ i = 1 \lambda_i=1 λi=1 Σ = E \Sigma = E Σ=E。任意单位向量 v i \mathbf{v}_i vi 均满足方程 A T A v i = λ i v i A^TA\mathbf{v}_i = \lambda_i\mathbf{v}_i ATAvi=λivi,故可取任意正交矩阵 V V V ,它们均是特征值 1 1 1 对应的特征向量。根据 A v i = σ i u i A\mathbf{v}_i = \sigma_i\mathbf{u}_i Avi=σiui u i = Q v i \mathbf{u}_i=Q\mathbf{v}_i ui=Qvi U = Q V U=QV U=QV ,故正交矩阵的奇异值分解为 Q = ( Q V ) E V T Q=(QV)EV^T Q=(QV)EVT V V V 是任意正交矩阵。

    3、对秩为 1 1 1 矩阵 A = x y T A=\mathbf{x}\mathbf{y}^T A=xyT 进行奇异值分解,其中 x , y \mathbf{x},\mathbf{y} x,y 是单位向量。根据 A T A v i = λ i v i A^TA\mathbf{v}_i = \lambda_i\mathbf{v}_i ATAvi=λivi y y T v i = λ i v i \mathbf{y}\mathbf{y}^T\mathbf{v}_i = \lambda_i\mathbf{v}_i yyTvi=λivi ,当取 v i = y \mathbf{v}_i=\mathbf{y} vi=y 时有 λ i = 1 \lambda_i=1 λi=1 。由于秩为 1 1 1 ,故只有 λ 1 = 1 \lambda_1=1 λ1=1 ,其它奇异值均为 0 0 0 u 1 = A v 1 = x \mathbf{u}_1=A\mathbf{v}_1=\mathbf{x} u1=Av1=x 。故矩阵 A = x y T A=\mathbf{x}\mathbf{y}^T A=xyT 的奇异值分解就是 A = x y T A=\mathbf{x}\mathbf{y}^T A=xyT 。在 R n R^n Rn 空间扩充基向量得到正交矩阵 V V V ,在 R m R^m Rm 空间扩充基向量得到正交矩阵 U U U ,则 A = U Σ V T A = U\Sigma V^T A=UΣVT ,其中伪对角阵 Σ 11 = 1 , 其 它 元 素 均 为 0 \Sigma_{11}=1,其它元素均为 0 Σ11=10

    4、对角阵 A = D = d i a g ( d 1 , ⋯   , d n ) A=D=diag(d_1,\cdots,d_n) A=D=diag(d1,,dn) 进行奇异值分解。根据 A T A v i = λ i v i A^TA\mathbf{v}_i = \lambda_i\mathbf{v}_i ATAvi=λivi d i a g ( d 1 2 , ⋯   , d n 2 ) v i = λ i v i diag(d^2_1,\cdots,d^2_n)\mathbf{v}_i = \lambda_i\mathbf{v}_i diag(d12,,dn2)vi=λivi ( d i a g ( d 1 2 , ⋯   , d n 2 ) − λ i E ) v i = d i a g ( d 1 2 − λ i , ⋯   , d n 2 − λ i ) v i = ( ( d 1 2 − λ i ) v i 1 , ⋯   , ( d n 2 − λ i ) v i n ) = 0 (diag(d^2_1,\cdots,d^2_n)-\lambda_i E)\mathbf{v}_i = diag(d^2_1-\lambda_i,\cdots,d^2_n-\lambda_i)\mathbf{v}_i = ((d^2_1-\lambda_i)v_{i1} ,\cdots,(d^2_n-\lambda_i)v_{in}) = \mathbf{0} (diag(d12,,dn2)λiE)vi=diag(d12λi,,dn2λi)vi=((d12λi)vi1,,(dn2λi)vin)=0 ,所以 λ 1 = d 1 2 \lambda_1=d^2_1 λ1=d12 v 1 = e 1 \mathbf{v}_1=\mathbf{e}_1 v1=e1 λ i = d i 2 \lambda_i=d^2_i λi=di2 v i = e i \mathbf{v}_i=\mathbf{e}_i vi=ei。故正交矩阵 V = E V=E V=E ,奇异值为 σ i = ∣ d i ∣ \sigma_i=|d_i| σi=di Σ = ∣ D ∣ \Sigma=|D| Σ=D,根据 A v i = σ i u i A\mathbf{v}_i = \sigma_i\mathbf{u}_i Avi=σiui u i = D e i / ∣ d i ∣ = s i g n ( d i ) e i \mathbf{u}_i=D\mathbf{e}_i/|d_i|=sign(d_i)\mathbf{e}_i ui=Dei/di=sign(di)ei U = s i g n ( D ) E U=sign(D)E U=sign(D)E ,故对角阵的奇异值分解为 D = U Σ V T = ( s i g n ( D ) E ) ∣ D ∣ E T D=U\Sigma V^T=(sign(D)E)|D|E^T D=UΣVT=(sign(D)E)DET

    展开全文
  • 矩阵谱分解

    2014-01-05 12:26:34
    添加路径后,调用函数 spectral(A)进行矩阵A的谱分解,s为特征值,g为对应的G矩阵
  • 矩阵谱分解关于谱分解有很多定义,主要区别在于条件的强弱,有的要求一个nn阶矩阵不仅要求可对角化,而且加强条件至其nn个特征值λ1,λ2,...,λn\lambda_1,\lambda_2,...,\lambda_n互异,我们这里由于不深入讨论谱...

    上次听AK讲到谱分解的时候,若有所思,下面将对思考稍作记录。

    矩阵谱分解

    关于谱分解有很多定义,主要区别在于条件的强弱,有的要求一个 n n n阶矩阵不仅要求可对角化,而且加强条件至其 n n n个特征值 λ 1 , λ 2 , . . . , λ n \lambda_1,\lambda_2,...,\lambda_n λ1,λ2,...,λn互异,我们这里由于不深入讨论谱分解,所以就采用最简单的定义来说。

    定义:若 n n n阶矩阵 A A A可对角化,那么存在 n n n n n n阶方阵 G i G_i Gi使得 A = ∑ i = 1 n λ i G i A=\sum_{i=1}^n\lambda_iG_i A=i=1nλiGi.

    证明:设矩阵 A A A n n n个特征值为 λ 1 , λ 2 , . . . , λ n \lambda_1,\lambda_2,...,\lambda_n λ1,λ2,...,λn,其对应的特征向量进行Gram-Schmidt 正交化后为 α 1 , α 2 , . . . , α n \alpha_1,\alpha_2,...,\alpha_n α1,α2,...,αn,那么有 A α i = λ i α i A\alpha_i=\lambda_i\alpha_i Aαi=λiαi。令 P = [ α 1 , α 2 , . . . , α n ] P=[\alpha_1,\alpha_2,...,\alpha_n] P=[α1,α2,...,αn],可以写成矩阵形式有 A P = P ⋅ d i a g ( λ 1 , λ 2 , . . . , λ n ) AP=P\cdot diag(\lambda_1,\lambda_2,...,\lambda_n) AP=Pdiag(λ1,λ2,...,λn)
    此时,令: P − 1 = ( β 1 T , β 2 T , . . . β n T , ) T P^{-1}=(\beta_1^T,\beta_2^T,...\beta_n^T,)^T P1=(β1T,β2T,...βnT,)T,注意到这里的可逆性是由Gram-Schmidt 正交化保证的,当然,如果条件加强至特征值均互异,那么特征向量是相互独立的,这样不需要进行正交化,也可以保证可逆性。 β i \beta_i βi α i \alpha_i αi的size相同。
    KaTeX parse error: Unknown column alignment: * at position 112: …{\begin{array}{*̲{20}{c}} {\beta…

    于是谱分解的命题得证,上述证明同时给出了谱分解的一个构造。

    问题引入

    在讲座中AK猜测谱分解可以像SVD那样对图像进行压缩,但是有个不好的地方在于和SVD不同,谱分解要求矩阵(图像)为方阵。

    当时有若干想法(假设谱分解可以用于图像压缩):

    • 既然谱分解只能作用于方阵,而对于一个 m ⋅ n m\cdot n mn的图像矩阵 A A A,那我们是否能对一个矩形方阵先进行正方形剖分,后处理呢?
    • 正方形剖分后,分别进行压缩后重组的图像和直接进行压缩(假设是图像本来就是方阵的情况下)是否有区别?如果有,那么从肉眼角度,区别大不大?
    • 既然要正方形剖分,那么这样的剖分是否存在?如果存在是否有最小正方形个数的剖分(这样的剖分可以使得处理和重组次数都最小)?如果有最小的剖分,那么这样的剖分数的方法是否唯一?
    • 矩形的正方形剖分种类是否有限

    后来觉得不太对劲,虽然由谱分解 A = ∑ i = 1 n λ i G i A=\sum_{i=1}^n\lambda_iG_i A=i=1nλiGi,可以舍弃掉特征值较小的部分。但是,较小?实际上,矩阵的特征值完全有可能是复数,甚至几乎都是复数(当然这里的复数是特指虚部不为0的意思)。而SVD所求的特征值是 A T A A^TA ATA的,作为实对称矩阵的所有特征值必为实数。先用SVD来验证一下,“剖分-重组”的思路如何:
    这里写图片描述

    (a)和(b)两图都用SVD处理(仅保留一个特征值),从(a)中可以发现“剖分-重组”从肉眼上差别不大,但是从(b)中可以发现差别还是有点明显的,实际上这种思路本身就不抱太大的希望2333。

    矩形的最少正方形剖分

    完美正方形剖分不同的是,我们这里关注的是分成的正方形数量最小,而不需要和完美正方形剖分那样要求每个正方形大小互异。

    • 正方形剖分是否存在?
      存在性是显然的,我们以一个5x3的矩形为例,我们显然可以如下图(a)所示

    这里写图片描述

    将其分成15个小正方形显然是一种剖分,存在性即可证明。此时实际上不仅给出了一种剖分的构造同时也给出了"de数"(剖分后正方形的数量,de是decomposition的缩写)的一个上界,由最小数原理(自然数集的任一非空子集必有最小数)知道,"de数"必有最小值,即对于任意矩形,存在最少的正方形剖分。

    关于"de数"的界还可以参考这篇文章Tiling a Rectangle with the Fewest Squares ,这篇文章指出,对于一个 m ⋅ n m \cdot n mn的矩形,其中 m ≥ n m\geq n mn,那么$log_2 n \leq $ de数 ≤ m n + C ⋅ l o g 2 n \leq \frac{m}{n}+C \cdot log_2 n nm+Clog2n,其中 C C C是一个常数,虽然这个结论没什么太大的用处,但是上下界都出现的 l o g 2 n log_2 n log2n引起了我的注意,它恰是辗转相除法的时间复杂度,为何突然扯到辗转相除法呢?且听我慢慢分析。

    • 贪心策略下的剖分

    狗蔡在ak那场讨论班中给出了一种贪心的办法,即上图(b)中的办法。
    对于这个5x3的矩形,先取一个以短边的正方形,即3x3的正方形,然后一直下去,可以观察发现似乎可以作为一种剖分的办法。

    做了两三次手动计算后发现,实际上这就是一个辗转相除法,可以说明最后剩下的正方形的边长大小恰好就是 g c d ( m , n ) gcd(m,n) gcd(m,n)。对于相邻Fibonacci数型的矩形,这样的方法也是很优美的说,如下图所示:

    这里写图片描述

    对于这个8x13的矩形,我们甚至可以从繁分数的角度来一目了然:
    13 8 = 1 + 1 1 + 1 1 + 1 1 + 1 2 \frac{{13}}{8} = 1 + \frac{1}{{1 + \frac{1}{{1 + \frac{1}{{1 + \frac{1}{2}}}}}}} 813=1+1+1+1+21111
    F { 1 , 1 , 1 , 1 , 2 } F\{1,1,1,1,2\} F{1,1,1,1,2}表示,4个1恰好就是黄、绿、蓝、红四个正方形,最后一个2就是紫色的两个正方形。遗憾的是,这种辗转相除法并不是最优解,因为很快就构造出了反例
    这里写图片描述

    上面是9x10的矩形,可以发现右边这种辗转大法并不是最优的。但似乎可以证明,斐波那契型的矩形是最优解(具体是否有看到这样的文献不是太记得了ww)

    • "de数"剖分的方法是否唯一?

    从目前来看,这个问题并不确定,一般情况下,除了对称解外,至今没有找到通用反例。但是对于斐波那契型矩形而言,却很容易构造多解。(利用辗转相除法)

    好吧还是给出构造吧(如下图所示),注意到由于每次划分的时候,两部分之间都可以对调(如图),而由辗转相除法的复杂度可以估计数量大约有 O ( l o g n ) O(log n) O(logn)个,由乘法原理知道,这种情况下。同一个de数有 O ( 2 [ l o g n ] ) = O ( n ) O(2^{[log n]})=O(n) O(2[logn])=O(n)种划分。

    这里写图片描述

    • 矩形的正方形剖分种类是否有限?

    考虑一个这样的额外问题,一个矩形的正方形剖分的方法的种类是否是有限的呢?辗转相除法是一种通用剖分,直接分为 m ⋅ n m \cdot n mn个矩形也是一种通用剖分,所以对于一个矩形,它至少有两种方法,那么方法数是否有上界呢?

    这个问题是和AK在吃饭的时候解决的,当时西园一楼的天花板恰好就是一个一个的小格子,有灯的部分恰好是有小格子的大矩形,恰好可以用来观察。下面这一步思考虽然有冗余,但是恰是思考的过程,我们可以得到:
    D S q u a r e ≤ D R e c t a n g l e ≤ D T e t r i s , D_{Square}\leq D_{Rectangle} \leq D_{Tetris}, DSquareDRectangleDTetris,
    其中 D S q u a r e , D R e c t a n g l e , D T e t r i s D_{Square}, D_{Rectangle}, D_{Tetris} DSquareDRectangleDTetris分别表示正方形剖分种数,矩形剖分种数和俄罗斯方块剖分种数,用 S n a m e S_{name} Sname表示他们的剖分方法的集合。其如下图所示:

    这里写图片描述

    上述不等式成立的原因是,显然有 S S q u a r e ⊆ S R e c t a n g l e ⊆ S T e t r i s S_{Square}\subseteq S_{Rectangle} \subseteq S_{Tetris} SSquareSRectangleSTetris,所以我们只需要给出 D T e t r i s D_{Tetris} DTetris的一个有限上界就可以说明正方形剖分种类是有限的了,实际上这个有限上界并不难给出。

    考虑一个 m ⋅ n m \cdot n mn的矩形,可以容易知道它一共有 m ( n + 1 ) + n ( m + 1 ) m(n+1)+n(m+1) m(n+1)+n(m+1)条单位边,其中横向的有 m ( n + 1 ) m(n+1) m(n+1)条,纵向的有 n ( m + 1 ) n(m+1) n(m+1)条。对这些边进行二染色,即要么染色,要么不染色,设这样的处理种数的集合为 S b i n S_{bin} Sbin,显然有 S T e t r i s ⊆ S b i n S_{Tetris} \subseteq S_{bin} STetrisSbin,于是立马有:
    D S q u a r e ≤ D T e t r i s < D b i n = 2 m ( n + 1 ) + n ( m + 1 ) , D_{Square} \leq D_{Tetris} < D_{bin}=2^{m(n+1)+n(m+1)}, DSquareDTetris<Dbin=2m(n+1)+n(m+1),
    综上所述,正方形剖分种数的有限性得证。

    数值求解

    我们不妨回顾一下完全背包问题:

    (完全背包问题)有 N N N种物品和一个容量为 V V V的背包,每种物品都有无限件可用。第 i i i种物品的体积是 c i c_i ci,价值是 w i w_i wi。将哪些物品装入背包可使这些物品的体积总和不超过背包容量,且价值总和最大。

    而对于我们的剖分问题而言,我们可以将 m ⋅ n m \cdot n mn的矩形看成是一个容量为 m n mn mn的背包,有 n n n种物品(注意到,不妨设 m ≥ n m\geq n mn,那么最大最大的正方形边长为 n n n),那我们可以改写一下完全背包问题:

    (矩形最少正方形剖分)有 n n n种物品和一个容量为 m n mn mn的背包,每种物品都有无限件可用。第 i i i种物品的体积是 c i 2 c_i^2 ci2,价值是1。将哪些物品装入背包可使这些物品的体积总和等于背包容量,且价值总和最小。

    可以看出,矩形最少正方形剖分问题应该是比完全背包问题要强的,而完全背包问题是NP-complete问题,所以说可以大致估计矩形最少正方形剖分问题也应该是NP-complete问题。所以,本问题不妨从最优化的角度入手。

    先约定一些符号,下面的模型也可以直接参考论文Minimum Tiling of a Rectangle by Squares:。对矩形建立一个平面直角坐标系,不过不是连续的,而是格点状的,左下角的格子看做为 ( 0 , 0 ) (0,0) (0,0)

    这里写图片描述

    我们称边长为 k k k的正方形占据着坐标 ( i , j ) (i,j) (i,j)是指,坐标 ( i , j ) (i,j) (i,j)恰好为正方形 k k k左下角,用 k ∈ ( i , j ) k \in (i,j) k(i,j)表示。由此定义,我们等会讨论的关注点都在上左下角!(注意辣)。更进一步定义:
    KaTeX parse error: Unknown column alignment: * at position 36: …{\begin{array}{*̲{20}{c}} {1,t \…
    其中,对于一个 M N MN MN的矩形, t ∈ { 1 , 2 , . . . , N } t \in \{1,2,...,N\} t{1,2,...,N}, i ∈ N t = { 0 , 1 , . . . , N − t } i\in N_t=\{0,1,...,N-t\} iNt={0,1,...,Nt}以及 j ∈ M t = { 0 , 1 , . . . , M − t } j\in M_t=\{0,1,...,M-t\} jMt={0,1,...,Mt}。由此,我们可以建立一个0-1规划的模型:
    KaTeX parse error: Unknown column alignment: * at position 32: … \begin{array}{*̲{20}{c}} {}&{}&…
    优化目标容易理解,而限制条件的目的是使得任意一个坐标 ( i , j ) (i,j) (i,j)最多只有一个正方形占据(占据是指 k ∈ ( i , j ) k \in (i,j) k(i,j)),上图(a),(b)给出两种案例给大家理解限制条件中和号的范围取定。(重申一次,我们考察的是正方形的左下角,上图黑框给出左下角的范围)另一方面,限制条件还有一个功能:使得矩形每个位置均在一个正方形内,没有缺漏。(想一想为什么,假设有缺漏,直接以这点为 ( i , j ) (i,j) (i,j)考虑一下限制条件即可)

    这个0-1规划问题问题如何求解,额,只能上启发式算法了,特别注意到的是,模型中优化目标有 M N 2 MN^2 MN2个0-1变量,限制条件有大约 O ( M N ) O(MN) O(MN)个。规模可以说是相当地巨大。

    这灰常考验计算能力,截止至2016年6月14日,已经在这里公布了380x380以内的矩形的计算结果。同时这里给出了一个在线的可视化结果。

    下面给出40x40以内的直观结果, z z z轴表示de数,纵横代表 m , n m,n m,n,其中 m ≥ n m \geq n mn所以有一半是没有的,下面给大家欣赏一下:
    这里写图片描述

    一些补充

    • 最少正方形剖分的应用

    最少正方形剖分是有直接的应用的,如有关量子霍尔阵列电阻的文章。

    • 猜想1: d e ( m , n ) = d e ( k m , k n ) de(m,n)=de(km,kn) de(m,n)=de(km,kn)

    其实从上图(右)可以看出很多斜率相同的格点的值是相同的,这个猜想如果成立可以迅速扩大矩形的规模(现在是380x380),另外这个猜想至今没有找到反例。

    • 猜想2:若 m ≥ n m \geq n mn,那么有 d e ( m + n , n ) = d e ( m , n ) + 1 de(m+n,n)=de(m,n)+1 de(m+n,n)=de(m,n)+1

    这个稍微画个图大致就会觉得还是蛮有道理的,但是很遗憾的是,在近几年里,这个猜想被推翻,反例是: d e ( 112 , 53 ) = d e ( 59 , 53 ) = 11 de(112,53) = de(59,53) = 11 de(112,53)=de(59,53)=11

    • 猜想3: d e ( m , n ) ∼ g ( m ) = l o g ϕ ( m ⋅ 5 ) de(m,n) \sim g(m)=log_\phi (m \cdot \sqrt{5}) de(m,n)g(m)=logϕ(m5 ),其中 ϕ = 1 + 5 2 \phi=\frac{1+\sqrt{5}}{2} ϕ=21+5

    上面提到了繁分数,对于Fibonacci型的矩形,如 F k ⋅ F k + 1 F_k \cdot F_{k+1} FkFk+1的矩形,其繁分数对应的数码之和,或者说 d e ( F k , F k + 1 ) de(F_k,F_{k+1}) de(Fk,Fk+1)是满足(应该是成立的,暂时没证明), d e ( F k , F k + 1 ) ∼ l o g ϕ ( F k + 1 ⋅ 5 ) de(F_k,F_{k+1}) \sim log_\phi (F_{k+1} \cdot \sqrt{5}) de(Fk,Fk+1)logϕ(Fk+15 ),而对于一般情况我们用程序验证一下 d e ( m , n ) de(m,n) de(m,n) g ( m ) g(m) g(m)的关系,如下图所示:

    这里写图片描述

    可以看出效果还是可以的,“阶”大致吻合。

    展开全文
  • 矩阵分解——谱分解

    千次阅读 2020-11-25 21:32:18
    矩阵谱分解

    先修知识: 幂等矩阵

    在这里插入图片描述

    谱分解定理

    在这里插入图片描述


    在这里插入图片描述
    在这里插入图片描述

    谱分解的流程

    在这里插入图片描述

    谱分解的推论

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    谱分解的应用

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 此提交包含用于通过基于频谱分而治之的高效稳定算法计算对称矩阵 (QDWHEIG.M) 的特征值分解和奇异值分解 (QDWHSVD.M) 的函数。 计算结果往往比 MATLAB 的内置函数 EIG.M 和 SVD.M 给出的结果更准确。 函数 TEST.M ...
  • 本文主要针对线性代数中的正定矩阵、实对称矩阵、矩阵特征值分解以及矩阵 SVD 分解进行总结。 如果你对这篇文章可感兴趣,可以点击「【访客必读 - 指引页】一文囊括主页内所有高质量博客」,查看完整博客分类与对应...

    前言

    本文主要针对线性代数中的正定矩阵、实对称矩阵、矩阵特征值分解以及矩阵 SVD 分解进行总结。

    如果你对这篇文章可感兴趣,可以点击「【访客必读 - 指引页】一文囊括主页内所有高质量博客」,查看完整博客分类与对应链接。


    正定矩阵

    1. 概念

    首先正定矩阵是定义在对称矩阵的基础上,其次对于任意非零向量 x \textbf{x} x,若 x T A x > 0 \textbf{x}^T\textbf{\textit{A}}\textbf{x}>0 xTAx>0 恒成立,则矩阵 A \textbf{\textit{A}} A 为正定矩阵;若 x T A x ≥ 0 \textbf{x}^T\textbf{\textit{A}}\textbf{x}\geq 0 xTAx0 恒成立,则矩阵 A \textbf{\textit{A}} A 为半正定矩阵。

    2. 物理意义

    任意非零向量 x \textbf{x} x 经过矩阵 A A A 线性变换后,与原先向量的夹角 ≤ 90 \leq 90 90 度。

    3. 其他充要条件

    • 充要条件1: 矩阵 A \textbf{\textit{A}} A 的全部特征值都是正数
      • 推论: A \textbf{\textit{A}} A 正定,则 ∣ A ∣ > 0 |\textbf{\textit{A}}|>0 A>0,即 A \textbf{\textit{A}} A 可逆(有时会根据矩阵正定来判断是否可逆)
      • 推论: A \textbf{\textit{A}} A 正定,则 A \textbf{\textit{A}} A 与单位阵合同,即存在可逆阵 C \textbf{\textit{C}} C,使得 C T AC = E \textbf{\textit{C}}^T\textbf{\textit{A}}\textbf{\textit{C}}=\textbf{\textit{E}} CTAC=E 成立
    • 充要条件2: 矩阵 A \textbf{\textit{A}} A 的各阶顺序主子式都是正数,即 Δ i > 0 \Delta_i>0 Δi>0
      • 其中 Δ i \Delta_i Δi 表示矩阵 A \textbf{\textit{A}} A i i i 行与前 i i i 列组成的子矩阵的行列式的值
      • 推论: ∣ A ∣ > 0 |A|>0 A>0 A A A 一定可逆

    实对称矩阵

    1. 概念

    矩阵为方阵,其中元素均为实数,且 A = A T \textbf{\textit{A}}=\textbf{\textit{A}}^T A=AT

    2. 性质

    • 性质1: 实对称矩阵的特征值都是实数。
      • 假设 λ \lambda λ x \textbf{x} x 分别为矩阵 A \textbf{\textit{A}} A 的特征值、特征向量,即 A x = λ x \textbf{\textit{A}}\textbf{x}=\lambda \textbf{x} Ax=λx
      • 等式两边取共轭,即 a + b i ‾ = a − b i \overline{a+bi}=a-bi a+bi=abi A ‾ x ‾ = λ ‾ x ‾ \overline{\textbf{\textit{A}}}\overline{\textbf{x}}=\overline{\lambda} \overline{\textbf{x}} Ax=λx A \textbf{\textit{A}} A 是实对称矩阵,因此 A = A T = A ‾ \textbf{\textit{A}}=\textbf{\textit{A}}^T=\overline{\textbf{\textit{A}}} A=AT=A,即 A x ‾ = λ ‾ x ‾ \textbf{\textit{A}}\overline{\textbf{x}}=\overline{\lambda} \overline{\textbf{x}} Ax=λx
      • 等式两边取转置,则 x T A = λ x T \textbf{x}^T\textbf{\textit{A}}=\lambda \textbf{x}^T xTA=λxT
      • x T A x ‾ = λ ‾ x T x ‾ = λ x T x ‾ \textbf{x}^T\textbf{\textit{A}}\overline{x}=\overline{\lambda}\textbf{x}^T\overline{\textbf{x}}=\lambda \textbf{x}^T\overline{\textbf{x}} xTAx=λxTx=λxTx
      • ( λ − λ ‾ ) ∥ x ∥ 2 2 = 0 (\lambda-\overline{\lambda})\left\|\textbf{x}\right\|_2^2=0 (λλ)x22=0,由于 ∥ x ∥ 2 2 > 0 \left\|\textbf{x}\right\|_2^2>0 x22>0,因此 λ = λ ‾ \lambda=\overline{\lambda} λ=λ λ \lambda λ 为实数
    • 性质2: 实对称矩阵不同特征值所对应的特征向量必定正交。
      • 假设 A x 1 = λ 1 x 1 \textbf{\textit{A}}\textbf{x}_1=\lambda_1 \textbf{x}_1 Ax1=λ1x1 A x 2 = λ 2 x 2 \textbf{\textit{A}}\textbf{x}_2=\lambda_2 \textbf{x}_2 Ax2=λ2x2 成立
      • x 1 T A = λ 1 x 1 T \textbf{x}_1^T\textbf{\textit{A}}=\lambda_1 \textbf{x}_1^T x1TA=λ1x1T
      • x 1 T A x 2 = λ 1 x 1 T x 2 = λ 2 x 1 T x 2 \textbf{x}_1^T\textbf{\textit{A}}\textbf{x}_2=\lambda_1 \textbf{x}_1^T\textbf{x}_2=\lambda_2\textbf{x}_1^T\textbf{x}_2 x1TAx2=λ1x1Tx2=λ2x1Tx2
      • ( λ 1 − λ 2 ) x 1 T x 2 = 0 (\lambda_1-\lambda_2)\textbf{x}_1^T\textbf{x}_2=0 (λ1λ2)x1Tx2=0,因此 x 1 \textbf{x}_1 x1 x 2 \textbf{x}_2 x2 正交
    • 性质3: 实对称矩阵相同特征值所对应的特征向量必定线性无关。
      • 证明较繁琐,不详细展开
      • 线性无关的向量可以通过施密特正交化转为正交向量
        • 对于线性无关向量组 x 1 , x 2 , . . . , x n \textbf{x}_1,\textbf{x}_2,...,\textbf{x}_n x1,x2,...,xn,转为正交向量组 y 1 , y 2 , . . . , y n \textbf{y}_1,\textbf{y}_2,...,\textbf{y}_n y1,y2,...,yn
        • y 1 = x 1 \textbf{y}_1=\textbf{x}_1 y1=x1
        • y i = x i − ∑ j = 1 i − 1 x i T y j y j T y j y j \textbf{y}_i=\textbf{x}_i-\sum\limits_{j=1}^{i-1}\displaystyle\frac{\textbf{x}_i^T\textbf{y}_j}{\textbf{y}_j^T\textbf{y}_j}\textbf{y}_j yi=xij=1i1yjTyjxiTyjyj
      • 由于新的正交向量都是原来线性无关向量的线性组合,而原先的线性无关向量对应的特征值均相同,因此新的正交向量也均为该相同特征值对应的特征向量
    • 性质4: 任何一个实对称矩阵,都可以正交对角化。
      • 正交对角化,即存在一个正交矩阵 Q ( Q T = Q − 1 ) \textbf{\textit{Q}}(\textbf{\textit{Q}}^T=\textbf{\textit{Q}}^{-1}) Q(QT=Q1) 使得 Q T AQ = D \textbf{\textit{Q}}^T\textbf{\textit{A}}\textbf{\textit{Q}}=\textbf{\textit{D}} QTAQ=D,其中 D \textbf{\textit{D}} D 是一个对角矩阵
      • 实对称矩阵,一定有 n n n 个解,因为实对称矩阵特征值都是实数,因此一共有 n n n 个实特征值(包括重特征值)—— 性质 1 1 1
      • 不同特征值对应的特征向量正交,相同特征值也一定存在对应的正交向量 —— 性质 2 , 3 2,3 2,3
      • 实对称矩阵,一定有 n n n 个正交特征向量,因此可以特征值分解,即该性质成立
    • 性质5: 实对称矩阵的非零特征值个数等于矩阵的秩
      • 矩阵 A \textbf{\textit{A}} A 相似于对角矩阵, P − 1 AP = D \textbf{\textit{P}}^{-1}\textbf{\textit{A}}\textbf{\textit{P}}=\textbf{\textit{D}} P1AP=D
      • 对角矩阵 D \textbf{\textit{D}} D 的秩 = 矩阵 A \textbf{\textit{A}} A 的秩 = D \textbf{\textit{D}} D 非零特征值个数
      • 矩阵 A \textbf{\textit{A}} A 与 矩阵 D \textbf{\textit{D}} D 相似,则特征值相同
    • 性质6:实对称矩阵不一定可逆,但若可逆,则一定是实对称矩阵
      • 0 矩阵对称不可逆
      • ( A − 1 ) T = ( A T ) − 1 = A − 1 (A^{-1})^T=(A^T)^{-1}=A^{-1} (A1)T=(AT)1=A1

    矩阵特征值分解

    1. 概念

    n ∗ n n*n nn 的方阵 A \textbf{\textit{A}} A,由 A x = λ x \textbf{\textit{A}}\textbf{x}=\lambda \textbf{x} Ax=λx 可以得到 AV = V Λ \textbf{\textit{A}}\textbf{\textit{V}}=\textbf{\textit{V}}\Lambda AV=VΛ

    • 如果方阵 A \textbf{\textit{A}} A n n n 个线性无关的特征向量,则 V \textbf{\textit{V}} V 可逆
    • A = V Λ V − 1 \textbf{\textit{A}}=\textbf{\textit{V}}\Lambda\textbf{\textit{V}}^{-1} A=VΛV1
    • 其中矩阵 V \textbf{\textit{V}} V 的列为方阵 A \textbf{\textit{A}} A 的特征向量, Λ = d i a g ( λ 1 , λ 2 , . . . , λ n ) , λ i ≥ λ i + 1 \Lambda=diag(\lambda_1,\lambda_2,...,\lambda_n),\lambda_i\geq \lambda_{i+1} Λ=diag(λ1,λ2,...,λn),λiλi+1

    矩阵 SVD 分解

    1. 概念

    任意一个矩阵 A \textbf{\textit{A}} A 都可以分解为 A = U Σ V T \textbf{\textit{A}}=\textbf{\textit{U}}\Sigma\textbf{\textit{V}}^T A=UΣVT,其中 U , V \textbf{\textit{U}},\textbf{\textit{V}} U,V 均为正交单位矩阵, Σ \Sigma Σ 为对角矩阵。

    2. 证明

    • A T A = ( U Σ V T ) T U Σ V T = V Σ 2 V T \textbf{\textit{A}}^T\textbf{\textit{A}}=(\textbf{\textit{U}}\Sigma\textbf{\textit{V}}^T)^T\textbf{\textit{U}}\Sigma\textbf{\textit{V}}^T=\textbf{\textit{V}}\Sigma^2\textbf{\textit{V}}^T ATA=(UΣVT)TUΣVT=VΣ2VT,由于 A T A \textbf{\textit{A}}^T\textbf{\textit{A}} ATA 为实对称矩阵,因此 V \textbf{\textit{V}} V 为矩阵 A T A \textbf{\textit{A}}^T\textbf{\textit{A}} ATA 对应特征向量组成的正交单位阵。
    • A A T = U Σ V T ( U Σ V T ) T = U Σ 2 U T \textbf{\textit{A}}\textbf{\textit{A}}^T=\textbf{\textit{U}}\Sigma\textbf{\textit{V}}^T(\textbf{\textit{U}}\Sigma\textbf{\textit{V}}^T)^T=\textbf{\textit{U}}\Sigma^2\textbf{\textit{U}}^T AAT=UΣVT(UΣVT)T=UΣ2UT,由于 A A T \textbf{\textit{A}}\textbf{\textit{A}}^T AAT 为实对称矩阵,因此 U \textbf{\textit{U}} U 矩阵 A A T \textbf{\textit{A}}\textbf{\textit{A}}^T AAT 对应特征向量组成的正交单位阵。
    • AV = U Σ \textbf{\textit{A}}\textbf{\textit{V}}=\textbf{\textit{U}}\Sigma AV=UΣ,其中 Σ \Sigma Σ 为对角阵,因此 A v i = σ i u i \textbf{\textit{A}}\textbf{v}_i=\sigma_i\textbf{u}_i Avi=σiui,由此可以得到对角矩阵 Σ \Sigma Σ,其中 σ i \sigma_i σi 就是奇异值。
    • A m ∗ n = U m ∗ m Σ m ∗ n V n ∗ n T \textbf{\textit{A}}_{m*n}=\textbf{\textit{U}}_{m*m}\Sigma_{m*n}\textbf{\textit{V}}_{n*n}^T Amn=UmmΣmnVnnT

    3. 几何角度

    矩阵 U , V U,V U,V 仅负责旋转, Σ \Sigma Σ 负责放缩,具体示意图如下:
    在这里插入图片描述

    4. SVD 压缩

    如下所示,仅选取前 r r r 个不为零的奇异值,可以实现无损压缩。注意非零奇异值的个数等于矩阵 A A A 的秩。

    在这里插入图片描述

    5. 计算伪逆

    在这里插入图片描述

    6. Eckart-Young Theorem

    如果矩阵 B \mathbf{B} B 的秩为 k k k,则 ∣ ∣ A − B ∣ ∣ ≥ ∣ ∣ A − A k ∣ ∣ ||A-B||\geq||A-A_k|| ABAAk 对如下三个矩阵范数成立:

    • ∣ ∣ A ∣ ∣ 2 = σ 1 ||A||_2=\sigma_1 A2=σ1,即最大的奇异值
    • ∣ ∣ A ∣ ∣ N u c l e a r = ∑ i = 1 r σ i ||A||_{Nuclear}=\sum\limits_{i=1}^r\sigma_i ANuclear=i=1rσi
    • Frobenius norm = ∣ ∣ A ∣ ∣ 2 , 1 = ∣ ∣ A ∣ ∣ F = ( t r ( A T A ) ) 1 / 2 = ( ∑ i = 1 m ∑ j = 1 n a i j 2 ) 1 / 2 =||A||_{2,1}=||A||_F=(tr(A^TA))^{1/2}=(\sum\limits_{i=1}^m\sum\limits_{j=1}^na_{ij}^2)^{1/2} =A2,1=AF=(tr(ATA))1/2=(i=1mj=1naij2)1/2

    其中 A \mathbf{A} A A k \mathbf{A_k} Ak 定义如下:
    A = U Σ V T = ∑ i = 1 r σ i u i v i T A k = U k Σ k V k T = ∑ i = 1 k σ i u i v i T \begin{aligned} & \mathbf{A}=\mathbf{U}\Sigma\mathbf{V}^T=\sum\limits_{i=1}^r \sigma_i\mathbf{u}_i\mathbf{v}_i^T\\ & \mathbf{A}_k=\mathbf{U}_k\Sigma_k\mathbf{V}_k^T=\sum\limits_{i=1}^k \sigma_i\mathbf{u}_i\mathbf{v}_i^T \end{aligned} A=UΣVT=i=1rσiuiviTAk=UkΣkVkT=i=1kσiuiviT

    需要注意,矩阵乘上一个正交矩阵,其奇异值不会发生变化,即上述涉及的矩阵范数不会改变。

    7. LSI

    计算不同 q u e r y query query 之间的相似程度,常用于推荐系统。
    在这里插入图片描述
    更多 SVD 的应用:

    展开全文
  • 对称矩阵及SVD分解

    千次阅读 2020-05-09 19:08:57
    对称矩阵及奇异值介绍
  • 完美的对称矩阵 A=ATA = A^TA=AT ⋆\star⋆ 对称矩阵特征值一定是实数 ⋆\star⋆ 对称矩阵的多重特征值,对应的特征空间的维度一定等于重数 ⇔\Leftrightarrow⇔ 几何重数 == 代数重数 ⇔\Leftrightarrow⇔ 一定有n...
  • 只可以用在方阵上2.1.1 特征分解的原理2.1.2 特征分解的合理性2.1.3 特征分解的计算2.1.4 对称矩阵的特征分解(这个性质后面SVD推导用到) 1. 前言 要学会矩阵的特征分解,可以提前看矩阵的一些基础知识: ...
  • 1 对称矩阵性质 1)对称矩阵的特征值都是实数 证明:以2*2的为例 ...在之前对角化一章中,我们知道,不同特征值对应的特征空间,里面的基互相独立 ...这里我们跟进一个更为特殊的性质:...3对称矩阵谱分解 ...
  • 对称矩阵对称矩阵(Symmetric Matrix)是指元素以主对角线为对称轴对应相等的矩阵,例如: 可以看到,对称矩阵的转置等于其自身,即: 对角矩阵对角矩阵(Diagonal Matrix)是指除主对角线之外其他元素都为0的矩阵,...
  • 机器学习笔记——14 奇异值分解(图像压缩)
  • 对称矩阵的SVD分解和正交对角化的区别
  • 对称矩阵 对称矩阵的特征值是实数(越不对称越可能特征值不是实数),并且正交向量是相互正交的。也就是说正交向量构成的矩阵是正交矩阵。 在特征值构造对角矩阵这个文章我们提到了矩阵A可以这样分解成正交向量矩阵...
  • 要学会矩阵的特征分解,可以提前看矩阵的一些基础知识: https://blog.csdn.net/qq_30232405/article/details/1045882932.矩阵的进阶知识2.1 特征分解(谱分解)=>只可以用在方阵上2.1.1 特征分解...
  • 对称正定矩阵的Cholesky分解

    千次阅读 2020-11-08 21:27:42
    对称正定矩阵的三角分解 设 A\ A A为n阶对称正定矩阵,则 A\ A A可以分解为一个单位下三角矩阵 L~\ \tilde{L} L~和一个上三角矩阵 U~\ \tilde{U} U~的乘积:  A=L~U~\...
  • 对称矩阵的合同分解就是他的奇异分解
  • 对称矩阵

    千次阅读 2018-11-07 08:54:50
    对称矩阵   特征向量特征值对角化   维基百科,自由的百科全书 线性代数 A = [ 1 2 3 4 ] {\displaystyle \mathbf {A} ={\begin{bmatrix}1&amp;2\\3&amp;4\end{bmatrix))} 向量 · 向量空间 · 行列...