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 a partes iguales. puntos o frecuencias espaciados (o ambos). Es una generalización de la DFT desplazada . Tiene importantes aplicaciones en el procesamiento de señales, ^[1] imágenes por resonancia magnética , ^[2] y la solución numérica de ecuaciones diferenciales parciales. ^[3]

Como enfoque generalizado para el muestreo no uniforme , el NUDFT permite obtener información en el dominio de la frecuencia de una señal de longitud finita en cualquier frecuencia. Una de las razones para adoptar NUDFT es que muchas señales tienen su energía distribuida de manera no uniforme en el dominio de la 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, 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 están los puntos muestrales y son las frecuencias. Tenga en cuenta que si y , entonces la ecuación ( 1 ) se reduce a la transformada discreta de Fourier . Hay tres tipos de NUDFT. ^[4] Tenga en cuenta 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 evaluar una serie de Fourier generalizada en puntos equiespaciados. También se conoce como NDFT ^[5] o NDFT directo ^{[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 evaluar una serie de Fourier en puntos no equiespaciados. También se le conoce como NDFT adjunto. ^{[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 evaluar una serie de Fourier generalizada en puntos no equiespaciados. También se le conoce como NNDFT. ${\displaystyle p_{n}}$ ${\displaystyle f_{k}}$

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

NUDFT multidimensional

El 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 son vectores -dimensionales de índices de 0 a . Las NUDFT multidimensionales de 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

El NUDFT-I se puede expresar como una transformada Z. ^[8] El 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. Tenga en cuenta que la NUDFT se reduce a la DFT cuando los puntos de muestreo están ubicados en el círculo unitario en ángulos equidistantes. ${\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, el NUDFT-I se caracteriza por y por tanto los puntos. Si factorizamos más , podemos ver que no es singular siempre que los puntos sean distintos. Si no es singular, podemos obtener un NUDFT-I inverso único 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 usar 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 mediante interpolación polinomial: ${\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}$.

Entonces son los coeficientes del polinomio de interpolación anterior. ${\displaystyle x[n]}$

Expresando como polinomio de orden de Lagrange , 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 de orden enésimo 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 llevará a la necesidad de volver a calcular todos los polinomios fundamentales. Sin embargo, cualquier punto adicional incluido en la representación de Newton sólo requiere la adición de un término más.

Podemos usar 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&0&\cdots &0\\1&(1-z_{0}z_{1}^{-1})&0&0&\cdots &0\\1&(1-z_{0}z_{2}^{-1})&(1-z_{0}z_{2}^{-1})(1-z_{1}z_{2}^{-1})&0&\cdots &0\\\vdots &\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 por ${\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). Estos algoritmos se denominan NUFFT o NFFT y se han desarrollado basándose en sobremuestreo e interpolación, ^{[9] [10] [11] [12]} interpolación min-max, ^[2] y aproximación de rango bajo. ^[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 semi-lagrangianos
• Métodos espectrales
• Análisis espectral
• Diseño de filtros digitales
• Diseño de conjunto de antenas
• Detección y decodificación de señales multifrecuencia de doble tono (DTMF)

Ver también

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

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 EE. UU. ISBN 978-1-4615-4925-3.
2. Fessler, JA; Sutton, BP (febrero de 2003). "Transformaciones rápidas de Fourier no uniformes mediante interpolación mínimo-máximo". Transacciones IEEE sobre procesamiento de señales . 51 (2): 560–574. Código Bib : 2003ITSP...51..560F. doi :10.1109/TSP.2002.807005. hdl : 2027.42/85840 .
3. Lee, junio-Yub; Greengard, Leslie (junio de 2005). "La FFT no uniforme tipo 3 y sus aplicaciones". Revista de Física Computacional . 206 (1): 1–5. Código Bib : 2005JCoPh.206....1L. doi :10.1016/j.jcp.2004.12.004.
4. Greengard, Leslie; Lee, June-Yub (enero de 2004). "Acelerar la transformada rápida de Fourier no uniforme". Revisión SIAM . 46 (3): 443–454. Código Bib : 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 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. La Fundación Simons. "Definiciones matemáticas de transformaciones: documentación 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. págs. 325–360. ISBN 978-1-4615-1229-5.
9. Dutt, Alok (mayo de 1993). Transformadas rápidas de Fourier para datos no equiespaciados (PDF) (Doctor). Universidad de Yale.
10. Dutt, Alok; Rokhlin, Vladimir (noviembre de 1993). "Transformadas rápidas de Fourier para datos no equiespaciados". Revista SIAM de Computación Científica . 14 (6): 1368-1393. Código bibliográfico : 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 Computación Científica . 24 (6): 2013-2037. Código Bib : 2003SJSC...24.2013P. doi :10.1137/S1064827502400984.
12. Boyd, John P (diciembre de 1992). "Un algoritmo rápido para Chebyshev, Fourier y la interpolación sinc en una cuadrícula irregular" (PDF) . Revista de Física Computacional . 103 (2): 243–257. Código bibliográfico : 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 rango bajo" (PDF) . Revista SIAM de Computación Científica . 40 (1): A529 – A547. arXiv : 1701.04492 . Código Bib : 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 . 2019-02-13.
17. "chebfun/chebfun". GitHub . 2019-02-07.

Enlaces externos

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