¿Por qué la salida de la FFT es igual al tamaño de los datos de entrada?

Question

Lo que entiendo de la fórmula de DFT a continuación puedo decidir el N por mí mismo. Puedo intentar usar sólo 16 bins para describir una función o incluso puedo usar 4, no será muy preciso pero puedo hacerlo, ¿verdad?

La parte confusa es que incluso la mayoría de los sitios web de empuje dicen siguiente frase extraída de este enlace : El caso más general permite números complejos en la entrada y resulta en una secuencia de igual longitud .

Eso es extremadamente extraño para mí porque digamos que tengo 100000 datos , y la complejidad de fourier es Nlog(N), ¿tengo que ir con 100000log(100000). ¿Por qué no puedo ir con menos precisa pero más eficiente N = 16. ¿Por qué las bibliotecas no implementan esto?

Ps: Como licenciado en informática lo siento si mi pregunta no es lo suficientemente científica pero la pregunté en stackoverflow, en la página de DSP etc. pero no pude aclararme. Espero haber aclarado mi punto de vista esta vez.

Answer 1

Sin duda, puede utilizar $16$ o $4$ bins, sí. Me parece extraño que las bibliotecas no implementen recuentos arbitrarios de contenedores, pero supongo que me encogeré de hombros y diré que probablemente se deba a que están escritas para personas que manejan muchos más datos que tú.

(A no ser que sólo quieras usar 16 bins para grandes conjuntos de datos para tu propia diversión, pero entonces probablemente deberías escribir tus propias funciones DFT :P )

Answer 2

Estás confundiendo la longitud de la secuencia de valores y la cantidad de cálculos para obtener la transformada de Fourier. La definición de la transformada de Fourier (rápida o no) toma $N$ valores en el tiempo y devuelve $N$ valores en frecuencia. Si $N$ es una potencia de $2$ la FFT permite realizar una serie de operaciones en coma flotante que se escalan como $N \log N$ para obtener el resultado. Una rutina de transformada de Fourier ingenua tomaría $N^2$ operaciones. El resultado será el mismo de cualquier manera. La FFT es inteligente al utilizar secciones repetibles del cálculo para mejorar la eficiencia. Para $N=16, N \log N=64, N^2=256$ sólo un factor de $4$ diferente. Pero para $N=2^{16}=65,536, N \log N=2^{20}=1,048,576$ , mientras que $N^2=2^{32}=4,294,967,296$ o $4,096$ veces mayor.