统计学/数值方法/基础线性代数与格拉姆-施密特正交化

引言

基本上，这里找到的所有章节都可以在线性代数书籍中找到。但是，格拉姆-施密特正交化被用于统计算法和统计问题的解决。因此，我们简要地介绍一下理解格拉姆-施密特正交化所需的线性代数理论。

以下小节也包含示例。对于进一步理解，理解此处介绍的概念不仅对作为实数元组的典型向量有效，而且对可以被视为向量的函数也有效，这一点非常重要。

域

定义

一个集合$R$，在其元素上具有两个运算$+$和$*$，被称为域（或简写为$(R,+,*)$），如果满足以下条件

1. 对于所有$\alpha ,\beta \in R$，成立$\alpha +\beta \in R$
2. 对于所有$\alpha ,\beta \in R$，成立$\alpha +\beta =\beta +\alpha$（交换律）
3. 对于所有$\alpha ,\beta ,\gamma \in R$，成立$\alpha +(\beta +\gamma )=(\alpha +\beta )+\gamma$（结合律）

4. 存在一个唯一的元素$0$，称为零，使得对于所有$\alpha \in R$ 都成立$\alpha +0=\alpha$
5. 对于所有$\alpha \in R$，存在一个唯一的元素$-\alpha$，使得成立$\alpha +(-\alpha )=0$
6. 对于所有$\alpha ,\beta \in R$ 都成立$\alpha *\beta \in R$
7. 对于所有$\alpha ,\beta \in R$ 都成立$\alpha *\beta =\beta *\alpha$（交换律）
8. 对于所有$\alpha ,\beta ,\gamma \in R$ 都成立$\alpha *(\beta *\gamma )=(\alpha *\beta )*\gamma$（结合律）
9. 存在一个唯一的元素$1$，称为一，使得对于所有$\alpha \in R$ 都成立$\alpha *1=\alpha$
10. 对于所有非零$\alpha \in R$，存在一个唯一的元素$\alpha ^{-1}$，使得成立$\alpha *\alpha ^{-1}=1$
11. 对于所有$\alpha ,\beta ,\gamma \in R$ 都成立$\alpha *(\beta +\gamma )=\alpha *\beta +\alpha *\gamma$（分配律）

$R$中的元素也称为标量。

示例

很容易证明，具有熟知的加法和乘法运算的实数$(IR,+,*)$构成一个域。复数在加法和乘法运算下也同样满足域的条件。实际上，满足所有这些条件的集合，带有两种运算的，并不多。

对于统计学来说，只有实数和复数以及它们的加法和乘法运算才是重要的。

向量空间

定义

如果一个集合$V$上的两个运算$+$和$*$作用于其元素上，并且满足以下条件，则称其为R上的向量空间。

1. 对于所有$x,y\in V$，成立$x+y\in V$
2. 对于所有$x,y\in V$，成立$x+y=y+x$（交换律）
3. 对于所有$x,y,z\in V$，成立$x+(y+z)=(x+y)+z$（结合律）
4. 存在一个唯一的元素$\mathbb {O}$，称为零向量，使得对于所有$x\in V$，成立$x+\mathbb {O} =x$
5. 对于所有$x\in V$，存在一个唯一的元素$-v$，使得成立$x+(-x)=\mathbb {O}$
6. 对于所有$\alpha \in R$和$x\in V$，成立$\alpha *x\in V$

7. 对于所有$\alpha ,\beta \in R$ 和 $x\in V$，都成立 $\alpha *(\beta *x)=(\alpha *\beta )*x$（结合律）
8. 对于所有$x\in V$ 和 $1\in R$，都成立 $1*x=x$
9. 对于所有$\alpha \in R$ 和所有 $x,y\in V$，都成立 $\alpha *(x+y)=\alpha *x+\alpha *y$（对向量加法的分配律）
10. 对于所有$\alpha ,\beta \in R$ 和所有 $x\in V$，都成立 $(\alpha +\beta )*x=\alpha *x+\beta *x$（对标量加法的分配律）

