网站进度条特效,新乡彩票网站建设,手册设计,wordpress 主题 瀑布流1. 奇异值分解
假设矩阵 A A A有 m m m行 n n n列
奇异值分解就是在 A A A的行向量上选取若干对标准正交基#xff0c;对它作 A A A矩阵变化并投射到了 A A A的列空间上的正交基的若干倍数。 A v → u → σ u → ∈ R m v → ∈ R n A\overrightarrow{v}\overrightarrow{u…1. 奇异值分解
假设矩阵 A A A有 m m m行 n n n列
奇异值分解就是在 A A A的行向量上选取若干对标准正交基对它作 A A A矩阵变化并投射到了 A A A的列空间上的正交基的若干倍数。 A v → u → σ u → ∈ R m v → ∈ R n A\overrightarrow{v}\overrightarrow{u} \sigma\\ \overrightarrow{u} \in R^{m} \quad \overrightarrow{v} \in R^{n} Av u σu ∈Rmv ∈Rn
其中 σ \sigma σ被称为奇异值我们在计算时将奇异值从大到小进行排列。
假设有 r r r对行空间和列空间上的标准正交基可以进行上面的变化
那么我们得到了 A [ v 1 → ⋯ v r → v r 1 → ⋯ v n → ] [ u 1 → ⋯ u r → u r 1 → ⋯ u m → ] [ σ 1 σ 2 ⋯ σ r ] A[\overrightarrow{v_1}\cdots\overrightarrow{v_r}\overrightarrow{v_{r1}}\cdots \overrightarrow{v_n}] \\ [\overrightarrow{u_1}\cdots\overrightarrow{u_r}\overrightarrow{u_{r1}}\cdots\overrightarrow{u_m}] \begin{bmatrix} \sigma_1 \ \ \ \\ \ \sigma_2 \ \ \\ \ \ \cdots \ \\ \ \ \ \ \sigma_r \\ \ \ \ \ \\ \end{bmatrix} A[v1 ⋯vr vr1 ⋯vn ][u1 ⋯ur ur1 ⋯um ] σ1 σ2 ⋯ σr 其中 u 1 → u 2 → ⋯ u r → ∈ C ( A ) \overrightarrow{u_1}\overrightarrow{u_2} \cdots \overrightarrow{u_r} \in C(A) u1 u2 ⋯ur ∈C(A) u r 1 → ⋯ u m → ∈ N ( A ⊤ ) \overrightarrow{u_{r1}} \cdots \overrightarrow{u_m}\in N(A^{\top}) ur1 ⋯um ∈N(A⊤) v 1 → v 2 → ⋯ v r → ∈ C ( A ⊤ ) \overrightarrow{v_1}\overrightarrow{v_2} \cdots \overrightarrow{v_r}\in C(A^{\top}) v1 v2 ⋯vr ∈C(A⊤) v r 1 → ⋯ v r → ∈ N ( A ) \overrightarrow{v_{r1}} \cdots \overrightarrow{v_r} \in N(A) vr1 ⋯vr ∈N(A) Σ \Sigma Σ矩阵有 m m m行 m − r m-r m−r个零行。
SVD将四个空间联系起来 将上面公式换成矩阵形式我们得到。 A V U Σ AVU\Sigma AVUΣ 更进一步地有 A U Σ V − 1 U Σ V ⊤ AU\Sigma V^{-1}U\Sigma V^{\top} AUΣV−1UΣV⊤ 加上行列号标识 A m × n U m × m Σ m × n V n × n ⊤ A_{m\times n}U_{m\times m}\Sigma_{m\times n}V^{\top}_{n\times n} Am×nUm×mΣm×nVn×n⊤ A σ 1 u 1 v 1 ⊤ ⋯ σ r u r v r ⊤ ∑ i 1 r σ i u i v i ⊤ A \sigma_1u_1v_1^{\top} \cdots \sigma_r u_rv_r^{\top}\sum_{i1}^{r}\sigma_iu_iv_i^{\top} Aσ1u1v1⊤⋯σrurvr⊤∑i1rσiuivi⊤
这也是svd最精华的地方任何一个矩阵都可以写成至多 n n n个 m × 1 m\times1 m×1矩阵和 1 × n 1\times n 1×n矩阵的倍数相加。
为了规范我们约定 σ 1 ≥ σ 2 ≥ ⋯ ≥ σ r \sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_r σ1≥σ2≥⋯≥σr。
如何求 A A A的奇异值分解呢
可以利用 A ⊤ A A A ⊤ A^{\top}A\quad AA^{\top} A⊤AAA⊤来求。
假设 A U Σ V ⊤ A U\Sigma V^{\top} AUΣV⊤ A ⊤ A V Σ ⊤ U ⊤ U Σ V ⊤ V Σ ⊤ Σ V ⊤ A A ⊤ U Σ ⊤ V ⊤ V Σ U ⊤ U Σ ⊤ Σ U ⊤ A^{\top}AV \Sigma^{\top}U^{\top}U\Sigma V^{\top}V\Sigma^{\top}\Sigma V^{\top}\\ AA^{\top}U \Sigma^{\top}V^{\top}V\Sigma U^{\top}U\Sigma^{\top}\Sigma U^{\top}\\ A⊤AVΣ⊤U⊤UΣV⊤VΣ⊤ΣV⊤AA⊤UΣ⊤V⊤VΣU⊤UΣ⊤ΣU⊤ 由于 A ⊤ A A A ⊤ A^{\top}A \quad AA^{\top} A⊤AAA⊤都是对称矩阵 ( A A ⊤ ) ⊤ A A ⊤ ( A ⊤ A ) ⊤ A ⊤ A (AA^{\top})^{\top} AA^{\top}\\ (A^{\top}A)^{\top} A^{\top}A (AA⊤)⊤AA⊤(A⊤A)⊤A⊤A 不严谨的说它们可以分解为 S Λ S ⊤ S\Lambda S^{\top} SΛS⊤的形式。
因此求解 U V Σ U\quad V\quad \Sigma UVΣ变为了求解 A A ⊤ A ⊤ A AA^{\top}\quad A^{\top}A AA⊤A⊤A的特征值和特征向量。
2. 举例子
上面的符号描述还是太抽象了我们举例子。
2.1 案例1 A [ 4 4 − 3 3 ] A\begin{bmatrix} 4 4 \\ -3 3 \end{bmatrix} A[4−343] A A A的转置 A ⊤ [ 4 − 3 4 3 ] A^{\top}\begin{bmatrix} 4 -3 \\ 4 3 \\ \end{bmatrix} A⊤[44−33] A A ⊤ [ 32 0 0 18 ] AA^{\top}\begin{bmatrix} 32 0\\ 0 18\\ \end{bmatrix} AA⊤[320018] λ 1 32 M 1 A A ⊤ − λ 1 I [ 0 0 0 − 14 ] M 1 [ 1 0 ] [ 0 0 ] \lambda_132\\ M_1AA^{\top}-\lambda_1 I\\ \begin{bmatrix} 0 0 \\ 0 -14 \end{bmatrix}\\ M_1\begin{bmatrix} 1\\0 \end{bmatrix}\begin{bmatrix} 0 \\ 0 \end{bmatrix} λ132M1AA⊤−λ1I[000−14]M1[10][00] 因此 A A ⊤ AA^{\top} AA⊤的一个特征向量为 u 1 → [ 1 0 ] \overrightarrow{u_1}\begin{bmatrix} 1\\0 \end{bmatrix} u1 [10] 同理 λ 2 18 M 2 A A ⊤ − λ 2 I [ 14 0 0 0 ] M 2 [ 0 1 ] [ 0 0 ] \lambda_218\\ M_2AA^{\top}-\lambda_2 I\\ \begin{bmatrix} 14 0 \\ 0 0 \end{bmatrix}\\ M_2\begin{bmatrix} 0 \\ 1 \end{bmatrix}\begin{bmatrix} 0 \\ 0 \end{bmatrix} λ218M2AA⊤−λ2I[14000]M2[01][00] 因此 A A ⊤ AA^{\top} AA⊤的另一个特征向量为 u 2 → [ 0 1 ] \overrightarrow{u_2} \begin{bmatrix} 0 \\ 1 \end{bmatrix} u2 [01] 因此我们可以得到矩阵 U U U U [ 1 0 0 1 ] U\begin{bmatrix} 1 0\\ 0 1\\ \end{bmatrix} U[1001]
另一方面 A ⊤ A [ 25 7 7 25 ] A^{\top}A\begin{bmatrix} 25 7 \\ 7 25 \end{bmatrix} A⊤A[257725] 同理我们可以求得 ( 25 − λ ) ( 25 − λ ) − 49 0 ( λ − 32 ) ( λ − 18 ) 0 λ 1 32 λ 2 18 (25-\lambda)(25-\lambda)-490\\ (\lambda-32)(\lambda-18)0\\ \lambda_132\quad \lambda_218 (25−λ)(25−λ)−490(λ−32)(λ−18)0λ132λ218 对应的 M 1 ′ A ⊤ A − λ 1 I [ − 7 7 7 − 7 ] M 1 ′ [ 1 1 ] 0 M_1A^{\top}A-\lambda_1I \begin{bmatrix} -7 7\\ 7 -7 \end{bmatrix}\\ M_1\begin{bmatrix}1\\1\end{bmatrix}0 M1′A⊤A−λ1I[−777−7]M1′[11]0 因此 A ⊤ A A^{\top}A A⊤A的一个特征向量单位化后 v 1 → 2 2 [ 1 1 ] \overrightarrow{v_1}\frac{\sqrt{2}}{2}\begin{bmatrix} 1 \\1 \end{bmatrix} v1 22 [11] 同理 M 2 ′ A ⊤ A − λ 2 I [ 7 7 7 7 ] M 2 ′ [ 1 − 1 ] [ 0 0 ] M_2A^{\top}A-\lambda_2I\begin{bmatrix}7 7\\7 7 \end{bmatrix}\\ M_2\begin{bmatrix}1 \\ -1 \end{bmatrix}\begin{bmatrix}0\\0\end{bmatrix} M2′A⊤A−λ2I[7777]M2′[1−1][00] A ⊤ A A^{\top}A A⊤A的另一个特征向量单位化后 v 2 → 2 2 [ 1 − 1 ] \overrightarrow{v_2}\frac{\sqrt{2}}{2}\begin{bmatrix} 1\\ -1 \end{bmatrix} v2 22 [1−1] 因此得到矩阵 V V V V [ 2 2 2 2 2 2 − 2 2 ] V \begin{bmatrix} \frac{\sqrt{2}}{2} \frac{\sqrt{2}}{2}\\ \frac{\sqrt{2}}{2} -\frac{\sqrt{2}}{2}\\ \end{bmatrix} V[22 22 22 −22 ]
又有 σ 2 λ \sigma^2\lambda σ2λ
那么 Σ \Sigma Σ矩阵为 Σ [ 4 2 0 0 3 2 ] \Sigma\begin{bmatrix} 4\sqrt{2} 0\\ 0 3\sqrt{2} \end{bmatrix} Σ[42 0032 ]
最终分解形式为 A U Σ V ⊤ [ 1 0 0 1 ] [ 4 2 0 0 3 2 ] [ 2 2 2 2 2 2 − 2 2 ] AU\Sigma V^{\top} \begin{bmatrix} 1 0\\ 0 1\\ \end{bmatrix} \begin{bmatrix} 4\sqrt{2} 0\\ 0 3\sqrt{2} \end{bmatrix} \begin{bmatrix} \frac{\sqrt{2}}{2} \frac{\sqrt{2}}{2}\\ \frac{\sqrt{2}}{2} -\frac{\sqrt{2}}{2}\\ \end{bmatrix} AUΣV⊤[1001][42 0032 ][22 22 22 −22 ] 我们验算后发现右边符号不对劲得到的矩阵为 [ 4 4 3 − 3 ] \begin{bmatrix}4 4\\ 3 -3\\ \end{bmatrix} [434−3] 因此上面有一步错误 验证 A v 1 → [ 4 4 − 3 3 ] [ 2 2 2 2 ] [ 4 2 0 ] σ 1 v 1 → A v 2 → [ 4 4 − 3 3 ] [ 2 2 − 2 2 ] [ 0 − 3 2 ] ≠ σ 2 v 2 → A\overrightarrow{v_1} \begin{bmatrix} 4 4 \\ -3 3 \end{bmatrix} \begin{bmatrix} \frac{\sqrt{2}}{2}\\ \frac{\sqrt{2}}{2} \end{bmatrix} \begin{bmatrix} 4\sqrt{2}\\0 \end{bmatrix}\sigma_1\overrightarrow{v_1}\\ A\overrightarrow{v_2} \begin{bmatrix} 4 4 \\ -3 3 \end{bmatrix} \begin{bmatrix} \frac{\sqrt{2}}{2}\\ -\frac{\sqrt{2}}{2} \end{bmatrix} \begin{bmatrix} 0\\-3\sqrt{2} \end{bmatrix}\ne\sigma_2\overrightarrow{v_2}\\ Av1 [4−343][22 22 ][42 0]σ1v1 Av2 [4−343][22 −22 ][0−32 ]σ2v2 因此 v 2 → ≠ [ 2 2 − 2 2 ] \overrightarrow{v_2} \ne \begin{bmatrix}\frac{\sqrt{2}}{2}\\-\frac{\sqrt{2}}{2}\end{bmatrix} v2 [22 −22 ]我们符号换下下就好了。 v 2 → [ − 2 2 2 2 ] \overrightarrow{v_2} \begin{bmatrix} -\frac{\sqrt{2}}{2}\\\frac{\sqrt{2}}{2} \end{bmatrix} v2 [−22 22 ]
最终 A A A的奇异值分解形式为 A [ 1 0 0 1 ] [ 4 2 0 0 3 2 ] [ 2 2 2 2 − 2 2 2 2 ] A\begin{bmatrix} 1 0\\ 0 1\\ \end{bmatrix} \begin{bmatrix} 4\sqrt{2} 0\\ 0 3\sqrt{2} \end{bmatrix} \begin{bmatrix} \frac{\sqrt{2}}{2} \frac{\sqrt{2}}{2}\\ -\frac{\sqrt{2}}{2} \frac{\sqrt{2}}{2}\\ \end{bmatrix} A[1001][42 0032 ][22 −22 22 22 ] 变成秩1矩阵相乘相加的形式为 A 4 2 [ 1 0 ] [ 2 2 2 2 ] 3 2 [ 0 1 ] [ − 2 2 2 2 ] A4\sqrt{2} \begin{bmatrix}1\\0\end{bmatrix}\begin{bmatrix}\frac{\sqrt{2}}{2} \frac{\sqrt{2}}{2}\end{bmatrix}3\sqrt{2}\begin{bmatrix}0 \\ 1\end{bmatrix}\begin{bmatrix}-\frac{\sqrt{2}}{2} \frac{\sqrt{2}}{2}\end{bmatrix} A42 [10][22 22 ]32 [01][−22 22 ]
2.2 案例2
过程就省略一些了 A [ 1 0 − 1 0 1 0 ] A ⊤ [ 1 0 0 1 − 1 0 ] A\begin{bmatrix} 1 0 -1 \\ 0 1 0 \end{bmatrix}\\ A^{\top}\begin{bmatrix} 1 0\\0 1\\-1 0 \end{bmatrix} A[1001−10]A⊤ 10−1010 A ⊤ A [ 1 0 − 1 0 1 0 − 1 0 1 ] λ 1 2 , λ 1 1 , λ 3 0 v 1 [ 2 2 0 − 2 2 ] v 2 [ 0 1 0 ] v 3 [ 2 2 0 2 2 ] A^{\top}A\begin{bmatrix} 1 0 -1 \\ 0 1 0\\ -1 0 1 \end{bmatrix}\\ \lambda_12,\lambda_11,\lambda_30\\ v_1\begin{bmatrix} \frac{\sqrt{2}}{2}\\ 0\\ -\frac{\sqrt{2}}{2}\\ \end{bmatrix} v_2\begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} v_3 \begin{bmatrix} \frac{\sqrt{2}}{2}\\0 \\ \frac{\sqrt{2}}{2} \end{bmatrix} A⊤A 10−1010−101 λ12,λ11,λ30v1 22 0−22 v2 010 v3 22 022 因此 V [ 2 2 0 2 2 0 1 0 − 2 2 0 2 2 ] V\begin{bmatrix} \frac{\sqrt{2}}{2} 0 \frac{\sqrt{2}}{2}\\ 0 1 0\\ -\frac{\sqrt{2}}{2} 0 \frac{\sqrt{2}}{2} \end{bmatrix} V 22 0−22 01022 022 同理 A A ⊤ [ 2 0 0 1 ] λ 1 2 , λ 2 1 u 1 [ 1 0 ] u 2 [ 0 1 ] AA^{\top}\begin{bmatrix} 2 0\\ 0 1 \end{bmatrix}\\ \lambda_1 2, \lambda_21\\ u_1\begin{bmatrix} 1 \\0 \end{bmatrix} u_2\begin{bmatrix} 0 \\ 1 \end{bmatrix} AA⊤[2001]λ12,λ21u1[10]u2[01] 因此 U [ 1 0 0 1 ] U\begin{bmatrix} 1 0 \\ 0 1 \end{bmatrix} U[1001] 最终 A A A的奇异值分解为 A U Σ V ⊤ [ 1 0 0 1 ] [ 2 0 0 0 1 0 ] [ 2 2 0 − 2 2 0 1 0 2 2 0 2 2 ] AU\Sigma V^{\top}\\ \begin{bmatrix} 1 0\\ 0 1 \end{bmatrix} \begin{bmatrix} \sqrt{2} 0 0\\ 0 1 0 \end{bmatrix} \begin{bmatrix} \frac{\sqrt{2}}{2} 0 -\frac{\sqrt{2}}{2}\\ 0 1 0\\ \frac{\sqrt{2}}{2} 0 \frac{\sqrt{2}}{2} \end{bmatrix} AUΣV⊤[1001][2 00100] 22 022 010−22 022 变成秩1矩阵相乘相加的形式为 A 2 [ 1 0 ] [ 2 2 0 2 2 ] 1 [ 0 1 ] [ 0 1 0 ] A\sqrt{2} \begin{bmatrix}1\\0\end{bmatrix}\begin{bmatrix}\frac{\sqrt{2}}{2} 0 \frac{\sqrt{2}}{2}\end{bmatrix} 1\begin{bmatrix}0 \\ 1\end{bmatrix}\begin{bmatrix}0 1 0\end{bmatrix} A2 [10][22 022 ]1[01][010]
2.3 案例3 A [ 1 − 2 0 0 − 2 1 ] A\begin{bmatrix} 1 -2 0\\ 0 -2 1 \end{bmatrix} A[10−2−201] A ⊤ [ 1 0 − 2 − 2 0 1 ] A ⊤ A [ 1 − 2 0 − 2 8 − 2 0 − 2 1 ] λ 1 9 , λ 2 1 , λ 3 0 v 1 [ 2 6 − 2 2 3 2 6 ] v 2 [ 2 2 0 − 2 2 ] v 3 [ 2 3 1 3 2 3 ] A^{\top}\begin{bmatrix} 1 0\\ -2 -2 \\ 0 1 \end{bmatrix}\\ A^{\top}A\begin{bmatrix} 1 -2 0\\ -2 8 -2\\ 0 -2 1 \end{bmatrix}\\ \lambda_19,\lambda_21,\lambda_30\\ v_1\begin{bmatrix} \frac{\sqrt{2}}{6} \\ -\frac{2\sqrt{2}}{3}\\\frac{\sqrt{2}}{6} \end{bmatrix} v_2\begin{bmatrix} \frac{\sqrt{2}}{2} \\ 0 \\ -\frac{\sqrt{2}}{2} \end{bmatrix} v_3\begin{bmatrix} \frac{2}{3} \\ \frac{1}{3} \\ \frac{2}{3} \end{bmatrix} A⊤ 1−200−21 A⊤A 1−20−28−20−21 λ19,λ21,λ30v1 62 −322 62 v2 22 0−22 v3 323132 因此 V [ 2 6 2 2 2 3 − 2 2 3 0 1 3 2 6 2 2 2 3 ] V\begin{bmatrix} \frac{\sqrt{2}}{6} \frac{\sqrt{2}}{2} \frac{2}{3}\\ -\frac{2\sqrt{2}}{3} 0 \frac{1}{3}\\ \frac{\sqrt{2}}{6} \frac{\sqrt{2}}{2} \frac{2}{3} \end{bmatrix} V 62 −322 62 22 022 323132 同理 A A ⊤ [ 5 4 4 5 ] λ 1 9 λ 2 1 u 1 [ 2 2 2 2 ] u 2 [ 2 2 − 2 2 ] AA^{\top} \begin{bmatrix} 5 4 \\4 5 \end{bmatrix}\\ \lambda_19\ \lambda_21\\ u_1\begin{bmatrix} \frac{\sqrt{2}}{2} \\ \frac{\sqrt{2}}{2} \end{bmatrix}u_2\begin{bmatrix} \frac{\sqrt{2}}{2} \\ -\frac{\sqrt{2}}{2} \end{bmatrix} AA⊤[5445]λ19 λ21u1[22 22 ]u2[22 −22 ] 因此 U [ 2 2 2 2 2 2 − 2 2 ] U \begin{bmatrix} \frac{\sqrt{2}}{2} \frac{\sqrt{2}}{2}\\ \frac{\sqrt{2}}{2} -\frac{\sqrt{2}}{2} \end{bmatrix} U[22 22 22 −22 ] 最终 A A A的奇异值分解为 A U Σ V ⊤ [ 2 2 2 2 2 2 − 2 2 ] [ 3 0 0 0 1 0 ] [ 2 6 − 2 2 3 2 6 2 2 0 − 2 2 2 3 1 3 2 3 ] AU\Sigma V^{\top}\\ \begin{bmatrix} \frac{\sqrt{2}}{2} \frac{\sqrt{2}}{2}\\ \frac{\sqrt{2}}{2} -\frac{\sqrt{2}}{2} \end{bmatrix} \begin{bmatrix} 3 0 0\\ 0 1 0 \end{bmatrix} \begin{bmatrix} \frac{\sqrt{2}}{6} -\frac{2\sqrt{2}}{3} \frac{\sqrt{2}}{6} \\ \frac{\sqrt{2}}{2} 0 -\frac{\sqrt{2}}{2}\\ \frac{2}{3} \frac{1}{3} \frac{2}{3} \end{bmatrix} AUΣV⊤[22 22 22 −22 ][300100] 62 22 32−322 03162 −22 32 变成秩1矩阵相乘相加的形式为 A 3 [ 2 2 2 2 ] [ 2 6 − 2 2 3 2 6 ] 1 [ 2 2 − 2 2 ] [ 2 2 0 − 2 2 ] A3\begin{bmatrix}\frac{\sqrt{2}}{2} \\ \frac{\sqrt{2}}{2}\end{bmatrix}\begin{bmatrix}\frac{\sqrt{2}}{6} -\frac{2\sqrt{2}}{3} \frac{\sqrt{2}}{6}\end{bmatrix}\\ 1\begin{bmatrix}\frac{\sqrt{2}}{2} \\ -\frac{\sqrt{2}}{2} \end{bmatrix}\begin{bmatrix} \frac{\sqrt{2}}{2} 0 -\frac{\sqrt{2}}{2}\\\end{bmatrix} A3[22 22 ][62 −322 62 ]1[22 −22 ][22 0−22 ]
参考
mit_svd svd_numerical_examples zhihu-svd
