正交變換

在線性代數中，正交轉換是線性轉換的一種。如果對於任意向量$\mathbf{u}$和$\mathbf{v}$其內積等於正交轉換後之向量$T({\displaystyle \mathbf {u} })$和$T({\displaystyle \mathbf {v} })$之內積，則稱之為正交變換。

$$\langle{\mathbf{u},\mathbf{v}}\rangle =\langle{T(\mathbf{u}),T(\mathbf{v})}\rangle$$

按照長度的定義，可知正交轉換後的向量長度與轉換前的長度相同。

$$\|T(\mathbf{x})\|=\|\mathbf{x}\|$$

其中$\|\mathbf{x}\|$在空間$R^n$內，$n$表示維度。

$$\langle{\mathbf{u},\mathbf{v}}\rangle =\langle{T(\mathbf{u}),T(\mathbf{v})}\rangle=\textstyle \sum_{n=0}^{N-1}u[n]v[n] \displaystyle$$

其中$N$為向量長度，$u[n]$和$v[n]$分別為$\mathbf{u}$和$\mathbf{v}$之元素，正交變換不會影響轉換前後向量間的夾角和內積長度。

在矩陣表示形式上，如果$T(\mathbf{x})=\mathbf{A}\mathbf{x}$為正交變換，則為$\mathbf{A}$正交矩陣，對於正交變換之正交矩陣$\mathbf{A}$，其每個列互為正交，令$\mathbf{A}$為$M\times N$之矩陣，取兩個不相同的列$\phi_k$和$\phi_h$ ($k\neq h$)遵守下列關係。

$$\langle \phi_k, \phi_h \rangle = 0$$

## 性質

- 正交變換$T$不會改變向量間的正交性，如果$\mathbf{u}$和$\mathbf{v}$正交，則$T({\displaystyle \mathbf {u} })$和$T({\displaystyle \mathbf {v} })$亦為正交。

$$Proof:$$

根據畢氏定理，正交變換後的向量會符合下式：

$$\|T(\mathbf{u}) +T(\mathbf{v}) \|^2=\|T(\mathbf{u})\|^2 + \|T(\mathbf{v})\|^2$$

因為正交變換屬於線性轉換：

$$\|T(\mathbf{u}) +T(\mathbf{v}) \|^2=\|T(\mathbf{u}+\mathbf{v})\|^2$$

正交變換前後向量的長度相同：

$$\|T(\mathbf{u}) +T(\mathbf{v}) \|^2=\|\mathbf{u}+\mathbf{v}\|^2$$

再根據畢氏定理，且和正交：

$$\|\mathbf{u}+\mathbf{v}\|^2 = \|\mathbf{u}\|^2 + \|\mathbf{v}\|^2$$

再根據正交變換的性質，正交變換前後向量的長度相同：

$$\|\mathbf{u}\|^2 + \|\mathbf{v}\|^2 = \|T(\mathbf{u})\|^2 + \|T(\mathbf{v})\|^2$$

- 如果$\mathbf{A}$和$\mathbf{B}$皆為正交矩陣，則$\mathbf{AB}$亦為正交矩陣。

$$Proof:$$

令一正交變換為：

$$T(\mathbf{x})=\mathbf{ABx}$$

正交變換後長度不變：

$$\|T(\mathbf{x})\|=\|\mathbf{ABx}\|=\|\mathbf{A(Bx)}\|=\|\mathbf{Bx}\|=\|\mathbf{x}\|$$

- 如果$\mathbf{A}$為正交矩陣，$\mathbf{A}$的反矩陣$\mathbf{A}^{-1}$亦為正交矩陣。

$$Proof:$$

令一正交變換為：

$$T(\mathbf{x})=\mathbf{Ax}$$

單位矩陣$\mathbf{I}$和$\mathbf{x}$相乘為$\mathbf{x}$自己，且矩陣和反矩陣相乘為單位矩陣：

$$\mathbf{Ix}=\mathbf{AA^{-1} x}=\mathbf{x}$$

正交變換後長度不變：

