数据科学数学基础笔记 - 3月

Author Avatar
MorphLing 3月 25, 2021


XCPC 2021 Happy Winter Vacation

2021.03.18

度量

  • 余弦相似度
  • 距离

曼哈顿距离：$d(A,B)=\sum_\limits{jk}|A_{jk}-T_{jk}|$

向量范数

  • 模

复数$x=(a,b)=a+ib$的长度或者模定义：$||x||=\sqrt{a^2+b^2}$

显然，模具有以下三个性质

  1. 非负性：$||x||\ge0$，当且仅当$x=0$时等号成立
  2. 齐次性：$||\lambda x||=|\lambda|||x||(\forall \lambda \in \mathbb{R})$
  3. 三角不等式：$||x + y||\le ||x||+||y||(x,y\in\mathbb{R}^n)$

模：向量到实数的一个函数

公理化推广，得到范数定义

函数$||·||:\mathbb{V}\rightarrow\mathbb{R},x\rightarrow||x||$

这个函数把向量$x$映射为它的长度$||x||\in \mathbb{R}$，并且使得对$\forall \lambda \in \mathbb{R}$和$\forall x, y \in \mathbb{V}$，满足非负性、齐次性和三角不等式，则称$||x||$是向量$x$的向量范数，称定义了范数的线性空间$\mathbb{V}$为赋范线性空间

常用的向量范数：$l_p$范数

$||x||_p=(\sum_\limits{i=1}^n|x_i|^p)^{\frac{1}{p}},1\le p<\infty$

定义的$||·||$是$\mathbb{R}^n$上的向量范数，称为$p$范数或$l_p$范数

当p=1时，得到1范数或$l_1$范数，或Manhattan范数

当p=2时，得到2范数或$l_2$范数，或欧几里得范数

容易验证，以上范数满足范数性质

当p取到无穷大时：$||x||_\infty=\lim_\limits{p\rightarrow\infty}||x||_p$，称为$\infty$范数，或$l_\infty$范数

证明无穷范数是向量范数：证明三条性质即可，主要证$||x||_\infty=\max_\limits{i}|x_i|=\lim_\limits{p\rightarrow+\infty}||x||_p$

证明见4.1 17:00（利用极限夹逼准则）

（所以无穷范数等价于最大值函数$\max_\limits{i}|x_i|$）

当$0<p<1$时，所定义的$||·||_p$不是$\mathbb{R}^n$上的向量范数

考虑$n=2,p=\frac{1}{2}$，$||\alpha+\beta||_{\frac{1}{2}}\ge||\alpha||_{\frac{1}{2}}+||\beta||_{\frac{1}{2}}$，也就是说不满足三角不等式

基数函数

向量x的基数函数定义为x中非零元素的个数，即$card(x)=\sum_\limits{i=1}^nI(X_i\ne 0)$

基数函数也被称为$l_0$范数，但它不满足范数定义的条件（不满足齐次性）

范数的几何意义

  • 单位范数球$\mathbb{B}_p=\{x\in\mathbb{R}^n:||x||_p\le1\}$：对于$l_p$范数小于等于1的向量集合

单位范数球反映了不同范数的性质，对于不同二点p，范数球有着不同的几何形状。

$\mathbb{B}_2$：圆，$\mathbb{B}_1$：球，$\mathbb{B}_\infty$：方形

向量收敛

如果$\lim_\limits{k\rightarrow\infty}x_i^{(k)}=x_i^\ast(i=1,2,…,n)$，则称$x^{(k)}$收敛于向量$x^\ast$

即向量收敛$\Leftrightarrow$分量收敛

范数的性质

  • 范数的连续性

设非负函数$N(x)=||x||$为$\mathbb{R}^n$上任一向量范数，则$N(x)$是$x$分量$x_1,x_2,…,x_n$的连续函数

  • 柯西收敛原理

实数域或复数域上的有限维线性空间按任何范数$||·||$必定完备。

（也就是说高等数学中学到的关于函数结论都可以推广到有限维线性空间中）

