SVD 分解是线性代数的一大亮点。
1. SVD 分解
A A A 是任意的 m × n m×n m×n 矩阵，它的秩为 r r r，我们要对其进行对角化，但不是通过 S − 1 A S S^{-1}A S S−1AS。 S S S 中的特征向量有三个大问题：它们通常不是正交的；并不总是有足够的特征向量； A x = λ x Ax=\lambda x Ax=λx 需要 A A A 是一个方阵。 A A A 的奇异向量很好地解决了上述所有问题。
代价是我们需要两组奇异向量，一组是 u \boldsymbol{u} u， 一组是 v \boldsymbol{v} v。 u \boldsymbol{u} u 是 A A T AA^T AAT 的特征向量， v \boldsymbol{v} v 是 A T A A^TA ATA 的特征向量，因为这两个矩阵都是对称矩阵，我们可以选出一组标准正交的特征向量。即：
A A T = U Σ 2 U T A T A = V Σ 2 V T AA^T=U\Sigma^2U^T \quad A^TA =V\Sigma^2V^T AAT=UΣ2UTATA=VΣ2VT
证明：
让我们从 A T A v i = σ i 2 v i A^TAv_i=\sigma_i^2v_i ATAvi=σi2vi 开始，两边同乘以 v i T v_i^T viT，有：
v i T A T A v i = σ i 2 v i T v i = σ i 2 → ∣ ∣ A v i ∣ ∣ = σ i v_i^TA^TAv_i=\sigma_i^2v_i^Tv_i=\sigma_i^2 \to ||Av_i||=\sigma_i viTATAvi=σi2viTvi=σi2→∣∣Avi∣∣=σi
这说明向量 A v i Av_i Avi 的长度为 σ i \sigma_i σi。然后两边同乘以 A A A，有：
A A T ( A v i ) = σ i 2 ( A v i ) → u i = A v i / σ i AA^T(Av_i)=\sigma_i^2(Av_i) \to u_i = Av_i / \sigma_i AAT(Avi)=σi2(Avi)→ui=Avi/σi
这说明 A v i Av_i Avi 是 A A T AA^T AAT 的特征向量，除以其长度 σ i \sigma_i σi 我们便可以得到单位向量 u i u_i ui。这些 u \boldsymbol{u} u 还是正交的，因为：
( A v i ) T A v j = v i T ( A T A v j ) = v i T ( σ j 2 v j ) = σ j 2 v i T v j = 0 (Av_i)^TAv_j = v_i^T(A^TAv_j) = v_i^T(\sigma_j^2v_j) =\sigma_j^2v_i^Tv_j=0 (Avi)TAvj=viT(ATAvj)=viT(σj2vj)=σj2viTvj=0
奇异向量 v \boldsymbol{v} v 位于 A A A 的行空间，而结果 u \boldsymbol{u} u 位于 A A A 的列空间，奇异值都是正数。然后 A v i = σ i u i Av_i=\sigma_iu_i Avi=σiui 一列一列告诉我们 A V = U Σ AV=U\Sigma AV=UΣ，
A [ v 1 v 2 ⋯ v r ] = [ u 1 u 2 ⋯ u r ] [ σ 1 σ 2 ⋯ σ r ] A \begin{bmatrix} &&&\\ v_1&v_2&\cdots&v_r\\&&& \end{bmatrix} = \begin{bmatrix} &&&\\ u_1&u_2&\cdots&u_r\\&&& \end{bmatrix} \begin{bmatrix} \sigma_1&&&\\ &\sigma_2&&\\&&\cdots&\sigma_r \end{bmatrix} A⎣⎡v1v2⋯vr⎦⎤=⎣⎡u1u2⋯ur⎦⎤⎣⎡σ1σ2⋯σr⎦⎤
( m × n ) ( n × r ) = ( m × r ) ( r × r ) (m×n)(n×r)=(m×r)(r×r) (m×n)(n×r)=(m×r)(r×r)
这是 SVD 的核心，但不仅仅到此为止，这些 v \boldsymbol{v} v 和 u \boldsymbol{u} u 只负责矩阵 A A A 的行空间和列空间，我们需要 n − r n-r n−r 个额外的 v \boldsymbol{v} v 和 m − r m-r m−r 个额外的 u \boldsymbol{u} u，分别来自零空间 N ( A ) N(A) N(A) 和左零空间 N ( A T ) N(A^T) N(AT)。它们可以是这两个空间的标准正交基，当然它们也自动正交于前 r r r 个 v \boldsymbol{v} v 和 u \boldsymbol{u} u。将这些新的向量包含进 V V V 和 U U U，我们依然有 $AV=U\Sigma $：
新的 Σ \Sigma Σ 是 m × n m×n m×n 的，由之前的 r × r r×r r×r 矩阵 Σ r \Sigma_r Σr 和 m − r m-r m−r 行零和 n − r n-r n−r 列零组成。此时， V V V 和 U U U 分别是大小为 n , m n,m n,m 的方阵，有 V − 1 = V T V^{-1}=V^T V−1=VT，则 A V = U Σ AV=U\Sigma AV=UΣ 就变成了
A = U Σ V T A=U\Sigma V^T A=UΣVT
这也就是 SVD 分解。当我们将奇异值降序排列时，上述的方程按照重要性给出了矩阵 A A A 的 r r r个秩为 1 的小片。
2. 图像压缩
这是一个数据的时代，并且数据经常存储在一个矩阵中。数字图像就是一个存储像素值的矩阵，比如一个大小为 256×512 的图像总共有 2 8 ∗ 2 9 = 2 17 2^8*2^9=2^{17} 28∗29=217 个元素。单独存储这一个图像对计算机来说是没问题的，但在 CT 和 MR 扫描过程中会产生大量的数据，又或者它们是电影中的帧图片，那么需要存储的数据量将会非常大。高清晰度的数字电视特别需要压缩，否则设备无法实时跟踪。
什么是压缩呢？我们想要用更少的数字代替这 2 17 2^{17} 217 个元素，但同时不损失图像质量。一个简单的办法就是用一组中四个元素的均值来替换它们，这就是 4:1 压缩。但是如果我们想进一步压缩，比如 16:1，那么我们的图像就会有一些块效应，我们想要用一个人的视觉系统注意不到的方式进行压缩。
很多方法被提出来解决这个问题，比如用在 jpeg 中的傅里叶变换以及用在 JPEG2000 中的小波变换。这里我们尝试一个 SVD 的方法：用一个秩为 1 的矩阵，一列乘以一行，来替换原始的 256×512 矩阵。这样奏效的话，压缩比将会是 (256*512)/(256+512) 超过 170:1。实际上，我们会用 5 个秩为 1 的矩阵，这时候压缩比仍然有 34:1，而更重要的问题是图像质量。
为什么会牵涉到 SVD 呢？矩阵 A A A 最好的秩 1 近似为 σ 1 u 1 v 1 T \sigma_1u_1v_1^T σ1u1v1T，使用了最大的奇异值 σ 1 \sigma_1 σ1。最好的秩 5 近似为 σ 1 u 1 v 1 T + σ 2 u 2 v 2 T + ⋯ + σ 5 u 5 v 5 T \sigma_1u_1v_1^T+\sigma_2u_2v_2^T+\cdots+\sigma_5u_5v_5^T σ1u1v1T+σ2u2v2T+⋯+σ5u5v5T，SVD 按照降序放置矩阵 A 的小片。
3. 基和 SVD
让我们以一个 2×2 的矩阵开始，
它的秩为 2，是可逆的。我们想要 v 1 , v 2 v_1,v_2 v1,v2 是正交的单位向量，同时使得 A v 1 , A v 2 Av_1,Av_2 Av1,Av2 正交。没有一个正交矩阵 Q Q Q 可以让 Q − 1 A Q Q^{-1}AQ Q−1AQ 对角化，我们需要 U − 1 A V U^{-1}AV U−1AV。
有一个简单的办法可以移除 U U U 而只留下 V V V，
A T A = ( U Σ V T ) T ( U Σ V T ) = V Σ T Σ V T A^TA=(U\Sigma V^T)^T(U\Sigma V^T)=V\Sigma ^T\Sigma V^T ATA=(UΣVT)T(UΣVT)=VΣTΣVT
这就和 A = Q Λ Q T A=Q\Lambda Q^T A=QΛQT 一样，只不过这里的对称矩阵不是 A A A 本身，而是 A T A A^TA ATA ， V V V 的列是 A T A A^TA ATA 的特征向量。然后我们可以利用 u = A v / σ u=Av/\sigma u=Av/σ 来得到 U U U，也可以直接得到，
A A T = ( U Σ V T ) ( U Σ V T ) T = U Σ Σ T U T AA^T=(U\Sigma V^T)(U\Sigma V^T)^T=U\Sigma \Sigma ^TU^T AAT=(UΣVT)(UΣVT)T=UΣΣTUT
矩阵 U U U 和 V V V 包含了四个子空间的标准正交基：
以下的例子很好地展示了矩阵的四个字空间和 SVD 的关系。
4. 特殊矩阵的特征值和特征向量
获取更多精彩，请关注「seniusen」!