$$\|\mathbf{AA^{-1} x}\|=\|\mathbf{A(A^{-1}x)}\|=\|\mathbf{x}\|$$

- 正交變換容易做反運算

$$Proof:$$

令ㄧ正交矩陣$\mathbf{A}$，$\mathbf{A}$和$\mathbf{A}^H$相乘為一對角矩陣$\mathbf{D}$，其中上標$H$表示Hermitain運算。

$$\mathbf{A}\mathbf{A}^H=\mathbf{D}$$

將$\mathbf{D}$乘上自己的反矩陣$\mathbf{D}^{-1}$可得一單為矩陣$\mathbf{I}$。

$$\mathbf{D}\mathbf{D}^{-1}=\mathbf{I}$$

又$\mathbf{D}$可分解為$\mathbf{A}$和$\mathbf{A}^H$

$$\mathbf{A}\mathbf{A}^H \mathbf{D}^{-1}=\mathbf{I}$$

根據上式，將兩側乘上$\mathbf{A}$的反矩陣$\mathbf{A}^{-1}$即可得知的反矩陣知公式。

$$\mathbf{A}^{-1}=\mathbf{A}^{H}\mathbf{D}^{-1}$$

計算$\mathbf{D}$的反矩陣$\mathbf{D}^{-1}$比直接求反矩陣容易，只要相對角線之值做倒數即可。如果$\mathbf{A}^T$的每一行皆為單位向量，則：

$$\mathbf{A}^{-1}=\mathbf{A}^{H}$$

- 對於正交變換$T$，如果$\mathbf{u}$和$\mathbf{v}$可以做內積，$T({\displaystyle \mathbf {u} })$和$T({\displaystyle \mathbf {v} })$做內積之值等於$\mathbf{u}$和$\mathbf{v}$做內積之值。

$$Proof:$$

根據極化恆等式：

$$\langle{\mathbf{x},\mathbf{y}}\rangle = \frac{1}{4} (\|\mathbf{x}+\mathbf{y}\|^2-\|\mathbf{x}-\mathbf{y}\|^2)$$

將上式代入$T({\displaystyle \mathbf {u} })$和$T({\displaystyle \mathbf {v} })$：

$$\langle{T(\mathbf{u}),T(\mathbf{v})}\rangle = \frac{1}{4} (\|T(\mathbf{u})+T(\mathbf{v})\|^2-\|T(\mathbf{u})-T(\mathbf{v})\|^2)$$

因為$T$為線性轉換，轉換前做加減法和轉換後做加減法之值應相同：

$$\langle{T(\mathbf{u}),T(\mathbf{v})}\rangle = \frac{1}{4} (\|T(\mathbf{u}+\mathbf{v})\|^2-\|T(\mathbf{u}-\mathbf{v})\|^2)$$

正交變換前後向量的長度相同：

$$\langle{T(\mathbf{u}),T(\mathbf{v})}\rangle = \frac{1}{4} (\|\mathbf{u}+\mathbf{v}\|^2-\|\mathbf{u}-\mathbf{v}\|^2)$$

再根代入$\mathbf{u}$和$\mathbf{v}$之據極化恆等式：

$$\langle{T(\mathbf{u}),T(\mathbf{v})}\rangle = \langle{\mathbf{u},\mathbf{v}}\rangle$$

## 範例和應用

正交變換的種類非常的廣，像是discrete Fourier transform、discrete cosine, sine, Hartley transforms、Walsh Transform, Haar Transform等都屬於正交變換。對矩陣做旋轉或是鏡射也屬於正交變換。這裡會舉出一些簡單的正交變換例子。

- 對於$reflect_V()$以subspace $V$為基準做鏡射($V$ in $R^n$)，令$\mathbf{x}^\shortparallel$為平行之向量，$\mathbf{x}^\perp$為正交之向量：

$$\|reflect_V(\mathbf{x})\|^2 = \|\mathbf{x}^\shortparallel-\mathbf{x}^\perp\|^2$$

因為$\mathbf{x}^\shortparallel$和$\mathbf{x}^\perp$互為正交，可以根據畢氏定理做分解：

