Transformada de Fourier discreta no uniforme

En matemàtiques aplicades, la transformada de Fourier discreta no uniforme (NUDFT o NDFT) d'un senyal és un tipus de transformada de Fourier, relacionada amb una transformada de Fourier discreta o transformada de Fourier en temps discret, però en la qual el senyal d'entrada no es mostra igual. punts o freqüències espaiades (o ambdues). És una generalització de la DFT desplaçada. Té aplicacions importants en el processament de senyals, ^[1] imatges de ressonància magnètica, ^[2] i la solució numèrica d'equacions diferencials parcials.^[3]

Com a enfocament generalitzat per al mostreig no uniforme, el NUDFT permet obtenir informació del domini de la freqüència d'un senyal de longitud finita a qualsevol freqüència. Una de les raons per adoptar el NUDFT és que molts senyals tenen la seva energia distribuïda de manera no uniforme en el domini de la freqüència. Per tant, un esquema de mostreig no uniforme podria ser més convenient i útil en moltes aplicacions de processament de senyal digital. Per exemple, el NUDFT proporciona una resolució espectral variable controlada per l'usuari.

Definició

La transformada discreta de Fourier no uniforme transforma una seqüència de $N$ nombres complexos $x_{0},\ldots ,x_{N-1}$ en una altra seqüència de nombres complexos $X_{0},\ldots ,X_{N-1}$ definit per

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

(1)

on $p_{0},\ldots ,p_{N-1}\in [0,1]$ són punts de mostra i $f_{0},\ldots ,f_{N-1}\in [0,N]$ són freqüències. Tingueu en compte que si $p_{n}=n/N$ i $f_{k}=k$ , aleshores l'equació (1) es redueix a la transformada de Fourier discreta. Hi ha tres tipus de NUDFT.^[4] Tingueu en compte que aquests tipus no són universals i diferents autors es referiran a diferents tipus amb números diferents.

La transformada discreta de Fourier no uniforme de tipus I (NUDFT-I) utilitza punts de mostra uniformes $p_{n}=n/N$ però freqüències no uniformes (és a dir, no enteres). $f_{k}$ . Això correspon a avaluar una sèrie de Fourier generalitzada en punts equiespaiats. També es coneix com a NDFT ^[5] o NDFT endavant ^[6]^[7]
La transformada discreta de Fourier no uniforme de tipus II (NUDFT-II) utilitza freqüències uniformes (és a dir, enters) $f_{k}=k$ però punts de mostra no uniformes $p_{n}$ . Això correspon a l'avaluació d'una sèrie de Fourier en punts no equiespaiats. També es coneix com a NDFT adjunt.^[7] ^[6]
La transformada discreta de Fourier no uniforme de tipus III (NUDFT-III) utilitza els dos punts de mostra no uniformes $p_{n}$ i freqüències no uniformes $f_{k}$ . Això correspon a l'avaluació d'una sèrie de Fourier generalitzada en punts no equiespaiats. També es coneix com NNDFT.

Un conjunt similar de NUDFT es pot definir substituint $-i$ per $+i$ a l'equació (1). A diferència del cas uniforme, però, aquesta substitució no està relacionada amb la transformada de Fourier inversa. La inversió del NUDFT és un problema separat, que es discuteix a continuació.

Relació amb la transformació Z

El NUDFT-I es pot expressar com una transformada Z.^[8] El NUDFT-I d'una seqüència $x[n]$ de llargada $N$ és

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

on $X(z)$ és la transformada Z de $x[n]$ , i $\{z_{i}\}_{i=0,1,...,N-1}$ són punts arbitràriament diferents en el pla z. Cal tenir en compte que la NUDFT es redueix a la DFT quan els punts de mostreig es troben al cercle unitari a angles igualment espaiats.

Transformada ràpida de Fourier no uniforme

Mentre que una aplicació ingènua de l'equació ( 1 ) dóna lloc a an $O(N^{2})$ algorisme per calcular el NUDFT, $O(N\log N)$ Existeixen algorismes basats en la transformada ràpida de Fourier (FFT). Aquests algorismes s'anomenen NUFFT o NFFT i s'han desenvolupat basant-se en el sobremostreig i la interpolació, ^[9]^[10]^[11]^[12] interpolació min-max, ^[13] i aproximació de rang baix.^[14] En general, els NUFFT aprofiten la FFT convertint el problema no uniforme en un problema uniforme (o una seqüència de problemes uniformes) al qual es pot aplicar la FFT.^[15] Les biblioteques de programari per realitzar NUFFT estan disponibles en 1D, 2D i 3D.^[16]^[17]^[18]^[19]^[20]^[21]

