1. 向量基础

1.1 向量

向量可以被视为数字的集合(collection)，通常写为列排列

xix_i被称为向量x\mathbf{x}的第ii个元素(element)/条目(entry)/分量(component)，元素的数量为x\mathbf{x}的维度

向量中的元素为实数(real)时，i.e. xi∈Rx_i \in \mathbb{R}，向量为实数向量，i.e. x∈Rn\mathbf{x} \in \mathbb{R}^n；若向量中的元素为复数(complex)时，i.e. xi∈Cx_i \in \mathbb{C}，向量为复数向量，i.e. x∈Cn\mathbf{x} \in \mathbb{C}^n

当我们不在乎向量是行向量(row)还是列向量(column)时，可以直接使用x=(x1,x2⋯ ,xn)\mathbf{x}=(x_1,x_2 \cdots, x_n)来表示向量

1.2 向量空间

向量可以被视为空间中的点

向量空间(vector space),X\mathcal{X}是通过为向量配备加法和标量乘法的操作而获得的，最常见的向量空间为X=Rn\mathcal{X} = \mathbb{R}^n

如果V\mathcal{V}是向量空间X\mathcal{X}的一个非空子集，并且V\mathcal{V}在加法和标量乘法下是封闭的(closed)，那么V\mathcal{V}是X\mathcal{X}的子空间(subspace)。

加法和标量乘法下的封闭性可以表述为：对于任意标量α,β\alpha,\beta有

x,y∈V⇒αx+βy∈Vx,y \in \mathcal{V} \Rightarrow \alpha x + \beta y \in \mathcal{V}

子空间必须包含原点

线性组合(linear combination)的形式如下

α1x(1)+α2x(2)+α3x(3)+⋯αmx(m),αi∈R\alpha_1 \mathbf{x}^{(1)} + \alpha_2 \mathbf{x}^{(2)} + \alpha_3 \mathbf{x}^{(3)} + \cdots \alpha_m \mathbf{x}^{(m)}, \alpha_i \in \mathbb{R}

向量集合S\mathcal{S}中的向量组成的所有线性组合会形成一个子空间，称为由S\mathcal{S}生成的子空间，或者称为S\mathcal{S}的张成，记为span(S)span(\mathcal{S})

  1. 由单向量S={x(1)}\mathcal{S}=\{ x^{(1)} \}生成的子空间是一条过原点的直线
  2. 由不共线的两个向量S={x(1),x(2)}\mathcal{S}=\{ x^{(1)},x^{(2)} \}生成的子空间是一个过原点的平面

当两个子空间的交集只有零向量的时候，i.e. X∩Y=0\mathcal{X}\cap \mathcal{Y} = \mathbf{0}，那么这两个子空间的和称为直和(direct sum)，定义为X⊕Y\mathcal{X} \oplus \mathcal{Y}。子空间的和并非单纯的元素合并而是基合并后进行线性组合形成的子空间

如果向量集合中的任何一个向量都无法表示为其他向量的线性组合，那么这个集合是线性无关的(linearly independent)，充要条件为

∑i=1mαixi=0⟹α=0\sum_{i=1}^m\alpha_i \mathbf{x}_i = \mathbf{0}\Longrightarrow \alpha = 0

包含mm个元素的向量集合S={x1,⋯ ,xm}\mathcal{S} = \{\mathbf{x}_1, \cdots, \mathbf{x}_m \}，它可以生成一个子空间span(S)span(\mathcal{S})。假设最后一个元素可以写成集合中其他元素的线性组合，那么去掉这个元素后生成的子空间是一样的，i.e. span(S)=span(S∖xm)span(\mathcal{S}) = span(\mathcal{S} \setminus \mathbf{x}_m)。重复这个步骤直到集合中的向量都是线性无关的，得到的集合为B={x1,⋯ ,xd},d≤m\mathcal{B} = \{\mathbf{x}_1, \cdots , \mathbf{x}_d \}, d \le m，这样的集合称为span(S)span(\mathcal{S})的基(basis)，元素数量dd称为span(S)span(\mathcal{S})的维数(dimension)

