統計學/數值方法/基礎線性代數與格拉姆-施密特正交化

簡介

基本上，這裡的所有部分都可以線上性代數書中找到。但是，格拉姆-施密特正交化被用於統計算法和解決統計問題。因此，我們將簡要介紹理解格拉姆-施密特正交化所需的線性代數理論。

以下子節也包含示例。對於進一步理解，重要的是這裡介紹的概念不僅適用於作為實數元組的典型向量，也適用於可以被視為向量的函式。

域

定義

一個集合 $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}.$