2D-循环卷积与2D-DFT关系

2D transforms doubly circulant block matrices and 2D circular convolution图像技术经常处理2D信号其经常通过2D卷积来处理各种类型的线性滤波。通信中的Delay-Doppler信道便是一个时变的2D高速移动信道很适合处理2D信号。2D信号可以通过一个M×NM\times NM×N矩阵来描述。给定一个2D信号X\mathsf{X}X其2D-DFT可以定义如下:X^FMXFN \hat{\mathsf{X}}\mathsf F_{M}\mathsf{X}\mathsf F_NX^FM​XFN​对每一行进行一个M点的DFT对于每一列进行一个N点的DFT。其逆傅里叶变化可以表示如下XFM†X^FN† \mathsf{X}\mathsf{F_{M}^{\dagger}}\hat{\mathsf{X}}\mathsf{F_{N}^{\dagger}}XFM†​X^FN†​对每一列和每一行进行一个IDFT。上述变化可以被向量形式vec(X^)(FN⊗FM).vec(X)vec(X)(FN†⊗FM†).vec(X^) \mathrm{vec}(\mathsf{\hat{X}})(\mathsf{F_{N}}\otimes \mathsf{F_{M}}).\mathrm{vec(\mathsf{X})}\\ \mathrm{vec}(\mathsf{X})(\mathsf{F_{N}^{\dagger}}\otimes \mathsf{F_{M}^{\dagger}}).\mathrm{vec(\mathsf{\hat{X}})}vec(X^)(FN​⊗FM​).vec(X)vec(X)(FN†​⊗FM†​).vec(X^)上述主要使用了矩阵性质vec(ABC)(C⊗A).vec(B)\mathrm{vec}(\mathsf{ABC})(\mathsf{C\otimes A}).\mathrm{vec}(\mathsf{B})vec(ABC)(C⊗A).vec(B),当C\mathsf{C}C是一个对称矩阵。我们定义一个2D循环卷积操作ZX⊛Y\mathsf{Z}\mathsf{X}\circledast\mathsf{Y}ZX⊛Y,X[x1,x2,⋯ ,xn]\mathsf{X}[\mathsf{x_1},\mathsf{x_2},\cdots,\mathsf{x_n}]X[x1​,x2​,⋯,xn​]。Z[m,n]∑k0M−1∑l0N−1X[[m−k]M,[n−l]N]Y[k,l] \mathsf{Z}[m,n]\sum_{k0}^{M-1}\sum_{l0}^{N-1}\mathsf{X}[[m-k]_{M},[n-l]_{N}]\mathsf{Y}[k,l]Z[m,n]k0∑M−1​l0∑N−1​X[[m−k]M​,[n−l]N​]Y[k,l]上式可以写成向量形式vec(Z)B.vec(Y) \mathsf{vec}(\mathsf{Z})\mathsf{B}.\mathrm{vec}(\mathsf{Y})vec(Z)B.vec(Y)Bcirc[circ(x1),⋯ ,circ(xN)] \mathsf{B}\mathrm{circ[circ(\mathsf{x_1}),\cdots,circ(\mathsf{x_N})]}Bcirc[circ(x1​),⋯,circ(xN​)]双循环block矩阵可以被对角化ΛFN⊗FM.B.(FN†⊗FM†) \Lambda\mathsf{F_{N}\otimes F_{M}.B.(F_{N}^{\dagger}\otimes F_{M}^{\dagger})}ΛFN​⊗FM​.B.(FN†​⊗FM†​)Λdiag[vec(X^)]\Lambda\mathrm{diag}[\mathrm{vec}(\hat{\mathsf{X}})]Λdiag[vec(X^)]vec(Z)B.vec(Y) \begin{align*} \mathsf{vec}(\mathsf{Z})\mathsf{B}.\mathrm{vec}(\mathsf{Y}) \end{align*}vec(Z)​B.vec(Y)​FN⊗FM.vec(Z)FN⊗FM.B.vec(Y) \mathsf{F_{N}\otimes F_{M}}.\mathsf{vec}(\mathsf{Z})\mathsf{F_{N}\otimes F_{M}}.\mathsf{B}.\mathrm{vec}(\mathsf{Y})FN​⊗FM​.vec(Z)FN​⊗FM​.B.vec(Y)FN⊗FM.vec(Z)FN⊗FM.B.FN†⊗FM†.FN⊗FM.vec(Y) \mathsf{F_{N}\otimes F_{M}}.\mathsf{vec}(\mathsf{Z})\mathsf{F_{N}\otimes F_{M}}.\mathsf{B}.\mathsf{F_{N}^{\dagger}\otimes F_{M}^{\dagger}}.\mathsf{F_{N}\otimes F_{M}} .\mathrm{vec}(\mathsf{Y})FN​⊗FM​.vec(Z)FN​⊗FM​.B.FN†​⊗FM†​.FN​⊗FM​.vec(Y)Z^X^.Y^ or vec(Z^)vec(X^).vec(Y^) \hat{\mathsf{Z}}\hat{\mathsf{X}}.\hat{\mathsf{Y}} \text{ or } \mathsf{vec}({\hat{\mathsf{Z}}})\mathsf{vec}({\hat{\mathsf{X}}}).\mathsf{vec}({\hat{\mathsf{Y}}})Z^X^.Y^orvec(Z^)vec(X^).vec(Y^)同理辛有限傅里叶变化SFFT为X^FM†XFN \hat{\mathsf{X}}\mathsf{F_{M}^{\dagger}XF_{N}}X^FM†​XFN​ISFFTXFMX^FN† \mathsf{X}\mathsf{F_{M}\hat{X}F_{N}^{\dagger}}XFM​X^FN†​也存在上述关系Z^X^.Y^ or vec(Z^)vec(X^).vec(Y^) \hat{\mathsf{Z}}\hat{\mathsf{X}}.\hat{\mathsf{Y}} \text{ or } \mathsf{vec}({\hat{\mathsf{Z}}})\mathsf{vec}({\hat{\mathsf{X}}}).\mathsf{vec}({\hat{\mathsf{Y}}})Z^X^.Y^orvec(Z^)vec(X^).vec(Y^)