从题目出发复习数据科学数学基础

导论

求卷积

求TF-IDF

考虑结构风险的损失函数

线性代数

求矩阵的逆

求解线性方程组

求线性组合

求特征值与特征向量

求新基坐标

求二次型的标准型

判断正定矩阵

标准正交化

[a,b]即a与b的内积之意

度量与投影

范数

范数的定义

设 $\mathbb V$ 是数域上 $\mathbb K$ 的 n 维线性空间，那么函数 $||\cdot||: \mathbb V\rightarrow \mathbb R,x\rightarrow ||x||$ 就是将 $x$ 映射为它的长度 $||x||\in \mathbb R$ ，并且满足非负性、齐次性和三角不等式。

我们称$||x||$ 是向量 x 的向量函数，称定义了范数的线性空间 $\mathbb V$ 为赋范线性空间。

几种常用的向量范数

$l_p$ 范数

对于任意 $x = (x1,x_2,\cdots,x_n)\in \mathbb R^n$ ，由 $||x||_p = (\sum{i=1}^n |x_i|^p)\frac{1}{p}, 1\leq p< \infty$

定义的 $||\cdot||_p$ 是 $\mathbb R^n$ 上的向量范数，称为 $p$ 范数或者 $l_p$范数

当 p = 1时，得到 1范数 或者 $l1$ 范数，也称 Manhattan 范数 ： $||x||_1 =\sum{i = 1}^n |x_i|$
当 p = 2时，得到 2范数 或者 $l2$ 范数，也称为欧几里得范数 : $||x||_2 = \sqrt{\sum{i=1}^n x_i^2}$

$l_\infty $ 范数

当p取无线大的时候，是否存在这种范数呢？

对 $\forall x=(x1,x_2,\cdots,x_n)\in \mathbb R^2$ ，由 $||x||\infty = \lim \limits_{p\rightarrow\infty} ||x||_p$

也就是$||x||\infty = \max{i=1,\cdots,n}|x_i|$

定义 $||\cdot||\infty$ 是 $\mathbb R^n$ 上的向量范数，称为 $\infty$ 范数或者 $l\infty$ 范数。

非向量范数

当 $0<p<1$ 时，由 $||x||p = (\sum{i=1}^n|x_i|^p)$ 定义的 $||\cdot||_P $ 不是 $\mathbb R$ 上的向量范数

举一个特例就能证明。

基数函数 $l_0$ 范数

向量 $x$ 的基数函数定义为 $x$ 即 $card(x) = \sum_{i=1}^m \mathcal I(x_i \neq 0)$

其中， $\mathcal I(x_i\neq 0)= \begin{cases}{1},x_i\neq 0\ 0, {x_i = 0}\end{cases}$

基数函数也被称为$l_0$ 范数，但是它并不满足范数定义的条件

几种常见的矩阵范数

矩阵1范数(列模)

矩阵的每一列上的元素绝对值先求和，再从中取个最大的，(列和最大)

矩阵2范数(谱模)

$||A||2 = \max\limits{X\neq0} \frac{||AX||2}{||X||_2}=\sqrt{\lambda{max}(A^TA)} =\sqrt{\max\limits_{1\leq i\leq n}|\lambda_i|}$ ,其中 $\lambda_i$为 $A^TA$ 的特征值。

也就是说求矩阵 $A^TA$ 的最大特征值的开方

矩阵的无穷范数(行模)

矩阵的每一行上的元素绝对值先求和，再从中取个最大的，（行和最大）

求范数、无穷范数

例题

求向量 $x=(-1,2,4)^T$ 的 0，1，2 和 $\infty$ 范数

$||x||_0 = 3$ 非0元素的个数

$||x||_1= |-1|+2+4 = 7$

$||x||_2 = \sqrt{|-1|^2+2^2+4^2} = \sqrt{21}$

$||x||_\infty = max {|-1|,2,4}$

证明某函数为向量范数

思路：

满足三个性质，即非负性、齐次性以及三角不等式

注意了，当且仅当$x_i$ 全是0的时候，范数才等于零；如果$x_i$ 不为零式子却是0，那么这就不满足非负性

例题

1

对任意的 $x = (x_1,x_2,x_3)^T\in \mathbb C^3$ ，试问如下实值函数是否构成向量范数?