（以及机器学习中的算法一定会趋于某一个值或某一个精度？）

  • 向量序列收敛定理

$\lim_\limits{k\rightarrow\infty}x^{(k)}=x^\ast\Leftrightarrow\lim_\limits{k\rightarrow\infty}||x^{(k)}-x^\ast||=0$

也就是向量收敛$\Leftrightarrow$范数收敛$\Leftrightarrow$坐标收敛

范数的等价性

各种向量范数之间存在下述重要关系

$||x||_{\infty}\le||x||_{2}\le||x||_{1}\le\sqrt n||x||_{2}\le n||x||_{\infty}$

等价范数

若存在$c1,c2>0$使得$c1||x||_s\le||x||_t\le c_2||x||_s$成立，则称$||x||_t$和$||x||_s$为$\mathbb{R}^n$上的等价范数

标准内积（点积）

$\langle x,y\rangle=x^Ty=\sum_\limits{i=1}^nx_iy_i$

内积的性质：

  • 非负性$\langle x,x\rangle\ge0$当且仅当x=0
  • 对称性$\langle x,y\rangle=\langle y,x\rangle$
  • 齐次性$\langle \lambda x,y\rangle=\lambda\langle x,y\rangle$
  • 线性性$\langle x+y,z\rangle=\langle x,z\rangle+\langle y,z\rangle$

称$\langle x,y\rangle$是向量$x,y$的内积，称定义了内积的线性空间$\mathbb{V}$为内积空间。若内积是点积时，称定义了标准内积的线性空间为欧氏空间。

内积不一定是点积，反例：$\langle x,y\rangle:=x_1y_1-(x_1y_2+x_2y_1)+2x_2y_2$，是内积而不是点积

对称正定矩阵

若对称矩阵$A\in \mathbb{R}^{n\times n}$满足$\forall x\in \mathbb{V}\setminus {0}:x^TAx>0$，则我们称$A$对称正定矩阵或正定矩阵；

若满足$\forall x\in \mathbb{V}\setminus {0}:x^TAx\ge0$，则我们称$A$对称正半定矩阵或正半定矩阵

内积和对称、正定矩阵的关系：

对于一个有限维空间$\mathbb{V}$和一个有序基底$B$，如果$\langle·,·\rangle$是一个内积，当且仅当存在一个对称、正定矩阵$A\in\mathbb{R}^{n\times n}$满足$\langle x,y\rangle=\hat{x}^TA\hat{y}$

对称正定矩阵A的性质：

  • A的核（零空间）只包含0，因为$x^TAx>0$对于任意$x\ne0$成立，即如果$x\ne0$则$Ax\ne0$
  • A的对角元是正的，因为$a_{ii}=e_i^TAe_i>0$，其中$e_i$是$\mathbb{R}^n$中的标准基

内积导出的范数

$||x||=\sqrt{\langle x, x\rangle}$

标准内积与2-范数存在的联系：$||x||^2_2=x^Tx$

  • 不是每个范数都能由内积导出

柯西施瓦兹不等式

内积和范数之间的不等关系

若$||·||$是由$(\mathbb{V},\langle·,·\rangle)$导出的范数，则$\langle x, y\rangle^2\le||x||^2||y||^2$

证明见4.2 15:00

image-20210318231047011

用内积计算向量的长度

向量长度:$\langle x, x\rangle$

向量在不同内积下长度不同，不同内积代表不同的度量尺度

距离

考虑一个内积空间$\langle \mathbb{V},\langle\cdot,\cdot\rangle\rangle$，我们称$d(x,y):=||x-y||=\sqrt{\langle x-y, x-y\rangle}$为$x,y\in\mathbb{V}$的距离。如果我们用点积作为内积，则上述距离称为欧几里得距离，简称欧氏距离

向量间的距离不必需要内积，使用范数就够了

度量

考虑一个内积空间$\langle \mathbb{V},\langle\cdot,\cdot\rangle\rangle$，我们称映射$d:\mathbb{V}\times\mathbb{V}\rightarrow\mathbb{R}$（$(x,y)\rightarrow d(x,y)$）为度量