一个子空间可以有无限个不同的基，但任何基中的元素数量是固定的，并且等于子空间的维度。如果我们得到了子空间的基，那么我们可以用基中元素的线性组合表达子空间中的所有向量。Rn\mathbb{R}^n中的标准基写为{e1,⋯ ,en}\{ \mathbf{e}_1, \cdots, \mathbf{e}_n \}，ei\mathbf{e}_i中第ii个元素为11其余全为00

仿射集(affine sets)被定义为子空间的平移

A={x∣x=v+y,v∈V}\mathcal{A} = \{ \mathbf{x} \mid \mathbf{x} = \mathbf{v} + \mathbf{y}, \mathbf{v} \in \mathcal{V} \}

其中y\mathbf{y}是给定的点，V\mathcal{V}是给定的子空间.仿射集必定经过y\mathbf{y}

一个直线可以由两个元素描述：一个是直线上的点和一个表示直线方向的向量

L={x∣x=x0+v}\mathcal{L} = \{ \mathbf{x} \mid \mathbf{x} = \mathbf{x}_0 + \mathbf{v} \}

2. 范数和内积

2.1 欧几里得长度和一般的LpL_p范数

向量的欧几里得长度是对所有元素的平方和取平方根，它代表了从原点到达点x\mathbf{x}的直线距离。当沿着正交网格从原点到达点x\mathbf{x}的时候，距离为向量所有元素的绝对值之和

由于向量空间中由不同的长度度量，由此产生了向量范数(norm)的概念

范数是一个具有特殊性质的实值函数，它将向量映射为一个实数∥x∥\lVert \mathbf{x} \rVert，它满足的特殊性质如下

∀x∈X,∥x∥≥0,and∥x∥=0 if and only if ∥x∥=0\forall \mathbf{x} \in \mathcal{X} ,\lVert \mathbf{x} \rVert \ge 0 ,and\lVert \mathbf{x} \rVert = 0 \text{ if and only if } \lVert \mathbf{x} \rVert = \mathbf{0}

∀x,y∈X,∥x+y∥≤∥x∥+∥y∥(triangle inequality)\forall \mathbf{x}, \mathbf{y} \in \mathcal{X} ,\lVert \mathbf{x}+\mathbf{y} \rVert \le \lVert \mathbf{x} \rVert + \lVert \mathbf{y} \rVert (\text{triangle inequality})

∀x∈X,∥αx∥=∣α∣∥x∥\forall \mathbf{x} \in \mathcal{X} ,\lVert \alpha \mathbf{x} \rVert = \lvert \alpha \rvert \lVert \mathbf{x} \rVert

LpL_p范数被定义为

∥x∥≔(∑k=1n∣xk∣p)1/p\lVert \mathbf{x} \rVert \coloneqq \left(\sum_{k=1}^n \lvert x_k \rvert ^p\right)^{1/p}

如果p=2p=2我们便得到了欧几里得长度

∥x∥2≔∑k=1nxk2\lVert \mathbf{x} \rVert_2 \coloneqq \sqrt{\sum_{k=1}^n x_k^2}

如果p=1p=1我们便得到了在正交网格中的长度

∥x∥1≔∑k=1n∣xk∣\lVert \mathbf{x} \rVert_1 \coloneqq \sum_{k=1}^n \lvert x_k \rvert

如果p=∞p=\infty我们便得到了最大绝对值范数

∥x∥∞≔max⁡k=1,…,n∣xk∣\lVert \mathbf{x} \rVert_\infty \coloneqq \max_{k=1,\dots,n} \lvert x_k \rvert

除了范数函数外，还有一些函数可以表示向量的大小，如基数函数(cardinality function)，表示非零元素的个数

