Loading...
墨滴

张春成

2021/09/18  阅读:41  主题:默认主题

卷积及傅立叶变换的矩阵计算

卷积及傅立叶变换的矩阵计算

傅氏变换与卷积都可以用矩阵乘法的形式进行表达。 图神经网络的优化正是以这种矩阵形式为基础的, 从信号连续空间到图拓扑空间的拓展。

本文是其中的第一步, 用矩阵的形式表达信号的傅氏变换与卷积。

本文只涉及必要的原理解释, 具体实现代码可见我的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 linear-independence base waveforms.

where refers the matrix of the linear-independence 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.

cosTexture
cosTexture

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?

longMatrix
longMatrix

Both the equation and the experiment results all requires that, the diagonal of the matrix equals to the real part of the low-pass 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

where the symbol refers the multiply of the elements. And the refers the Fourier transformation.

参考资料

[1]

GitHub 仓库: https://github.com/listenzcc/JupyterScripts.git

张春成

2021/09/18  阅读:41  主题:默认主题

作者介绍

张春成