注意，我们对 $R$ 和 $V$ 中的不同运算使用了相同的符号 $+$ 和 $*$。 $V$中的元素也称为向量。

示例

1. 实值向量集$IR^{p}$，其中向量表示为$(x_{1},...,x_{p})$，并定义逐元素加法$x+y=(x_{1}+y_{1},...,x_{p}+y_{p})$和逐元素乘法$\alpha *x=(\alpha x_{1},...,\alpha x_{p})$，构成一个在$IR$上的向量空间。
2. 次数为$p$的多项式集$P(x)=b_{0}+b_{1}x+b_{2}x^{2}+...+b_{p}x^{p}$，使用通常的加法和乘法，构成一个在$IR$上的向量空间。

线性组合

如果向量$x$可以表示为向量$x_{1},...x_{n}$的线性组合，则

$x=\sum _{i=1}^{n}\alpha _{i}x_{i}$

其中$\alpha _{i}\in R$。

示例

• $(1,2,3)$是$(1,0,0),\,(0,1,0),\,(0,0,1)$的线性组合，因为$(1,2,3)=1*(1,0,0)+2*(0,1,0)+3*(0,0,1)$

• $1+2*x+3*x^{2}$ 是 $1+x+x^{2},\,x+x^{2},\,x^{2}$ 的线性组合，因为 $1+2*x+3*x^{2}=1*(1+x+x^{2})+1*(x+x^{2})+1*(x^{2})$

向量空间的基

如果一组向量 $x_{1},...,x_{n}$ 满足以下条件，则称其为向量空间 $V$ 的 基：

1. 对于向量空间 $V$ 中的每个向量 $x\in V$，都存在标量 $\alpha _{1},...,\alpha _{n}\in R$，使得 $x=\sum _{i}\alpha _{i}x_{i}$ 2. $\{x_{1},...,x_{n}\}$ 的任何子集都不能满足条件 1。

需要注意的是，一个向量空间可以有多个基。

示例

• 每个向量 $(\alpha _{1},\alpha _{2},\alpha _{3})\in IR^{3}$ 可以写成 $\alpha _{1}*(1,0,0)+\alpha _{2}*(0,1,0)+\alpha _{3}*(0,0,1)$ 的形式。因此，$\{(1,0,0),(0,1,0),(0,0,1)\}$ 是 $IR^{3}$ 的一个基。

• 每个次数为$p$的多项式可以写成$\{1,x,x^{2},...,x^{p}\}$的线性组合，因此构成该向量空间的一个基。

实际上，对于这两个例子，我们都需要证明条件2，但很明显它成立。

向量空间的维数

向量空间的维数是指构成一个基所需要的向量的个数。一个向量空间有无限多个基，但维数是唯一确定的。注意，向量空间的维数可以是无限的，例如，考虑连续函数的空间。

示例

• $IR^{3}$的维数是三，$IR^{p}$的维数是$p$。

• 次数为$p$的多项式的维数是$p+1$。

标量积

映射$<.,.>:V\times V\rightarrow R$称为标量积，如果对于所有$x,x_{1},x_{2},y,y_{1},y_{2}\in V$和$\alpha _{1},\alpha _{2}\in R$都成立：

1. $<\alpha _{1}x_{1}+\alpha _{2}x_{2},y>=\alpha _{1}<x_{1},y>+\alpha _{2}<x_{2},y>$
2. $<x,\alpha _{1}y_{1}+\alpha _{2}y_{2}>=\alpha _{1}<x,y_{1}>+\alpha _{2}<x,y_{2}>$
3. $<x,y>={\overline {<y,x>}}$，其中${\overline {\alpha +\imath \beta }}=\alpha -\imath \beta$

4. ⟨x,x⟩≥0，其中⟨x,x⟩=0⇔x=O

示例

• 在IR^p中的典型标量积为⟨x,y⟩=∑_ix_iy_i。
• ⟨f,g⟩=∫_a^bf(x)*g(x)dx是关于p次多项式向量空间的标量积。

