¿Hay una FFT que utiliza una división logarítmica de frecuencia?

Question

Wavelet artículo contiene este texto:

  

La transformada de wavelet discreta es también menos computacionalmente compleja, teniendo un tiempo O (N) en comparación con O (N log N) para el transformada rápida de Fourier . Esta ventaja computacional no es inherente a la transformación, sino que refleja la elección de una división logarítmica de frecuencia, en contraste con las divisiones de frecuencia equidistantes de la FFT.

¿Esto implica que también hay un algoritmo FFT similar que utiliza una división logarítmica de frecuencia en lugar de lineal? Es también O (N)? Esto, obviamente, sería preferible para muchas aplicaciones.

Answer 1

Sí. Si. No.

Se llama el logarítmica transformada de Fourier. Tiene tiempo O (n). Sin embargo, es útil para funciones que decaen lentamente con el aumento de dominio / abscisa.

Haciendo referencia de nuevo el artículo de Wikipedia:

  

La diferencia principal es que las ondas   se localizan en el tiempo y   frecuencia mientras que el estándar de Fourier   transformen sólo se localiza en   frecuencia.

Así que si puede ser localizado sólo en el tiempo (o espacio, escoger su interpretación de la abscisa) y luego Wavelets (o transformada discreta del coseno) son una aproximación razonable. Pero si tiene que seguir y seguir y seguir, entonces necesita la transformada de Fourier.

Más información sobre LFT en http://homepages.dias.ie/~ ajones / publicaciones / 28.pdf

Este es el resumen:

  

Se presenta una expresión exacta y analítico para la transformada de Fourier de una función que ha sido muestreada de forma logarítmica. El procedimiento es significativamente más eficiente computacionalmente que la transformación rápida de Fourier (FFT) para la transformación de funciones o respuestas medidas que decaen lentamente con el aumento de abscisa valor. Se ilustra el método propuesto con un ejemplo de la geofísica electromagnéticos, donde la escala es a menudo de tal manera que nuestra transformación logarítmica de Fourier (LFT) se debe aplicar. Para el ejemplo elegido, somos capaces de obtener resultados que están de acuerdo con los de una FFT dentro de 0,5 por ciento en un tiempo que es un factor de 1.0e2 más corto. Las aplicaciones potenciales de nuestra LFT en geofísica incluyen la conversión de banda ancha respuestas de frecuencia electromagnética a respuestas transitorias, carga y descarga glacial,   acuíferos problemas de recarga, el modo normal y estudios de mareas tierra en sismología, y el modelado de ondas de choque impulsivo.

Answer 2

Para hacer lo que quiera, es necesario medir el tiempo diferentes de Windows, lo que significa que las frecuencias más bajas consiguen actualización con menos frecuencia (inversamente proporcional a las potencias de 2).

Comprobar FPPO aquí: https://www.rationalacoustics.com/files/FFT_Fundamentals.pdf

Esto significa que las frecuencias más altas se actualizan con más frecuencia, pero siempre la media (promedio móvil es buena), pero también puede dejar que se mueva más rápido. Por supuesto, si el plan sobre el uso de la FFT inversa, que no quiere nada de esto. Además, para tener una mejor precisión (menor ancho de banda) a frecuencias más bajas, significa que estos necesitan actualizar mucho más lentamente, como 16k de Windows (1/3 m / s).

Sí, una señal de baja frecuencia natural se desplaza lentamente, y por lo tanto, por supuesto, se necesita mucho tiempo para detectarlos. Esto no es un problema que las matemáticas pueden arreglar. Es un intercambio natural de, y no se puede tener una alta precisión una frecuencia más baja y una rápida respuesta.

Creo que el enlace que proporcione será aclarar algunas de las opciones de ... 7 años después de la pregunta, por desgracia.

Answer 3

EDIT: Después de leer en esto creo que este algoritmo no es realmente útil para esta pregunta, voy a dar una descripción de todos modos para otros lectores

.

También hay algoritmo de Filon un método basado en qudrature de Filon que se puede encontrar en Numerical Recipes esta [tesis doctoral] [1]. La escala de tiempo es log espaciados como es la escala frequeny resultante.

Este algoritmo se utiliza para datos / funciones que cariados a 0 en el intervalo de tiempo observado (que probablemente no es su caso), un ejemplo típico simple sería un decaimiento exponencial.

Si los datos se observó por los puntos (x 0, y_0), (x_1, y1) ... (x_i, y_i) y se desea calcular el espectro A (f), donde f es la frecuencia de digamos f_min = 1 / máx_x a f_max = 1 / mín_x  log espaciados. La parte real para cada frecuencia f se calcula a continuación:

A (f) = suma de i = 0 ... i-1 {(y_i + 1 - y_i) / (x_i + 1 - x_i) * [cos (2 * pi * f * t_i + 1) - cos (2 * pi * f * t_i)] / ((2 * pi f *) ^ 2)}

La parte imaginaria es:

A (f) = y_0 / (2 * pi f *) + suma de i = 0 ... i-1 {(y_i + 1 - y_i) / (x_i + 1 - x_i) * [sen (2 * pi * f * t_i + 1) - sen (2 * pi * f * t_i)] / ((2 * pi f *) ^ 2)}

[1] Blochowicz, Thomas:. Banda ancha dieléctrica Espectroscopia en aseado y binario Molecular cristal Formadores Universidad de Bayreuth, 2003, Capítulo 3.2.3