Transformada de Fourier discreta no uniforme

En matemáticas aplicadas, la transformada discreta de Fourier 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 igualmente espaciados o frecuencias (o ambas). Es una generalización de la DFT desplazada . Tiene importantes aplicaciones en el procesamiento de señales, ^[1] imagen 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, el NUDFT proporciona una resolución espectral variable controlada por el usuario.

Definición

La transformada discreta de Fourier 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}}$

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-2\pi ip_{n}f_{k}},\quad 0\leq k\leq N-1,}$

( 1 )

donde están los puntos de muestra y 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]${\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 discreta de Fourier 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.${\displaystyle p_{n}=n/N}$${\displaystyle f_{k}}$
• La transformada discreta de Fourier 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 espaciados.${\displaystyle f_{k}=k}$${\displaystyle p_{k}}$
• La transformada discreta de Fourier 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 espaciados.${\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 de Fourier inversa. La inversión del NUDFT es un problema separado, 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 muestrales, 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 forma análoga al caso 1D. ^[4]${\displaystyle \mathbf {p} _{\mathbf {k} }\in [0,1]^{d}}$${\displaystyle {\boldsymbol {f}}_{\mathbf {n} }\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 transformación Z

El NUDFT se puede expresar como una transformada Z . ^[5] El NUDFT 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 el NUDFT se reduce al 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

Como podemos ver, el NUDFT se caracteriza por y por tanto 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 un NUDFT 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 por 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 el 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],}$

donde 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 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 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 sea modificada 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, ^{[6] [7] [8] [9]} interpolación mínima-máxima, ^[2] y aproximación de rango bajo. ^[10] En general, los NUFFT aprovechan la FFT convirtiendo 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. ^{[11] [12]}${\displaystyle O(N^{2})}$${\displaystyle O(N\log N)}$^{[13] [14]}

Aplicaciones

Las aplicaciones del NUDFT incluyen:

• Procesamiento de señales digitales
• Imagen de resonancia magnética
• Ecuaciones diferenciales parciales numéricas
• Esquemas semilagrangianos
• Métodos espectrales
• Análisis espectral
• Diseño de filtro digital
• Diseño de matriz de antenas
• Detección y decodificación de señales multifrecuencia de tono dual (DTMF)

Ver también

• Transformada discreta de Fourier
• Transformada rápida de Fourier
• Series de tiempo desigualmente espaciadas
• Estimación espectral

Referencias

1. Bagchi, Sonali; Mitra, Sanjit K. (1999). La transformada discreta de Fourier 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). "Transformadas de Fourier rápidas no uniformes mediante interpolación mínima-máxima". Transacciones IEEE sobre procesamiento de señales . 51 (2): 560–574. Código bibliográfico : 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 tipo 3 y sus aplicaciones". Revista de Física Computacional . 206 (1): 1–5. Código bibliográfico : 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". Revisión SIAM . 46 (3): 443–454. Código Bibliográfico : 2004SIAMR..46..443G . CiteSeerX 10.1.1.227.3679 . doi : 10.1137 / S003614450343200X . 
5. Marvasti, Farokh (2001). Muestreo no uniforme: teoría y práctica . Nueva York: Springer. págs. 325–360. ISBN 978-1-4615-1229-5.
6. Dutt, Alok (mayo de 1993). Transformaciones rápidas de Fourier para datos no espaciados (PDF) (PhD). Universidad de Yale.
7. Dutt, Alok; Rokhlin, Vladimir (noviembre de 1993). "Transformadas rápidas de Fourier para datos no espaciados". Revista SIAM de Computación Científica . 14 (6): 1368-1393. doi : 10.1137 / 0914081 .
8. Potts, Daniel; Steidl, Gabriele (enero de 2003). "Suma rápida en nudos no escalonados por NFFT". Revista SIAM de Computación Científica . 24 (6): 2013-2037. doi : 10.1137 / S1064827502400984 .
9. Boyd, John P (diciembre de 1992). "Un algoritmo rápido para la interpolación de Chebyshev, Fourier y 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 .
10. 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 . doi : 10.1137 / 17M1134822 . hdl : 10902/13767 .
11. "Página NUFFT" . cims.nyu.edu .
12. "NFFT" . www.nfft.org .
13. "MikaelSlevinsky / FastTransforms.jl" . GitHub . 2019-02-13.
14. "chebfun / chebfun" . GitHub . 2019-02-07.

Enlaces externos

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