Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Non-uniform discrete Fourier transform
open-in-new
<h2 id="definition">Definition</h2> <p>The <i>nonuniform discrete Fourier transform</i> transforms a sequence of N {\displaystyle N} complex numbers x 0 , … , x N − 1 {\displaystyle x_{0},\ldots ,x_{N-1}} into another sequence of complex numbers X 0 , … , X N − 1 {\displaystyle X_{0},\ldots ,X_{N-1}} defined by </p> <table><tbody><tr><td> X k = ∑ n = 0 N − 1 x n e − 2 π i p n f k , 0 ≤ k ≤ 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,} </td> <td></td> <td>1</td></tr></tbody></table> <p>where p 0 , … , p N − 1 ∈ [ 0 , 1 ] {\displaystyle p_{0},\ldots ,p_{N-1}\in [0,1]} are sample points and f 0 , … , f N − 1 ∈ [ 0 , N ] {\displaystyle f_{0},\ldots ,f_{N-1}\in [0,N]} are frequencies. Note that if p n = n / N {\displaystyle p_{n}=n/N} and f k = k {\displaystyle f_{k}=k} , then equation (1) reduces to the <a href="/facts/Discrete_Fourier_transform/uK9Tjsbl">discrete Fourier transform</a>. There are three types of NUDFTs.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> Note that these types are not universal and different authors will refer to different types by different numbers. </p> <ul><li>The nonuniform discrete Fourier transform of type I (NUDFT-I) uses uniform sample points p n = n / N {\displaystyle p_{n}=n/N} but nonuniform (i.e. non-integer) frequencies f k {\displaystyle f_{k}} . This corresponds to evaluating a <a href="/facts/Generalized_Fourier_series/jpd2a7nM">generalized Fourier series</a> at equispaced points. It is also known as NDFT<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> or forward NDFT <a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a><a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a></li> <li>The nonuniform discrete Fourier transform of type II (NUDFT-II) uses uniform (i.e. integer) frequencies f k = k {\displaystyle f_{k}=k} but nonuniform sample points p n {\displaystyle p_{n}} . This corresponds to evaluating a Fourier series at nonequispaced points. It is also known as adjoint NDFT.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a><a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a></li> <li>The nonuniform discrete Fourier transform of type III (NUDFT-III) uses both nonuniform sample points p n {\displaystyle p_{n}} and nonuniform frequencies f k {\displaystyle f_{k}} . This corresponds to evaluating a <a href="/facts/Generalized_Fourier_series/jpd2a7nM">generalized Fourier series</a> at nonequispaced points. It is also known as NNDFT.</li></ul> <p>A similar set of NUDFTs can be defined by substituting − i {\displaystyle -i} for + i {\displaystyle +i} in equation (1). Unlike in the uniform case, however, this substitution is unrelated to the inverse Fourier transform. The inversion of the NUDFT is a separate problem, discussed below. </p> <h2 id="multidimensional-nudft">Multidimensional NUDFT</h2> <p>The multidimensional NUDFT converts a d {\displaystyle d} -dimensional array of complex numbers x n {\displaystyle x_{\mathbf {n} }} into another d {\displaystyle d} -dimensional array of complex numbers X k {\displaystyle X_{\mathbf {k} }} defined by </p> X k = ∑ n = 0 N − 1 x n e − 2 π i p n ⋅ f 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} }}} <p>where p n ∈ [ 0 , 1 ] d {\displaystyle \mathbf {p} _{\mathbf {n} }\in [0,1]^{d}} are sample points, f k ∈ [ 0 , N 1 ] × [ 0 , N 2 ] × ⋯ × [ 0 , N d ] {\displaystyle {\boldsymbol {f}}_{\mathbf {k} }\in [0,N_{1}]\times [0,N_{2}]\times \cdots \times [0,N_{d}]} are frequencies, and n = ( n 1 , n 2 , … , n d ) {\displaystyle \mathbf {n} =(n_{1},n_{2},\ldots ,n_{d})} and k = ( k 1 , k 2 , … , k d ) {\displaystyle \mathbf {k} =(k_{1},k_{2},\ldots ,k_{d})} are d {\displaystyle d} -dimensional vectors of indices from 0 to N − 1 = ( N 1 − 1 , N 2 − 1 , … , N d − 1 ) {\displaystyle \mathbf {N} -1=(N_{1}-1,N_{2}-1,\ldots ,N_{d}-1)} . The multidimensional NUDFTs of types I, II, and III are defined analogously to the 1D case.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> </p> <h2 id="relationship-to-z-transform">Relationship to Z-transform</h2> <p>The NUDFT-I can be expressed as a <a href="/facts/Z-transform/ERNvDJqt">Z-transform</a>.<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> The NUDFT-I of a sequence x [ n ] {\displaystyle x[n]} of length N {\displaystyle N} is </p> X ( z k ) = X ( z ) | z = z k = ∑ n = 0 N − 1 x [ n ] z k − n , k = 0 , 1 , . . . , N − 1 , {\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,} <p>where X ( z ) {\displaystyle X(z)} is the Z-transform of x [ n ] {\displaystyle x[n]} , and { z i } i = 0 , 1 , . . . , N − 1 {\displaystyle \{z_{i}\}_{i=0,1,...,N-1}} are arbitrarily distinct points in the z-plane. Note that the NUDFT reduces to the DFT when the sampling points are located on the unit circle at equally spaced angles. </p><p>Expressing the above as a matrix, we get </p> X = D x {\displaystyle \mathbf {X} =\mathbf {D} \mathbf {x} } <p>where </p> X = [ X ( z 0 ) X ( z 1 ) ⋮ X ( z N − 1 ) ] , x = [ x [ 0 ] x [ 1 ] ⋮ x [ N − 1 ] ] , and D = [ 1 z 0 − 1 z 0 − 2 ⋯ z 0 − ( N − 1 ) 1 z 1 − 1 z 1 − 2 ⋯ z 1 − ( N − 1 ) ⋮ ⋮ ⋮ ⋱ ⋮ 1 z N − 1 − 1 z N − 1 − 2 ⋯ z N − 1 − ( N − 1 ) ] . {\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}}.} <h3>Direct inversion of the NUDFT-I</h3> <p>As we can see, the NUDFT-I is characterized by D {\displaystyle \mathbf {D} } and hence the N {\displaystyle N} z k {\displaystyle {z_{k}}} points. If we further factorize det ( D ) {\displaystyle \det(\mathbf {D} )} , we can see that D {\displaystyle \mathbf {D} } is nonsingular provided the N {\displaystyle N} z k {\displaystyle {z_{k}}} points are distinct. If D {\displaystyle \mathbf {D} } is nonsingular, we can get a unique inverse NUDFT-I as follows: </p> x = D − 1 X {\displaystyle \mathbf {x} =\mathbf {D^{-1}} \mathbf {X} } . <p>Given X and D {\displaystyle \mathbf {X} {\text{ and }}\mathbf {D} } , we can use <a href="/facts/Gaussian_elimination/23Rvf4ht">Gaussian elimination</a> to solve for x {\displaystyle \mathbf {x} } . However, the complexity of this method is O ( N 3 ) {\displaystyle O(N^{3})} . To solve this problem more efficiently, we first determine X ( z ) {\displaystyle X(z)} directly by polynomial interpolation: </p> X ^ [ k ] = X ( z k ) , k = 0 , 1 , . . . , N − 1 {\displaystyle {\hat {X}}[k]=X(z_{k}),\quad k=0,1,...,N-1} . <p>Then x [ n ] {\displaystyle x[n]} are the coefficients of the above interpolating polynomial. </p><p>Expressing X ( z ) {\displaystyle X(z)} as the <a href="/facts/Lagrange_polynomial/MnpMmhtC">Lagrange polynomial</a> of order N − 1 {\displaystyle N-1} , we get </p> X ( z ) = ∑ k = 0 N − 1 L k ( z ) L k ( z k ) X ^ [ k ] , {\displaystyle X(z)=\sum _{k=0}^{N-1}{\frac {L_{k}(z)}{L_{k}(z_{k})}}{\hat {X}}[k],} <p>where { L i ( z ) } i = 0 , 1 , . . . , N − 1 {\displaystyle \{L_{i}(z)\}_{i=0,1,...,N-1}} are the fundamental polynomials: </p> L k ( z ) = ∏ i ≠ k ( 1 − z i z − 1 ) , k = 0 , 1 , . . . , N − 1 {\displaystyle L_{k}(z)=\prod _{i\neq k}(1-z_{i}z^{-1}),\quad k=0,1,...,N-1} . <p>Expressing X ( z ) {\displaystyle X(z)} by the Newton interpolation method, we get </p> X ( z ) = c 0 + c 1 ( 1 − z 0 z − 1 ) + c 2 ( 1 − z 0 z − 1 ) ( 1 − z 1 z − 1 ) + ⋯ + c N − 1 ∏ k = 0 N − 2 ( 1 − z k z − 1 ) , {\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}),} <p>where c j {\displaystyle c_{j}} is the divided difference of the j {\displaystyle j} th order of X ^ [ 0 ] , X ^ [ 1 ] , . . . , X ^ [ j ] {\displaystyle {\hat {X}}[0],{\hat {X}}[1],...,{\hat {X}}[j]} with respect to z 0 , z 1 , . . . , z j {\displaystyle z_{0},z_{1},...,z_{j}} : </p> c 0 = X ^ [ 0 ] , {\displaystyle c_{0}={\hat {X}}[0],} c 1 = X ^ [ 1 ] − c 0 1 − z 0 z 1 − 1 , {\displaystyle c_{1}={\frac {{\hat {X}}[1]-c_{0}}{1-z_{0}z_{1}^{-1}}},} c 2 = X ^ [ 2 ] − c 0 − c 1 ( 1 − z 0 z − 1 ) ( 1 − z 0 z 2 − 1 ) ( 1 − z 1 z 2 − 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 } <p>The disadvantage of the Lagrange representation is that any additional point included will increase the order of the interpolating polynomial, leading to the need to recompute all the fundamental polynomials. However, any additional point included in the Newton representation only requires the addition of one more term. </p><p>We can use a lower triangular system to solve { c j } {\displaystyle \{c_{j}\}} : </p> L c = X {\displaystyle \mathbf {L} \mathbf {c} =\mathbf {X} } <p>where </p> X = [ X ^ [ 0 ] X ^ [ 1 ] ⋮ X ^ [ N − 1 ] ] , c = [ c 0 c 1 ⋮ c N − 1 ] , and L = [ 1 0 0 ⋯ 0 1 ( 1 − z 0 z 1 − 1 ) 0 ⋯ 0 1 ( 1 − z 0 z 2 − 1 ) ( 1 − z 0 z 2 − 1 ) ( 1 − z 1 z 2 − 1 ) ⋯ 0 ⋮ ⋮ ⋮ ⋱ ⋮ 1 ( 1 − z 0 z N − 1 − 1 ) ( 1 − z 0 z N − 1 − 1 ) ( 1 − z 1 z N − 1 − 1 ) ⋯ ∏ k = 0 N − 2 ( 1 − z k z N − 1 − 1 ) ] . {\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}}.} <p>By the above equation, { c j } {\displaystyle \{c_{j}\}} can be computed within O ( N 2 ) {\displaystyle O(N^{2})} operations. In this way Newton interpolation is more efficient than Lagrange Interpolation unless the latter is modified by </p> L k + 1 ( z ) = ( 1 − z k + 1 z − 1 ) ( 1 − z k z − 1 ) L k ( z ) , k = 0 , 1 , . . . , N − 1 {\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} . <h2 id="nonuniform-fast-fourier-transform">Nonuniform fast Fourier transform</h2> <p>While a naive application of equation (1) results in an O ( N 2 ) {\displaystyle O(N^{2})} algorithm for computing the NUDFT, O ( N log N ) {\displaystyle O(N\log N)} algorithms based on the <a href="/facts/Fast_Fourier_transform/caT7UUCh">fast Fourier transform</a> (FFT) do exist. Such algorithms are referred to as NUFFTs or NFFTs and have been developed based on oversampling and interpolation,<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a><a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a><a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a><a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a> min-max interpolation,<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a> and low-rank approximation.<a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a> In general, NUFFTs leverage the FFT by converting the nonuniform problem into a uniform problem (or a sequence of uniform problems) to which the FFT can be applied.<a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a> Software libraries for performing NUFFTs are available in 1D, 2D, and 3D.<a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a><a class="footnote-ref" id="fnref:20" href="#fn:20"><sup>20</sup></a><a class="footnote-ref" id="fnref:21" href="#fn:21"><sup>21</sup></a><a class="footnote-ref" id="fnref:22" href="#fn:22"><sup>22</sup></a><a class="footnote-ref" id="fnref:23" href="#fn:23"><sup>23</sup></a><a class="footnote-ref" id="fnref:24" href="#fn:24"><sup>24</sup></a> </p> <h2 id="applications">Applications</h2> <p>The applications of the NUDFT include: </p> <ul><li><a href="/facts/Digital_signal_processing/PEG7azr8">Digital signal processing</a></li> <li><a href="/facts/Magnetic_resonance_imaging/Vh9yG9qq">Magnetic resonance imaging</a></li> <li><a href="/facts/Numerical_partial_differential_equations/69kwj7mL">Numerical partial differential equations</a></li> <li><a href="/facts/Semi-Lagrangian_scheme/2dJHR94n">Semi-Lagrangian schemes</a></li> <li><a href="/facts/Spectral_methods/25VTd7oc">Spectral methods</a></li> <li><a href="/facts/Spectroscopy/mj71FuNK">Spectral analysis</a></li> <li><a href="/facts/Digital_filter/2wcxCRdh">Digital filter design</a></li> <li><a href="/facts/Antenna_array/HYRcdJsm">Antenna array design</a></li> <li>Detection and decoding of <a href="/facts/Dual-tone_multi-frequency_signaling/vg5vFo0X">dual-tone multi-frequency (DTMF) signals</a></li></ul> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Discrete_Fourier_transform/uK9Tjsbl">Discrete Fourier transform</a></li> <li><a href="/facts/Fast_Fourier_transform/caT7UUCh">Fast Fourier transform</a></li> <li><a href="/facts/Least-squares_spectral_analysis/GYXrRKsB">Least-squares spectral analysis</a></li> <li><a href="/facts/Lomb%E2%80%93Scargle_periodogram/GYXrRKsB">Lomb–Scargle periodogram</a></li> <li><a href="/facts/Spectral_estimation/JefWFBsx">Spectral estimation</a></li> <li><a href="/facts/Unevenly_spaced_time_series/CI58SNC3">Unevenly spaced time series</a></li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/PIRODDI1/NUFT/NUFT.html">Non-Uniform Fourier Transform: A Tutorial</a>.</li> <li><a href="http://www-user.tu-chemnitz.de/~potts/nfft/guide3/html/index.html">NFFT 3.0 – Tutorial</a></li> <li><a href="https://cims.nyu.edu/cmcl/nufft/nufft.html">NUFFT software library</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Bagchi, Sonali; Mitra, Sanjit K. (1999). The Nonuniform Discrete Fourier Transform and Its Applications in Signal Processing. Boston, MA: Springer US. ISBN 978-1-4615-4925-3. <a href="978-1-4615-4925-3" target="_blank">978-1-4615-4925-3</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Fessler, J.A.; Sutton, B.P. (February 2003). "Nonuniform fast fourier transforms using min-max interpolation". IEEE Transactions on Signal Processing. 51 (2): 560–574. Bibcode:2003ITSP...51..560F. doi:10.1109/TSP.2002.807005. hdl:2027.42/85840. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Lee, June-Yub; Greengard, Leslie (June 2005). "The type 3 nonuniform FFT and its applications". Journal of Computational Physics. 206 (1): 1–5. Bibcode:2005JCoPh.206....1L. doi:10.1016/j.jcp.2004.12.004. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Greengard, Leslie; Lee, June-Yub (January 2004). "Accelerating the Nonuniform Fast Fourier Transform". SIAM Review. 46 (3): 443–454. Bibcode:2004SIAMR..46..443G. CiteSeerX 10.1.1.227.3679. doi:10.1137/S003614450343200X. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Plonka, Gerlind; Potts, Daniel; Steidl, Gabriele; Tasche, Manfred (2019). Numerical Fourier Analysis. Birkhäuser. doi:10.1007/978-3-030-04306-3. ISBN 978-3-030-04306-3. <a href="978-3-030-04306-3" target="_blank">978-3-030-04306-3</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>PyNUFFT Services. "Basic use of PyNUFFT — PyNUFFT 2023.2.2 documentation". pynufft.readthedocs.io. Retrieved 27 February 2024. <a href="https://pynufft.readthedocs.io/en/latest/tutor/basic_use.html" target="_blank">https://pynufft.readthedocs.io/en/latest/tutor/basic_use.html</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>The Simons Foundation. "Mathematical definitions of transforms — finufft 2.2.0 documentation". finufft.readthedocs.io. Retrieved 27 February 2024. <a href="https://finufft.readthedocs.io/en/latest/math.html#math" target="_blank">https://finufft.readthedocs.io/en/latest/math.html#math</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>The Simons Foundation. "Mathematical definitions of transforms — finufft 2.2.0 documentation". finufft.readthedocs.io. Retrieved 27 February 2024. <a href="https://finufft.readthedocs.io/en/latest/math.html#math" target="_blank">https://finufft.readthedocs.io/en/latest/math.html#math</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>PyNUFFT Services. "Basic use of PyNUFFT — PyNUFFT 2023.2.2 documentation". pynufft.readthedocs.io. Retrieved 27 February 2024. <a href="https://pynufft.readthedocs.io/en/latest/tutor/basic_use.html" target="_blank">https://pynufft.readthedocs.io/en/latest/tutor/basic_use.html</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Greengard, Leslie; Lee, June-Yub (January 2004). "Accelerating the Nonuniform Fast Fourier Transform". SIAM Review. 46 (3): 443–454. Bibcode:2004SIAMR..46..443G. CiteSeerX 10.1.1.227.3679. doi:10.1137/S003614450343200X. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Marvasti, Farokh (2001). Nonuniform Sampling: Theory and Practice. New York: Springer. pp. 325–360. ISBN 978-1-4615-1229-5. <a href="978-1-4615-1229-5" target="_blank">978-1-4615-1229-5</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Dutt, Alok (May 1993). Fast Fourier Transforms for Nonequispaced Data (PDF) (PhD). Yale University. <a href="https://cpsc.yale.edu/sites/default/files/files/tr981.pdf" target="_blank">https://cpsc.yale.edu/sites/default/files/files/tr981.pdf</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Dutt, Alok; Rokhlin, Vladimir (November 1993). "Fast Fourier Transforms for Nonequispaced Data". SIAM Journal on Scientific Computing. 14 (6): 1368–1393. Bibcode:1993SJSC...14.1368D. doi:10.1137/0914081. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Potts, Daniel; Steidl, Gabriele (January 2003). "Fast Summation at Nonequispaced Knots by NFFT". SIAM Journal on Scientific Computing. 24 (6): 2013–2037. Bibcode:2003SJSC...24.2013P. doi:10.1137/S1064827502400984. <a href="/wiki/Gabriele_Steidl" target="_blank">/wiki/Gabriele_Steidl</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Boyd, John P (December 1992). "A fast algorithm for Chebyshev, Fourier, and sinc interpolation onto an irregular grid" (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. <a href="https://deepblue.lib.umich.edu/bitstream/2027.42/29694/1/0000026.pdf" target="_blank">https://deepblue.lib.umich.edu/bitstream/2027.42/29694/1/0000026.pdf</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>Fessler, J.A.; Sutton, B.P. (February 2003). "Nonuniform fast fourier transforms using min-max interpolation". IEEE Transactions on Signal Processing. 51 (2): 560–574. Bibcode:2003ITSP...51..560F. doi:10.1109/TSP.2002.807005. hdl:2027.42/85840. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>Ruiz-Antolín, Diego; Townsend, Alex (20 February 2018). "A Nonuniform Fast Fourier Transform Based on Low Rank Approximation" (PDF). SIAM Journal on Scientific Computing. 40 (1): A529 – A547. arXiv:1701.04492. Bibcode:2018SJSC...40A.529R. doi:10.1137/17M1134822. hdl:10902/13767. <a href="https://repositorio.unican.es/xmlui/bitstream/handle/10902/13767/ANonuniform.pdf" target="_blank">https://repositorio.unican.es/xmlui/bitstream/handle/10902/13767/ANonuniform.pdf</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> <li id="fn:18"><p>Greengard, Leslie; Lee, June-Yub (January 2004). "Accelerating the Nonuniform Fast Fourier Transform". SIAM Review. 46 (3): 443–454. Bibcode:2004SIAMR..46..443G. CiteSeerX 10.1.1.227.3679. doi:10.1137/S003614450343200X. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li> <li id="fn:19"><p>The Simons Foundation. "Mathematical definitions of transforms — finufft 2.2.0 documentation". finufft.readthedocs.io. Retrieved 27 February 2024. <a href="https://finufft.readthedocs.io/en/latest/math.html#math" target="_blank">https://finufft.readthedocs.io/en/latest/math.html#math</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li> <li id="fn:20"><p>PyNUFFT Services. "Basic use of PyNUFFT — PyNUFFT 2023.2.2 documentation". pynufft.readthedocs.io. Retrieved 27 February 2024. <a href="https://pynufft.readthedocs.io/en/latest/tutor/basic_use.html" target="_blank">https://pynufft.readthedocs.io/en/latest/tutor/basic_use.html</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></p></li> <li id="fn:21"><p>"NUFFT page". cims.nyu.edu. <a href="https://cims.nyu.edu/cmcl/nufft/nufft.html" target="_blank">https://cims.nyu.edu/cmcl/nufft/nufft.html</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></p></li> <li id="fn:22"><p>"NFFT". www.nfft.org. <a href="http://www.nfft.org/" target="_blank">http://www.nfft.org/</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></p></li> <li id="fn:23"><p>"MikaelSlevinsky/FastTransforms.jl". GitHub. 2019-02-13. <a href="https://github.com/MikaelSlevinsky/FastTransforms.jl" target="_blank">https://github.com/MikaelSlevinsky/FastTransforms.jl</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></p></li> <li id="fn:24"><p>"chebfun/chebfun". GitHub. 2019-02-07. <a href="https://github.com/chebfun/chebfun" target="_blank">https://github.com/chebfun/chebfun</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></p></li> </ol>