范数

向量的范数是一个映射||.||:V→R，如果满足以下条件：

1. ||x||≥0，对于所有x∈V，并且||x||=0⇔x=O（正定性）
2. ||αv||=|α|||x||，对于所有x∈V和所有α∈R
3. ||x+y||≤||x||+||y||，对于所有x,y∈V（三角不等式）

示例

• 向量在$IR^{p}$中的$L_{q}$范数定义为$\|x\|_{q}={\sqrt[{q}]{\sum _{i=1}^{p}x_{i}^{q}}}$。
• 每个标量积通过$\|x\|={\sqrt {<x,x>}}$生成一个范数，因此$\|f\|={\sqrt {\int _{a}^{b}f^{2}(x)dx}}$是度数为$p$的多项式的范数。

正交性

如果$<x,y>=0$，则两个向量$x$和$y$彼此正交。在$IR^{p}$中，两个向量之间夹角的余弦可以表示为

$\cos(\angle (x,y))={\frac {<x,y>}{\|x\|\|y\|}}$.

如果$x$和$y$之间的夹角为90度（正交），则余弦为零，因此$<x,y>=0$。

如果向量集$x_{1},...,x_{p}$满足

$<x_{i},x_{j}>={\begin{cases}0&{\mbox{ if }}i\neq j\\1&{\mbox{ if }}i=j\end{cases}}$，则该向量集被称为标准正交。

.

如果我们考虑向量空间的一组基$e_{1},...,e_{p}$，那么我们希望得到一组正交规范基。为什么呢？

由于我们有一组基，每个向量$x$和$y$都可以表示为$x=\alpha _{1}e_{1}+...+\alpha _{p}e_{p}$和$y=\beta _{1}e_{1}+...+\beta _{p}e_{p}$的形式。因此，$x$和$y$的标量积简化为

$<x,y>\$	$=<\alpha _{1}e_{1}+...+\alpha _{p}e_{p},\beta _{1}e_{1}+...+\beta _{p}e_{p}>\$
	$=\sum _{i=1}^{p}\sum _{j=1}^{p}\alpha _{i}\beta _{j}<e_{i},e_{j}>$
	$=\sum _{i=1}^{p}\alpha _{i}\beta _{i}<e_{i},e_{i}>$
	$=\alpha _{1}\beta _{1}+...+\alpha _{p}\beta _{p}.\$

因此，如果已知系数，标量积的计算就简化为简单的乘法和加法。记住，对于我们的多项式，我们需要求解一个积分！

Gram-Schmidt正交化

算法

Gram-Schmidt正交化的目的是为一组向量$x_{1},...,x_{p}$找到一组等价的标准正交向量$o_{1},...,o_{p}$，使得任何可以表示为$x_{1},...,x_{p}$线性组合的向量，也可以表示为$o_{1},...,o_{p}$的线性组合。

1. 令$b_{1}=x_{1}$ 且 $o_{1}=b_{1}/\|b_{1}\|$

2. 对于每个$i>1$，令$b_{i}=x_{i}-\sum _{j=1}^{i-1}{\frac {<x_{i},b_{j}>}{<b_{j},b_{j}>}}b_{j}$ 且 $o_{i}=b_{i}/\|b_{i}\|$，在每一步中，向量$x_{i}$被投影到$b_{j}$上，并将结果从$x_{i}$中减去。

示例

考虑区间$[-1,1]$内次数为2的多项式，其内积为$<f,g>=\int _{-1}^{1}f(x)g(x)dx$，范数为$\|f\|={\sqrt {<f,f>}}$。我们知道$f_{1}(x)=1,f_{2}(x)=x$和$f_{3}(x)=x^{2}$是该向量空间的一组基。现在让我们构造一个正交规范基。

步骤 1a：$b_{1}(x)=f_{1}(x)=1$

