Transformada de Fourier discreta no uniforme

En matemáticas aplicadas, la transformada de Fourier discreta no uniforme ( NUDFT o NDFT ) de una señal es un tipo de transformada de Fourier , relacionada con una transformada de Fourier discreta o transformada de Fourier de tiempo discreto , pero en la que la señal de entrada no se muestrea en puntos o frecuencias igualmente espaciados (o ambos). Es una generalización de la DFT desplazada . Tiene importantes aplicaciones en el procesamiento de señales, ^[1] la resonancia magnética ^[2] y la solución numérica de ecuaciones diferenciales parciales. ^[3]

Como método generalizado para el muestreo no uniforme , la NUDFT permite obtener información del dominio de frecuencia de una señal de longitud finita a cualquier frecuencia. Una de las razones para adoptar la NUDFT es que muchas señales tienen su energía distribuida de manera no uniforme en el dominio de frecuencia. Por lo tanto, un esquema de muestreo no uniforme podría ser más conveniente y útil en muchas aplicaciones de procesamiento de señales digitales . Por ejemplo, la NUDFT proporciona una resolución espectral variable controlada por el usuario.

Definición

La transformada de Fourier discreta no uniforme transforma una secuencia de números complejos en otra secuencia de números complejos definida por ${\displaystyle N}$ ${\displaystyle x_{0},\ldots ,x_{N-1}}$ ${\displaystyle X_{0},\ldots ,X_{N-1}}$

donde son puntos de muestra y son frecuencias. Nótese que si y , entonces la ecuación ( 1 ) se reduce a la transformada de Fourier discreta . Hay tres tipos de NUDFT. ^[4] Nótese que estos tipos no son universales y diferentes autores se referirán a diferentes tipos con diferentes números. ${\displaystyle p_{0},\ldots ,p_{N-1}\in [0,1]}$ ${\displaystyle f_{0},\ldots ,f_{N-1}\in [0,N]}$ ${\displaystyle p_{n}=n/N}$ ${\displaystyle f_{k}=k}$

• La transformada de Fourier discreta no uniforme de tipo I (NUDFT-I) utiliza puntos de muestra uniformes pero frecuencias no uniformes (es decir, no enteras) . Esto corresponde a la evaluación de una serie de Fourier generalizada en puntos equiespaciados. También se la conoce como NDFT ^[5] o NDFT directa ^{[6] [7]} ${\displaystyle p_{n}=n/N}$ ${\displaystyle f_{k}}$
• La transformada de Fourier discreta no uniforme de tipo II (NUDFT-II) utiliza frecuencias uniformes (es decir, enteras) pero puntos de muestra no uniformes . Esto corresponde a la evaluación de una serie de Fourier en puntos no equiespaciados. También se la conoce como NDFT adjunta. ^{[7] [6]} ${\displaystyle f_{k}=k}$ ${\displaystyle p_{n}}$
• La transformada de Fourier discreta no uniforme de tipo III (NUDFT-III) utiliza puntos de muestra no uniformes y frecuencias no uniformes . Esto corresponde a la evaluación de una serie de Fourier generalizada en puntos no equiespaciados. También se la conoce como NNDFT. ${\displaystyle p_{n}}$ ${\displaystyle f_{k}}$

Se puede definir un conjunto similar de NUDFT sustituyendo en la ecuación ( 1 ). Sin embargo, a diferencia del caso uniforme, esta sustitución no está relacionada con la transformada de Fourier inversa. La inversión de la NUDFT es un problema aparte, que se analiza a continuación. ${\displaystyle -i}$ ${\displaystyle +i}$

NUDFT multidimensional

La NUDFT multidimensional convierte una matriz -dimensional de números complejos en otra matriz -dimensional de números complejos definida por ${\displaystyle d}$ ${\displaystyle x_{\mathbf {n} }}$ ${\displaystyle d}$ ${\displaystyle X_{\mathbf {k} }}$

${\displaystyle X_{\mathbf {k} }=\sum _{\mathbf {n} =\mathbf {0} }^{\mathbf {N} -1}x_{\mathbf {n} }e^{-2\pi i\mathbf {p} _{\mathbf {n} }\cdot {\boldsymbol {f}}_{\mathbf {k} }}}$

