正交变换

在線性代數中，**正交轉換**是線性轉換的一種。如果对于任意向量\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 

## 性質
1. 正交變換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  

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

3. 如果\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}\|   

4. 正交變換容易做反運算

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}  

5. 對於正交變換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等都屬於正交變換。對矩陣做旋轉或是鏡射也屬於正交變換。這裡會舉出一些簡單的正交變換例子。

1. 對於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 

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} 

3. 正交變換可以參數計算變得容易，令\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}   

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

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}| 越小

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

## 参见
* 瑕旋转
* 内积空间
* 线性变换
* 正交矩阵
* 酉变换

## 参考文献
3.  Ding, J. J. (2017). Advanced Digital Signal Processing [Powerpoint slides] http://djj.ee.ntu.edu.tw/ADSP15.pdf  

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

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