张春成
2021/09/19阅读：68主题：默认主题
卷积及傅立叶变换的矩阵计算
卷积及傅立叶变换的矩阵计算
傅氏变换与卷积都可以用矩阵乘法的形式进行表达。 图神经网络的优化正是以这种矩阵形式为基础的， 从信号连续空间到图拓扑空间的拓展。
本文是其中的第一步， 用矩阵的形式表达信号的傅氏变换与卷积。
本文只涉及必要的原理解释， 具体实现代码可见我的GitHub 仓库^{[1]}。
Explore the Convolution and FFT using Matrix
The notebook is developed to show the Convolution and FFT computing equals to the Matrix Multiple.

Convolution

FFT

Convolution Theorem
where refers the digital series with samples. And refers the Fourier Weights of the frequencies. And refers the transformation Matrix.
Explain
Basic
The signal series can be expressed as the linear combination of linearindependence base waveforms.
where refers the matrix of the linearindependence waveforms. Each column of the matrix is one series of a waveform. Thus, refers the weights vector.
It is easy to choose certain to fit
where . And refers the column of the matrix.
FFT
One solution is using the Triangle Waveforms as the same with Fourier Transformation.
where refers the digital arc frequency. And refers the image unit fitting . Meanwhile, it is not easy to be confused with footnote.
Combining ( ) and ( ), it is easy to get
where , and the refers the Fourier transformation. Since
Then, using the definition of the Fourier Transformation, the FFT can be expressed using ( ). And the is the Fourier coefficients.
Thus, we have
Convolution
The linear convolution between and is computed as
where the belongs to the smaller range of and , usually it ranges as .
Using the definition of Matrix Multiple, the discrete version of ( ) can be expressed as
The matrix is designed based on the convolution core ( ). We assume the core fits
it refers a length signal.
The row of writes as
where refers the row of the matrix. It refers the center of the lies in the element of the .
As a result, the matrix LIKES a diagnostic matrix. And the core is SLIDING along the rows.
The convolution with the core equals to the formula
where refers the convoluted signal.
Thus, we have
Convolution Theorem
Let's keep things simple
Since then, the Convolution Theorem is expressed as
where .
Thus, we have
Taking a stop here, we have formulated the three transformation matrix.
However, the matrix Convolution Theorem is raising an interesting question that, I can not figure out how the playing its role still. More specifically, how it equals to a diagnostic matrix?
Both the equation and the experiment results all requires that, the diagonal of the matrix equals to the real part of the lowpass filter as the same as the convolution core is transforming. So the question is, why?
Appendix
Fourier Decomposition
Basically, the Fourier coefficients fit
The Digital arc frequency
In frequencies in discrete version are expressed as
The Property of the
The matrix has the property as below
The Convolution Theorem
The theorem says
参考资料
GitHub 仓库: https://github.com/listenzcc/JupyterScripts.git
作者介绍