donde son puntos de muestra, son frecuencias y y son vectores dimensionales de índices de 0 a . Las NUDFT multidimensionales de los tipos I, II y III se definen de manera análoga al caso 1D. ^[4] ${\displaystyle \mathbf {p} _{\mathbf {n} }\in [0,1]^{d}}$ ${\displaystyle {\boldsymbol {f}}_{\mathbf {k} }\in [0,N_{1}]\times [0,N_{2}]\times \cdots \times [0,N_{d}]}$ ${\displaystyle \mathbf {n} =(n_{1},n_{2},\ldots ,n_{d})}$ ${\displaystyle \mathbf {k} =(k_{1},k_{2},\ldots ,k_{d})}$ ${\displaystyle d}$ ${\displaystyle \mathbf {N} -1=(N_{1}-1,N_{2}-1,\ldots ,N_{d}-1)}$

Relación con la transformada Z

La NUDFT-I se puede expresar como una transformada Z. ^[8] La NUDFT-I de una secuencia de longitud es ${\displaystyle x[n]}$ ${\displaystyle N}$

${\displaystyle X(z_{k})=X(z)|_{z=z_{k}}=\sum _{n=0}^{N-1}x[n]z_{k}^{-n},\quad k=0,1,...,N-1,}$

donde es la transformada Z de , y son puntos arbitrariamente distintos en el plano z. Nótese que la NUDFT se reduce a la DFT cuando los puntos de muestreo están ubicados en el círculo unitario en ángulos igualmente espaciados. ${\displaystyle X(z)}$ ${\displaystyle x[n]}$ ${\displaystyle \{z_{i}\}_{i=0,1,...,N-1}}$

Expresando lo anterior como una matriz, obtenemos

${\displaystyle \mathbf {X} =\mathbf {D} \mathbf {x} }$

dónde