度量空间

一个度量空间由一个有序对$(\mathbb{V},d)$表示，其中$\mathbb{V}$是一种集合，$d$是定义在V上的一种度量

对任意$x,y,z\in\mathbb{V}$，需满足：

  • 非负性：$d(x,y)\ge0$，且$d(x,y)=0\Leftrightarrow x=y$
  • 对称性：$d(x,y)=d(y,x)$
  • 三角不等式：$d(x,z)\le d(x,y)+d(y,z)$

度量空间也称为距离空间

夹角

$cos\theta=\frac{x^Ty}{||x||_2||y||_2}$

当$x^Ty=0$时，向量$x,y$之间角度为$90^\circ$，称为正交。当$\theta=0^\circ或180^\circ$时，$x,y$成一直线，即$y=kx,k\in\mathbb{K}$，称为平行

正交

如果$\langle x,y\rangle=0$，则称$x,y$正交，记作$x\perp y$，特别低，如果$||x||=1=||y||$，也即是单位向量时，称$x,y$标准正交。

  • 两两正交的向量组线性无关

证明：反证法4.2 25:00

  • 计算夹角来判断是否正交

正交矩阵

$AA^T=I=A^TA$

因此$A^{-1}=A^T$

正交矩阵变换的特殊性：用正交矩阵A作用一个向量x时，向量x的长度不变，两个向量x,y的夹角也不会在正交矩阵的作用下改变，用点积作为内积时：

  • $||Ax||^2=(Ax)^T(Ax)=x^TA^TAx=x^TIx=x^Tx=||x||^2$
  • $\cos\omega=\frac{(Ax)^T(Ax)}{||Ax||||Ay||}=\frac{x^TA^TAy}{\sqrt{x^TA^TAxy^YA^YAy}}=\frac{x^Ty}{||x||||y||}$

也就是说，角度和长度在正交矩阵的变化下是一个不变量

2021.03.19

闵可夫斯基距离

$d(x_i,x_j)=\sqrt[p]{\sum\limits_{k=1}^m|x_{ki}-x_{kj}}|^p||x_i-x_j||_p$

p=2：欧氏距离

p=1：曼哈顿距离

p=$\infty$：切比雪夫距离

缺点：给定二维样本（身高，体重）。但身高和体重的单位不同，不等价

余弦相似度

$sim_{\cos}(x_i,x_j)=\frac{x_i\cdot x_j}{|x_i||x_j|}$

在夹角上区分差异，而对绝对的数值不敏感

可以采用调整余弦相似度，即对所有维度上的数值都减去一个均值

汉明距离

表示两个（相同长度）字符串对应位置上值不等的个数

矩阵的内积：矩阵向量化

将$m\times n$实矩阵A，将这个矩阵拉长为$mn\times 1$的向量，$a=vec(A)$

$A,B$是线性空间$\mathbb{R}^{m\times n}$中任意两个实矩阵，定义内积：$\langle A,B\rangle=\langle vec(A),vec(B)\rangle$

矩阵范数

定义$||\cdot||:\mathbb{R}^{m\times n}\rightarrow\mathbb{R}$满足以下性质

  • $||A||\ge0$ 正定条件
  • $||cA||=|c|||A||$ 齐次条件
  • $||A+B||\le||A||+||B||$三角不等式

则称$||\cdot||$是$\mathbb{R}^{m\times n}$上一个（广义）矩阵范数

（vec(A)的）$l_1$范数：$||A||_{m1}:=\sum\limits_{i=1}^m\sum\limits_{j=1}^n|a_{ij}|$

三条性质易证 证明见4.4 5:00

（vec(A)的）$l_\infty$范数：$||A||_{m\infty}:=\max\limits_{1\le i\le m,1\le j\le n}|a_{ij}|$

$l_2$范数又称为$Frobenius$范数：$||A||_{F}:=(\sum\limits_{i=1}^m\sum\limits_{j=1}^n|a_{ij}|^2)^{\frac{1}{2}}=Tr(A^TA)^{\frac{1}{2}}$

