1.奇异值分解

笔记来源：Singular Value Decomposition (SVD) and Image Compression

1.1 变换（Transformations）

左侧图形先进行水平方向缩放，再进行垂直方向缩放，而后进行旋转，发现经过一系列变换后与右侧图形不符，说明缩放和旋转的操作有时是有顺序的

正确操作：先进行旋转，再进行水平方向缩放，而后进行垂直方向缩放，得到与右侧一致的图形

1.2 线性变换（Linear Transformations）

一步复杂变换 $A$（主要考虑高维）分解为了三个简单变换 $V^{†}、\Sigma 、U$

1.3 降维（Dimensionality Reduction）

我们将上述矩阵$\Sigma$中的 ${\sigma }_2=0.44$ 修改为 ${\sigma }_2=0$ ，二维图形直接被压缩成了一维

降维的好处：存储数据减少

1.4 奇异值分解（SVD）

1.4.1 如果矩阵$A$是方阵（Square Matrix）

例子：

1.4.2 如果矩阵$A$是非方阵（Non-Square Matrix）

1.5 图像压缩（Image Compression）

1.6 如何计算分解的三个矩阵？

$$\begin{gathered} U=\left[\begin{array}{ccc}{\mathbf{u}}_1& {\mathbf{u}}_2& \cdots \end{array}\right] \\ \Sigma =diag\left[\begin{array}{ccc}{\sigma }_1& {\sigma }_2& \cdots \end{array}\right] \\ {V}^T=\left[\begin{array}{c}{v}_1^T\\ v_2^T\\ ⋮\end{array}\right] \end{gathered}$$

计算矩阵$A$的特征值
$$\begin{gathered} detA={\lambda }_1{\lambda }_2=15 \\ trA={\lambda }_1+{\lambda }_2=8 \\ {\lambda }_1=3、{\lambda }_2=5 \end{gathered}$$
计算 $A{A}^T$
$$\begin{gathered} A{A}^T{\mathbf{u}}_i={\sigma }_i^2{\mathbf{u}}_i \\ A{A}^T=\left[\begin{array}{cc}3& 0\\ 4& 5\end{array}\right]\left[\begin{array}{cc}3& 4\\ 0& 5\end{array}\right]=\left[\begin{array}{cc}25& 20\\ 20& 25\end{array}\right] \end{gathered}$$
计算$A{A}^T$的特征值 ${\sigma }^2$【这里的 $\sigma$ 叫做矩阵$A$的奇异值】
法一：$det(A{A}^T-\sigma I)=0$
法二：
$$\begin{gathered} detA{A}^T=225={\sigma }_1^2{\sigma }_2^2 \\ trA{A}^T=50={\sigma }_1^2+{\sigma }_2^2 \\ {\sigma }_1^2=45、{\sigma }_2^2=5 \\ {\sigma }_1=\sqrt{45}、{\sigma }_2=\sqrt{5} \\ {\sigma }_1{\sigma }_2=15=detA \end{gathered}$$

计算 $A^{T}A$
$$\begin{gathered} A^{T}A{\mathbf{v}}_i={\sigma }_i^2{\mathbf{v}}_i \\ {A}^{T}A=\left[\begin{array}{cc}3& 4\\ 0& 5\end{array}\right]\left[\begin{array}{cc}3& 0\\ 4& 5\end{array}\right]=\left[\begin{array}{cc}9& 12\\ 12& 41\end{array}\right] \end{gathered}$$
计算 $A^{T}A$的特征向量 ${\mathbf{v}}_1$【这里的 ${\mathbf{v}}_1$ 是矩阵 $A$ 的右奇异向量】
$$\begin{gathered} A^{T}A{\mathbf{v}}_1={\sigma }_1^2{\mathbf{v}}_1 \\ \left[\begin{array}{cc}9& 12\\ 12& 41\end{array}\right]\left[\begin{array}{c}{a}_1\\ a_2\end{array}\right]=45\left[\begin{array}{c}{a}_1\\ a_2\end{array}\right] \\ {a}_1=a_2 \\ \left[\begin{array}{cc}9& 12\\ 12& 41\end{array}\right]\left[\begin{array}{c}1\\ 1\end{array}\right]=45\left[\begin{array}{c}1\\ 1\end{array}\right] \end{gathered}$$
计算 $A^{T}A$的特征向量 ${\mathbf{v}}_2$【这里的 ${\mathbf{v}}_2$ 是矩阵 $A$ 的右奇异向量】
$$\begin{gathered} A^{T}A{\mathbf{v}}_2={\sigma }_2^2{\mathbf{v}}_2 \\ \left[\begin{array}{cc}9& 12\\ 12& 41\end{array}\right]\left[\begin{array}{c}{a}_3\\ a_4\end{array}\right]=5\left[\begin{array}{c}{a}_3\\ a_4\end{array}\right] \\ {a}_3=-a_4 \\ \left[\begin{array}{cc}9& 12\\ 12& 41\end{array}\right]\left[\begin{array}{c}-1\\ 1\end{array}\right]=5\left[\begin{array}{c}-1\\ 1\end{array}\right] \end{gathered}$$
单位化后的矩阵$A$的右奇异向量${\mathbf{v}}_1、{\mathbf{v}}_2$
$${\mathbf{v}}_1=\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ 1\end{array}\right]、{\mathbf{v}}_2=\frac{1}{\sqrt{2}}\left[\begin{array}{c}-1\\ 1\end{array}\right]$$
计算矩阵$A$的左奇异向量${\mathbf{u}}_1、{\mathbf{u}}_2$
$$\begin{gathered} A{\mathbf{v}}_1={\sigma }_1{\mathbf{u}}_1 \\ {\mathbf{u}}_1=\frac{A{\mathbf{v}}_1}{{\sigma }_1}=\left[\begin{array}{c}1\\ 3\end{array}\right] \\ A{\mathbf{v}}_2={\sigma }_2{\mathbf{u}}_2 \\ {\mathbf{u}}_2=\frac{A{\mathbf{v}}_2}{{\sigma }_2}=\left[\begin{array}{c}-3\\ 1\end{array}\right] \end{gathered}$$
单位化矩阵$A$的左奇异向量${\mathbf{u}}_1、{\mathbf{u}}_2$
$${\mathbf{u}}_1=\frac{1}{\sqrt{10}}\left[\begin{array}{c}1\\ 3\end{array}\right]、{\mathbf{u}}_2=\frac{1}{\sqrt{10}}\left[\begin{array}{c}-3\\ 1\end{array}\right]$$

