网站设计的步骤,使用div建设的网站,运动分类的网站设计论文,html5 经典网站文章目录 矩阵分解LU分解QR分解特征值分解奇异值分解奇异值分解矩阵的基本子空间奇异值分解的性质矩阵的外积展开式 矩阵分解
矩阵的因式分解是把矩阵表示为多个矩阵的乘积#xff0c;这种结构更便于理解和计算。
LU分解
设 A A A 是 m n m\times n mn 矩阵#xff0c;… 文章目录 矩阵分解LU分解QR分解特征值分解奇异值分解奇异值分解矩阵的基本子空间奇异值分解的性质矩阵的外积展开式 矩阵分解
矩阵的因式分解是把矩阵表示为多个矩阵的乘积这种结构更便于理解和计算。
LU分解
设 A A A 是 m × n m\times n m×n 矩阵若 A A A 可以写成乘积 A L U ALU ALU 其中 L L L 为 m m m 阶下三角方阵主对角线元素全是1。 U U U 为 A A A 得到一个行阶梯形矩阵。这样一个分解称为LU分解。 L L L 称为单位下三角方阵。
我们先来看看LU分解的一个应用。当 A L U ALU ALU 时方程 A x b A\mathbf x\mathbf b Axb 可写成 L ( U x ) b L(U\mathbf x)\mathbf b L(Ux)b于是分解为下面两个方程 L y b U x y L\mathbf y\mathbf b \\ U\mathbf x\mathbf y LybUxy 因为 L L L 和 U U U 都是三角矩阵每个方程都比较容易解。
LU 分解算法本节只讲述仅用行倍加变换求解。可以证明单位下三角矩阵的乘积和逆也是单位下三角矩阵 。此时可以用行倍加变换寻找 L L L 和 U U U 。假设存在单位下三角初等矩阵 P 1 , ⋯ , P s P_1,\cdots,P_s P1,⋯,Ps 使 P 1 ⋯ P s A U P_1\cdots P_sAU P1⋯PsAU 于是便得到了 U U U 和 L L L L ( P 1 , ⋯ , P s ) − 1 L(P_1,\cdots,P_s)^{-1} L(P1,⋯,Ps)−1
QR分解
如果 m × n m\times n m×n 矩阵 A A A 的列向量线性无关那么 A A A 可以分解为 A Q R AQR AQR其中 Q Q Q 是一个 m × n m\times n m×n 正交矩阵其列为 col A \text{col }A col A 的一组标准正交基 R R R 是一个上 n × n n\times n n×n 三角可逆矩阵且其对角线上的元素全为正数。
证矩阵 A ( x 1 , x 2 , ⋯ , x n ) A(\mathbf x_1,\mathbf x_2,\cdots,\mathbf x_n) A(x1,x2,⋯,xn) 的列向量是 col A \text{col }A col A 的一组基使用施密特正交化方法可以构造一组标准正交基 u 1 , u 2 , ⋯ , u n \mathbf u_1,\mathbf u_2,\cdots,\mathbf u_n u1,u2,⋯,un 取 Q ( u 1 , u 2 , ⋯ , u n ) Q(\mathbf u_1,\mathbf u_2,\cdots,\mathbf u_n) Q(u1,u2,⋯,un) 因为在正交化过程中 x k ∈ span { x 1 , ⋯ , x k } span { u 1 , ⋯ , u k } , k 1 , 2 , ⋯ , n \mathbf x_k\in\text{span}\{\mathbf x_1,\cdots,\mathbf x_k\}\text{span}\{\mathbf u_1,\cdots,\mathbf u_k\},\quad k1,2,\cdots,n xk∈span{x1,⋯,xk}span{u1,⋯,uk},k1,2,⋯,n 。所以 x k \mathbf x_k xk 可线性表示为 x k r 1 k u 1 ⋯ r k k u k 0 ⋅ u k 1 ⋯ 0 ⋅ u n \mathbf x_kr_{1k}\mathbf u_1\cdotsr_{kk}\mathbf u_k0\cdot\mathbf u_{k1}\cdots0\cdot\mathbf u_n xkr1ku1⋯rkkuk0⋅uk1⋯0⋅un 于是 x k Q r k \mathbf x_kQ\mathbf r_k xkQrk 其中 r k ( r 1 k , ⋯ , r k k , 0 , ⋯ , 0 ) T \mathbf r_k(r_{1k},\cdots,r_{kk},0,\cdots,0)^T rk(r1k,⋯,rkk,0,⋯,0)T 且 r k k ⩾ 0 r_{kk}\geqslant 0 rkk⩾0 (在正交化过程中若 r k k 0 r_{kk}0 rkk0 则 r k k r_{kk} rkk 和 u k \mathbf u_k uk 同乘-1)。取 R ( r 1 , r 2 , ⋯ , r n ) R(\mathbf r_1,\mathbf r_2,\cdots,\mathbf r_n) R(r1,r2,⋯,rn) 则 A ( Q r 1 , Q r 2 , ⋯ , Q r n ) Q R A(Q\mathbf r_1,Q\mathbf r_2,\cdots,Q\mathbf r_n)QR A(Qr1,Qr2,⋯,Qrn)QR 例求 A [ 1 0 0 1 1 0 1 1 1 1 1 1 ] A\begin{bmatrix}100\\110\\111\\111\end{bmatrix} A 111101110011 的一个 QR 分解
解通过施密特正交化方法我们可以得到 col A \text{col }A col A 的一组标准正交基将这些向量组成矩阵 Q [ 1 / 2 − 3 / 12 0 1 / 2 1 / 12 − 2 / 6 1 / 2 1 / 12 1 / 6 1 / 2 1 / 12 1 / 6 ] Q\begin{bmatrix}1/2-3/\sqrt{12}0\\1/21/\sqrt{12}-2/\sqrt{6}\\1/21/\sqrt{12}1/\sqrt{6}\\1/21/\sqrt{12}1/\sqrt{6}\end{bmatrix} Q 1/21/21/21/2−3/12 1/12 1/12 1/12 0−2/6 1/6 1/6 注意到 Q Q Q 是正交矩阵 Q T Q − 1 Q^TQ^{-1} QTQ−1 。所以 R Q − 1 A Q T A RQ^{-1}AQ^TA RQ−1AQTA R [ 1 / 2 1 / 2 1 / 2 1 / 2 − 3 / 12 1 / 12 1 / 12 1 / 12 0 − 2 / 6 1 / 6 1 / 6 ] [ 1 0 0 1 1 0 1 1 1 1 1 1 ] [ 2 3 / 2 1 0 3 / 12 2 / 12 0 0 2 / 6 ] R\begin{bmatrix}1/21/21/21/2\\ -3/\sqrt{12}1/\sqrt{12}1/\sqrt{12}1/\sqrt{12} \\ 0-2/\sqrt{6}1/\sqrt{6}1/\sqrt{6} \end{bmatrix} \begin{bmatrix}100\\110\\111\\111\end{bmatrix} \begin{bmatrix}23/21\\03/\sqrt{12}2/\sqrt{12}\\002/\sqrt{6} \end{bmatrix} R 1/2−3/12 01/21/12 −2/6 1/21/12 1/6 1/21/12 1/6 111101110011 2003/23/12 012/12 2/6
特征值分解
特征值分解是将矩阵分解成特征值和特征向量形式 A Q Σ Q − 1 AQ\Sigma Q^{-1} AQΣQ−1 其中 Σ diag ( λ 1 , λ 2 , ⋯ , λ n ) \Sigma\text{diag}(\lambda_1,\lambda_2,\cdots,\lambda_n) Σdiag(λ1,λ2,⋯,λn) 是一个对角阵其对角线元素是矩阵 A A A 的特征值按降序排列 λ 1 ⩾ λ 2 ⩾ ⋯ ⩾ λ n \lambda_1\geqslant\lambda_2\geqslant\cdots\geqslant\lambda_n λ1⩾λ2⩾⋯⩾λn Q ( u 1 , u 2 , … , u n ) Q(\mathbf u_1,\mathbf u_2,\dots,\mathbf u_n) Q(u1,u2,…,un) 是特征值对应的特征向量组成的矩阵。 特征值分解后方阵的幂变得更容易计算 A t Q Σ t Q − 1 Q [ λ 1 t ⋱ λ n t ] Q − 1 A^tQ\Sigma^t Q^{-1}Q\begin{bmatrix}\lambda_1^t\\\ddots\\\lambda_n^t\end{bmatrix}Q^{-1} AtQΣtQ−1Q λ1t⋱λnt Q−1 特征值分解可以理解为先切换基向量然后伸缩变换最后再切换回原来的基向量。其中 Σ \Sigma Σ 中的特征向量描述伸缩变换的程度特征向量描述变换的方向。
特征值分解有一定的局限性因为它只适用于满秩的方阵。
例求矩阵 A [ − 2 1 1 0 2 0 − 4 1 3 ] A\begin{bmatrix}-211\\020\\-413\end{bmatrix} A −20−4121103 的特征值分解。
解矩阵 A A A 的特征多项式为 det ( A − λ I ) − ( λ − 2 ) 2 ( λ 1 ) \det(A-\lambda I)-(\lambda-2)^2(\lambda1) det(A−λI)−(λ−2)2(λ1) 。特征值和特征向量分别为 λ 1 − 1 : u 1 [ 1 0 1 ] ; λ 2 2 : u 2 [ 0 1 − 1 ] , u 3 [ 1 0 4 ] \lambda_1-1:\mathbf u_1\begin{bmatrix}1\\0\\1\end{bmatrix};\quad \lambda_22:\mathbf u_2\begin{bmatrix}0\\1\\-1\end{bmatrix}, \mathbf u_3\begin{bmatrix}1\\0\\4\end{bmatrix} λ1−1:u1 101 ;λ22:u2 01−1 ,u3 104 可通过行变换计算逆矩阵 ( Q , I ) [ 0 1 1 1 0 0 1 0 0 0 1 0 − 1 4 1 0 0 1 ] → [ 1 0 0 0 1 0 0 1 0 − 1 / 3 1 / 3 1 / 3 0 0 1 4 / 3 − 1 / 3 − 1 / 3 ] ( I , Q − 1 ) (Q,I)\begin{bmatrix}\begin{array}{ccc:ccc} 011100\\100010\\-141001 \end{array}\end{bmatrix}\to \begin{bmatrix}\begin{array}{ccc:ccc} 100010\\010-1/31/31/3\\0014/3-1/3-1/3 \end{array}\end{bmatrix}(I,Q^{-1}) (Q,I) 01−1104101100010001 → 1000100010−1/34/311/3−1/301/3−1/3 (I,Q−1) 所以 A [ 0 1 1 1 0 0 − 1 4 1 ] [ 2 0 0 0 2 0 0 0 − 1 ] [ 0 1 0 − 1 / 3 1 / 3 1 / 3 4 / 3 − 1 / 3 − 1 / 3 ] A\begin{bmatrix}011\\100\\-141\end{bmatrix} \begin{bmatrix}200\\020\\00-1\end{bmatrix} \begin{bmatrix}010\\-1/31/31/3\\4/3-1/3-1/3\end{bmatrix} A 01−1104101 20002000−1 0−1/34/311/3−1/301/3−1/3
奇异值分解
奇异值分解
奇异值分解(Singular Value Decomposition, SVD)是线性代数中一种重要的矩阵分解在生物信息学、信号处理、金融学、统计学等领域有重要应用。
SVD 可以理解为同一线性变换 T : R n ↦ R m T:\R^n\mapsto\R^m T:Rn↦Rm 在不同基下的矩阵表示。假设 Grant 选用标准基对应的矩阵为 A m × n A_{m\times n} Am×n 。类似于特征值分解 Jennifer 通过选择合适的基向量对应的矩阵变为简单的长方形对角矩阵 Σ m × n \Sigma_{m\times n} Σm×n即只有伸缩变换。
假定 Jennifer 使用矩阵 V n ( v 1 , ⋯ , v n ) V_n(\mathbf v_1,\cdots,\mathbf v_n) Vn(v1,⋯,vn) 的列向量作为 R n R^n Rn 的基使用矩阵 U n ( u 1 , ⋯ , u m ) U_n(\mathbf u_1,\cdots,\mathbf u_m) Un(u1,⋯,um)的列向量作为 R m R^m Rm 的基 。那么对于 Jennifer 视角下的向量 x ∈ R n \mathbf x\in R^n x∈Rn
同样的向量用 Grant 的坐标系表示为 V x V\mathbf x Vx用 Grant 的语言描述变换后的向量 A V x AV\mathbf x AVx将变换后的结果变回 Jennifer 的坐标系 U − 1 A V x U^{-1}AV\mathbf x U−1AVx
于是我们得到同一个线性变换 T T T 在 Jennifer 的坐标系下对应的矩阵 Σ U − 1 A V \SigmaU^{-1}AV ΣU−1AV 也可理解为矩阵 A A A 分解为 A m × n U m Σ m × n V n − 1 A_{m\times n}U_m\Sigma_{m\times n}V^{-1}_n Am×nUmΣm×nVn−1 。
接下来自然是探讨上述矩阵分解的适用条件。
注意到 A T A ( U Σ V − 1 ) T ( U Σ V − 1 ) V − T Σ T U T U Σ V − 1 A^TA(U\Sigma V^{-1})^T(U\Sigma V^{-1})V^{-T}\Sigma^TU^TU\Sigma V^{-1} ATA(UΣV−1)T(UΣV−1)V−TΣTUTUΣV−1 不妨取 U , V U,V U,V 为单位正交基即 U , V U,V U,V 为正交矩阵 U T U I , V T V I U^TUI,V^TVI UTUI,VTVI 则 A T A V Σ T Σ V T A^TAV\Sigma^T\Sigma V^T ATAVΣTΣVT 于是可知 V V V 的列向量为 A T A A^TA ATA 的特征向量 Σ T Σ \Sigma^T\Sigma ΣTΣ 为 n n n 阶对角阵其对角元素为 A T A A^TA ATA 的特征值。事实上 A T A A^TA ATA 为对称阵必定存在正交矩阵 V V V 相似对角化。
同理 A A T U Σ Σ T U T AA^TU\Sigma\Sigma^T U^T AATUΣΣTUT 可知 U U U 的列向量为 A A T AA^T AAT 的特征向量 Σ Σ T \Sigma\Sigma^T ΣΣT 为 m m m 阶对角阵其对角元素为 A A T AA^T AAT 的特征值。矩阵 A T A A^TA ATA 为对称阵必定存在正交矩阵 U U U 相似对角化。
目前 U , V U,V U,V 我们都求出来了只剩下求出长方形对角矩阵 Σ \Sigma Σ 。根据 Sylvester降幂公式 A T A A^TA ATA 和 A A T AA^T AAT 有相同的非零特征值。
令 Σ [ Λ r O O O ] \Sigma\begin{bmatrix}\Lambda_rO\\OO\end{bmatrix} Σ[ΛrOOO] 其中 Λ r diag ( σ 1 , ⋯ , σ r ) \Lambda_r\text{diag}(\sigma_1,\cdots,\sigma_r) Λrdiag(σ1,⋯,σr) 。则 Σ T Σ [ Λ r 2 O O O ] n , Σ Σ T [ Λ r 2 O O O ] m \Sigma^T\Sigma\begin{bmatrix}\Lambda_r^2O\\OO\end{bmatrix}_n,\quad \Sigma\Sigma^T\begin{bmatrix}\Lambda_r^2O\\OO\end{bmatrix}_m ΣTΣ[Λr2OOO]n,ΣΣT[Λr2OOO]m 其中 Λ r 2 diag ( σ 1 2 , ⋯ , σ r 2 ) \Lambda_r^2\text{diag}(\sigma_1^2,\cdots,\sigma_r^2) Λr2diag(σ12,⋯,σr2) 。因此矩阵 Σ \Sigma Σ 的对角元素是 A T A A^TA ATA 和 A A T AA^T AAT 的特征值 λ j \lambda_j λj 的平方根 σ j λ j \sigma_j\sqrt{\lambda_j} σjλj 综上任意矩阵均可奇异值分解。 定义SVD是指将秩为 r r r 的 m × n m\times n m×n 矩阵 A A A分解为 A U Σ V T AU\Sigma V^T AUΣVT
其中 U U U 为 m m m 阶正交阵 V V V 为 n n n 阶正交阵 Σ \Sigma Σ 为 m × n m\times n m×n 维长方形对角矩阵对角元素称为矩阵 A A A 的奇异值一般按降序排列 σ 1 ⩾ σ 2 ⩾ ⋯ ⩾ σ r 0 \sigma_1\geqslant\sigma_2\geqslant\cdots\geqslant\sigma_r0 σ1⩾σ2⩾⋯⩾σr0 这样 Σ \Sigma Σ 就唯一确定了。矩阵 U U U 的列向量称为左奇异向量(left singular vector)矩阵 V V V 的列向量称为右奇异向量(right singular vector)。 例这里我们用一个简单的矩阵来说明奇异值分解的步骤。求矩阵 A [ 0 1 1 1 1 0 ] A\begin{bmatrix}01\\11\\10\end{bmatrix} A 011110 的奇异值分解
解首先求出对称阵 A T A A^TA ATA 和 A A T AA^T AAT A T A [ 0 1 1 1 1 0 ] [ 0 1 1 1 1 0 ] [ 2 1 1 2 ] A A T [ 0 1 1 1 1 0 ] [ 0 1 1 1 1 0 ] [ 1 1 0 1 2 1 0 1 1 ] A^TA\begin{bmatrix}011\\110\end{bmatrix} \begin{bmatrix}01\\11\\10\end{bmatrix} \begin{bmatrix}21\\12\end{bmatrix} \\ AA^T\begin{bmatrix}01\\11\\10\end{bmatrix} \begin{bmatrix}011\\110\end{bmatrix} \begin{bmatrix}110\\121\\011\end{bmatrix} ATA[011110] 011110 [2112]AAT 011110 [011110] 110121011 然后求出 A T A A^TA ATA 的特征值和特征向量 λ 1 3 : v 1 [ 1 / 2 1 / 2 ] ; λ 2 1 : v 2 [ − 1 / 2 1 / 2 ] \lambda_13:\mathbf v_1\begin{bmatrix}1/\sqrt{2}\\1/\sqrt{2}\end{bmatrix};\quad \lambda_21:\mathbf v_2\begin{bmatrix}-1/\sqrt{2}\\1/\sqrt{2}\end{bmatrix} λ13:v1[1/2 1/2 ];λ21:v2[−1/2 1/2 ] 求出 A A T AA^T AAT 的特征值和特征向量 λ 1 3 : u 1 [ 1 / 6 2 / 6 1 / 6 ] ; λ 2 1 : u 2 [ 1 / 2 0 − 1 / 2 ] ; λ 3 0 : u 3 [ 1 / 3 − 1 / 3 1 / 3 ] ; \lambda_13:\mathbf u_1\begin{bmatrix}1/\sqrt{6}\\2/\sqrt{6}\\1/\sqrt{6}\end{bmatrix};\quad \lambda_21:\mathbf u_2\begin{bmatrix}1/\sqrt{2}\\0\\-1/\sqrt{2}\end{bmatrix};\quad \lambda_30:\mathbf u_3\begin{bmatrix}1/\sqrt{3}\\-1/\sqrt{3}\\1/\sqrt{3}\end{bmatrix}; λ13:u1 1/6 2/6 1/6 ;λ21:u2 1/2 0−1/2 ;λ30:u3 1/3 −1/3 1/3 ; 其次可以利用 σ i λ i \sigma_i\sqrt{\lambda_i} σiλi 求出奇异值 3 , 1 \sqrt{3},1 3 ,1
最终得到 A A A的奇异值分解 A U Σ V T [ 1 / 6 1 / 2 1 / 3 2 / 6 0 − 1 / 3 1 / 6 − 1 / 2 1 / 3 ] [ 3 0 0 1 0 0 ] [ 1 / 2 1 / 2 − 1 / 2 1 / 2 ] AU\Sigma V^T\begin{bmatrix}1/\sqrt{6}1/\sqrt{2}1/\sqrt{3}\\2/\sqrt{6}0-1/\sqrt{3}\\1/\sqrt{6}-1/\sqrt{2}1/\sqrt{3}\end{bmatrix} \begin{bmatrix}\sqrt{3}0\\01\\00\end{bmatrix} \begin{bmatrix}1/\sqrt{2}1/\sqrt{2}\\-1/\sqrt{2}1/\sqrt{2}\end{bmatrix} AUΣVT 1/6 2/6 1/6 1/2 0−1/2 1/3 −1/3 1/3 3 00010 [1/2 −1/2 1/2 1/2 ]
矩阵的基本子空间
设矩阵 A U Σ V T AU\Sigma V^T AUΣVT 有 r r r 个不为零的奇异值则可以得到矩阵 A A A 的四个基本子空间
正交阵 U U U 的前 r r r 列是 col A \text{col }A col A 的一组单位正交基正交阵 U U U 的后 m − r m-r m−r 列是 ker A T \ker A^T kerAT 的一组单位正交基正交阵 V V V 的前 r r r 列是 col A T \text{col }A^T col AT 的一组单位正交基正交阵 V V V 的后 n − r n-r n−r 列是 ker A \ker A kerA 的一组单位正交基 A ( v 1 , ⋯ , v r ⏟ col A T , v r 1 ⋯ v n ⏟ ker A ) ( u 1 , ⋯ , u r ⏟ col A , u r 1 ⋯ u m ⏟ ker A T ) [ σ 1 ⋱ σ r O ] ⏟ Σ m × n A(\underbrace{\mathbf v_1,\cdots,\mathbf v_r}_{\text{col }A^T},\underbrace{\mathbf v_{r1}\cdots\mathbf v_n}_{\ker A}) (\underbrace{\mathbf u_1,\cdots,\mathbf u_r}_{\text{col }A},\underbrace{\mathbf u_{r1}\cdots\mathbf u_m}_{\ker A^T}) \underbrace{\begin{bmatrix}\sigma_1\\\ddots\\\sigma_r\\O \end{bmatrix}}_{\Sigma_{m\times n}} A(col AT v1,⋯,vr,kerA vr1⋯vn)(col A u1,⋯,ur,kerAT ur1⋯um)Σm×n σ1⋱σrO
证易知 A V U Σ AVU\Sigma AVUΣ 即 { A v i σ i u i , 1 ⩽ i ⩽ r A v i 0 , r i ⩽ n \begin{cases} A\mathbf v_i\sigma_i\mathbf u_i, 1\leqslant i\leqslant r \\ A\mathbf v_i0, r i\leqslant n \end{cases} {Aviσiui,Avi0,1⩽i⩽rri⩽n 取 v 1 , ⋯ , v n \mathbf v_1,\cdots,\mathbf v_n v1,⋯,vn 为 R n \R^n Rn 的单位正交基对于 ∀ x ∈ R n \forall\mathbf x\in \R^n ∀x∈Rn 可以写出 x c 1 v 1 ⋯ c n v n \mathbf xc_1\mathbf v_1\cdotsc_n\mathbf v_n xc1v1⋯cnvn于是 A x c 1 A v 1 ⋯ c r A v r c r 1 A v r 1 ⋯ c n v n c 1 σ 1 u 1 ⋯ c r σ 1 u r 0 ⋯ 0 \begin{aligned} A\mathbf xc_1A\mathbf v_1\cdotsc_rA\mathbf v_rc_{r1}A\mathbf v_{r1}\cdotsc_n\mathbf v_n \\ c_1\sigma_1\mathbf u_1\cdotsc_r\sigma_1\mathbf u_r0\cdots0 \end{aligned} Axc1Av1⋯crAvrcr1Avr1⋯cnvnc1σ1u1⋯crσ1ur0⋯0 所以 A x ∈ span { u 1 , ⋯ , u r } A\mathbf x\in\text{span}\{\mathbf u_1,\cdots,\mathbf u_r\} Ax∈span{u1,⋯,ur} 这说明矩阵 U U U 的前 r r r 列是 col A \text{col }A col A 的一组单位正交基因此 rank A r \text{rank }Ar rank Ar 。同时可知对于任意的 x ∈ span { v r 1 , ⋯ , v n } ⟺ A x 0 \mathbf x\in\text{span}\{\mathbf v_{r1},\cdots,\mathbf v_n\}\iff A\mathbf x0 x∈span{vr1,⋯,vn}⟺Ax0 于是 V V V 的后 n − r n-r n−r 列是 ker A \ker A kerA 的一组单位正交基。
同样通过 A T U V Σ A^TUV\Sigma ATUVΣ 可说明 V V V 的前 r r r 列是 col A T \text{col }A^T col AT 的一组单位正交基 U U U 的后 m − r m-r m−r 列是 ker A T \ker A^T kerAT 的一组单位正交基。
奇异值分解的性质
设矩阵 A U Σ V T AU\Sigma V^T AUΣVT 秩 rank A r \text{rank }Ar rank Ar 分别将 U , Σ , V U,\Sigma,V U,Σ,V 进行分块 U ( U r , U m − r ) V ( V r , V n − r ) Σ [ Λ r O O O ] U(U_r,U_{m-r}) \\ V(V_r,V_{n-r}) \\ \Sigma\begin{bmatrix}\Lambda_rO\\OO\end{bmatrix} U(Ur,Um−r)V(Vr,Vn−r)Σ[ΛrOOO] 其中 U r ( u 1 , ⋯ , u r ) U_r(\mathbf u_1,\cdots,\mathbf u_r) Ur(u1,⋯,ur) 为 m × r m\times r m×r维矩阵 V r ( v 1 , ⋯ , v r ) V_r(\mathbf v_1,\cdots,\mathbf v_r) Vr(v1,⋯,vr) 为 n × r n\times r n×r维矩阵 Λ r diag ( σ 1 , ⋯ , σ r ) \Lambda_r\text{diag}(\sigma_1,\cdots,\sigma_r) Λrdiag(σ1,⋯,σr) 为 r r r 阶对角阵。应用矩阵乘法的性质奇异值分解可以简化为 A U r Λ r V r T AU_r\Lambda_r V^T_r AUrΛrVrT 这个分解称为简化奇异值分解。
性质
奇异值分解可理解为将线性变换分解为三个简单的变换正交变换 V T V^T VT伸缩变换 Σ \Sigma Σ 和正交变换 U U U 。矩阵 A A A 的奇异值分解中奇异值是唯一的但矩阵 U , V U,V U,V 不是唯一的。令 λ \lambda λ 为 A T A A^TA ATA 的一个特征值 v \mathbf v v 是对应的特征向量则 ∥ A v ∥ 2 v T A T A v λ v T v λ ∥ v ∥ \|A\mathbf v\|^2\mathbf v^TA^TA\mathbf v\lambda\mathbf v^T\mathbf v\lambda\|\mathbf v\| ∥Av∥2vTATAvλvTvλ∥v∥易知 A V U Σ AVU\Sigma AVUΣ 或 A T U V Σ T A^TUV\Sigma^T ATUVΣT则左奇异向量和右奇异向量存在关系 A v j σ j u j A T u j σ j v j A\mathbf v_j\sigma_j\mathbf u_j \\ A^T\mathbf u_j\sigma_j\mathbf v_j AvjσjujATujσjvj
矩阵的外积展开式
矩阵 A U Σ V T AU\Sigma V^T AUΣVT 可展开为若干个秩为1的 m × n m\times n m×n矩阵之和 A σ 1 u 1 v 1 T σ 2 u 2 v 2 T ⋯ σ r u r v r T A\sigma_1\mathbf u_1\mathbf v_1^T\sigma_2\mathbf u_2\mathbf v_2^T\cdots\sigma_r\mathbf u_r\mathbf v_r^T Aσ1u1v1Tσ2u2v2T⋯σrurvrT
上式称为矩阵 A A A 的外积展开式。
在长方形对角矩阵 Σ \Sigma Σ 中奇异值按从大到小的顺序排列 σ 1 ⩾ σ 2 ⩾ ⋯ ⩾ σ r 0 \sigma_1\geqslant\sigma_2\geqslant\cdots\geqslant\sigma_r0 σ1⩾σ2⩾⋯⩾σr0 。在很多情况下由于奇异值递减很快前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上。因此我们可以用前面 k k k 个大的奇异值来近似描述矩阵。
奇异值分解也是一种矩阵近似的方法这个近似是在矩阵范数意义下的近似。矩阵范数是向量范数的直接推广。 ∥ A ∥ 2 ( ∑ j 1 n ∑ i 1 m ∣ a i j ∣ 2 ) 1 / 2 \|A\|_2(\sum_{j1}^{n}\sum_{i1}^{m} |a_{ij}|^2)^{1/2} ∥A∥2(j1∑ni1∑m∣aij∣2)1/2 可以证明 ∥ A ∥ 2 2 tr ( A T A ) ∑ i 1 r σ i 2 \|A\|_2^2\text{tr}(A^TA) \sum_{i1}^{r} \sigma_i^2 ∥A∥22tr(ATA)i1∑rσi2 设矩阵 A k ∑ i 1 k σ i u i v i T A_k\sum_{i1}^k\sigma_i\mathbf u_i\mathbf v_i^T Aki1∑kσiuiviT 则 A k A_k Ak 的秩为 k k k 矩阵 A k A_k Ak 称为 A A A 的截断奇异值分解。并且 A k A_k Ak 是秩为 k k k 时的最优近似即 A k A_k Ak 为以下最优问题的解 min ∥ A − X ∥ 2 s.t. rank A k \min\|A-X\|_2 \\ \text{s.t. rank }Ak min∥A−X∥2s.t. rank Ak 上式称为低秩近似(low-rank approximation)。于是奇异值分解可近似为 A ≈ ∑ i 1 k σ i u i v i T U m × k Σ k × k V n × k T A\approx \sum_{i1}^k\sigma_i\mathbf u_i\mathbf v_i^TU_{m\times k}\Sigma_{k\times k}V_{n\times k}^T A≈i1∑kσiuiviTUm×kΣk×kVn×kT
其中 k k k 是一个远远小于 m m m和 n n n的数从计算机内存的角度来说矩阵左(右)奇异向量和奇异值的存储要远远小于矩阵 A A A的。所以截断奇异值分解就是在计算精度和时间空间之间做选择。如果 k k k越大右边的三个矩阵相乘的结果越接近于 A A A。
截断奇异值分解常用于图像压缩如下图
