7.1.1.1 Vectors#

一个向量 $\boldsymbol{x} \in \mathbb{R}^n$ 是 n 个数值的列表，通常写成列向量的形式：

全 1 向量：$\boldsymbol{1}$；全 0 向量：$\boldsymbol{0}$

单位向量 $\boldsymbol{e}_i$ 是除了位置 i 为 1 之外全为 0 的向量，也称为 one-hot vector：

7.1.1.2 Matrices#

矩阵转置的性质：

如果一个方阵满足 $\mathrm A = \mathrm A^\mathsf T$​，称其为对称矩阵，我们记所有大小为 n 的对称矩阵为：$\mathbb S^n$.

7.1.1.3 Tensors#

张量是机器学习术语，是 2d 数组推广到多于 2d 的情况。

7.1.2.1 向量相加和缩放#

我们可以把一个向量 $x \in \mathbb{R}^n$ 看成 n 维欧几里得空间里的一个点。一个向量空间是一系列向量的集合，这些向量可以互相相加或乘以标量来缩放。

7.1.2.2 线性无关，张成和基向量#

如果一组向量 $\{x_1,x_2,\dots,x_n\}$ 中没有向量可以被表示成其余向量的线性组合，那么这组向量被认为线性无关。反之，如果一个向量可以被表示为其余向量的线性组合，这组向量就是线性相关的。

一组向量 $\{x_1,x_2,\dots,x_n\}$ 的张成 span指的是由 $\{x_1,x_2,\dots,x_n\}$ 的所有线性组合组成的集合。

当 $\{x_1,x_2,\dots,x_n\}$ 是一组线性无关向量且 $x_i \in \mathbb{R}^n$，则 $\mathrm {span}(\{ x_1,\dots,x_n \})=\mathbb{R}^n$. 换句话说，任何向量 $v \in \mathbb{R}^n$ 可以被写成 $\{x_1,x_2,\dots,x_n\}$ 的线性组合。

一个基 basis $\mathcal B$ 是一组张成整个空间的线性无关向量，即 $\mathrm {span}(\mathcal B)=\mathbb{R}^n$.

7.1.2.3 线性映射与矩阵#

一个线性映射或线性变换指的是任何满足下面条件的函数 $f:\mathcal V \rightarrow \mathcal W$：

$f(v+w)=f(v)+f(w)$，$f(a\ \boldsymbol v)=af(\boldsymbol v)$ for all $v,w \in \mathcal V$

假设 $\mathcal V = \mathbb{R}^n,\ \mathcal W = \mathbb{R}^m$，我们可以按如下方式对任意 $x\in \mathbb{R}^n$ 计算 $y=f(x)\in \mathbb{R}^m$ :

上式可以简化为用一个 $m\times n$ 的矩阵 $\mathrm A$ 乘以向量 $x$：

具体见 Section 7.2.

如果函数可逆：

具体见 Section 7.3.

7.1.2.4 矩阵的值域空间和零值空间#

假设我们把一个矩阵 $\mathrm A \in \mathbb{R}^{m\times n}$ 看成 $\mathbb{R}^n$ 空间的 m 个向量，矩阵的值域空间 range（又称 column space）为 $\mathrm A$ 的列向量的张成，即：

range 可以理解为可以由矩阵 $\mathrm A$ 生成的所有向量的集合；它是 $\mathbb{R}^m$ 的子空间，维数由 $\mathrm A$ 的秩决定（见 Section 7.1.4.3）

零值空间 nullspace 是所有乘以矩阵 $\mathrm A$ 后为 0 的向量集合，即：

$\mathrm A$ 的行的张成是 $\mathrm A$ 的 nullspace 的补集。

上图展示了矩阵 range 和 nullspace 的直观表示。下面我们会在 Section 7.5.4 讨论如何计算这两个空间。

7.1.2.5 线性投影#

一个向量 $y \in \mathbb{R}^m$ 的在 $\mathrm{span}(\{x_1,\dots,x_n\}),\ x_i\in \mathbb{R}^m$ 上的投影是指在 $\mathrm{span}(\{x_1,\dots,x_n\})$ 空间上且和 $y$ 的欧式距离 $||v-y||_2$ 尽可能接近的向量。我们记为 $\mathrm{Proj}(y;\{x_1,\dots,x_n\})$，定义如下：

给定一个满秩矩阵 $\mathrm A \in \mathbb{R}^{m\times n}$ 且 $m\geq n$，我们可以定义向量 $y\in \mathbb{R}^m$ 在 $\mathrm A$ 的 range 上的投影为：

这个公式和 Section 11.2.2.2 的 normal equation 是一致的。

7.1.3.1 向量范数#

向量的范数 $||x||$ 不正规地说就是向量长度的一种测量。正式的说法是，一个范数是满足下列4个条件的任意函数 $f:\mathbb{R}^n\rightarrow \mathbb{R}$：