矩阵范数的相容性条件： $||AB||\le||A||||B||$

不满足相容性条件的矩阵范数，称为广义矩阵范数

$||\cdot||_{m1},||\cdot||_F$满足相容性条件，但$||\cdot||_{m\infty}$不满足相容性条件

修改$||\cdot||_{m\infty}$使其满足相容性条件：$||A||_{m_\infty}:=n\max\limits_{1\le i\le m,1\le j\le n}|a_{ij}|$

矩阵范数和向量范数的相容性

若$||Ax||_v\le||A||_M||x||_v$，则称矩阵范数$||\cdot||_M$和向量范数$||\cdot||_v$相容

算子范数

对任意向量范数，都可以构造一个与该矩阵范数相容的矩阵范数（算子范数）

$||A||=\max\{||Ax||_v:x\in\mathbb{R}^n,||x||_v=1\}=max\{\frac{||Ax||_v}{||x||_v}:x\in \mathbb{R}^n,x\ne 0\}$

  • 算子范数都满足相容性条件

$p=1,\infty,2$时，向量$l_p$范数诱导出的算子范数分别是：最大列（绝对值）和、最大行（绝对值）和，和最大谱（$A^TA$的最大特征值开根号?）

算子范数的几何意义

2021.03.22

损失函数$L(y_i,f(x_i))$

$R_{srm}(f)=\frac{1}{N}\sum\limits_{i=1}^NL(y_i,f(x_i))+\lambda J(f)$

其中$y_i$是特征$x_i$的标签，$f(x_i)$是模型$f$对于特征$x_i$给出的一个预测值；$L(y_i,f(x_i))$是损失函数，用于衡量单个样本预测值和真实值的误差；

$\frac{1}{N}\sum\limits_{i=1}^NL(y_i,f(x_i))$是误差项，或代价函数

$\lambda J(f)$是正则化项，主要用于防止模型过拟合

  • 基于距离度量的损失
  • 非距离度量形式的损失

距离相关损失函数

  • 0-1损失函数
  • 绝对损失函数
  • 平方损失函数

正则化

  • 经验风险：$min Loss(\theta, X,Y)$
  • 结构风险：$min Loss(\theta,X,Y)+\lambda J(\theta)$

一个向量的元素个数正好是向量的$l_0$范数

$l_1$范数

$l_1$范数是$l_0$范数的最优凸近似，而且它比$l_0$范数更容易优化求解，所以$l_1$范数被称为“稀疏规则算子”(Lasso)，常常可应用在

  • 稀疏编码
  • 特征选择
  • 压缩感知

$l_1$和$l_0$范数都可以实现稀疏，$l_1$优化求解特性更好因此广泛应用。

稀疏矩阵的优点：计算速度更快、存储成本低、可解释性强

$l_2$范数

最小化$l_2$范数可以使得参数向量的元素值很小，大都接近于0，可以改善过拟合、易于优化

$l_2$范数是光滑的，$l_1$范数存在不可导点，但因此$l_2$范数较差，因为会倾向于将异常值的影响变得更大

2021.03.25

$||A||_{2,1}$和$||A||_{1,2}$范数

$||A||_{2,1}=\sum\limits_{j=1}^n||a_j||_2=\sum\limits_{j=1}^n(\sum\limits_{i=1}^m|A_{ij}|^2)^\frac{1}{2}$

最小化$||A||_{2,1}$范数能让矩阵A不同行之间（列向量）稀疏

