离散正交转换

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

正交矩阵by列向量：

${\displaystyle {\boldsymbol {A}}={\begin{bmatrix}{{\boldsymbol {\phi }}_{0}^{*}}\\{{\boldsymbol {\phi }}_{1}^{*}}\\{{\boldsymbol {\phi }}_{2}^{*}}\\\vdots \\{{\boldsymbol {\phi }}_{M-1}^{*}}\end{bmatrix}}}$ 

若${\displaystyle {\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}},}$ 

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

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

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

${\displaystyle {\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}},}$ 

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

${\displaystyle 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.}$ 

若${\displaystyle C_{m}=1}$ ，即简化成，

${\displaystyle 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行向量：

${\displaystyle {\boldsymbol {A}}={\begin{bmatrix}{{\boldsymbol {\beta }}_{0}^{*}}&{{\boldsymbol {\beta }}_{1}^{*}}&{{\boldsymbol {\beta }}_{2}^{*}}&\cdots &{{\boldsymbol {\beta }}_{N-1}^{*}}\end{bmatrix}}}$ 

若${\displaystyle {\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}},}$ 

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

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

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

${\displaystyle {\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}},}$ 

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

${\displaystyle 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.}$ 

若${\displaystyle C_{n}=1}$ ，即简化成，

${\displaystyle 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）：列向量型式${\displaystyle \Longrightarrow }$ 反向转换（Inverse Transform）：行向量型式。
  • 顺向转换（FT）：行向量型式${\displaystyle \Longrightarrow }$ 反向转换（IT）：列向量型式。

• 于正规化正交情况下：

• • 若为行向量所组成的正规化正交矩阵，则它所对应的列向量形成的反矩阵${\displaystyle {\boldsymbol {\left(A^{-1}\right)}}}$ 必为正规化正交矩阵。
  • 若为列向量所组成的正规化正交矩阵，则它所对应的行向量形成的反矩阵${\displaystyle {\boldsymbol {\left(A^{-1}\right)}}}$ 必为正规化正交矩阵。

• 彼此间的列向量（或行向量）不会互相产生干扰（Interference）。

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

${\displaystyle {\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) 正交情况下

${\displaystyle 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）： ${\displaystyle \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}.}$ 

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

（b）非正交情况下

${\displaystyle x_{k}\left[{n}\right]=\sum _{m=0}^{K-1}B\left[{n,m}\right]y\left[m\right],\quad {\mbox{for }}K<N.}$ 

因此，对于局部重建所产生的平方误差： ${\displaystyle \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].}$ 

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

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

• Jian-Jiun Ding, Advanced Digital Signal Processing class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2008.
• http://fourier.eng.hmc.edu/e101/lectures/Image_Processing/node15.html （页面存档备份，存于互联网档案馆）.
• http://mathworld.wolfram.com/KrawtchoukPolynomial.html （页面存档备份，存于互联网档案馆）.