Aplicacions

Les aplicacions del NUDFT inclouen:

Referències

↑ Bagchi, Sonali. The Nonuniform Discrete Fourier Transform and Its Applications in Signal Processing (en anglès). Boston, MA: Springer US, 1999. ISBN 978-1-4615-4925-3.
↑ Fessler, J.A.; Sutton, B.P. IEEE Transactions on Signal Processing, 51, 2, 2-2003, pàg. 560–574. Bibcode: 2003ITSP...51..560F. DOI: 10.1109/TSP.2002.807005.
↑ Lee, June-Yub; Greengard, Leslie Journal of Computational Physics, 206, 1, 6-2005, pàg. 1–5. Bibcode: 2005JCoPh.206....1L. DOI: 10.1016/j.jcp.2004.12.004.
↑ Greengard, Leslie; Lee, June-Yub SIAM Review, 46, 3, 1-2004, pàg. 443–454. Bibcode: 2004SIAMR..46..443G. DOI: 10.1137/S003614450343200X.
↑ Plonka, Gerlind. Numerical Fourier Analysis (en anglès). Birkhäuser, 2019. DOI 10.1007/978-3-030-04306-3. ISBN 978-3-030-04306-3.
↑ ^6,0 ^6,1 PyNUFFT Services. «Basic use of PyNUFFT — PyNUFFT 2023.2.2 documentation» (en anglès). pynufft.readthedocs.io. [Consulta: 27 febrer 2024].
↑ ^7,0 ^7,1 The Simons Foundation. «Mathematical definitions of transforms — finufft 2.2.0 documentation» (en anglès). finufft.readthedocs.io. [Consulta: 27 febrer 2024].
↑ Marvasti, Farokh. Nonuniform Sampling: Theory and Practice (en anglès). New York: Springer, 2001, p. 325–360. ISBN 978-1-4615-1229-5.
↑ (Tesi), May 1993.
↑ Dutt, Alok; Rokhlin, Vladimir SIAM Journal on Scientific Computing, 14, 6, 11-1993, pàg. 1368–1393. Bibcode: 1993SJSC...14.1368D. DOI: 10.1137/0914081.
↑ Potts, Daniel; Steidl, Gabriele SIAM Journal on Scientific Computing, 24, 6, 1-2003, pàg. 2013–2037. Bibcode: 2003SJSC...24.2013P. DOI: 10.1137/S1064827502400984.
↑ Boyd, John P Journal of Computational Physics, 103, 2, 12-1992, pàg. 243–257. Bibcode: 1992JCoPh.103..243B. DOI: 10.1016/0021-9991(92)90399-J.
↑ Fessler, J.A.; Sutton, B.P. IEEE Transactions on Signal Processing, 51, 2, 2-2003, pàg. 560–574. Bibcode: 2003ITSP...51..560F. DOI: 10.1109/TSP.2002.807005.
↑ Ruiz-Antolín, Diego; Townsend, Alex SIAM Journal on Scientific Computing, 40, 1, 20-02-2018, pàg. A529–A547. arXiv: 1701.04492. Bibcode: 2018SJSC...40A.529R. DOI: 10.1137/17M1134822.
↑ Greengard, Leslie; Lee, June-Yub SIAM Review, 46, 3, 1-2004, pàg. 443–454. Bibcode: 2004SIAMR..46..443G. DOI: 10.1137/S003614450343200X.
↑ The Simons Foundation. «Mathematical definitions of transforms — finufft 2.2.0 documentation» (en anglès). finufft.readthedocs.io. [Consulta: 27 febrer 2024].
↑ PyNUFFT Services. «Basic use of PyNUFFT — PyNUFFT 2023.2.2 documentation» (en anglès). pynufft.readthedocs.io. [Consulta: 27 febrer 2024].
↑ «NUFFT page» (en anglès). cims.nyu.edu.
↑ «NFFT» (en anglès). www.nfft.org.
↑ «MikaelSlevinsky/FastTransforms.jl» (en anglès). GitHub, 13-02-2019.
↑ «chebfun/chebfun» (en anglès). GitHub, 07-02-2019.