card⁡(x)≔∑k=1nI(xk≠0),whereI(xk≠0)≔{1if xk≠00otherwise\operatorname{card}( \mathbf{x} ) \coloneqq \sum_{k=1}^n\mathbb{I}(x_k \neq 0),\quad\text{where}\quad\mathbb{I}(x_k \neq 0) \coloneqq \left\{ \begin{array} {ll}1 & \text{if }x_k \neq 0 \\ 0 & \text{otherwise} \end{array}\right.

向量的基数也经常被称为L0L_0范数，写为∥x∥0\lVert \mathbf{x} \rVert_0，但它并不是严格意义上的范数，因为它不满足范数的性质

单位LpL_p范数球(norm ball)是指由所有LpL_p范数小于等于11的向量组成的集合

Bp={x∣∥x∥p≤1}\mathcal{B}_p = \{ \mathbf{x} \mid \lVert \mathbf{x} \rVert _p \le 1 \}

2.11

L2L_2范数类似由于一个球，因此它是旋转不变的，这意味着一个固定长度的向量如果任意旋转，将保持相同的L2L_2范数

实数向量空间的内积(inner product)是一个实值函数，将两个向量映射为一个标量，记为⟨x,y⟩\langle \mathbf{x},\mathbf{y} \rangle，内积满足以下条件：for any x,y,z∈Xand scalar α\text{for any }\mathbf{x},\mathbf{y},\mathbf{z} \in \mathcal{X} \text{and scalar }\alpha

⟨x,y⟩≥0;⟨x,x⟩=0 if and only if x=0;⟨x+y,z⟩=⟨x,z⟩+⟨y,z⟩;⟨αx,y⟩=α⟨x,y⟩;⟨x,y⟩=⟨y,x⟩. \begin{aligned} & \langle \mathbf{x},\mathbf{y} \rangle \ge 0; \\ & \langle \mathbf{x},\mathbf{x} \rangle = 0 \text{ if and only if }\mathbf{x} = \mathbf{0}; \\ & \langle \mathbf{x} + \mathbf{y},\mathbf{z}\rangle = \langle \mathbf{x},\mathbf{z} \rangle + \langle \mathbf{y},\mathbf{z} \rangle; \\ & \langle \alpha\mathbf{x},\mathbf{y} \rangle = \alpha \langle \mathbf{x},\mathbf{y} \rangle; \\ & \langle \mathbf{x},\mathbf{y} \rangle= \langle \mathbf{y},\mathbf{x} \rangle. \end{aligned}

配备了内积操作的向量空间被称为内积空间(inner product space)

标准内积是两个向量的“行列”积

⟨x,y⟩=x⊤y=∑k=1nxkyk\langle \mathbf{x},\mathbf{y} \rangle = \mathbf{x} ^\top \mathbf{y} = \sum^n_{k=1} x_k y_k

除了标准内积，我们还可以定义其他内积，并且在矩阵空间中内积也有很好的定义

在内积空间中⟨x,x⟩\sqrt{\langle \mathbf{x},\mathbf{x} \rangle}是一个范数，经常被简写为∥x∥\lVert \mathbf{x} \rVert

∥x−y∥22=(x−y)⊤(x−y)=x⊤x+y⊤y−2x⊤y\lVert \mathbf{x} - \mathbf{y} \rVert^2_2 = \left( \mathbf{x} - \mathbf{y} \right)^\top \left( \mathbf{x} - \mathbf{y} \right) = \mathbf{x}^\top \mathbf{x} + \mathbf{y}^\top \mathbf{y} - 2 \mathbf{x}^\top \mathbf{y}

标准向量积和两个向量的夹角有关，定义θ\theta为0x\mathbf{0} \mathbf{x}和0y\mathbf{0} \mathbf{y}的夹角，通过几何关系可以得到

cos⁡θ=x⊤y∥x∥2∥y∥2\cos \theta = \frac{\mathbf{x} ^\top \mathbf{y}}{\lVert \mathbf{x} \rVert_2 \lVert \mathbf{y} \rVert_2}

当两个向量内积为00时说明两个线是正交的(orthogonal)；当θ\theta为0∘0^\circ或者±180∘\pm180^\circ时两直线平行(parallel)，这时标准内积的绝对值最大，为二者绝对值的乘积

通过推导可以得到x⊤y=∥x∥∥y∥cos⁡θ\mathbf{x} ^\top \mathbf{y}=\lVert \mathbf{x} \rVert \lVert \mathbf{y} \rVert \cos\theta，由于∣θ∣≤1\lvert \theta \rvert \le 1，因此可以得到柯西不等式(Cauchy–Schwarz inequality)

∣x⊤y∣≤∥x∥∥y∥\lvert \mathbf{x} ^\top \mathbf{y} \rvert \le \lVert \mathbf{x} \rVert \lVert \mathbf{y} \rVert

将这个不等式推广到LpL_p范数称为霍尔德不等式(Holder)：for any p,q≤1 such that 1/p+1/q=1, it holds that\text{for any }p,q \le 1 \text{ such that } 1/p + 1/q = 1, \text{ it holds that}

∣x⊤y∣≤∑k=1n∣xkyk∣≤∥x∥p∥y∥p\lvert \mathbf{x} ^\top \mathbf{y} \rvert \le \sum^n_{k=1} \lvert x_k y_k \rvert \le \lVert \mathbf{x} \rVert_p \lVert \mathbf{y} \rVert_p

考虑到一个非零向量y∈Rn\mathbf{y} \in \mathbb{R}^n，寻找某个向量x∈Bp\mathbf{x} \in \mathcal{B}_p（在LpL_p范数下的单位球）使得内积x⊤y\mathbf{x}^\top\mathbf{y} 最大化的问题-，即

max⁡∥x∥p≤1x⊤y\max_{ \lVert \mathbf{x} \rVert_p \le 1} \mathbf{x}^\top\mathbf{y}

当p=2p=2时最优解可以从几何意义x⊤y=∥x∥∥y∥cos⁡θ\mathbf{x} ^\top \mathbf{y}=\lVert \mathbf{x} \rVert \lVert \mathbf{y} \rVert \cos\theta中得到，即x\mathbf{x}与y\mathbf{y}对齐(aligned)/平行(parallel)，同时范数取最大值11时为最优解。唯一解是

x2∗=y∥y∥\mathbf{x}_2^*=\frac{\mathbf{y}}{\lVert \mathbf{y} \rVert}

此时最大值为max⁡∥x∥2≤1x⊤y=∥y∥2\max_{ \lVert \mathbf{x} \rVert_2 \le 1} \mathbf{x}^\top\mathbf{y} =\lVert \mathbf{y} \rVert_2

当p=∞p=\infin时最优解可以从定义x⊤y=∑k=1nxkyk\mathbf{x} ^\top \mathbf{y} = \sum^n_{k=1} x_k y_k中得到，由于x\mathbf{x}中的每个元素的绝对值都小于等于11，那么令xi=sgn(yi)x_i = \mathrm{sgn}\left( y_i \right)可以使求和为最大值，此时xiyi=∣yi∣x_iy_i=\lvert y_i \rvert，最优解为

x∞∗=sgn(y)\mathbf{x}_{\infin}^*=\mathrm{sgn}\left( \mathbf{y} \right)

此时最大值为max⁡∥x∥∞≤1x⊤y=∑i=1n∣yi∣=∥y∥1\max_{ \lVert \mathbf{x} \rVert_{\infin} \le 1} \mathbf{x}^\top\mathbf{y} =\sum_{i=1}^n\lvert y_i \rvert = \lVert \mathbf{y} \rVert_1。最优解并非唯一，因为yi=0y_i=0时任意xi∈[−1,1]x_i \in \left[ -1,1 \right]都能满足最优目标

当p=1p=1时内积定义x⊤y=∑k=1nxkyk\mathbf{x} ^\top \mathbf{y} = \sum^n_{k=1} x_k y_k可以被解释为yiy_i的加权平均，其中xix_i是权重且绝对值相加为11。首先找到绝对值最大的yiy_i，将它的索引设为mm，也就是说对于所有i=1,…,ni=1,\dots,n有∣yi∣≤∣ym∣\lvert y_i \rvert \le \lvert y_m \rvert，最优解为

[x1∗]i={sgn(yi)if i=m0otherwise,i=1,…,n \left[ \mathbf{x}^*_1 \right]_i = \left\{ \begin{array} {ll}\text{sgn}\left( y_i \right) & \text{if }i = m \\ 0 & \text{otherwise} \end{array}\right. ,\quad i=1,\dots,n

此时最大值为max⁡∥x∥1≤1x⊤ymax⁡i∣yi∣=∥y∥∞\max_{ \lVert \mathbf{x} \rVert_{1} \le 1} \mathbf{x}^\top\mathbf{y} \max_i\lvert y_i \rvert = \lVert \mathbf{y} \rVert_{\infin}。最优解并非唯一，因为当y\mathbf{y}有多个相同最大绝对值的元素时mm可以选择这些元素的任意索引

未完待续