离散正交转换

数学上，任一的$M \times N$离散线性转换皆可表示成矩阵（Matrix）的型式：$\boldsymbol{Y = AX}$

$$\begin{bmatrix} y\left[{0}\right] \\ y\left[{1}\right] \\ y\left[{2}\right] \\ \vdots \\ y\left[{M-1}\right] \end{bmatrix} = \begin{bmatrix} {a_0\left[0\right]} & {a_0\left[1\right]} & {a_0\left[2\right]} & \cdots & {a_0\left[N-1\right]} \\ {a_1\left[0\right]} & {a_1\left[1\right]} & {a_1\left[2\right]} & \cdots & {a_1\left[N-1\right]} \\ {a_2\left[0\right]} & {a_2\left[1\right]} & {a_2\left[2\right]} & \cdots & {a_2\left[N-1\right]} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {a_{M-1}\left[0\right]} & {a_{M-1}\left[1\right]} & {a_{M-1}\left[2\right]} & \cdots & {a_{M-1}\left[N-1\right]} \end{bmatrix} \begin{bmatrix} x\left[{0}\right] \\ x\left[{1}\right] \\ x\left[{2}\right] \\ \vdots \\ x\left[{N-1}\right] \end{bmatrix}.$$

$$\mathbf{{CASE} \, {1}}$$

再进一步假设，若矩阵$\boldsymbol{A}$ by正交基底 (Orthogonal basis) 列向量（Row vector）所组成：

$$\begin{bmatrix} {\boldsymbol{\phi}_0^*} \\ {\boldsymbol{\phi}_1^*} \\ {\boldsymbol{\phi}_2^*} \\ \vdots \\ {\boldsymbol{\phi}_{M-1}^*} \end{bmatrix} = \begin{bmatrix} {\phi_0^*\left[0\right]} & {\phi_0^*\left[1\right]} & {\phi_0^*\left[2\right]} & \cdots & {\phi_0^*\left[N-1\right]} \\ {\phi_1^*\left[0\right]} & {\phi_1^*\left[1\right]} & {\phi_1^*\left[2\right]} & \cdots & {\phi_1^*\left[N-1\right]} \\ {\phi_2^*\left[0\right]} & {\phi_2^*\left[1\right]} & {\phi_2^*\left[2\right]} & \cdots & {\phi_2^*\left[N-1\right]} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ {\phi_{M-1}^*\left[0\right]} & {\phi_{M-1}^*\left[1\right]} & {\phi_{M-1}^*\left[2\right]} & \cdots & {\phi_{M-1}^*\left[N-1\right]} \end{bmatrix} = \boldsymbol{A}.$$

也可表示成级数和形式（Summation form）：

$$y\left[m\right] = \left \langle {\boldsymbol{\phi}_m^*} , x\left[n\right] \right \rangle = \sum_{n=0}^{N-1} {\phi_m^*\left[n\right]} x\left[n\right], \quad \mbox{for }m = 0,\, 1,\, \cdots,\, M-1.$$

其中$\left \langle \cdot \,, \cdot \right \rangle$代表内积运算（Inner product）。

$$\mathbf{{CASE} \, {2}}$$

同理也可假设，若矩阵$\boldsymbol{A}$ by正交基底行向量（Column vector）所组成：

$$\begin{bmatrix} {\boldsymbol{\beta}_0^*} & {\boldsymbol{\beta}_1^*} & {\boldsymbol{\beta}_2^*} & \cdots & {\boldsymbol{\beta}_{N-1}^*} \end{bmatrix} = \begin{bmatrix} {\beta_0^*\left[0\right]} & {\beta_1^*\left[0\right]} & {\beta_2^*\left[0\right]} & \cdots & {\beta_{N-1}^*\left[0\right]} \\ {\beta_0^*\left[1\right]} & {\beta_1^*\left[1\right]} & {\beta_2^*\left[1\right]} & \cdots & {\beta_{N-1}^*\left[1\right]} \\ {\beta_0^*\left[2\right]} & {\beta_1^*\left[2\right]} & {\beta_2^*\left[2\right]} & \cdots & {\beta_{N-1}^*\left[2\right]} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ {\beta_0^*\left[M-1\right]} & {\beta_1^*\left[M-1\right]} & {\beta_2^*\left[M-1\right]} & \cdots & {\beta_{N-1}^*\left[M-1\right]} \end{bmatrix} = \boldsymbol{A}.$$