$||A||_{1,2}=(\sum\limits_{j=1}^n||a_j||^\frac{1}{2})=(\sum\limits_{j=1}^n(\sum\limits_{i=1}^m|A_{ij}|^2)^\frac{1}{2}$

最小化$||A||_{1,2}$范数能让矩阵行内元素互斥，即存在0元素但不能全为0

核范数

$||A||_*=Tr(\sqrt{A^TA})$

核范数指矩阵奇异值的和，最小化核范数，可以导致低秩矩阵。

应用：矩阵填充，推荐系统、鲁棒PCA

投影

应用：信号降噪滤波、数据降维、主成分分析、时间序列分析

许多问题的最优求解可归结为数据在某个子空间的投影问题

矩阵四个基本子空间

  • 列空间 - 其列向量的所有线性组合的集合 - $Col(A)$
  • 行空间 - 其行向量的所有线性组合的集合 - $Row(A)=Col(A^T)$
  • 零空间 - $\{x|Ax=0\}$ - $Null(A)$
  • 左零空间 - $\{x|A^Tx=0\}$ - $Null(A^T)$（因为$\{x|x^TA=0\}$而被称为左零）

定理1：

  1. 一系列初等行变换不改变矩阵的行空间
  2. 一系列初等行变换不改变矩阵的零空间
  3. 一系列初等列变换不改变矩阵的列空间
  4. 一系列初等列变换不改变矩阵的左零空间

零空间计算方法https://zhuanlan.zhihu.com/p/149213639

定理2：

  • 矩阵的行秩等于列秩，因此$dim(Col(A))=dim(Row(A))=rank(A)$

定理3：

  • $dim(Null(A))=n-rank(A)$

定理4：

  • 对于矩阵$A_{m\times n}$有$dim(Col(A))+dim[Null(A)]=n$

推论：

  • 对于$A\in\mathbb{R}^{m\times n}$，$dim(Null(A^T))=m-rank(A)$

四个子空间的正交关系

定理5：

  • 设$A\in\mathbb{R}^{m\times n}$，有$Col(A)\bigcap Null(A^T)=\{0\}$和$Col(A^T)\bigcap Null(A)=\{0\}$

    证明见4.7 1:30

若$\mathbb{S和T}是R^n$的两个子空间，且$S\bigcap T=\{0\}$，则称$\mathbb{S}$和$\mathbb{T}$无交连。

若$\forall v\in S,\forall w \in T$，均有$v^Tw=0$，我们说S垂直于T，T垂直于S，记作$S\perp T$，$T\perp S$，或者说子空间S和子空间T是正交的。

定理6：

  • 正交的两个子空间必定是无交连的。

    证明见4.7 5:50

    但无交连不一定正交

正交补关系

设$\mathbb{V}\sub \mathbb{R}^n$是一个子空间，$\mathbb{V}$在$\mathbb{R}^n$中的正交补定义为集合$\{w\in \mathbb{R}^n|v^Tw=0,\forall v\in \mathbb{V}\}$，记作$\mathbb{V}^\perp$

一个空间与它的正交补空间正交，即$\mathbb{V}\perp\mathbb{V}^\perp$，这两个子空间的和是直和

正交分解：对于$\mathbb{R}^n$中的任意向量x可以唯一分解成如下形式：$x=x_1+x_2$，其中$x_1\in\mathbb{V},x_2\in\mathbb{V}^\perp$，且$x_1^Tx_2=0$，这种分解形式叫做正交分解

  • $Col(A^T)^\perp=Null(A),Col(A)^\perp=Null(A^T)$

正交补的含义：正交+补充（$R^n$是由Zion关键$\mathbb{V}$补充$\mathbb{V}^\perp$而成）

2021.03.26

基本定理

  • 正交角度：$Col(A^T)\perp Null(A),Col(A)\perp Null(A^T)$
  • 扩张角度：$Col(A^T)\oplus Null(A)=\mathbb{R}^n,Col(A)\oplus Null(A^T)=\mathbb{R}^n$
  • 维数角度：$dimCol(A^T)+dimNull(A)=n, dimCol(A)+dimNull(A^T)=m$

投影

如果线性映射$\pi:\mathbb{V}\rightarrow\mathbb{U}$满足$\pi^2=\pi\circ\pi=\pi$则称$\pi$为投影

设$\pi$对应的矩阵$P_\pi$，称$P_\pi$为投影矩阵

正交投影

$\mathbb{U}$是$\mathbb{R}^n$的子空间，求$y\in\mathbb{U}$，使得$||y-x||$最小，即$\pi_\mathbb{U}(x)=arg\min\limits_{y\in U}||y-x||$

投影到一维子空间

$\pi_u(x)=\lambda b$

  • 确定$\lambda=\frac{b^Tx}{b^tb}$
  • 确定$\pi_U(x)=\frac{b^Tx}{||b||^2}b$，$||\pi_U(x)||=|cos\omega|||x||$，$\omega$是x和b之间的夹角，$cos\omega=\frac{b^Tx}{||b||||x||}$
  • 确定投影矩阵$P_\pi$=$\frac{bb^T}{||b||^2}$（$bb^T$是一个对称矩阵，而$b^Tb$则是一个标量）

投影到一般子空间

设$=(b_1,…,b_n)$是子空间U的一个有序基底。U上的任何投影$\pi_U(x)$必须是U中的一个元素，故有$\pi_U(x)=\sum\limits_{i=1}^n\lambda_ib_i$，逐步确定$\lambda_1,…,\lambda_n$和投影矩阵$P_\pi$

  • 确定$\lambda_1,…,\lambda_n$，因为$\pi_U(x)$是x的投影，所以$x-\pi_U(x)\in Col(B)^\perp=Null(B^T)$

    所以$b_n^T(x-\pi_U(x))=\langle bn, x-\pi_U(x)\rangle=0$

    得到$\lambda=(B^TB)^{-1}B^Tx$

    见4.8 25:00

  • 确定$\pi_U(x)=B\lambda=B(B^TB)^{-1}B^Tx$

  • 确定$P_\pi=B(B^TB)^{-1}B^T$

投影和$Ax=b$无解情况

方程无解说明b不在A的范围内，即向量b不在A的列张成的子空间中

我们可以找到一个近似解

想法是在A的列张成的子空间中找到最接近b的向量，即计算b到A列张成的子空间上的正交投影

该解被称为超定系统的最小二乘解

标准正交基

$e_1,e_2,…,e_r$是线性空间V的一个基，若任意向量$a=\lambda_1e_1+\lambda_2e_2+…+\lambda_re_r$

为求其中的系数$\lambda_i(i=1,…,r)$可以计算$e_i$与$a$的内积，有$\lambda_i=\langle a,e_i\rangle$

Gram-Schimidt正交化

$b1=a1;\\b2=a2-\frac{\langle b_1,a_2\rangle}{\langle b_1, b_1\rangle}b1;\\br=a_r-\frac{\langle b_1,a_r\rangle}{\langle b_1,b_1\rangle}b1-\frac{\langle b_2,a_r\rangle}{\langle b_2,b_2\rangle}b2-…-\frac{\langle b_{r-1},a_r\rangle}{\langle b_{r-1},b_{r-1}\rangle}b_{r-1}$

然后单位化，取$e_1=\frac{1}{||b1||}b1,…,e_r=\frac{1}{||br||}br$，就是V的一个规范正交基

例见4.9 12:00

旋转

在平面内，一个图形绕着一个顶点旋转一定角度得到另一个图形的变化叫做旋转。

旋转是一个线性映射，可以看成欧氏空间的一个自同构，它把空间中元素映射为另外一个元素。

旋转保持基底性质不变：例见4.10 3:50

$\mathbb{R}^n$中的旋转

Givens旋转矩阵

2维旋转是n-2时$Givens$旋转的一个特殊情形

旋转矩阵的性质

  • $R$是旋转矩阵当且仅当它是正交矩阵且$det(R)=1$

  • 保距性：设$R_\theta$是旋转矩阵，$\forall x,y\in\mathbb{R}^n$，有$||x-y||_2=||R_\theta(x)-R_\theta(y)||_2$

    即空间中两个点在旋转前后距离保持不变（可利用正交矩阵变换后距离不变的性质证明）

  • 保角性：设$R_\theta$是旋转矩阵，$\forall x,y\in\mathbb{R}^n\setminus\{0\}$，有$\frac{\langle x, y\rangle}{||x||||y||}=\frac{\langle R_\theta(x),R_\theta(y)\rangle}{||R_\theta(x)||||R_\theta(y)||}$，即两个向量在旋转前后角度保持不变

  • 多个旋转矩阵的乘积仍然是旋转矩阵

  • 仅在二维情形有可交换性即$R_\theta R\phi=R_\phi R\theta$,，在三维或更高维，交换性不成立

2021.03.30

群

性质：

  1. 封闭性
  2. 结合性
  3. 有单位元
  4. 有逆元

如果有$\forall x,y\in\mathbb{G}:x\circ y=y\circ x$则$G=(\mathbb{G},\circ)$称作阿贝尔群，或称作可交换群

$\mathbb{R}^{n\times n}$中的所有旋转矩阵构成的集合再矩阵乘法下构成群，称为特殊正交群，记作$SO(n)$，当n=2时，$SO(2)$是阿贝尔群

两个例子：Procrustes问题和Wahba问题 4.10 24:00

反射矩阵，Householder变换矩阵

设$w\in R^n$满足$||w||_2=1$，定义$H\in\mathbb{R}^{n\times n}$为$H=I-2ww^T$则称H为Householder变换矩阵，也叫做初等反射矩阵或者镜像变换

性质：

  • 对称性：$H^T=H$
  • 正交性：$H^TH=I$
  • 对合性：$H^2=I$
  • 反射性：对任意的$x\in R^n$，$Hx$是$x$关于$w$的垂直超平面的镜像反射

证见4.11 8:00

  • Householder矩阵的行列式是-1
  • 反射矩阵乘以反射矩阵会得到旋转矩阵
  • 旋转矩阵乘以反射矩阵会得到反射矩阵

Haar矩阵/哈尔小波变换

Haar矩阵是哈尔小波变换的离散情形。Haar矩阵中的每个元素都是0，+1或者-1，并且任意两行都是正交的。n=2时，

Haar矩阵的构造：4.12 4;00

Hadamard矩阵

$H_n\in \mathbb{R}^{n\times n}$称为Hadamard矩阵，若其所有元素取+1或-1，且满足$H_nH_n^T=H_n^TH_n=nI_n$，其中$I_n$是n阶单位矩阵

  • 用-1乘Hadamard矩阵的任意行或者任意列得到的结果仍然是Hadamard矩阵
  • 称第一行和第一列所有元素都是+1的Hadamard矩阵为规范化的Hadamard矩阵
  • $\frac{1}{\sqrt n}$是标准正交矩阵

定理2：规范化的Hadamard矩阵具有构造公式

证见4.12 10:00

若$H$作为线性空间的一组基，由于Hadamard矩阵是正交矩阵而且元素只取+1或-1，我们计算一个向量在这组基下的坐标只需要加减法，并将最后的结果同一除以H的阶数。因此计算变换后的向量只需要加减法而不需要乘法。

克罗内克积

设$A=(a_{ik})_{m\times n},B=(b_{rl})_{r\times s}$，是域$\mathbb{K}$中的两个矩阵，则矩阵$C=(c_{\lambda\mu})_{mr\times ns}$称为A与B的克罗内克积，记作$C=A\otimes B$

克罗内克积的性质：

  • $A\otimes (B_1+B_2)=A\otimes B_1+A\otimes B_2$
  • $(A_1+A_2)\otimes B=A_1\otimes B + A_2\otimes B$
  • $A\otimes (B\otimes C)=(A\otimes B)\otimes C$
  • $(A\otimes B)^T=A^T\otimes b^T$
  • $(A\otimes B)(C\otimes D)=(AC)\otimes (BD)$

利用克罗内克积，我们可以利用n阶Haar矩阵构造2n阶的Haar矩阵：

也可以利用克罗内克积构造$2^k$阶的Hadamard矩阵：$H_{2^k}=H_2^{\otimes k}$

共轭转置

设矩阵$A=(a_{ij})_{n\times n}\in\mathbb{C}^{n\times n}$，则矩阵A的共轭转置矩阵为$A^H=(\overline{A}^T)=(\overline{A})^T=(\overline{a_{ji}})_{n\times n}$

  • 性质 4.12 26:00

傅里叶矩阵

image-20210330143458078