步骤 1b：$o_{1}(x)={\frac {b_{1}(x)}{\|b_{1}(x)\|}}={\frac {1}{\sqrt {<b_{1}(x),b_{1}(x)>}}}={\frac {1}{\sqrt {\int _{-1}^{1}1dx}}}={\frac {1}{\sqrt {2}}}$

步骤 2a：$b_{2}(x)=f_{2}(x)-{\frac {<f_{2}(x),b_{1}(x)>}{<b_{1}(x),b_{1}(x)>}}b_{1}(x)=x-{\frac {\int _{-1}^{1}x\ 1dx}{2}}1=x-{\frac {0}{2}}1=x$

步骤 2b：$o_{2}(x)={\frac {b_{2}(x)}{\|b_{2}(x)\|}}={\frac {x}{\sqrt {<b_{2}(x),b_{2}(x)>}}}={\frac {x}{\sqrt {\int _{-1}^{1}x^{2}dx}}}={\frac {x}{\sqrt {2/3}}}=x{\sqrt {3/2}}$

步骤 3a：$b_{3}(x)=f_{3}(x)-{\frac {<f_{3}(x),b_{1}(x)>}{<b_{1}(x),b_{1}(x)>}}b_{1}(x)-{\frac {<f_{3}(x),b_{2}(x)>}{<b_{2}(x),b_{2}(x)>}}b_{2}(x)=x^{2}-{\frac {\int _{-1}^{1}x^{2}1\ dx}{2}}1-{\frac {\int _{-1}^{1}x^{2}x\ dx}{2/3}}x=x^{2}-{\frac {2/3}{2}}1-{\frac {0}{2/3}}x=x^{2}-1/3$

步骤 3b：$o_{3}(x)={\frac {b_{3}(x)}{\|b_{3}(x)\|}}={\frac {x^{2}-1/3}{\sqrt {<b_{3}(x),b_{3}(x)>}}}={\frac {x^{2}-1/3}{\sqrt {\int _{-1}^{1}(x^{2}-1/3)^{2}dx}}}={\frac {x^{2}-1/3}{\sqrt {\int _{-1}^{1}x^{4}-2/3x^{2}+1/9\ dx}}}={\frac {x^{2}-1/3}{\sqrt {8/45}}}={\sqrt {\frac {5}{8}}}(3x^{2}-1)$

可以证明$1/{\sqrt {2}},x{\sqrt {3/2}}$和${\sqrt {\frac {5}{8}}}(3x^{2}-1)$构成具有上述标量积和范数的正交规范基。

数值不稳定性

考虑向量 $x_{1}=(1,\epsilon ,0,0),x_{2}=(1,0,\epsilon ,0)$ 和 $x_{3}=(1,0,0,\epsilon )$。假设 $\epsilon$ 足够小，使得在计算机上计算 $1+\epsilon =1$ 成立（参见 http://en.wikipedia.org/wiki/Machine_epsilon）。让我们计算在 $IR^{4}$ 中，使用标准内积 $<x,y>=x_{1}y_{1}+x_{2}y_{2}+x_{3}y_{3}+x_{4}y_{4}$ 和范数 $\|x\|={\sqrt {x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2}}}$，这些向量的正交基。

步骤 1a. $b_{1}=x_{1}=(1,\epsilon ,0,0)$

步骤 1b. $o_{1}={\frac {b_{1}}{\|b_{1}\|}}={\frac {b_{1}}{\sqrt {1+\epsilon ^{2}}}}=b_{1}$，其中 $1+\epsilon ^{2}=1$

步骤 2a. $b_{2}=x_{2}-{\frac {<x_{2},b_{1}>}{<b_{1},b_{1}>}}b_{1}=(1,0,\epsilon ,0)-{\frac {1}{1+\epsilon ^{2}}}(1,\epsilon ,0,0)=(0,-\epsilon ,\epsilon ,0)$

步骤 2b. $o_{2}={\frac {b_{2}}{\|b_{2}\|}}={\frac {b_{2}}{\sqrt {2\epsilon ^{2}}}}=(0,-{\frac {1}{\sqrt {2}}},{\frac {1}{\sqrt {2}}},0)$