分解成的三个矩阵

1.7 联系与区别

笔记来源：Understanding Eigenvalues and Singular Values

联系：特征值和奇异值都描述了线性变换的量级或者说是变换幅度

They (eigenvalues and singular values) both describe the behavior of a matrix on a certain set of vectors.
And the corresponding eigen- and singular values describe the magnitude of that action.

1.7.1 特征值和特征向量

本人相关博客：特征值、特征向量、迹

笔记来源：Understanding Eigenvalues and Singular Values

The eigenvectors of a matrix describe the directions of its invariant action.（不变作用方向）

That eigenvectors give the directions of invariant action is obvious from the definition. The definition says that when A acts on an eigenvector, it just multiplies it by a constant, the corresponding eigenvalue. In other words, when a linear transformation acts on one of its eigenvectors, it shrinks the vector or stretches it and reverses its direction if λ is negative, but never changes the direction otherwise. The action is invariant.

$$A\mathbf{v}=\lambda \mathbf{v}$$

the vector $\mathbf{v}$ is called eigenvector
A scalar $\lambda$ is called eigenvalue of $A$

1.7.2 奇异值和奇异向量

笔记来源：Understanding Eigenvalues and Singular Values
$$\begin{gathered} A\mathbf{v}=\sigma \mathbf{u} \\ {A}^{\ast }\mathbf{u}=\sigma \mathbf{v} \end{gathered}$$
where $A^{\ast }$ is the conjugate transpose of $A$

$$\begin{gathered} A{\mathbf{v}}_1={\sigma }_1{\mathbf{u}}_1 \\ A{\mathbf{v}}_2={\sigma }_2{\mathbf{u}}_2 \end{gathered}$$

A scalar $\sigma$ is a singular value of $A$
${\sigma }_1$ is the largest singular value of $A$ with right singular vector $\mathbf{v}$
${\sigma }_2$ is the least singular value of $A$ with left singular vector $\mathbf{u}$

the vectors $\mathbf{u}、\mathbf{v}$ are singular vectors
the vector $\mathbf{u}$ is called a left singular vectors
the vector $\mathbf{v}$ is called a right singular vectors

The singular vectors of a matrix describe the directions of its maximum action. （最大作用方向）

矩阵$A$对原空间中的任一单位向量$\mathbf{x}$进行变换
$$\underset{\mathbf{x},||\mathbf{x}||=1}{\mathrm{argmax}}||A\mathbf{x}||=||A\mathbf{v}||={\sigma }_1$$

所有单位向量$\mathbf{x}$中某一个向量长度变换最大，它就是右奇异向量$\mathbf{v}$
其在矩阵$A$的作用下，长度 $||A\mathbf{v}||={\sigma }_1$

单位圆经过线性变换$A$得到椭圆
右奇异向量$\mathbf{v}$在椭圆的半长轴上
左奇异向量$\mathbf{u}$在椭圆的半短轴上

拓展到三维空间

1.8 矩阵估计（Matrix Approximation with SVD）

将当前最大奇异值 $3$ 改写为 $0$

改写后矩阵 $A_1$ 对应的线性变换如下图

将矩阵$A_1$中的当前最大奇异值 $2$ 改写为 $0$

改写后矩阵 $A_2$ 对应的线性变换如下图

重点：每一个奇异向量都会产生一个线性子空间中的标准正交基

在所有方向正交于有最大奇异向量（最大奇异值对应的向量）中，一个奇异值和其奇异向量将给出最大作用的方向

重要应用：
1.在一些统计学、机器学习中要求找到某个矩阵的低秩估计（Low-rank approximation）
2.主成分分析（PCA）也是这一类问题，即用一些最大方差的不相关分量近似某个观测矩阵X

具体做法：
计算SVD并将最小的奇异值改为0