${\displaystyle \mathbf {X} ={\begin{bmatrix}X(z_{0})\\X(z_{1})\\\vdots \\X(z_{N-1})\end{bmatrix}},\quad \mathbf {x} ={\begin{bmatrix}x[0]\\x[1]\\\vdots \\x[N-1]\end{bmatrix}},{\text{ and}}\quad \mathbf {D} ={\begin{bmatrix}1&z_{0}^{-1}&z_{0}^{-2}&\cdots &z_{0}^{-(N-1)}\\1&z_{1}^{-1}&z_{1}^{-2}&\cdots &z_{1}^{-(N-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&z_{N-1}^{-1}&z_{N-1}^{-2}&\cdots &z_{N-1}^{-(N-1)}\end{bmatrix}}.}$

Inversión directa del NUDFT-I

Como podemos ver, la NUDFT-I se caracteriza por y, por lo tanto, por los puntos. Si factorizamos aún más , podemos ver que no es singular siempre que los puntos sean distintos. Si no es singular, podemos obtener una NUDFT-I inversa única de la siguiente manera: ${\displaystyle \mathbf {D} }$ ${\displaystyle N}$ ${\displaystyle {z_{k}}}$ ${\displaystyle \det(\mathbf {D} )}$ ${\displaystyle \mathbf {D} }$ ${\displaystyle N}$ ${\displaystyle {z_{k}}}$ ${\displaystyle \mathbf {D} }$

${\displaystyle \mathbf {x} =\mathbf {D^{-1}} \mathbf {X} }$.

Dado , podemos utilizar la eliminación gaussiana para resolver . Sin embargo, la complejidad de este método es . Para resolver este problema de manera más eficiente, primero determinamos directamente por interpolación polinómica: ${\displaystyle \mathbf {X} {\text{ and }}\mathbf {D} }$ ${\displaystyle \mathbf {x} }$ ${\displaystyle O(N^{3})}$ ${\displaystyle X(z)}$

${\displaystyle {\hat {X}}[k]=X(z_{k}),\quad k=0,1,...,N-1}$.

Luego están los coeficientes del polinomio de interpolación anterior. ${\displaystyle x[n]}$

Expresándolo como polinomio de Lagrange de orden , obtenemos ${\displaystyle X(z)}$ ${\displaystyle N-1}$

${\displaystyle X(z)=\sum _{k=0}^{N-1}{\frac {L_{k}(z)}{L_{k}(z_{k})}}{\hat {X}}[k],}$

¿Dónde están los polinomios fundamentales? ${\displaystyle \{L_{i}(z)\}_{i=0,1,...,N-1}}$

${\displaystyle L_{k}(z)=\prod _{i\neq k}(1-z_{i}z^{-1}),\quad k=0,1,...,N-1}$.

Expresando por el método de interpolación de Newton, obtenemos ${\displaystyle X(z)}$

${\displaystyle X(z)=c_{0}+c_{1}(1-z_{0}z^{-1})+c_{2}(1-z_{0}z^{-1})(1-z_{1}z^{-1})+\cdots +c_{N-1}\prod _{k=0}^{N-2}(1-z_{k}z^{-1}),}$

donde es la diferencia dividida del orden ésimo de con respecto a : ${\displaystyle c_{j}}$ ${\displaystyle j}$ ${\displaystyle {\hat {X}}[0],{\hat {X}}[1],...,{\hat {X}}[j]}$ ${\displaystyle z_{0},z_{1},...,z_{j}}$

${\displaystyle c_{0}={\hat {X}}[0],}$

${\displaystyle c_{1}={\frac {{\hat {X}}[1]-c_{0}}{1-z_{0}z_{1}^{-1}}},}$

${\displaystyle c_{2}={\frac {{\hat {X}}[2]-c_{0}-c_{1}(1-z_{0}z^{-1})}{(1-z_{0}z_{2}^{-1})(1-z_{1}z_{2}^{-1})}},}$

${\displaystyle \vdots }$

La desventaja de la representación de Lagrange es que cualquier punto adicional incluido aumentará el orden del polinomio de interpolación, lo que lleva a la necesidad de volver a calcular todos los polinomios fundamentales. Sin embargo, cualquier punto adicional incluido en la representación de Newton solo requiere la adición de un término más.

Podemos utilizar un sistema triangular inferior para resolver : ${\displaystyle \{c_{j}\}}$

${\displaystyle \mathbf {L} \mathbf {c} =\mathbf {X} }$

dónde

${\displaystyle \mathbf {X} ={\begin{bmatrix}{\hat {X}}[0]\\{\hat {X}}[1]\\\vdots \\{\hat {X}}[N-1]\end{bmatrix}},\quad \mathbf {c} ={\begin{bmatrix}c_{0}\\c_{1}\\\vdots \\c_{N-1}\end{bmatrix}},{\text{ and}}\quad \mathbf {L} ={\begin{bmatrix}1&0&0&\cdots &0\\1&(1-z_{0}z_{1}^{-1})&0&\cdots &0\\1&(1-z_{0}z_{2}^{-1})&(1-z_{0}z_{2}^{-1})(1-z_{1}z_{2}^{-1})&\cdots &0\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&(1-z_{0}z_{N-1}^{-1})&(1-z_{0}z_{N-1}^{-1})(1-z_{1}z_{N-1}^{-1})&\cdots &\prod _{k=0}^{N-2}(1-z_{k}z_{N-1}^{-1})\end{bmatrix}}.}$

Mediante la ecuación anterior, se puede calcular dentro de las operaciones. De esta manera, la interpolación de Newton es más eficiente que la interpolación de Lagrange a menos que esta última se modifique mediante ${\displaystyle \{c_{j}\}}$ ${\displaystyle O(N^{2})}$

${\displaystyle L_{k+1}(z)={\frac {(1-z_{k+1}z^{-1})}{(1-z_{k}z^{-1})}}L_{k}(z),\quad k=0,1,...,N-1}$.

Transformada rápida de Fourier no uniforme

Si bien una aplicación ingenua de la ecuación ( 1 ) da como resultado un algoritmo para calcular la NUDFT, existen algoritmos basados ​​en la transformada rápida de Fourier (FFT). Dichos algoritmos se denominan NUFFT o NFFT y se han desarrollado en función del sobremuestreo y la interpolación, ^{[9] [10] [11] [12]} interpolación mínima-máxima, ^[2] y aproximación de bajo rango. ^[13] En general, las NUFFT aprovechan la FFT al convertir el problema no uniforme en un problema uniforme (o una secuencia de problemas uniformes) al que se puede aplicar la FFT. ^[4] Las bibliotecas de software para realizar NUFFT están disponibles en 1D, 2D y 3D. ^{[7] [6] [14] [15] [16] [17]} ${\displaystyle O(N^{2})}$ ${\displaystyle O(N\log N)}$

Aplicaciones

Las aplicaciones de la NUDFT incluyen:

• Procesamiento de señales digitales
• Imágenes por resonancia magnética
• Ecuaciones diferenciales parciales numéricas
• Esquemas semilagrangianos
• Métodos espectrales
• Análisis espectral
• Diseño de filtros digitales
• Diseño de red de antenas
• Detección y decodificación de señales multifrecuencia de doble tono (DTMF)

Véase también

• Transformada de Fourier discreta
• Transformada rápida de Fourier
• Análisis espectral de mínimos cuadrados
• Periodograma de Lomb-Scargle
• Estimación espectral
• Series temporales espaciadas de manera desigual

Referencias

1. Bagchi, Sonali; Mitra, Sanjit K. (1999). La transformada de Fourier discreta no uniforme y sus aplicaciones en el procesamiento de señales . Boston, MA: Springer US. ISBN 978-1-4615-4925-3.
2. Fessler, JA; Sutton, BP (febrero de 2003). "Transformadas rápidas de Fourier no uniformes utilizando interpolación mín-máx". IEEE Transactions on Signal Processing . 51 (2): 560–574. Bibcode :2003ITSP...51..560F. doi :10.1109/TSP.2002.807005. hdl : 2027.42/85840 .
3. Lee, June-Yub; Greengard, Leslie (junio de 2005). "La FFT no uniforme de tipo 3 y sus aplicaciones". Journal of Computational Physics . 206 (1): 1–5. Bibcode :2005JCoPh.206....1L. doi :10.1016/j.jcp.2004.12.004.
4. Greengard, Leslie; Lee, June-Yub (enero de 2004). "Aceleración de la transformada rápida de Fourier no uniforme". SIAM Review . 46 (3): 443–454. Bibcode :2004SIAMR..46..443G. CiteSeerX 10.1.1.227.3679 . doi :10.1137/S003614450343200X. 
5. Plonka, Gerlind ; Potts, Daniel; Steidl, Gabriele ; Tasche, Manfred (2019). Análisis Numérico de Fourier . Birkhäuser. doi :10.1007/978-3-030-04306-3. ISBN 978-3-030-04306-3.
6. Servicios de abc PyNUFFT. «Uso básico de PyNUFFT — Documentación de PyNUFFT 2023.2.2». pynufft.readthedocs.io . Consultado el 27 de febrero de 2024 .
7. The Simons Foundation. «Definiciones matemáticas de transformadas — documentación de finufft 2.2.0». finufft.readthedocs.io . Consultado el 27 de febrero de 2024 .
8. Marvasti, Farokh (2001). Muestreo no uniforme: teoría y práctica . Nueva York: Springer. pp. 325–360. ISBN 978-1-4615-1229-5.
9. Dutt, Alok (mayo de 1993). Transformadas rápidas de Fourier para datos no equiespaciados (PDF) (PhD). Universidad de Yale.
10. Dutt, Alok; Rokhlin, Vladimir (noviembre de 1993). "Transformadas rápidas de Fourier para datos no equiespaciados". Revista SIAM de informática científica . 14 (6): 1368–1393. Bibcode :1993SJSC...14.1368D. doi :10.1137/0914081.
11. Potts, Daniel; Steidl, Gabriele (enero de 2003). "Suma rápida en nudos no equiespaciados por NFFT". Revista SIAM de informática científica . 24 (6): 2013–2037. Código Bibliográfico :2003SJSC...24.2013P. doi :10.1137/S1064827502400984.
12. Boyd, John P (diciembre de 1992). "Un algoritmo rápido para interpolación de Chebyshev, Fourier y sinc en una cuadrícula irregular" (PDF) . Journal of Computational Physics . 103 (2): 243–257. Bibcode :1992JCoPh.103..243B. doi :10.1016/0021-9991(92)90399-J. hdl : 2027.42/29694 .
13. Ruiz-Antolín, Diego; Townsend, Alex (20 de febrero de 2018). "Una transformada rápida de Fourier no uniforme basada en una aproximación de bajo rango" (PDF) . Revista SIAM de Computación Científica . 40 (1): A529–A547. arXiv : 1701.04492 . Código Bibliográfico :2018SJSC...40A.529R. doi :10.1137/17M1134822. hdl :10902/13767.
14. "Página NUFFT". cims.nyu.edu .
15. "NFFT". www.nfft.org .
16. "MikaelSlevinsky/FastTransforms.jl". GitHub . 13 de febrero de 2019.
17. "chebfun/chebfun". GitHub . 7 de febrero de 2019.

Enlaces externos

• Transformada de Fourier no uniforme: un tutorial.
• NFFT 3.0 – Tutorial
• Biblioteca de software NUFFT