• Non-negativity：对所有 $x\in \mathbb{R}^n,\ f(x)\geq0$
• Definiteness：$f(x)=0\ \mathrm{if\ and\ only\ if\ }x=0$
• Absolute value homogeneity：对所有 $x\in \mathbb{R}^n,\ t\in \mathbb{R},\ f(tx)=|t|f(x)$
• Triangle inequality：：对所有 $x,y\in \mathbb{R}^n,\ f(x+y)\leq f(x)+f(y)$

下面是常用范数：

• p-norm：$||x||_p=(\sum_{i=1}^n|x_i|^p)^{1/p},\ \mathrm{for\ } p\geq1$
• 2-norm：$||x||_2=\sqrt{\sum_{i=1}^n x_i^2}$，又称欧式范数。注意性质：$||x||^2_2=x^\mathsf T x$
• 1-norm：$||x||_1=\sum_{i=1}^n |x_i|$
• Max-norm：$||x||_{\infty}=\mathrm{max}_i|x_i|$
• 0-norm：$||x||_0 = \sum_{i=1}^n\mathbb I(|x_i|>0)$. 这是伪范数，因为它不满足同质性，它指的是 $x$ 中的非零元素的数量。如果我们定义 $0^0 =0$，我们可以把它写成 $||x||_0 = \sum_{i=1}^nx_i^0$.

7.1.3.2 矩阵范数#

由于矩阵并没有长度的概念，因此将矩阵范数看作是对矩阵长度的度量并不可行。

假设我们认为一个矩阵 $\mathrm A \in \mathbb{R}^{m\times n}$ 定义了一个线性函数 $f(x)=\mathrm A x$ 我们定义 $\mathrm A$ 的 诱导范数 induced norm 为对输入的最大放大倍数：

通常令 $p=2$，此时：

其中 $\sigma_i$ 是 $\mathrm A$ 的奇异值。

核范数，又叫迹范数，定义为：

其中 $\sqrt{\mathrm A^\mathsf T\mathrm A}$ 是矩阵平方根。由于奇异值总是非负的，我们有：

使用该范数作为正则项会鼓励许多奇异值变为0，进而导致一个低秩矩阵。更一般的情况下，我们可以定义 Schatten p-norm 为：

如果我们将一个矩阵当成一个向量，我们就可以用向量范数定义矩阵范数，$||\mathrm A||=||\mathrm{vec(A)}||$. 如果向量范数是 2-norm，对应的矩阵范数称作 Frobenius norm：

如果 $\mathrm A$ 的计算代价太大，但 $\mathrm A v$ 的代价很小（对一个随机向量 $v$)，我们可以用 Hutchinson trace estimator 对 Frobenius norm 做一个随机近似：

其中 $v \sim \mathcal N (\boldsymbol{0},\mathrm{I})$.

7.1.4.1 方阵的迹 trace#

方阵 $\mathrm A\in \mathbb{R}^{n\times n}$ 的迹，记为 $\mathrm{tr(A)}$，定义为矩阵对角线元素之和：

迹拥有以下性质，令 $c\in \mathbb{R}$ 为一个标量，$\mathrm{A,B}\in \mathbb{R}^{n\times n}$ 均为方阵吗，$\lambda_i$ 为 $\mathrm A$ 的特征值：

重要性质：cyclic permutation property，对 $\mathrm {ABC}$ 为方阵的 $\mathrm {A,B,C}$ 有：

由此我们还可以推导出迹技巧，可以将标量内积 $x^\mathsf T \mathrm A x$ 重写为：

有些情况下，直接计算矩阵 $\mathrm A$ 的代价高昂，但计算矩阵向量乘积 $\mathrm A v$ 的代价较低。假设 $v$ 是一个随机向量且 $\mathbb E [vv^\mathsf T] = \mathrm I$. 在这种情况下，我们可以用下列关系对 $\mathrm {tr(A)}$ 进行蒙特卡洛近似：

这被称为 Hutchinson trace estimator.

7.1.4.2 方阵的行列式#

方阵的行列式 determinant 记为 $\rm \det(A)$ or $|\rm A|$ 是对一个单位体积在线性变换后的变化程度的度量。（更正式的定义较为复杂，这里不需要讨论）

行列式的性质，其中 $\mathrm {A,B} \in \mathbb{R}^{n\times n}$：

对于一个正定矩阵 $\mathrm A$，我们可以写成如下形式：$\mathrm {A =LL^\mathsf T}$，其中 $\mathrm L$ 是下三角 Cholesky 分解。此时可得：

7.1.4.3 矩阵的秩#

