对称矩阵、复数矩阵、FFT、正定矩阵、相似矩阵、SVD分解、线性变换、图像压缩、左右逆/伪逆
一. 对称矩阵及其正定性
在这里我们只讨论实对称矩阵。
我们很喜欢对称矩阵，因为它具有很好的性质。就拿实对称矩阵来举例，它具有下列两个性质：
- 其特征值均为实数
- 其一定可选出具有正交的特征向量。这里的“有”，是指可以选出一套完全正交的特征向量（例如在重特征值条件下，可能存在一个平面内向量都可以作为特征向量）
- 特征值的符号与主元的符号相同，即正数的个数相同，负数的个数也相同
上一章我们学过，若方阵\(A\)具有n个线性无关的特征向量，那么其可以对角化为\(S\Lambda S^{-1}\)。
对于有n个线性无关特征向量的对称矩阵来说，因为性质2，所以它的特征向量矩阵可化为一个正交阵\(Q\)，正交阵满足\(Q^\mathrm{T} = Q^{=1}\)
所以对于具有n个线性无关特征向量的对称矩阵\(A\)来说，其可对角化为\(Q\Lambda Q^T\)。
把上面的式子进一步展开：
\(A = Q\Lambda Q^\mathrm{T} = \begin{bmatrix} q_1 & q_2 & \cdots & q_n \end{bmatrix} \begin{bmatrix} \lambda_1 & & & \\ & \lambda_2 & & \\ & & \cdots & \\ \end{bmatrix} \begin{bmatrix} q_1^\mathrm{T} \\ q_2^\mathrm{T} \\ \cdots \\ \end{bmatrix}\)
利用"线性代数1"讲的用拆分矩阵乘法为加法去理解这个式子，可以写成：
\(A = \lambda_1q_1q_1^\mathrm{T} + \lambda_2q_2q_2^\mathrm{T} + \cdots + \lambda_nq_nq_n^\mathrm{T}\)
上面这个式子发现了吗，其实每一项都是一个系数乘一个投影矩阵，因为\(Q\)是正交矩阵，所以\(q_i^\mathrm{T}q_i = 1\)。
所以\(A\)可以理解为投影矩阵的线性组合，且投影方向都是互相正交的。
下面来介绍正定矩阵。
正定矩阵是对称矩阵的一个子类，且所有特征值>0
而且它的“子行列式”均>0，子行列式指的是n阶矩阵左上角的所有\(k \times k, 1 \le k \le n\)子行列式数值均为正。这很好理解，由对称矩阵的性质3，我们知道，其所有主元都>0。而行列式就等于主元之积，所以子行列式们自然都大于0。这就是用行列式判定矩阵正定的判据。
二. 复数矩阵, 快速傅里叶变换
对不起我的高数很垃圾，这节我也听不懂。等我学完mit 18.03再来听这一节课
三. 正定矩阵
正定矩阵是很好的矩阵，它是对称的而且所有特征值都大于零。那么如何判定一个方阵是正定矩阵呢？这里我给出几种方法
- 所有特征值\(\lambda_i > 0\)
- 所有主元大于零
- 所有子行列式们大于零
- \(x^\mathrm{T}Ax > 0, x \ne \textbf{0}\)
第一个是定义，第二个是因为对称矩阵有一个性质就是特征值正负号与主元相同，所以可根据(1)得到第二条等价条件。第三个是用行列式判断正定性(前面讲过)。第四个是新加的，我们很喜欢用第四个判据。让我们来看看为什么这个判据可以推出矩阵是正定的。
对于\(x^\mathrm{T}Ax\)，我们将其展开： \[ x^\mathrm{T}Ax = \begin{bmatrix}x_1, x_2, \cdots, x_n\end{bmatrix}\begin{bmatrix} a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n \\ a_{31}x_1 + a_{32}x_2 + \cdots + a_{3n}x_n \\ \cdots \\ a_{n1}x_1 + a_{n2}x_2 + \cdots + a_{nn}x_n\end{bmatrix} = \\ x_1(a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n)+ x_2(a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n) + \cdots + x_n(a_{n1}x_1 + a_{n2}x_2 + \cdots + a_{nn}x_n) \] 可以发现，每一项都是二次的。其实如果用图像去研究这个函数：\(f(x) = x^\mathrm{T}Ax\)，（这个函数也叫二次型）
矩阵为正定时二次型图像见左上角，为半正定时图像见右下角，为非正定/半正定时图像见左下角，负定时图像见右上角
这些图像研究的是二维方阵的二次型，xy轴是\(x\)的俩分量\(x_1, x_2\)，z轴是\(f(x)=x^\mathrm{T}Ax\)
下面继续讨论下正定矩阵还有哪些性质，假设\(A, B\)为正定矩阵，\(C\)为矩阵。
那么\(A\)是否可逆呢？答案是肯定的，因为我们知道\(A\)的子行列式们都大于0，所以\(det(A) > 0\)，所以\(A\)是非奇异的，即满秩可逆的。
那么\(A^{-1}\)是不是正定矩阵呢？答案是肯定的。因为我们知道\(A^{-1}\)的特征值们就是\(A\)的特征值取倒数，而\(A\)的特征值都大于0，所以\(A^{-1}\)的特征值也都大于0，所以\(A^{-1}\)也为正定矩阵。
那么\(A + B\)是不是正定矩阵呢？答案是肯定的。我们来看看\(x^\mathrm{T}(A+B)x = x^\mathrm{T}Ax + x^\mathrm{T}Bx > 0\)，所以\(A + B\)也是正定矩阵。
那么\(C^\mathrm{T}C\)是不是正定矩阵呢？答案是不一定。我们来看看\(x^\mathrm{T}(C^\mathrm{T}C)x = (Cx)^\mathrm{T}(CX) = \|Cx\|^2 \ge 0\)。
所以\(C^\mathrm{T}C\)至少是半正定的，那什么时候是正定的呢？只要没有非零向量使得\(Cx = \textbf{0}\)，那么就可以保证：\(x^\mathrm{T}(C^\mathrm{T}C)x > 0\)。
即要保证\(N(C) = \{\textbf{0}\}\)，即要保证\(r(C) = n\)，即可保证\(C^\mathrm{T}C\)是正定矩阵。
还记得\(C^\mathrm{T}C\)在哪用到吗？即最小二乘求最优近似解那里，最后方程为：\(C\hat{x}=Pb = C(C^\mathrm{T}C)^{-1}C^\mathrm{T}b\)
只要保证\(C\)各列线性无关，则\(C^\mathrm{T}C\)是正定矩阵，所以\(C^\mathrm{T}C\)可逆，则上述方程成立，同左乘\(C^\mathrm{T}\)，然后再左乘\((C^\mathrm{T}C)^{-1}\)，即可求出\(\hat{x}\)。
四. 相似矩阵
\(A, B\)均为\(n \times n\)的方阵，那么\(A\)与\(B\)相似，用数学语言表达为：存在可逆矩阵\(M\)，使得\(B = M^{-1}AM\)
它具有一个性质：相似的矩阵拥有相同的特征值。
证明：
\(Ax = \lambda x\)
\(A(MM^{-1})x = \lambda x\)
\(M^{-1}AMM^{-1}x = \lambda M^{-1}x\)
\(BM^{-1}x = \lambda M^{-1}x\)
\(B(M^{-1}x) = \lambda (M^{-1}x)\)
证毕。且可看出特征值虽然不变，但是特征向量由\(x\)变为了\(M^{-1}x\)。
举个例子，例如可对角化的矩阵\(A\)，其可分解为：\(A = S^{-1}\Lambda S\)。其中\(S\)是可逆的，因为各特征向量线性无关。所以\(A\)与\(\Lambda\)就相似。而且我们会发现，\(A\)与\(\Lambda\)的特征值一样。
五. 奇异值分解
SVD分解也是一种矩阵分解的形式。至今为止，我们已经学过了许多矩阵分解方法了：\(LU\)、\(S\Lambda S^{-1}\)（可对角矩阵）、\(Q\Lambda Q^\mathrm{T}\)（对称矩阵）、\(QR\)（满秩矩阵）。
可以发现，除了\(LU\)分解，其余分解都对矩阵有限制条件。但是这节我要讲的SVD分解，对任意矩阵都成立。
SVD用数学语言描述如下：
\(A = U\Sigma V^\mathrm{T}\)
\(A \in \mathbb{R}^{m \times n}\)是任意矩阵，\(U \in \mathbb{R}^{m \times m}\)是正交阵，\(\Sigma \in \mathbb{R}^{m \times n}\)是"对角阵"，\(V^\mathrm{T} \in \mathbb{R}^{n \times n}\)是正交阵。
我们来看下在已知\(A\)下，如何计算出\(U, \Sigma, V\)
\(\because A = U\Sigma V^\mathrm{T}\)
\(\therefore A^\mathrm{T}A = (V\Sigma^\mathrm{T}U^\mathrm{T})(U\Sigma V^\mathrm{T}) = V\Sigma^\mathrm{T}\Sigma V^\mathrm{T}\)
\(\because A^\mathrm{T}A \text{ is a symmetric matrix}\)
\(\therefore V \text{ is } Q, \Sigma^\mathrm{T}\Sigma \text{ is } \Lambda, \text{ where } A^\mathrm{T}A = Q\Lambda Q^{\mathrm{T}}\)
所以，对于\(A\)，求出\(A^\mathrm{T}A\)的特征值开根和对应的相互正交的标准特征向量，对应排好就是\(\Sigma, V\)
那有了\(\Sigma, V\)后，如何求\(U\)呢？
\(\because A = U\Sigma V^\mathrm{T}\)
\(\therefore AV = U\Sigma V^\mathrm{T}V = U\Sigma\)
即再算出\(AV\)，然后每一列除对应的奇异值，即可得到\(U\)。
多说无益，举个例子来看下如何将矩阵\(A\)分解为\(U\Sigma V^\mathrm{T}\)
已知\(A = \begin{bmatrix} 4 & 4 \\ -3 & 3 \end{bmatrix}\)
先算出\(A^\mathrm{T}A = \begin{bmatrix} 25 & 7 \\ 7 & 25 \end{bmatrix}\)
然后求其特征值和对应的互相正交的标准特征向量：
\(\lambda_1 = 18, x_1 = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ -1 \end{bmatrix}\)
\(\lambda_2 = 32, x_2 = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ 1 \end{bmatrix}\)
即已经求出\(\Sigma = \begin{bmatrix} \sqrt{18} & \\ & \sqrt{32} \end{bmatrix}, V = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ -1 & 1\end{bmatrix}, V^\mathrm{T} = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 & -1 \\ 1 & 1 \end{bmatrix}\)
然后算出\(AV\)，即\(U\Sigma\)：\(\begin{bmatrix} 0 & \frac{8}{\sqrt{2}} \\ -\frac{6}{\sqrt{2}} & 0\end{bmatrix}\)
每一列除对应的\(\sqrt{\lambda_i}\)，即第一列除\(\sqrt{18}\)，第二列除\(\sqrt{32}\)，得到\(U\)：\(\begin{bmatrix} 0 & 1 \\ -1 & 0 \end{bmatrix}\)
现在所有东西都已求出来： \[ U = \begin{bmatrix} 0 & 1 \\ -1 & 0 \end{bmatrix}, \Sigma = \begin{bmatrix} \sqrt{18} & \\ & \sqrt{32} \end{bmatrix}, V^\mathrm{T} = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 & -1 \\ 1 & 1 \end{bmatrix} \] 我们来验证一下，将这仨乘起来，发现等于\(A\)，check！
SVD有什么用呢？我来举一个例子，例如某件事物需要用两个维度来刻画，即\(f: (x, y) \to z\)。那么适合用一个矩阵来表示，不妨表示为\(A\)。
如果我们将\(A\)进行SVD分解为\(U\Sigma V^\mathrm{T}\)，进一步展开可以得到： \[ A = U\Sigma V^\mathrm{T} = \begin{bmatrix}u_1, u_2, \cdots, u_n\end{bmatrix} \cdot \begin{bmatrix}\sigma_1 & & & \\ & \sigma_2 & & \\ & & \cdots & \\ & & & \sigma_n\end{bmatrix} \cdot \begin{bmatrix}v_1^\mathrm{T} \\ v_2^\mathrm{T} \\ \cdots \\ v_n^\mathrm{T}\end{bmatrix} = \sigma_1u_1v_1^\mathrm{T} + \sigma_2u_2v_2^\mathrm{T} + \cdots + \sigma_nu_nv_n^\mathrm{T} \] 可以发现，一个矩阵被拆解为若干矩阵相加，奇异值\(\sigma_i\)可以理解为矩阵所占的权重。那些\(\sigma_i\)大的矩阵说明对整体矩阵的影响越大。
相当于对于一个模式\(A\)，我可以知道\(A\)重点体现在哪些子模式上，进而重点去优化那些子模式。
六. 线性变换
什么是坐标？
其实，世界上坐标不是天生存在的东西。而是人类以某些东西为标准，去测量其它东西的一种度量。
例如我们通常认知的坐标系，其实上就是以俩正交的标准向量基为标准，坐标就是用这俩去线性组合的系数。
所以如何理解一个线性变化？
我这么说吧，假设我们已经确定好一组基(n个)，那么这组基作为我们的“观测基准”，可以以它们为标准观测出万物的状态\((c_1, c_2, \cdots, c_n)\)。（\(c_i\)跟第i个基向量有关）
但是现在，我想换一套观察工具，也就是换一组基(m个)，那么换完之后，同样的一个事物，在之前用旧基观测的时候，它的状态是\((c_1, c_2, \cdots, c_n)\)，用新基观测的时候，它的状态变为\((d_1, d_2, \cdots, d_m)\)。
那么有没有一种映射，可以直接让我从\((c_1, c_2, \cdots, c_n)\)直接可以得到\((d_1, d_2, \cdots, d_m)\)？有，它就是——线性变换。
如何构造这个线性变换呢？如下：
对于旧基(\(v\))的每个基向量，我们都先用新基(\(w\))去观测它，并得到观测状态\(a_{ij}\)： \[ \begin{align*} v_1 &= a_{11}w_1 + a_{21}w_2 + \cdots + a_{m1}w_m \\ v_2 &= a_{12}w_1 + a_{22}w_2 + \cdots + a_{m2}w_m \\ &\cdots \\ v_n &= a_{1n}w_1 + a_{2n}w_2 + \cdots + a_{mn}w_m \end{align*} \] 对于一件事物\(x\)，用旧基观测可以得到：\(x = c_1v_1 + c_2v_2 + \cdots + c_nv_n\)
继续展开： \[ \begin{align*} x &= c_1v_1 + c_2v_2 + \cdots + c_nv_n \\ &= c_1a_{11}w_1 + c_1a_{21}w_2 + \cdots + c_1a_{m1}w_m + \\ &~~~~~c_2a_{12}w_1 + c_2a_{22}w_2 + \cdots + c_2a_{m2}w_m + \\ &~~~~~\cdots \\ &~~~~~c_na_{1n}w_1 + c_na_{2n}w_2 + \cdots + c_na_{mn}w_m \\ &= (c_1a_{11}+c_2a_{12}+\cdots+c_na_{1n})w_1 + \\ &~~~~~(c_1a_{21}+c_2a_{22}+\cdots+c_na_{2n})w_2 + \\ &~~~~~\cdots \\ &~~~~~(c_1a_{m1}+c_2a_{m2}+\cdots+c_na_{mn})w_m \\ &=d_1w_1 + d_2w_2 + \cdots + d_mw_m \end{align*} \] 用矩阵形式表达： \[ Ac = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix}\begin{bmatrix}c_1 \\ c_2 \\ \vdots \\ c_n\end{bmatrix}= \begin{bmatrix} a_{11}c_1 + a_{12}c_2 + \cdots + a_{1n}c_n \\ a_{21}c_1 + a_{22}c_2 + \cdots + a_{2n}c_n \\ \vdots \\ a_{m1}c_1 + a_{m2}c_2 + \cdots + a_{mn}c_n \end{bmatrix}= \begin{bmatrix} d_1 \\ d_2 \\ \vdots \\ d_m \end{bmatrix} \] 所以我们从旧观测状态\((c_1, c_2, \cdots, c_n)\)得到了新观测状态\((d_1, d_2, \cdots, d_m)\)。
问题的关键就是确定这个\(A\)矩阵，从旧基到新基的线性变换也就体现在这个\(A\)矩阵上。
那这个\(A\)咋求呢？\(A\)的每一列其实就是每一个旧基的基向量用新基去观测得到的状态。
至此，我们有了一种全新的视角去看待矩阵乘法\(Ax = b\)
\(x\)是旧基下对某事物的观测状态，\(b\)是新基下对某事物的观测状态。而实现基转换功能的东西，就是\(A\)。
\(A\)的每一列其实就是每一个旧基的基向量用新基去观测得到的状态。
至此，线性变换与矩阵乘法彻底联系了起来。线性变换就是矩阵，矩阵就是线性变换。
而我们知道，矩阵满足\((A + B)x = Ax + Bx, (cA)x = c(Ax)\)。所以线性变换\(T\)是满足加法和数乘的，即：
- \(T(v + w) = T(v) + T(w)\)
- \(T(cv) = cT(v)\)
其实线性变换一定满足\(T(0) = 0\)，因为当\(v = w = 0\)时，\(T(0) = 2T(0)\)，所以\(T(0) = 0\)。所以可以通过\(T(0)\)是否等于0来快速排除一些不是线性变换的映射。
告诉你三个有趣的事实：
- 矩阵的逆就是线性变换的逆变换
- 进行多次线性变换就是多个矩阵连乘，这样子矩阵乘法就有了几何上的直观理解
- 正交阵相当于对空间进行旋转，对角阵相当于对空间进行拉伸
七. 图像压缩
思考一个\(512 \times 512\)的图像，我们需要\(512 \times 512\)个数来保存图像的状态。
令\(n = 512 \times 512\)
具体来说，一个状态可以用一个\(\mathbb{R}^{n}\)向量\(x\)来描述（把矩阵拉成一个向量）
而我们存储的\(512 \times 512\)个数，其实是标准基的系数： \[ x = c_1\begin{bmatrix}1\\ \\ \\ \\ \\ \end{bmatrix} + c_2\begin{bmatrix}\\ 1 \\ \\ \\ \\ \end{bmatrix} + \cdots + c_n\begin{bmatrix} \\ \\ \\ \\ 1\end{bmatrix} \] 那如果换一组基呢？
假设我们的旧基（即标准基）为\(v\)，新基为\(w\)。旧的观测状态为\((c_1, c_2, ..., c_n)\)，那么新的观测状态\((d_1, d_2, ..., d_n)\)需要通过\(Ac\)才能得到，\(A\)的每一列为每一个旧基的基向量用新基去观测得到的状态。
\(A^{-1} = B\)的每一列为每一个新基的基向量用旧基去观测的状态，所以\(B\)其实就是把新基的基向量排成一排。
所以我们新的观测状态：\(d = B^{-1}c\)。
用新观测状态表示图片向量：\(x = d_1w_1 + d_2w_2 + \cdots + d_nw_n\)
我们可以设定一个阈值，对于那些很小的\(d_i\)那一项，我们就直接丢弃它，不存储了。例如我只要前5大的\(d_i\)，那么我原本要存\(n\)个数，现在我只需要存5个数了。
我还原出来的图片向量即为：\(\hat{x} = d_1w_1 + d_2w_2 + \cdots + d_5w_5\)。
非常巧妙，嗯哼？
相当于用时间换空间，因为压缩和还原的过程我都需要进行矩阵运算。所以想加速压缩/还原速度我需要保证挑选出来的新基组成的\(B\)的逆好求。
同时，为了尽可能压缩空间，我要使得挑选出来的新基的观测状态\((d_1, d_2, \cdots, d_n)\)尽可能多的使\(d_i < \text{阈值}\)。这样我就可能少保存系数，从而达到压缩存储空间的效果。
注意，为啥我新基的个数要和旧基保持一样（即都有\(n\)个基向量）？因为图片大小为\(512 \times 512\)，你不能直接把人家图片大小给改了啊，直接通过砍图片大小来达到的压缩不叫压缩。
多说一嘴，基的选择要结合实际情况分析，例如这张图片色彩很单调，且一大片区域都是同一种颜色的情况。那么基向量里必有\(\begin{bmatrix}1 \\ 1 \\ \vdots \\ 1 \end{bmatrix}\)。因为这个基向量表达的图片状态就是纯单色图片。当然了，我意思是这个基向量肯定起着主导作用（也就是系数\(d_i\)大），但是仍要结合使用别的基向量，要不你还原出来的图片就是纯单色图片。
八. 左右逆, 伪逆
对于矩阵\(A \in \mathbb{R}^{m \times n}\)，若\(A\)的各列线性无关。则\(A\)存在左逆：\((A^\mathrm{T}A)^{-1}A^\mathrm{T}\)。
拿这玩意左乘\(A\)可得到\(I\)，所以叫左逆。
为啥条件是各列线性无关呢？因为我们知道\(A^\mathrm{T}A\)一定是半正定矩阵。且当\(N(A) = {\textbf{0}}\)时，升级为正定矩阵，而正定矩阵一定可逆。所以才能有\((A^\mathrm{T}A)^{-1}\)。
对应的，我可以得到右逆的定义，若\(A\)的各行线性无关，则\(A\)存在右逆：\(A^\mathrm{T}(AA^\mathrm{T})^{-1}\)。
下面来讨论一下伪逆。
我们知道，如果矩阵\(r(A) < \min(m, n), A \in \mathbb{R}^{m \times n}\)，那么对于无解的最小二乘方程：\(Ax = b\)是求不出最优近似解的。但是伪逆\(A^+\)却可以求到"最优稳定解"\(\hat{x}\)，满足：\(\| A\hat{x}-b \| \le \| Ax - b \|\)。
ok，那如何求伪逆呢？用SVD。这里我直接给出公式：
\(A^+ = V\Sigma^+ U^\mathrm{T}\)，\(\Sigma^+\)就是\(\Sigma\)的每一个奇异值取倒数。
（伪逆这里讲的很浅，因为目前还不怎么用得着，等以后需要学习原理的时候再补充）