Artefatos na FFT

Recentemente, percebi que os FFT não são perfeitos. Ou seja, se eu pegar um sinal e depois pegar FFT, e depois fazer uma FFT inversa, a saída resultante não será exatamente a mesma da entrada. Aqui está uma imagem para mostrar o que eu quero dizer: FFT nem sempre funciona

Eu acho que a imagem é bastante auto-explicativa. O sinal IFFT é apenas uma transformação inversa do "espectro FFT" e o gráfico "Diferença" é a diferença entre o sinal IFFT e o sinal original ( ). $\text{IFFT - Original}$

Claramente, existem alguns artefatos, embora sejam realmente pequenos. Eu gostaria de saber por que eles ocorrem em primeiro lugar. Isso é devido à janela finita da transformação de Fourier? Ou por causa de algo no algoritmo FFT?

Nota: Este gráfico tem 32 pontos, mas verifiquei com 100, 1000, 1024, 256 e 64 pontos, e sempre há esse resíduo na diferença de magnitude semelhante ( ou ). $10^{-16}$ $10^{-15}$

fft fourier-transform dft Kitchi
fonte

Toda matemática de precisão limitada tem esses erros, não apenas FFTs.

Endolith

Respostas:

As diferenças que você vê são devidas a erros numéricos no formato de ponto flutuante. Todas as operações necessárias para executar uma FFT e uma FFT inversa só podem ser feitas com precisão finita e você mostrou o resultado dessa precisão finita no gráfico inferior direito.

Matt L.
fonte

Haveria uma situação em que esse erro poderia explodir além da precisão do ponto flutuante?

Kitchi

E apenas para confirmar a resposta de @ MattL: e existem 53 bits de mantissa em números de ponto flutuante de precisão dupla. Portanto, o erro de arredondamento que você vê é apenas nos últimos 2 bits. Isso é tão bom quanto possível.

10^{- 16} \approx 2^{- 53}

$10^{-16} \approx 2^{-53}$

Wandering Logic

@ Kitchi: sim, existem muitas situações em que erros numéricos podem ser um grande problema, mesmo no formato de ponto flutuante. A inversão de matrizes seria um dos muitos exemplos. Tudo tem a ver com o número da condição .

Matt L.

@MattL. - Maravilhoso! Obrigado pela referência.

Kitchi #

Em geral, um número não pode ser representado exatamente na forma digital. Um erro é introduzido. Se você está no Matlab, pode escrever eps no comando, ele fornece um número.

EPS, sem argumentos, é a distância de 1,0 ao próximo número de precisão dupla maior, ou seja, EPS = 2 ^ (- 52).

O erro que você vê no gráfico está no intervalo retornado por eps (ou seja, 2 ^ (- 52)).

Mesmo que você espere valores reais em sua saída do IFFT, poderá ver que sua parte imaginária não é exatamente igual a zero. Mesma coisa.

niaren
fonte