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

简介

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

以下子节也包含示例。对于进一步理解，重要的是这里介绍的概念不仅适用于作为实数元组的典型向量，也适用于可以被视为向量的函数。

域

定义

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

对于所有 $\alpha ,\beta \in R$ ，有 $\alpha +\beta \in R$
对于所有 $\alpha ,\beta \in R$ ，有 $\alpha +\beta =\beta +\alpha$ （交换律）
对于所有 $\alpha ,\beta ,\gamma \in R$ ，有 $\alpha +(\beta +\gamma )=(\alpha +\beta )+\gamma$ （结合律）
存在一个独特的元素 $0$ ，称为 *零*，使得对于所有 $\alpha \in R$ 都有 $\alpha +0=\alpha$
对于所有 $\alpha \in R$ ，存在一个唯一的元素 $-\alpha$ ，使得 $\alpha +(-\alpha )=0$
对于所有 $\alpha ,\beta \in R$ 都有 $\alpha *\beta \in R$
对于所有 $\alpha ,\beta \in R$ 都有 $\alpha *\beta =\beta *\alpha$ （交换律）
对于所有 $\alpha ,\beta ,\gamma \in R$ 都有 $\alpha *(\beta *\gamma )=(\alpha *\beta )*\gamma$ （结合律）
存在一个唯一的元素 $1$ ，称为 *一*，使得对于所有 $\alpha \in R$ 都有 $\alpha *1=\alpha$
对于所有非零 $\alpha \in R$ ，存在一个唯一的元素 $\alpha ^{-1}$ ，使得 $\alpha *\alpha ^{-1}=1$
对于所有 $\alpha ,\beta ,\gamma \in R$ 都有 $\alpha *(\beta +\gamma )=\alpha *\beta +\alpha *\gamma$ （分配律）

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

示例

很容易证明，具有众所周知的加法和乘法的实数 $(IR,+,*)$ 是一个域。对于具有加法和乘法的复数，情况也是如此。实际上，很少有其他集合可以满足所有这些条件。

对于统计学，只有实数和复数与加法和乘法很重要。

向量空间

定义

具有两个运算 $+$ 和 $*$ 的集合 $V$ 称为在 R 上的向量空间，如果满足以下条件：

对于所有 $x,y\in V$ 满足 $x+y\in V$
对于所有 $x,y\in V$ 满足 $x+y=y+x$ (交换律)
对于所有 $x,y,z\in V$ 满足 $x+(y+z)=(x+y)+z$ (结合律)
存在一个唯一的元素 $\mathbb {O}$ ，称为原点，使得对于所有 $x\in V$ 满足 $x+\mathbb {O} =x$
对于所有 $x\in V$ 存在一个唯一的元素 $-v$ ，使得满足 $x+(-x)=\mathbb {O}$
对于所有 $\alpha \in R$ 和 $x\in V$ 满足 $\alpha *x\in V$
对于所有 $\alpha ,\beta \in R$ 和 $x\in V$ 都满足 $\alpha *(\beta *x)=(\alpha *\beta )*x$ （结合律）
对于所有 $x\in V$ 和 $1\in R$ 都满足 $1*x=x$
对于所有 $\alpha \in R$ 和所有 $x,y\in V$ 都满足 $\alpha *(x+y)=\alpha *x+\alpha *y$ （对向量加法的分配律）
对于所有 $\alpha ,\beta \in R$ 和所有 $x\in V$ 都满足 $(\alpha +\beta )*x=\alpha *x+\beta *x$ （对标量加法的分配律）

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

示例

集合 $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$ 的向量空间。
度数为 $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. 对于每个向量 $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}$ 的维数是 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$ 以下成立：

$<\alpha _{1}x_{1}+\alpha _{2}x_{2},y>=\alpha _{1}<x_{1},y>+\alpha _{2}<x_{2},y>$
$<x,\alpha _{1}y_{1}+\alpha _{2}y_{2}>=\alpha _{1}<x,y_{1}>+\alpha _{2}<x,y_{2}>$
$<x,y>={\overline {<y,x>}}$ ，其中 ${\overline {\alpha +\imath \beta }}=\alpha -\imath \beta$
$<x,x>\geq 0$ ，其中 $<x,x>=0\Leftrightarrow x=\mathbb {O}$

示例

在 $IR^{p}$ 中，典型的标量积是 $<x,y>=\sum _{i}x_{i}y_{i}$ 。
$<f,g>=\int _{a}^{b}f(x)*g(x)dx$ 是度数为 $p$ 的多项式向量空间上的标量积。

范数

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

$\|x\|\geq 0$ 对于所有 $x\in V$ 以及 $\|x\|=0\Leftrightarrow x=\mathbb {O}$ （正定性）
$\|\alpha v\|=\mid \alpha \mid \|x\|$ 对于所有 $x\in V$ 以及所有 $\alpha \in R$
$\|x+y\|\leq \|x\|+\|y\|$ 对于所有 $x,y\in 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 正交化

算法

格拉姆-施密特正交化的目标是，对于一组向量 $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]$ 上的二次多项式，其标量积为 $<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 {}{}}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 算法。

设置 $b_{i}=x_{i}$ 对于所有 $i$
对于每个 $i$ $i$ 从 $1$ $1$ 到 $n$ $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)$ ，我们可以得出什么结论？

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

$\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}.$