也可表示成级数和：

$$y\left[m\right] = \sum_{n=0}^{N-1} x\left[n\right]{\beta_n^*\left[m\right]}, \quad \mbox{for }m = 0,\, 1,\, \cdots,\, M-1.$$

假若$M = N$时，则$det(A)\neq 0$可得

$$\begin{cases} Y = AX & (\mbox{Forward transform}) \\ X = A ^{-1} X & (\mbox{Inverse transform}) \end{cases}.$$

## 离散正交转换

大致上，可简单化将矩阵分类由（a）列向量（Row Vector）或（b）行向量（Column Vector）所组成。

### 正交矩阵by列向量：

$$\boldsymbol{A} = \begin{bmatrix} {\boldsymbol{\phi}_0^*} \\ {\boldsymbol{\phi}_1^*} \\ {\boldsymbol{\phi}_2^*} \\ \vdots \\ {\boldsymbol{\phi}_{M-1}^*} \end{bmatrix}$$

若$\begin{cases} \; \left \langle \boldsymbol{\phi}_l^*,\boldsymbol{\phi}_k^* \right \rangle = \sum_{n=0}^{N-1} {\phi_l^*\left[n\right]} \left({\phi_k^*\left[n\right]} \right)^T = 0, \quad \mbox{when } l \neq k \\ \; \left \langle \boldsymbol{\phi}_l^*,\boldsymbol{\phi}_l^* \right \rangle = \sum_{n=0}^{N-1} {\phi_l^*\left[n\right]} \left({\phi_l^*\left[n\right]} \right)^T = C_l = Constant \end{cases},$

其中，${\;\boldsymbol{\phi}_0^*},\; {\boldsymbol{\phi}_1^*},\; {\boldsymbol{\phi}_2^*},\; \ldots,\;$和${\;\boldsymbol{\phi}_{M-1}^*}$为一组列向量的正交集合且称$\boldsymbol{A}\ $为一种离散正交转换。

再者，若满足$C_l = 1, \; \mbox{for any }l$。则${\;\boldsymbol{\phi}_0^*},\; {\boldsymbol{\phi}_1^*},\; {\boldsymbol{\phi}_2^*},\; \ldots,\;$和${\;\boldsymbol{\phi}_{M-1}^*}$将组成一组列向量的正规化正交集合且称$\boldsymbol{A}\ $为一种离散正规化正交转换。

此时，我们可利用${\;\boldsymbol{\phi}_0^*},\; {\boldsymbol{\phi}_1^*},\; {\boldsymbol{\phi}_2^*},\; \ldots,\;$和${\;\boldsymbol{\phi}_{M-1}^*}$来求得$\boldsymbol{A}$的反矩阵：

$$\boldsymbol{A}^{-1} = \begin{bmatrix} {C_0^{-1}\phi_0^*\left[0\right]} & {C_1^{-1}\phi_1^*\left[0\right]} & {C_2^{-1}\phi_2^*\left[0\right]} & \cdots & {C_{N-1}^{-1}\phi_{N-1}^*\left[0\right]} \\ {C_0^{-1}\phi_0^*\left[1\right]} & {C_1^{-1}\phi_1^*\left[1\right]} & {C_2^{-1}\phi_2^*\left[1\right]} & \cdots & {C_{N-1}^{-1}\phi_{N-1}^*\left[1\right]} \\ {C_0^{-1}\phi_0^*\left[2\right]} & {C_1^{-1}\phi_1^*\left[2\right]} & {C_2^{-1}\phi_2^*\left[2\right]} & \cdots & {C_{N-1}^{-1}\phi_{N-1}^*\left[2\right]} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {C_0^{-1}\phi_0^*\left[M-1\right]} & {C_1^{-1}\phi_1^*\left[M-1\right]} & {C_2^{-1}\phi_2^*\left[M-1\right]} & \cdots & {C_{N-1}^{-1}\phi_{N-1}^*\left[M-1\right]} \end{bmatrix},$$

其中$C_m = \left \langle \boldsymbol{\phi}_m^*,\boldsymbol{\phi}_m^* \right \rangle$。再者，也可表示成级数和（Summation）形式：

