離散正交轉換

離散正交轉換

大致上，可簡單化將矩陣分類由（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.

應用於影像重建

通常對於影像重建或壓縮上大都採用局部重建（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] 不一定為正的，所以無法利用增加基底數來改善平方誤差。