$|x_1|+|2x_2+x_3|$
$|x_1|+|2x_2|-5|x_3| $

要让函数构成向量范数，必须满足三个性质，即非负性、齐次性以及三角不等式

对于1

非负性，易证
齐次性，令 $c\in \mathbb C, |cx_1|+|2cx_2+cx_3|=|c|(|x_1|+|2x_2+x_3|)$
三角不等式：$x = (x_1,x_2,x_3)^T,y = (y_1,y_2,y_2)^T \in \mathbb C^3$ , 则 $|x_1+y_1|+|2(x_2+y_2)+(x_3+y_3)|\leq |x_1|+|2x_2+x_3|+|y_1| + |2y_2+y_3|$ 即 x 的范式加上 y 的范式

对于2

取 $x=(0,0,1)$ 则 $|0|+|2\times 0|-5|1| = -5 < 0 $ 不满足非负性，所以2不是范范数

证明某函数是内积

标准内积的定义：

n维实向量空间 $\mathbb R^n$ 的标准内积(点积)是两个向量的对应元素乘积之和。

即： $ = x^Ty = \sum_{i=1}^n x_iy_i$ 通常我们指内积都是这种标准内积

现在我们引申出内积的定义。设$\mathbb V$是数域上$\mathbb K$ 的 n 维线性空间，函数$<\cdot,\cdot>:\mathbb V\times \mathbb V\rightarrow \mathbb R $它把向量$x,y\in \mathbb V $ 映射为一实数 $\in \mathbb R$ 并满足以下几个条件，其中， $\forall \lambda \in \mathbb R$和向量 $x,y,z\in \mathbb V$ ,满足

非负性：$ \geq 0$ 当且仅当x=0的时候，$ =0$
对称性：$=$
齐次性：$<\lambda x,y> = \lambda$
线性性：$=+$

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

四个基本子空间的计算

列空间 $Col(A)$

行空间是其列向量 ${a_1,a_2\cdots,a_n}$ 的所有线性组合的集合，它是 $\mathbb R^m$ 的一个子空间，用符号 $Col(A)$ 表示。有：

$Col(A)={y\in \mathbb R^m|y=\sum_{j=1}^n\alpha_ja_j,\alpha_j\in\mathbb R }=span{\alpha_1,\alpha_2,\cdots,\alpha_n }$

例题：

现有矩阵：$\begin{pmatrix} 1 & -1 & 0 \ 2 & 4 & 1 \ 4 & 2 & 1 \end{pmatrix}$ 求其列空间

矩阵列变换 ： $\begin{pmatrix} 1 & -1 & 0 \ 2 & 4 & 1 \ 4 & 2 & 1 \end{pmatrix}=\begin{pmatrix} 1 & 0 & 0 \ 2 & 1 & 0 \ 4 & 1 & 0 \end{pmatrix}$
列公式 : $Col(A)=\alpha_1(1,2,4)^T+\alpha_2(0,1,1)^T+\alpha_3(0,0,0)^T$
写成span形式： $=span{(1,2,4)^T,(0,1,1)^T}$

行空间$ Row(A)=Col(A^T)$

矩阵行变换: $\begin{pmatrix} 1 & -1 & 0 \ 2 & 4 & 1 \ 4 & 2 & 1 \end{pmatrix}=\begin{pmatrix} 1 & -1 & 0 \ 0 & 6 & 1 \ 0 & 0 & 0 \end{pmatrix}$
列公式： $Col(A^T)=\alpha_1(1,-1,0)^T+\alpha_2(0,6,1)^T+\alpha_3(0,0,0)^T$
写成span形式： $span{(1,-1,0)^T,(0,6,1)^T}$

零空间 $Null(A)$

零空间是所有满足齐次线性方程组$Ax = 0$ 的解向量集合，它是$\mathbb R^n$ 的一个子空间，用符号

$Null (A) $表示，即有 $Null(A)={x\in \mathbb R^n|Ax=0}$

求解线性方程组 $Ax=0$ ，$\begin{pmatrix} 1 & -1 & 0 \ 2 & 4 & 1 \ 4 & 2 & 1 \end{pmatrix}x=\begin{pmatrix} 1 & -1 & 0 \ 0 & 6 & 1 \ 0 & 0 & 0 \end{pmatrix}x =0$
解得$(x_1,x_2,x_3)^T =k (1,1,-6)^T$
写成span形式： $=span{(1,1,-6)^T}$