$$x\left[{n}\right] = \sum_{m=0}^{N-1} C_m^{-1} {\phi_m^*\left[n\right]} y\left[{m}\right], \quad \mbox{for }n = 0,\, 1,\, \cdots,\, N-1.$$

若$C_m = 1$，即简化成。

$$x\left[{n}\right] = \sum_{m=0}^{N-1} {\phi_m^*\left[n\right]} y\left[{m}\right], \quad \mbox{for }n = 0,\, 1,\, \cdots,\, N-1.$$

### 正交矩阵by行向量：

$$\boldsymbol{A} = \begin{bmatrix} {\boldsymbol{\beta}_0^*} & {\boldsymbol{\beta}_1^*} & {\boldsymbol{\beta}_2^*} & \cdots & {\boldsymbol{\beta}_{N-1}^*} \end{bmatrix}$$

若$\begin{cases} \; \left \langle \boldsymbol{\beta}_l^*,\boldsymbol{\beta}_k^* \right \rangle = \sum_{m=0}^{M-1} \left({\beta_l^*\left[m\right]} \right)^T {\beta_k^*\left[m\right]} = 0, \quad \mbox{when } l \neq k \\ \; \left \langle \boldsymbol{\beta}_l^*,\boldsymbol{\beta}_l^* \right \rangle = \sum_{m=0}^{M-1} \left({\beta_l^*\left[m\right]} \right)^T {\beta_l^*\left[m\right]} = C_l = Constant \end{cases},$

其中，${\;\boldsymbol{\beta}_0^*},\; {\boldsymbol{\beta}_1^*},\; {\boldsymbol{\beta}_2^*},\; \ldots,\;$和${\;\boldsymbol{\beta}_{N-1}^*}$为一组行向量的正交集合且也称$\boldsymbol{A}\ $是一种离散正交转换。

再者，若满足$C_l = 1, \; \mbox{for any }l$。则${\;\boldsymbol{\beta}_0^*},\; {\boldsymbol{\beta}_1^*},\; {\boldsymbol{\beta}_2^*},\; \ldots,\;$和${\;\boldsymbol{\beta}_{N-1}^*}$将组成一组行向量的正规化正交集合且称$\boldsymbol{A}\ $为一种离散正规化正交转换。

此时，我们再利用${\;\boldsymbol{\beta}_0^*},\; {\boldsymbol{\beta}_1^*},\; {\boldsymbol{\beta}_2^*},\; \ldots,\;$和${\;\boldsymbol{\beta}_{N-1}^*}$来组成$\boldsymbol{A}$的反矩阵：

$$\boldsymbol{A}^{-1} = \begin{bmatrix} {C_0^{-1}\beta_0^*\left[0\right]} & {C_0^{-1}\beta_0^*\left[1\right]} & {C_0^{-1}\beta_0^*\left[2\right]} & \cdots & {C_0^{-1}\beta_0^*\left[N-1\right]} \\ {C_1^{-1}\beta_1^*\left[0\right]} & {C_1^{-1}\beta_1^*\left[1\right]} & {C_1^{-1}\beta_1^*\left[2\right]} & \cdots & {C_1^{-1}\beta_1^*\left[N-1\right]} \\ {C_2^{-1}\beta_2^*\left[0\right]} & {C_2^{-1}\beta_2^*\left[1\right]} & {C_2^{-1}\beta_2^*\left[2\right]} & \cdots & {C_2^{-1}\beta_2^*\left[N-1\right]} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {C_{M-1}^{-1}\beta_{M-1}^*\left[0\right]} & {C_{M-1}^{-1}\beta_{M-1}^*\left[1\right]} & {C_{M-1}^{-1}\beta_{M-1}^*\left[2\right]} & \cdots & {C_{M-1}^{-1}\beta_{M-1}^*\left[N-1\right]} \end{bmatrix},$$

其中$C_n = \left \langle \boldsymbol{\beta}_n^*,\boldsymbol{\beta}_n^* \right \rangle$。再者，也可表示成级数和：

$$x\left[{n}\right] = C_n^{-1} \sum_{m=0}^{N-1} {\beta_n^*\left[m\right]} y\left[{m}\right], \quad \mbox{for }n = 0,\, 1,\, \cdots,\, N-1.$$

若$C_n = 1$，即简化成。

$$x\left[{n}\right] = \sum_{m=0}^{N-1} {\beta_n^*\left[m\right]} y\left[{m}\right], \quad \mbox{for }n = 0,\, 1,\, \cdots,\, N-1.$$

