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

## 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.

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 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