$$\|reflect_V(\mathbf{x})\|^2 = \|\mathbf{x}^\shortparallel\|^2+\|-\mathbf{x}^\perp\|^2=\|\mathbf{x}^\shortparallel\|^2+\|\mathbf{x}^\perp\|^2=\|\mathbf{x}\|^2$$

- 這裡以DFT為例證明DFT矩陣為正交矩陣，對於$N$點DFT，可得一個$N\times N$矩陣，且$\omega^n = e^{j2\pi n/N}$：

$$\mathbf{W}=\frac{1}{\sqrt{N}} \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega & \omega^2 & \cdots & \omega^{N-1}\\1 & \omega^2 & \omega^4 & \cdots &\omega^{2(N-1)}\\\cdots & \cdots& \cdots&\cdots&\cdots\\1& \omega^{N-1} & \omega^{2(N-1)} & \cdots&\omega^{(N-1)(N-1)} \end{bmatrix}$$

$\mathbf{W}$為symmetric矩陣，令的$\mathbf{W}$每個列為：

$$\mathbf {w}_n =\begin{bmatrix} 1 & \omega^n & \omega^2n & \cdots & \omega^{(N-1)n} \end{bmatrix}$$

令任意二列做內積：

$$\langle{\mathbf{w}_m,\mathbf{w}_n}\rangle=\mathbf{w}_m\centerdot\mathbf{w}_n^H =\frac{1}{N}\textstyle \sum_{k=0}^{N-1} e^{j2\pi km/N} e^{-j2\pi kn/N}\displaystyle =\frac{1}{N}\textstyle \sum_{k=0}^{N-1} e^{j(2\pi km/N)(m-n)}\displaystyle$$

上式可以化成pulse function，只有列和自己做內積才為$1$，即：

$$\langle{\mathbf{w}_m,\mathbf{w}_n}\rangle = \begin{cases} 1, & \text{if }m=n \\ 0, & \text{if }m\neq n \end{cases}$$

- 正交變換可以參數計算變得容易，令$\phi_n$為正交矩陣的列，列彼此互相正交，$c_n$而為$\phi_n$對應之參數，即給定下式中的$y$和$\phi_n$，參數$c_n$之值可以很容易的計算出來。

$$y=\textstyle \sum_{n=0}^{N-1}c_n \phi_n \displaystyle$$

如果要求出$c_m$，則將上式與$\phi_m$做內積：

$$\langle y, \phi_m\rangle=\textstyle \sum_{n=0}^{N-1}c_n \langle \phi_n , \phi_m\rangle\displaystyle$$

因為在$n\neq m$時，$\phi_n$和$\phi_m$做內積為0，可得下式：

$$\langle y, \phi_m\rangle= c_m \langle \phi_m , \phi_m\rangle$$

最後同除$\langle \phi_m, \phi_m\rangle$即可得到對應之參數：

$$c_m = \frac{\langle y, \phi_m\rangle}{\langle \phi_m , \phi_m\rangle}$$

- 在訊號壓縮上，對於原始訊號：

$$y=\textstyle \sum_{n=0}^{N-1}c_n \phi_n \displaystyle$$

假設進行壓縮，要壓縮成：

$$\hat{y}=\textstyle \sum_{n=0}^{K-1}c_n \phi_n \displaystyle$$

當$K\leq N$時，$K$越大，$|y-\hat{y}|$越小

- 在通訊應用上，會利用正交基來和訊號做調變，正交的特性會使通道間不會互相干擾。

## 參考文獻

- Ding, J. J. (2017). Advanced Digital Signal Processing Powerpoint slides http://djj.ee.ntu.edu.tw/ADSP15.pdf

- Chang, C.H. (2004). Linear Algebra PDF slides http://staff.csie.ncu.edu.tw/chia/Course/LinearAlgebra/sec5-3.pdf

- (2007). PDF slides http://isites.harvard.edu/fs/docs/icb.topic138287.files/Lesson15_-_Orthogonal_Transformations_and_Orthogonal_Matrices_slides.pdf