卷積及傅立葉變換的矩陣計算

張春成 2021-09-19 01:15:39 阅读数:968

卷積及傅立葉變換的矩陣計算

傅氏變換與卷積都可以用矩陣乘法的形式進行錶達。 圖神經網絡的優化正是以這種矩陣形式為基礎的, 從信號連續空間到圖拓撲空間的拓展。

本文是其中的第一步, 用矩陣的形式錶達信號的傅氏變換與卷積。

本文只涉及必要的原理解釋, 具體實現代碼可見我的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

版权声明:本文为[張春成]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/09/20210919011538655D.html