非一様離散フーリエ変換

応用数学において、信号の非一様離散フーリエ変換（NUDFTまたはNDFT ）は、離散フーリエ変換または離散時間フーリエ変換に関連するフーリエ変換の一種ですが、入力信号は等間隔の点または周波数（またはその両方）でサンプリングされません。これは、シフトDFTの一般化です。信号処理、 ^[1]、磁気共鳴イメージング、^[2]、偏微分方程式の数値解法で重要な用途があります。 ^[3]

非均一サンプリングの一般化されたアプローチとして、NUDFT を使用すると、任意の周波数で有限長信号の周波数領域情報を取得できます。NUDFT を採用する理由の 1 つは、多くの信号が周波数領域でエネルギーを非均一に分散していることです。したがって、非均一サンプリング方式は、多くのデジタル信号処理アプリケーションでより便利で有用です。たとえば、NUDFT は、ユーザーが制御できる可変スペクトル解像度を提供します。

非一様離散フーリエ変換は、複素数の列を次のように定義される 別の複素数の列に変換する。${\displaystyle N}$${\displaystyle x_{0},\ldots ,x_{N-1}}$${\displaystyle X_{0},\ldots ,X_{N-1}}$

ここで、はサンプル点、は周波数です。 および の場合、式 ( 1 )は離散フーリエ変換に簡約されることに注意してください。 NUDFT には 3 つのタイプがあります。^[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}$

• 非一様離散フーリエ変換I型（NUDFT-I）は、一様サンプル点を使用するが、非一様（非整数）周波数を使用する。これは、等間隔の点で一般化フーリエ級数を評価することに相当する。これは、NDFT ^[5]または順方向NDFT ^{[6] [7]}としても知られている。${\displaystyle p_{n}=n/N}$${\displaystyle f_{k}}$
• 非一様離散フーリエ変換II型（NUDFT-II）は、一様（つまり整数）周波数を使用するが、サンプル点は非一様である。これは、不等間隔の点でフーリエ級数を評価することに相当する。これは、随伴NDFTとしても知られている。^{[7] [6]}${\displaystyle f_{k}=k}$${\displaystyle p_{n}}$
• タイプ III の非一様離散フーリエ変換 (NUDFT-III) は、非一様サンプル ポイントと非一様周波数の両方を使用します。これは、非等間隔のポイントで一般化フーリエ級数を評価することに相当します。NNDFT とも呼ばれます。${\displaystyle p_{n}}$${\displaystyle f_{k}}$

同様のNUDFTのセットは、式( 1 )のを代入することによって定義できます。ただし、均一な場合とは異なり、この代入は逆フーリエ変換とは無関係です。NUDFTの逆変換は別の問題であり、以下で説明します。 ${\displaystyle -i}$${\displaystyle +i}$

多次元NUDFTは、複素数の次元配列を、次のように定義される 別の複素数の次元配列に変換します。${\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} }}}$

ここで、はサンプル点、は周波数、およびは0からまでのインデックスの次元ベクトルです。タイプI、II、IIIの多次元NUDFTは、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)}$

NUDFT-IはZ変換として表現できる。^[8]長さのシーケンスのNUDFT-Iは ${\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,}$

ここで、は の Z 変換であり、は z 平面上の任意の異なる点です。サンプリング ポイントが単位円上に等間隔の角度で配置されている場合、NUDFT は DFT に簡約されることに注意してください。 ${\displaystyle X(z)}$${\displaystyle x[n]}$${\displaystyle \{z_{i}\}_{i=0,1,...,N-1}}$

上記を行列で表すと、

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

どこ

${\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}}.}$

ご覧のとおり、NUDFT-I は によって特徴付けられ、したがって点 によって特徴付けられます。 をさらに因数分解すると、点が別個であれば は非特異であることがわかります。 が非特異である場合、次のように一意の逆 NUDFT-I を取得できます。 ${\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} }$。

が与えられれば、ガウス消去法を使って を解くことができます。しかし、この方法の複雑さは です。この問題をより効率的に解くために、まず多項式補間によって直接決定します。 ${\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}$。

次に、上記の補間多項式の係数を示します。 ${\displaystyle x[n]}$

次数のラグランジュ多項式として表すと、 ${\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],}$

基本多項式は 次のとおりです。${\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}$。

ニュートン補間法で 表すと、${\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}),}$

ここで、 はに関する の番目の階の差商です。 ${\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 }$

ラグランジュ表現の欠点は、追加ポイントが含まれると補間多項式の次数が上がり、すべての基本多項式を再計算する必要が生じることです。ただし、ニュートン表現に含まれる追加ポイントには、さらに 1 つの項を追加するだけで済みます。

下三角法を使って解くことができます: ${\displaystyle \{c_{j}\}}$

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

どこ

${\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}}.}$

上記の式により、は操作内で計算できます。このように、ニュートン補間はラグランジュ補間よりも効率的ですが、後者は次のように変更する必要があります。 ${\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}$。

式（１）を単純に適用するとNUDFTを計算するアルゴリズムが得られるが、高速フーリエ変換（FFT）に基づくアルゴリズムも存在する。このようなアルゴリズムはNUFFTまたはNFFTと呼ばれ、オーバーサンプリングと補間、^{[9] [10] [11] [12]}最小最大補間、^[2]および低ランク近似に基づいて開発されている。^[13]一般に、NUFFTは、非一様問題をFFTを適用できる一様問題（または一様問題のシーケンス）に変換することでFFTを活用する。^[4] NUFFTを実行するためのソフトウェアライブラリは、1D、2D、および3Dで利用できる。^{[7] [6] [14] [15] [16] [17]}${\displaystyle O(N^{2})}$${\displaystyle O(N\log N)}$

NUDFT の用途は次のとおりです。

• デジタル信号処理
• 磁気共鳴画像
• 数値偏微分方程式
• セミラグランジアンスキーム
• スペクトル法
• スペクトル分析
• デジタルフィルタ設計
• アンテナアレイ設計
• デュアルトーンマルチ周波数（DTMF）信号の検出とデコード

• 離散フーリエ変換
• 高速フーリエ変換
• 最小二乗スペクトル解析
• ロンブ・スカーグル ピリオドグラム
• スペクトル推定
• 不均等な間隔の時系列

• 非一様フーリエ変換: チュートリアル。
• NFFT 3.0 – チュートリアル
• NUFFT ソフトウェア ライブラリ