步骤 3a. $b_{3}=x_{3}-{\frac {<x_{3},b_{1}>}{<b_{1},b_{1}>}}b_{1}-{\frac {<x_{3},b_{2}>}{<b_{2},b_{2}>}}b_{2}=(1,0,0,\epsilon )-{\frac {1}{1+\epsilon ^{2}}}(1,\epsilon ,0,0)-{\frac {0}{2\epsilon ^{2}}}(0,-\epsilon ,\epsilon ,0)=(0,-\epsilon ,0,\epsilon )$

步骤 3b. $o_{3}={\frac {b_{3}}{\|b_{3}\|}}={\frac {b_{3}}{\sqrt {2\epsilon ^{2}}}}=(0,-{\frac {1}{\sqrt {2}}},0,{\frac {1}{\sqrt {2}}})$

很明显，对于向量

- $o_{1}=(1,\epsilon ,0,0)\$

- $o_{2}=(0,-{\frac {1}{\sqrt {2}}},{\frac {1}{\sqrt {2}}},0)$

- $o_{3}=(0,-{\frac {1}{\sqrt {2}}},0,{\frac {1}{\sqrt {2}}})$

标量积$<o_{2},o_{3}>=1/2\neq 0$。所有其他对也不为零，但它们乘以$\epsilon$，使得我们得到接近零的结果。

改进的 Gram-Schmidt 方法

为了解决这个问题，使用了改进的 Gram-Schmidt 算法

1. 设置$b_{i}=x_{i}$ 对于所有$i$

2. 对于每个$i$从$1$到$n$，计算
   1. $o_{i}={\frac {b_{i}}{\|b_{i}\|}}$
   2. 对于每个$j$从$i+1$到$n$，计算$b_{j}=b_{j}-<b_{j},o_{i}>o_{i}\$

不同之处在于，我们首先计算新的$b_{i}$，并将其从所有其他$b_{j}$中减去。我们将错误计算的向量应用于所有向量，而不是分别计算每个$b_{i}$。

示例（重新计算）

步骤 1. $b_{1}=(1,\epsilon ,0,0)$，$b_{2}=(1,0,\epsilon ,0)$，$b_{3}=(1,0,0,\epsilon )$

步骤 2a. $o_{1}={\frac {b_{1}}{\|b_{1}\|}}={\frac {b_{1}}{\sqrt {1+\epsilon ^{2}}}}=b_{1}=(1,\epsilon ,0,0)$，其中$1+\epsilon ^{2}=1$

步骤 2b. $b_{2}=b_{2}-<b_{2},o_{1}>o_{1}=(1,0,\epsilon ,0)-(1,\epsilon ,0,0)=(0,-\epsilon ,\epsilon ,0)\$

步骤 2c. $b_{3}=b_{3}-<b_{3},o_{1}>o_{1}=(1,0,0,\epsilon )-(1,\epsilon ,0,0)=(0,-\epsilon ,0,\epsilon )\$

步骤 3a. $o_{2}={\frac {b_{2}}{\|b_{2}\|}}={\frac {b_{2}}{\sqrt {2\epsilon ^{2}}}}=(0,-{\frac {1}{\sqrt {2}}},{\frac {1}{\sqrt {2}}},0)$

步骤 3b. $b_{3}=b_{3}-<b_{3},o_{2}>o_{2}=(0,-\epsilon ,0,\epsilon )-{\frac {\epsilon }{\sqrt {2}}}(0,-{\frac {1}{\sqrt {2}}},{\frac {1}{\sqrt {2}}},0)=(0,-\epsilon /2,-\epsilon /2,\epsilon )$

步骤 4a. $o_{3}={\frac {b_{3}}{\|b_{3}\|}}={\frac {b_{3}}{\sqrt {3/2\epsilon ^{2}}}}=(0,-{\frac {1}{\sqrt {6}}},-{\frac {1}{\sqrt {6}}},{\frac {2}{\sqrt {6}}})$

