18.06SC

Unit1

矩阵的LU分解

  • 其实就是分解成上三角乘下三角

  • 由来:正常的矩阵化行阶梯的时候

    • 划出来的是一个上三角

    • 划的过程使用左乘置换矩阵来表示,可以变成下三角

      • 每一步左乘置换矩阵Ei,jE_{i,j}都是在原本的矩阵的(i,j)(i,j)处产生零

  • 还有一种LDU分解:D为对角阵,U可以化成主对角线均为1的

  • 条件:顺序主子式均不为0

四个基本空间

  • 任何矩阵都定义了四个基本空间

    • 列空间C(A):A矩阵的列向量组成的空间
    • 零空间N(A):方程Ax=0的所有解构成的空间
    • 行空间 C(ATA^T):矩阵行向量
    • 左零空间N(ATA^T):矩阵转置的方程的解

‍

Unit2

正交向量与正交子空间

  • 正交:空间正交等价于所有向量都正交(正交一定垂直而反过来不一定)

    • 我们将中的三维空间的两个二维子空间推广到n维空间RnR^n的一个p维子空间V和一个q维子空间W

      则如果P+q>n，则V∩WV \cap W中有非零向量(V和W不正交)

    • 零空间和行空间正交(并且维数之和=n,这是正交补(orthogonal complements),意味着行空间包含所有和零空间正交的向量),列空间和左零空间正交

    • 左零空间法判断解:找一个线性变换使得等式变为0=1(在左零空间中去找)

  • 当Ax=0无解时,若A列向量线性无关,可以使用ATAX=ATbA^TAX=A^Tb求解

  • 对一个向量左乘A就是把所有该向量映射到A的列空间当中去(x可以分解为行空间成分和零空间成分)

投影

  • 投影矩阵:
  • why投影:很多时候线性方程组不一定有解,找投影上去的近似解用
  • 高维投影:

‍

  • 注意:投影矩阵(I-P)投影到与P投影的空间相正交的空间

正交&QR

  • 几种特殊的正交矩阵:

    • 旋转矩阵Q=(cosθ−sinθsinθcosθ)Q= \left( \begin{matrix} cos\theta & -sin\theta\\\\ sin\theta & cos\theta\\\\ \end{matrix} \right)，将空间旋转θ\theta度
    • reflection:

  • 应用

    • 求投影分量:xi=qiTvx_i=q^T_iv(因为其它分量的乘积均为0)
    • 向量重构:设原本向量b=x+y+z,投影之后b=k1p1+k2p2+k3p3b=k_1p_1+k_2p_2+k_3p_3

  • QR

    • 施密特正交化的本质:找正交基(通过对投影作差)然后标准化

    • q1aTq_1a^T即为a的长度

‍

杂&特征值

  • 矩阵的行列式的绝对值:其列(行)向量构成的平行六面体的体积,正负对应左手系和右手系

  • 投影矩阵是投影到某一个平面内:对该平面内的向量的特征值就是1,垂直的就是0

  • 对称矩阵的特征值互相垂直

  • 置换矩阵的所有特征值的绝对值的实部都是1

  • 平移矩阵:特征值会变但是特征向量不变(A+cI)x=(λ+c)x(A+cI)x=(\lambda+c)x

复数特征值

  • 特征值重数:

    • 几何重数(geometric multiplicity):为该特征值对应特征向量个数,A−λIA-\lambda I对应的零空间维数

    • 代数重数:为λ\lambda的重复次数

      • GM≤AMGM\le AM

  • 差分方程:

‍

微分方程

  • 稳定性:特征值实部小于零则趋近于0

    • 一个特征值为0,其余均实部小于零则稳定
    • 至少有一个实部为正就发散

解耦

矩阵指数

马尔科夫链和傅里叶级数

ATA^T的特征值和A相同

马尔科夫矩阵

  • 定义:所有元素非负且每列加和为1(最大特征值为1,对应特征向量称为pattern for markov chain)

  • 矩阵方幂中的稳定性:有一个特征值为1,其它绝对值小于1

傅里叶级数

  • 无限向量:分量的数量是无限的\这个向量是一个函数

    • 点积:

    • 其点积的收敛性:

      • 这种点积定义仍满足向量不等式

Unit3

‍

对称矩阵

  • 其行空间和列空间相同

谱分解


复数

  • 实矩阵出现了复数特征值和特征向量的话,一定还有一对共轭的特征值和特征向量
  • 特征值和主元的联系:主元之积和特征值之积是相等的

正定矩阵

  • ellipse:椭圆
  • 分解:
    • S=ATAS=A^TA
    • cholesky分解:
    • 对角化分解:
    • 半正定分解出来的因子矩阵是列相关的

椭圆方程

复数矩阵，快速傅里叶变换

  • 对复数向量来说AHB≠BHAA^HB\ne B^HA,实际上为共轭转置的关系
  • (Au)Hv=uH(AHv)(Au)^Hv=u^H(A^Hv)

hermitian matrix

  • 性质:
    • 对任意实或复向量的二次型结果为实数
    • 特征值为实数
    • 特征向量垂直

酉矩阵

    • 酉矩阵只有±1这两种特征值

傅里叶矩阵

    • 一定非酉矩阵,但是对称,列相互正交
    • 逆:
  • DFT(离散傅里叶变换)
  • Trigonometric Interpolation(三角插值)

