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

引言

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

以下小節也包含示例。對於進一步理解，理解此處介紹的概念不僅對作為實數元組的典型向量有效，而且對可以被視為向量的函式也有效，這一點非常重要。

域

定義

一個集合$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)。有限維向量空間，施普林格：紐約