我们可以很容易地验证$<o_{2},o_{3}>=0$。

应用

探索性投影追踪

在高维数据分析中，我们通常分析数据的投影。这种方法源于Cramer-Wold定理，该定理指出，如果我们知道所有一维投影，则多维分布就被确定。另一个定理指出，即使数据的多元分布高度非正态，多元数据的大多数（一维）投影看起来都是正态的。

因此，在探索性投影追踪中，我们通过与（标准）正态分布进行比较来判断投影的有趣性。如果我们假设一维数据$x$服从标准正态分布，那么经过变换$z=2\Phi ^{-1}(x)-1$，其中$\Phi (x)$是标准正态分布的累积分布函数，那么$z$在区间$[-1;1]$上均匀分布。

因此，我们可以用$\int _{-1}^{1}(f(z)-1/2)^{2}dx$来衡量数据的有趣程度，其中$f(z)$是根据数据估计得到的密度。如果密度$f(z)$在区间$[-1;1]$内等于$1/2$，则积分结果为零，这意味着我们投影后的数据服从正态分布。大于零的值表示投影后的数据偏离正态分布，并且可能存在有趣的分布。

用正交多项式展开

设$L_{i}(z)$是一组具有标量积$<f,g>=\int _{-1}^{1}f(z)g(z)dz$和范数$\|f\|={\sqrt {<f,f>}}$的正交多项式。在区间$[-1;1]$内，关于密度$f(z)$我们能得出什么结论？

如果对于某个最大阶数$I$，$f(z)=\sum _{i=0}^{I}a_{i}L_{i}(z)$，则成立

$\int _{-1}^{1}f(z)L_{j}(z)dz=\int _{-1}^{1}\sum _{i=0}^{I}a_{i}L_{i}(z)L_{j}(z)dz=a_{j}\int _{-1}^{1}L_{j}(z)L_{j}(z)dz=a_{j}$

我们也可以写成$\int _{-1}^{1}f(z)L_{j}(z)dz=E(L_{j}(z))$，或者根据经验，我们可以得到一个估计量${\hat {a}}_{j}={\frac {1}{n}}\sum _{k=1}^{n}L_{j}(z_{k})$。

我们描述术语$1/2=\sum _{i=1}^{I}b_{i}L_{i}(z)$，并得到我们的积分

$\int _{-1}^{1}(f(z)-1/2)^{2}dz=\int _{-1}^{1}\left(\sum _{i=0}^{I}(a_{i}-b_{i})L_{i}(z)\right)^{2}dz=\sum _{i,j=0}^{I}\int _{-1}^{1}(a_{i}-b_{i})(a_{j}-b_{j})L_{i}(z)L_{j}(z)dz=\sum _{i=0}^{I}(a_{i}-b_{i})^{2}.$

因此，使用正交函数集可以将积分简化为系数的求和，这些系数可以通过将${\hat {a}}_{j}$代入上述公式从数据中估计得到。系数$b_{i}$可以提前预先计算。

正则化勒让德多项式

剩下的唯一问题是找到正交多项式集$L_{i}(z)$，最高次数为$I$。我们知道$1,x,x^{2},...,x^{I}$构成此空间的基底。我们必须应用格拉姆-施密特正交化来找到正交多项式。这在第一个例子中已经开始。

得到的这些多项式称为正则化勒让德多项式。除了一个比例因子外，正则化勒让德多项式与勒让德多项式相同。勒让德多项式具有以下形式的递归表达式：

$L_{i}(z)={\frac {(2i-1)L_{i-1}(z)-(i-1)L_{i-2}(z)}{i}}$

因此，计算我们的积分就简化为计算$L_{0}(z_{k})$和$L_{1}(z_{k})$，并使用递归关系计算${\hat {a}}_{j}$。请注意，递归可能会出现数值不稳定！

参考文献

• Halmos, P.R. (1974)。有限维向量空间，施普林格：纽约