## 例子

- 离散傅里叶变换
- 离散余弦变换、离散正弦变换、离散哈特利转换
- 瓦希转换、哈尔小波转换
- 离散勒詹德转换
- 离散正交多项式转换

如：哈恩转换、Krawtchouk多项式、Charlier多项式。

## 特性

- 顺向转换（Forward Transform）：列向量型式$\Longrightarrow$反向转换（Inverse Transform）：行向量型式。
- 顺向转换（FT）：行向量型式$\Longrightarrow$反向转换（IT）：列向量型式。
- 若为行向量所组成的正规化正交矩阵，则它所对应的列向量形成的反矩阵$\boldsymbol{\left( A^{-1} \right)}$必为正规化正交矩阵。
- 若为列向量所组成的正规化正交矩阵，则它所对应的行向量形成的反矩阵$\boldsymbol{\left( A^{-1} \right)}$必为正规化正交矩阵。

## 优点

- 彼此间的列向量（或行向量）不会互相产生干扰（Interference）。
- 在同一维度（dimension）下，DOT提供正交矩阵内的列向量（或行向量）彼此间重要的正交特性，可借由此避免其他使用者干扰进而来实现多工存取技术。

$$\boldsymbol{Orthognal:} \quad \left \langle \boldsymbol{\phi}_l^*,\boldsymbol{\phi}_k^* \right \rangle = \sum_{n=0}^{N-1} {\phi_l^*\left[m\right]} {\phi_k^*\left[m\right]} = 0, \quad \mbox{when } l \neq k.$$

- 其本身的FT与对应的IT结构为相当类似。
- 此外，离散正交转换较非正交转换（Non-orthogonal Transform）计算上较为简单。
- 将DOT应用于影像重建（Reconstruction）或压缩上，可借由增加正交基底（Orthogonal basis）来控制误差的产生，是采用非正交转换所能及的。

## 应用于影像重建

通常对于影像重建或压缩上大都采用局部重建（Parital reconstruction）的机制，即：

(a) 正交情况下

$$x_k\left[{n}\right] = \sum_{m=0}^{K-1} C_m^{-1} y\left[{m}\right] {\phi_m^*\left[n\right]}, \quad \mbox{for }K < N.$$

因此，对于局部重建所产生的平方误差（Sqaure error）：

$$\left \| x\left[n\right] - x_k\left[n\right] \right \|^2 = \sum_{n=0}^{N-1} \left \| \sum_{m=k}^{N-1} C_m^{-1}y\left[{m}\right] \phi_m\left[n\right] \right \|^2 = \sum_{n=0}^{N-1} \sum_{m=k}^{N-1} C_m^{-1}y\left[{m}\right] \phi_m\left[n\right] \sum_{h=k}^{N-1} C_h^{-1}y^*\left[{h}\right] \phi_h^*\left[n\right] = \sum_{m=k}^{N-1} C_m^{-1}\left|\ y\left[{m}\right] \right|^2.$$

从此结果可发现$C_m^{-1}\left|\ y\left[{m}\right] \right|^2$必定为正的，因此可借由增加正交基底数来改善影像重建后的平方误差值。

（b）非正交情况下

$$x_k\left[{n}\right] = \sum_{m=0}^{K-1} B\left[{n,m}\right] y\left[m\right], \quad \mbox{for }K < N.$$

因此，对于局部重建所产生的平方误差：

$$\left \| x\left[n\right] - x_k\left[n\right] \right \|^2 = \sum_{n=0}^{N-1} \left \| \sum_{m=k}^{N-1} B\left[{n,m}\right] y\left[m\right] \right \|^2 = \sum_{m=k}^{N-1} \sum_{h=k}^{N-1} y\left[{m}\right] y^*\left[h\right] \sum_{n=0}^{N-1} B\left[{n,m}\right] B^*\left[{n,h}\right].$$

从此结果可发现$y\left[{m}\right] y^*\left[h\right] \sum_{n=0}^{N-1} B\left[{n,m}\right] B^*\left[{n,h}\right]$不一定为正的，所以无法利用增加基底数来改善平方误差。

## 参阅

- 离散傅里叶变换
- 离散余弦变换
- 离散正弦变换
- 哈尔小波转换
- 正交矩阵