左零空间 $Null(A^T)$

左零空间是所有满足齐次线性方程组$A^Ty = 0$ 的解向量集合，它是$\mathbb R^m$ 的一个子空间，用符号

$Null (A^T) $表示，即有 $Null(A^T)={y\in \mathbb R^n|A^Ty=0}$

求解线性方程组 $A^Ty =\begin{pmatrix} 1 & 2 & 4 \ -1 & 4 & 2 \ 0 & 1 & 1 \end{pmatrix}y=0$
解得$(x_1,x_2,x_3)^T = k(2,1,-1)^T$
写成span形式 $span{(2,1,-1)^T}$

求正交投影

设 $\mathbb V$ 是一向量空间，$\mathbb W\subseteq \mathbb V$ 是$\mathbb V$ 的一个子空间。如果线性映射$\pi:\mathbb V\rightarrow \mathbb W$ 满足 $\pi^2 =\pi\circ \pi = \pi$ 则称 $\pi$为投影。

设$\pi$对应的矩阵$P{\pi}$ ，显然$P{\pi}$ 满足 $P^2{\pi}=P{\pi}$ ，称$P_\pi$为投影矩阵。

到一维子空间

设基底矩阵$B = [b]$，也就是这组基中仅有一个向量。

设$\mathbb R^n$ 的子空间$\mathbb W = Col(B)$, 我们想寻找一个点$\pi_\mathbb W(x)\in\mathbb W $最接近x。

因为$\pi_\mathbb W(x)\in \mathbb W$，又 $W = Col (B) = span{b}$

所以$\pi_\mathbb W(x)=\lambda b,\lambda\in \mathbb R$

接下来，我们将逐步确定$\lambda,\pi\mathbb W(x)$和投影矩阵$P\pi$

确定 $\lambda$

确定 $\pi_\mathbb W(x)$

确定 $P_\pi$

求得投影：

到一般子空间

设$B = (b1,\cdots, b_n)$ 是子空间$\mathbb U$ 的一个有序基底。任何$\mathbb U$ 上的投影$\pi\mathbb U(x)$ 必须是U 中的一

个元素。故有$\pi\mathbb U(x) = \sum{i=1}^n\lambda_ib_i$

确定 $\lambda_1,\cdots,\lambda_n$

确定 $\pi_\mathbb W(x)$

投影矩阵$P_\pi$

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

例题：

到仿射空间

给定一个仿射空间 $\mathbb L = x0+\mathbb U$ 其中，$b_1,b_2$是$\mathbb U$ 的基向量，为了确定 x在$\mathbb L$ 上的正交投影 $\pi\mathbb L(x)$

我们将问题转化为我们知道如何解决的问题：投影到向量子空间上。为此，我们从x和$\mathbb L$ 中减去支撑点 $x_0$ ，所以 $\mathbb L-x_0=\mathbb U$恰好是向量子空间 $\mathbb U$

现在，我们前面讨论过的在子空间上的投影，获得投影$\pi_\mathbb U(x-x_0)$ 。最后我们通过添加$x_0$将该投影转换回 $\mathbb L$ ，这样我们就可以得到仿射空间 $\mathbb L$上的正交投影：

$\pi\mathbb L(x) = x_0+\pi\mathbb U(x-x_0)$

例题：

求向量 $(1,1,1)^T$ 投影到仿射空间，$span{(1,-1,1)^T,(1,1,0)^T}+(1,2,1)^T$ 的正交投影

首先我要求 $\pi\mathbb U(x-x_0)=\pi\mathbb U(0,-1,0)$

令 $B=\begin{pmatrix} 1 & 1 \ -1 & 1 \ 1 & 0 \end{pmatrix}$ , $B^TB=\begin{pmatrix} 3&0\0&2\end{pmatrix}$

$B^T(x-x_0)=\begin{pmatrix} 1&-1&1\1&1&0\end{pmatrix}\begin{pmatrix} 0&-1&0\end{pmatrix}^T =(1~~-1)^T$

解方程组 $B^TB\lambda=B^Tx \Rightarrow \begin{pmatrix} 3&0\0&2\end{pmatrix}\lambda = \begin{pmatrix} 1\-1\end{pmatrix}$ 解得 $\lambda=\begin{pmatrix} \frac{1}{3}\-\frac{1}{2}\end{pmatrix}$