矩阵 $\mathrm A$ 的列矩 column rank 是它的列张成的空间的维度，行距 row rank 是它的行张成的空间的维度。线性代数的一个基本事实：对任意矩阵 $\mathrm A$，$\rm columnrank(A)=rowrank(A)$，因此这个量就简化为 $\rm A$ 的秩，记为 $\rm rank(A)$. 秩的基本性质如下：

• For $\mathrm A \in \mathbb{R}^{m\times n},\ \mathrm{rank(A)}\leq\min(m,n)$. 如果 $\mathrm{rank(A)}=\min(m,n)$，则 $\mathrm A$ 是满秩 full rank 的，否则就是欠秩 rank deficient 的。
• For $\mathrm A \in \mathbb{R}^{m\times n},\ \mathrm{rank(A)}=\mathrm{rank(A^\mathsf T)}=\mathrm{rank(A^\mathsf T A)}=\mathrm{rank(AA^\mathsf T)}$.
• For $\mathrm A \in \mathbb{R}^{m\times n},\ \mathrm B\in \mathbb{R}^{n\times p},\ \rm rank(AB)\leq\min(rank(A),rank(B))$.
• For $\mathrm {A,B} \in \mathbb{R}^{m\times n},\ \rm rank(A+B) \leq rank(A) + rank(B)$.

另外可以证明方阵当且仅当是满秩时是可逆的。

7.1.4.4 条件数#

矩阵的条件数描述的是矩阵计算中的的数值稳定性，定义如下：

其中 $||\rm A||$ 是矩阵的范数。我们可以证明 $\kappa(\mathrm A)\geq 1$. (条件数依赖于范数的选取，我们默认用 $\ell_2$ 范数)

• 如果 $\kappa(\mathrm A)$ 较小（close to 1），则我们称 $\mathrm A$ 是 well-conditioned.
• 如果 $\kappa(\mathrm A)$ 较大，则我们称 $\mathrm A$ 是 ill-conditioned.

较大的条件数意味着 $\mathrm A$ 是接近奇异的，这是一个对奇异性接近度的度量，且是一个比行列式的大小更好的度量。例如，假设 $\mathrm A =0.1\mathrm I_{100\times 100}$，则 $\rm det(A)=10^{-100}$，意味着 $\rm A$ 接近奇异矩阵，但是 $\kappa(\mathrm A)=1$，表示 $\rm A$ 是 well-conditioned，实际上 $\mathrm A x$ 仅仅将输入 $x$ 缩放为 0.1 倍。

当使用 $\ell_2$ norm 时，条件数等于最大和最小的奇异值的比值，而奇异值是特征值的平方根：

我们可以进一步考虑一个二次目标函数 $f(x)=x^\mathsf T \mathrm A x$，我们可以画出这个函数的水平线，它是椭圆形的，见 Section 7.4.4. 当我们增加 $\rm A$ 的条件数，椭圆在某个方向上变得越来越狭长，像函数空间的一个狭窄山谷。如果 $\kappa =1$，也就是可以取到的最小值，水平线会变成圆形的。

7.1.5.1 对角矩阵#

非对角线元素均为0

单位矩阵 identity matrix，记为 $\mathrm I \in \mathbb{R}^{n\times n}$，是对角元素均为1，其他元素均为0的方阵，$\mathrm I = \mathrm{diag}(1,1,\dots,1)$. 它拥有性质：对于所有 $\mathrm A \in \mathbb{R}^{n\times n}$，$\rm AI=A=IA$.

7.1.5.2 Triangular matirces#

上三角和下三角矩阵。它的一个常用性质是对角元素即为特征值，因此行列式的值就是对角元素的乘积。

7.1.5.3 正定矩阵#

给定一个方阵 $\mathrm A \in \mathbb{R}^{n\times n}$ 和一个向量 $x \in \mathbb{R}^n$，标量 $x^\mathsf T \mathrm A x$ 被称为二次形。

注意：

所以我们常常隐式地假设二次型的矩阵是对称的。

我们给出如下定义：

• 一个对称矩阵 $\mathrm A \in \mathbb S^n$ 是正定矩阵 iff 对于所有非零向量 $x \in \mathbb{R}^n$，均有 $x^\mathsf T \mathrm A x>0$，记为 $\mathrm A \succ 0$ or just $\mathrm A >0$. 如果存在 $x^\mathsf T \mathrm A x = 0$，我们说这个矩阵是半正定的。我们记所有的正定矩阵为 $\mathbb{S}_{++}^n$.
• 一个对称矩阵 $\mathrm A \in \mathbb S^n$ 是负定矩阵 iff 对于所有非零向量 $x \in \mathbb{R}^n$，均有 $x^\mathsf T \mathrm A x<0$，记为 $\mathrm A \prec 0$ or just $\mathrm A < 0$. 如果存在 $x^\mathsf T \mathrm A x = 0$，我们说这个矩阵是半负定的。
• 一个对称矩阵 $\mathrm A \in \mathbb S^n$ 是不定矩阵 if 它既不是半正定又不是半负定矩阵。