快速傅里叶变换

  • recurssively call the factorization
  • 这里的ω is ω2n\omega\text{ is }\omega_{2n}

正定矩阵和最小值

  • 正定性判定:
    • eigenvalue test:均为正
    • determinant test:顺序主子式正
    • pivot test:消元后的主元为正
    • energy test:算其二次型

  • 配方法的实质是消元
  • 主轴定理

相似矩阵和jordan标准型

jordan form

  • jordam block:

    • 当矩阵具有n个特征值和n个块:进化为对角矩阵

  • 任意nn阶矩阵A\bf A都与一个若尔当矩阵J\bf J相似。若尔当矩阵中的每一个若尔当块对应一个特征向量。

  • 若矩阵具有nn个不同的特征向量，则可以对角化，此时其若尔当标准型J\bf J就是对角矩阵Λ\bf Λ。

  • 如果A\bf A有重复特征值，则特征向量个数变少, 其Jordan Matrix的对角线之上(上对角线有n−dn-d个11)。换句话说，就是说若尔当矩阵上对角线每多一个11, 就少一个特征向量。

  • 两个矩阵特征值和特征向量相同,若尔当块不同也不相似

奇异值分解(SVD)


  • 奇异值分解就是在行空间中寻找到正交基,经过线性变换变成列空间的正交基，(v1..vrv_1..v_r为行空间标准正交基vr+1...vnv_{r+1}...v_n为零空间标准正交基,u为列空间标准正交基)
    • 令Ur=(u1...ur)U_r=(u_1...u_r)可得AVr=ΣrUrAV_r=\Sigma_r U_r
    • 我们向UrU_r中添加与其正交的向量,另一个矩阵同理AVn×n=Um×mΛAV_{n\times n}=U_{m\times m}\Lambda
    • U,V均正交,取逆完成

reduced SVD

full SVD

rank one decomposition

A=UΣVT=∑i=1ruiσiviTA=U\Sigma V^T=\sum_{i=1}^r u_i\sigma _i v_i^T

奇异值 and 特征值

  • 奇异值一定非负,特征值可以为负
  • 奇异值的求法就是对ATAA^TA特征值开根
  • 当A正定或半正定的时候两者相同(奇异值就是列空间正交基的长度)

如何寻找SVD分解

  • 矩阵A有两组奇异向量:分别对应自身乘转置和转置乘自身

ATA=VΣ2VTA^TA=V\Sigma ^2V^T

AAT=UΣ2UTAA^T=U\Sigma^2U^T

  • 另一种方法

几何意义

快速计算和数值稳定性

  • 直接算计算量大并且有精度损失
    • 特征值:QTSQQ^TSQ化为对称三对角矩阵(tridiagonal,仅主对角和相邻非0)
    • 奇异值Q1TAQ2Q_1^TAQ_2可化为双对角矩阵
    • B为双对角,则BTBB^TB为三对角
  • 当ATAA^TA与AATAA^T有很大不同的时候,特征值非常不稳定,但是奇异值都是稳定的

线性变换

  • 本质上就是将一组基v1,v2...vnv_1,v_2...v_n变换为T(v1),T(v2)...T(vn)T(v_1),T(v_2)...T(v_n)然后保持系数不变
  • 设A为从V到W的变换矩阵,若基向量从v变换为w,A变为W−1AVW^{-1}AV
  • range of T:set of all outputs T(v)
  • kernel of T:set of all inputs for which T(v)=0
  • 投影变换也是一种线性变换

基变换和图像压缩

  • 这个矩阵B\mathbb B记录了如何将一组基中每一个基向量表示为另一组基向量的线性组合，而形成的矩阵
  • 我们希望基变换矩阵越简单越好(找n个线性无关的特征向量作为基)
    • eigenvectors are perfect basis,they produce eigenvalue matrix

选取奇异向量为基

  • 上述为恒等线性变换,下述适用于任意线性变换

图像压缩

标准方式:JPEG(joint photographic expert groups)

  • 压缩前采用的是标准基
  • 小波基:小波变换(wavelet transform):使用有限长或快速衰减的母小波表示波
    • 使用小波基表示向量()
  • 傅里叶基:傅里叶矩阵的列向量
    • 过程:将信号变为傅里叶基,再压缩舍弃掉小于阈值的值

矩阵的极坐标分解

左右逆,伪逆,极分解

  • 常规逆矩阵为两侧逆(two sided inverse)
  • 左逆:矩阵列满秩且非方阵时Aleft−1=(ATA)−1ATA_{left}^{-1}=(A^TA)^{-1}A^T
  • 右逆同理Aright−1=AT(ATA)−1A_{right}^{-1}=A^T(A^TA)^{-1}
  • 一个长方形矩阵不可能左右逆都有,左乘右逆和右乘左逆得到的都是投影矩阵
  • 从矩阵行空间到列空间的映射x∼Axx\sim Ax其实是双射,这可逆,这种变换就叫伪逆

伪逆

  • 求伪逆

A+A=projection matrix onto the row spaceAA+=projection matrix onto the column space\begin{aligned} A^+A=\text{projection matrix onto the row space}\\\\ AA^+=\text{projection matrix onto the column space} \end{aligned}