[1] Bagchi, Sonali. The Nonuniform Discrete Fourier Transform and Its Applications in Signal Processing (en anglès). Boston, MA: Springer US, 1999. ISBN 978-1-4615-4925-3.

[Fessler03-2] Fessler, J.A.; Sutton, B.P. IEEE Transactions on Signal Processing, 51, 2, 2-2003, pàg. 560–574. Bibcode: 2003ITSP...51..560F. DOI: 10.1109/TSP.2002.807005.

[3] Lee, June-Yub; Greengard, Leslie Journal of Computational Physics, 206, 1, 6-2005, pàg. 1–5. Bibcode: 2005JCoPh.206....1L. DOI: 10.1016/j.jcp.2004.12.004.

[Greengard2004-4] Greengard, Leslie; Lee, June-Yub SIAM Review, 46, 3, 1-2004, pàg. 443–454. Bibcode: 2004SIAMR..46..443G. DOI: 10.1137/S003614450343200X.

[Plonka2019-5] Plonka, Gerlind. Numerical Fourier Analysis (en anglès). Birkhäuser, 2019. DOI 10.1007/978-3-030-04306-3. ISBN 978-3-030-04306-3.

[PyNUFFT-6] 6,0 ^6,1 PyNUFFT Services. «Basic use of PyNUFFT — PyNUFFT 2023.2.2 documentation» (en anglès). pynufft.readthedocs.io. [Consulta: 27 febrer 2024].

[finufft-7] 7,0 ^7,1 The Simons Foundation. «Mathematical definitions of transforms — finufft 2.2.0 documentation» (en anglès). finufft.readthedocs.io. [Consulta: 27 febrer 2024].

[Marvasti2001-8] Marvasti, Farokh. Nonuniform Sampling: Theory and Practice (en anglès). New York: Springer, 2001, p. 325–360. ISBN 978-1-4615-1229-5.

[9] (Tesi), May 1993.

[10] Dutt, Alok; Rokhlin, Vladimir SIAM Journal on Scientific Computing, 14, 6, 11-1993, pàg. 1368–1393. Bibcode: 1993SJSC...14.1368D. DOI: 10.1137/0914081.

[11] Potts, Daniel; Steidl, Gabriele SIAM Journal on Scientific Computing, 24, 6, 1-2003, pàg. 2013–2037. Bibcode: 2003SJSC...24.2013P. DOI: 10.1137/S1064827502400984.

[12] Boyd, John P Journal of Computational Physics, 103, 2, 12-1992, pàg. 243–257. Bibcode: 1992JCoPh.103..243B. DOI: 10.1016/0021-9991(92)90399-J.

[Fessler032-13] Fessler, J.A.; Sutton, B.P. IEEE Transactions on Signal Processing, 51, 2, 2-2003, pàg. 560–574. Bibcode: 2003ITSP...51..560F. DOI: 10.1109/TSP.2002.807005.

[14] Ruiz-Antolín, Diego; Townsend, Alex SIAM Journal on Scientific Computing, 40, 1, 20-02-2018, pàg. A529–A547. arXiv: 1701.04492. Bibcode: 2018SJSC...40A.529R. DOI: 10.1137/17M1134822.

[Greengard20042-15] Greengard, Leslie; Lee, June-Yub SIAM Review, 46, 3, 1-2004, pàg. 443–454. Bibcode: 2004SIAMR..46..443G. DOI: 10.1137/S003614450343200X.

[finufft2-16] The Simons Foundation. «Mathematical definitions of transforms — finufft 2.2.0 documentation» (en anglès). finufft.readthedocs.io. [Consulta: 27 febrer 2024].

[PyNUFFT2-17] PyNUFFT Services. «Basic use of PyNUFFT — PyNUFFT 2023.2.2 documentation» (en anglès). pynufft.readthedocs.io. [Consulta: 27 febrer 2024].

[18] «NUFFT page» (en anglès). cims.nyu.edu.

[19] «NFFT» (en anglès). www.nfft.org.

[20] «MikaelSlevinsky/FastTransforms.jl» (en anglès). GitHub, 13-02-2019.

[21] «chebfun/chebfun» (en anglès). GitHub, 07-02-2019.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]