正交变换

在线性代数中，正交转换是线性转换的一种。如果对于任意向量$\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