最后我们求 $\pi_\mathbb W(x-x_0)=B\lambda = \begin{pmatrix} -\frac{1}{6}\-\frac{5}{6}\\frac{1}{3}\end{pmatrix}$

$\pi\mathbb L(x)=x_0+\pi\mathbb W(x-x_0)=\begin{pmatrix} \frac{5}{6}\\frac{7}{6}\\frac{4}{3}\end{pmatrix}$

线代基础

矩阵分解

求张成的子空间

设 $a1,a_2,\cdots,a_r$ 是$\mathbb V$ 的一组向量，则这组向量所有可能的线性组合 $\sum{k=1}^r\lambda_ka_k$ 所成的集合是$\mathbb V$ 的一个子空间，称为由 $a_1,a_2,\cdots,a_r$ 张成的子空间，记作 $L(a_1,a_2,\cdots,a_r)$ 或者 $span(a_1,a_2,\cdots,a_r)$ 。 $(a_1,a_2,\cdots,a_r)$ 叫做$\mathbb V$ 的生成集。

换句话说，张成子空间就是由$x_1,x_2,…,x_r(r>0)$中极大线性无关组作为基向量所构成的空间。因为其余任何向量都可以被这个无关组所表示，满足空间中向量的无穷性。

比如求向量$(1,2,0)^T,(0,1,2)^T$ 张成的子空间

首先确定两者线性无关，因此二者张成的子空间为 $((1,2,0)^T,(0,1,2)^T)$

求正交补空间

设 $\mathbb S$ 和 $\mathbb T$ 是 $\mathbb R^n$ 的两个子空间。如果对于 $\forall v\in \mathbb S,\forall w\in \mathbb T$ 均有 $v^Tw = 0$ 我们说 $\mathbb S$垂直于 $\mathbb T$ 或者说子空间$\mathbb S$ 和子空间 $\mathbb T$ 是正交的。

相对于正交，正交补是两个子空间更强的一种关系

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

记作$\mathbb V^{\bot}$

已经知道了一个子空间，怎么求它的正交补呢？我们可以利用这个性质：

$Col(A^T)^\bot = Null(A) , Col(A)^\bot = Null(A^T)$

因此$A= ((1,2,0)^T,(0,1,2)^T)$ 的正交补就可以写作$ Null(A^T) = span{(4,-2,1)^T} $

LU 分解

判断是否能进行 LU 分解：若矩阵的一阶顺序主子式为0，那么就不能分解。

LU 分解指将$n\times n$ 的矩阵A分解成两个三角矩阵的乘积

其中， L 为 $n\times n$ 单位下三角矩阵(对角元素为1)，U 是 $n\times n$ 上三角矩阵。

从秩1分解的角度分析 $A=LU$ , 可以将 A 写成若干个秩1矩阵和的形式：

$A = l_1u_1+\cdots+l_ru_r = \sum_{i=1}^r l_iu_i$

其中r为矩阵A的秩，若A是满秩，则 $r=n$ 。 $l_i$ 是 $L$ 的第$i$列；$u_i$ 是 $U$ 的第$i$行。 $l_iu_i$ 都是秩为1的矩阵，并且这个矩阵的前 $i-1$行和前$i-1$列的元素都是0

求矩阵A

$A=\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 10 \end{pmatrix}$

的LU分解

我们要像剥洋葱一样一层一层地分解矩阵A，同时要记得 L 的对角线都是1

第一步

令 $u1$ 是 A 的第1行，$l_1$ 是A的第1列除以 $u{11}$ ,则：

$l_1u_1 =\begin{pmatrix} 1 \\ 4 \\ 7 \end{pmatrix}\begin{pmatrix} 1 & 2 & 3\end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 8 & 12 \\ 7 & 14 & 21 \end{pmatrix}\\~~\\ A-l_1u_1 = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 10 \end{pmatrix}-\begin{pmatrix} 1 & 2 & 3 \\ 4 & 8 & 12 \\ 7 & 14 & 21 \end{pmatrix} = \begin{pmatrix} 0 & 0 & 0 \\ 0 & -3 & -6 \\ 0 & -6 & -11 \end{pmatrix}$