正定和负定矩阵总是可逆的。在 Section 7.4.3.1 中，我们会证明对称矩阵是正定矩阵 iff 它的所有特征值都是正的。

一个对称矩阵为正定矩阵的充分条件是对角主导：

2d情况下，任何 $2\times 2$ 矩阵 $\dbinom{a\quad b}{b\quad d}$ 是正定矩阵 iff $a>0,d>0,ad-b^2>0$.

最后，有一种正定矩阵很常见，需要额外注意。对任意矩阵 $\mathrm A \in \mathbb{R}^{m\times n}$（不需要对称或方阵），Gram matrix $G = \mathrm{A^\mathsf T A}$ 总是半正定的，如果 $m\geq n$ （这里为了方便假设 $\mathrm A$ 是满秩矩阵），那么矩阵 $G = \mathrm{A^\mathsf T A}$ 是正定矩阵。

7.1.5.4 正交矩阵#

两向量 $x,y \in \mathbb{R}^n$ 如果 $x^\mathsf T y =0$ 则称两向量正交。一个向量 $x\in \mathbb{R}^n$ 如果 $||x||_2=1$ 则该向量是标准化的。一组向量相互正交且标准化被称为标准正交。一个方阵 $\mathrm U \in \mathbb{R}^{n\times n}$ 如果所有列均标准正交则这个矩阵被称为正交矩阵。

$\mathrm U$ 为正交矩阵当且仅当：$\mathrm {U^\mathsf T U=I=UU^\mathsf T}$.

换句话说，正交矩阵的逆即为转置。

正交矩阵的一个例子是旋转矩阵，例如，一个 3d 空间关于 z 轴旋转 $\alpha$ 度的矩阵为：

正交矩阵的一个良好性质是一个向量乘以正交矩阵不会改变非零向量的欧式范数，$||\mathrm{U}x||_2=||x||_2$

相似的是，我们可以发现两向量的夹角在正交矩阵变换后也得已保存：

so

总的来说，正交矩阵变换是旋转和反射变换的扩展，都保存夹角和长度。

注意有一个 Gram Schmidt orthogonalization 的方法可以让任何方阵正交化，但这里我们不讨论。

7.2.4.1 切片求和#

假设 $\mathrm X$ 是一个 $N \times D$ 的矩阵，我们可以通过前乘一个 $1\times N$ 的全1矩阵实现按行求和：

因此，数据向量的均值可以表示为：

同理，后乘一个 $D\times 1$ 的全1矩阵实现按列求和：

由此我们可以对一个矩阵的所有元素实现求和：

所有元素的均值为：

7.2.4.2 对矩阵按行或列 scaling#

我们经常想要对数据矩阵按行或列进行标准化。我们现在展示怎样用矩阵记号进行表示

对数据矩阵 $\mathrm X$ 前乘一个对角矩阵 $\mathrm S= \mathrm {diag} (\boldsymbol s)$，其中 $\boldsymbol s$ 是一个 长度为 N 的向量，然后我们就对 $\mathrm X$ 按 $\boldsymbol s$ 中的 scale factor 进行了按行缩放：

同理，后乘一个对角矩阵等价于按列缩放：

由此我们可以把标准化操作写成矩阵形式：

其中 $\mu = \bar x$ 是经验均值，且 $\sigma$ 是经验标准差向量。

7.2.4.3 Sum of squares and scatter matrix#

Sum of squares matrix 是一个 $D\times D$ 的矩阵，定义为：

Scatter matrix 是一个 $D \times D$ 矩阵，定义为：

易见 scatter matrix 是中心化后数据的 sum of squares matrix，我们也可以用矩阵形式来表示中心化后的数据矩阵，即原矩阵每列减去每列均值：

$\mathrm C_N$ 是 centering matrix，由此 scatter matrix 可以用如下方式计算：

这里用到了 $\mathrm C_N$ 是对称且幂等的性质，即 $\mathrm C_N^k = \mathrm C_N\ (k=1,2,...)$. （可以理解为我们只要减掉一次均值，再次减去均值就不会起任何作用了）。

7.2.4.4 Gram matrix#

Gram matrix 是一个 $N \times N$ 的内积矩阵：

7.2.4.5 Distance matrix#

令 $\mathrm X$ 为 $N_x \times D$ 的数据矩阵，$\mathrm Y$ 为另一个 $N_y \times D$ 的数据矩阵。我们可以计算他们之间的平方距离

7.2.5 Kronecker products#

如果 $\mathrm A$ 是一个 $m\times n$ 的矩阵且 $\mathrm B$ 是一个 $p\times q$ 的矩阵，那么 Kronecker product $\mathrm A \otimes \mathrm B$ 是一个 $mp\times nq$ 的块矩阵：

7.2.6 Einstein summation#