第二步

令 $u2$ 是 $A-l_1 u_1$ 的第2行，$l_2$ 是 $A-l_1u_1$ 的第二列除以$u{22}$

$l_2u_2 =\begin{pmatrix} 0 \\ 1 \\ 2 \end{pmatrix}\begin{pmatrix} 0 & -3 & -6\end{pmatrix} = \begin{pmatrix} 0 & 0 & 0 \\ 0 & -3 & -6 \\ 0 & -6 & -12 \end{pmatrix}\\~~\\ A-l_1u_1-l_2u_2 = \begin{pmatrix} 0 & 0 & 0 \\ 0 & -3 & -6 \\ 0 & -6 & -11 \end{pmatrix}-\begin{pmatrix} 0 & 0 & 0 \\ 0 & -3 & -6 \\ 0 & -6 & -12 \end{pmatrix} = \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}$

第三步

令$u3$ 是$A-l_1u_1-l_2u_2$ 的第3行，$l_3$ 是 $A-l_1u_1-l_2u_2$ 的第3列除以$u{33}$ 即

$l_3 =\begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}, u_3 = \begin{pmatrix} 0 & 0 & 1 \end{pmatrix}$

第四步，我们要把$l_1,l_2,l_3$ 相加得到$L$ ,$u_1,u_2,u_3$ 相加得到$U$

$A = LU = \begin{pmatrix} 1 & 0 & 0 \\ 4 & 1 & 0 \\ 7 & 2 & 1 \end{pmatrix}\begin{pmatrix} 1 & 2 & 3 \\ 0 & -3 & -6 \\ 0 & 0 & 1 \end{pmatrix}$

Cholesky 分解

QR分解

奇异值分解

谱分解

方程求解问题，最小二乘

求解 $AA^T x = A^Tb \Rightarrow$ 方程组求解

QR 解法：

要求QR，为了凑分，我们只能先求正则化情况下的x，得到答案后，计算 R矩阵，令 $Rx =b^$ 然后装模做样的求出 $b^$, 其实只是我们反推得到的。

矩阵微分

求梯度：

首先，这让我们化简一下向量2-范数。$l_2 = \sqrt{\sum |x_i|^2}$ 那么对于这个矩阵，可以用 $\sqrt{(Ax+b-y)^T(Ax+b-y)}$ 来算

所以：

$f(A) = \frac{1}{2}(Ax+b-y)^T(Ax+b-y)$

由 $df = dTr(f) = Tr(df)$ 可得：

$df = dTr(\frac{1}{2}(Ax+b-y)^T(Ax+b-y))\\~\\ df = Tr(d(\frac12(Ax+b-y)^T(Ax+b-y)))$

我们知道这样一个公式： $df = Tr(A^Tdx)\Rightarrow \frac{\partial f}{\partial x}=(A^T)^T=A$

因此，我们如果要求 $\frac{\partial f}{\partial A}$, 也可以用这种方法

$df = Tr(\frac{1}{2}d(Ax)^T(Ax+b-y)+\frac12(Ax+b-y)^Td(Ax))\\~\\ As ~~~Tr(A+B)=Tr(A)+Tr(B)\\~\\ df = Tr(\frac{1}{2}d(Ax)^T(Ax+b-y))~~+~~Tr(\frac12(Ax+b-y)^Td(Ax))\\~\\$

因为我们知道$d(cA) = cd(A)$

所以前面这部分可以写成是：

$df = Tr(\frac{1}{2}x^Td(A)^T(Ax+b-y))~~+~~Tr(\frac12(Ax+b-y)^Txd(A))\\~\\$

又知道：$\frac{\partial}{\partial x^T}f = (\frac{\partial }{\partial x}f)^T$ ,所以这里 $x^T(Ax+b-y)$ 为f,

$df = Tr(\frac{1}{2}(x^T(Ax+b-y)d(A))^T)~~+~~Tr(\frac12(Ax+b-y)^Txd(A))\\~\\ df = Tr(\frac{1}{2}(Ax+b-y)^Txd(A))~~+~~Tr(\frac12(Ax+b-y)^Txd(A))\\~\\ df = Tr(x(Ax+b-y)^TdA)$

最后，我们求得：$df = (x(Ax+b-y)^T)^T=(Ax+b-y)x^T$