離散フーリエ変換
離散フーリエ変換（りさんフーリエへんかん、、DFT）とは離散化されたフーリエ変換であり、信号処理などで離散化されたデジタル信号の周波数解析などによく使われる。また偏微分方程式や畳み込み積分を効率的に計算するためにも使われる。離散フーリエ変換は（計算機上で）高速フーリエ変換(FFT)を使って高速に計算することができる。
離散フーリエ変換とは、複素関数 formula_1を複素関数formula_2に写す写像であって、次の式で定義されるものを言う。
ここで、Nは任意の自然数、 formula_3 はネイピア数、formula_4 は虚数単位 (formula_5)で、formula_6は円周率である。このとき、{formula_7}を標本点という。また、この変換を formula_8 という記号で表し、
のように略記することが多い。
この逆変換にあたる逆離散フーリエ変換（、IDFT）は
正規化係数（DFT は 1, IDFT は 1/"N"）や指数の符号は単なる慣習的なものであり、上式とは異なる式を扱うことがある。DFT と IDFT の差について、それぞれの正規化係数を掛けると 1 / "N" になることと、指数の符号が異符号であるということがだけが重要であり、根本的には同一の変換作用素と考えられる。DFT と IDFT の正規化係数を両方とも formula_9 にすると、両方ともユニタリ作用素（ユニタリ変換）になる。理論的にはユニタリ作用素にするのが好ましいが、実用上数値計算を行うときは上式のように正規化係数を1つにまとめて、スケーリングを一度に行うことが多い。
離散フーリエ変換はフーリエ変換を離散化したものであるので、フーリエ変換と同様の性質を持つ。
離散フーリエ変換においては、有限個の標本点しか使わないため、ある関数を離散フーリエ変換し、それを逆変換した場合に、標本点以外で元の関数と一致するとは限らない。
すなわち、複素関数ｆに対して、
により離散フーリエ変換を行い、それを逆変換したものをgとすると
は言えるが、その他の点でが言えるとは限らない。これを高周波の問題、あるいはエイリアシング(aliasing)という。
formula_10 は内積
に関し、formula_11が整数のとき直交基底である。
\right)
\left(e^{-i2\pi\frac{t'n}{N}}\right)
formula_12はクロネッカーのデルタ
formula_1 と formula_14 の畳み込みformula_15は次のように定義される。
ここでformula_16は次のような周期性を持つとする。
周期関数の畳み込みを離散フーリエ変換したものは、それぞれの離散フーリエ変換の積になる(畳み込み定理)。
つまり
畳み込み和を直接定義式を用いて計算すると "O"("N"²) の計算量が掛かる。しかし、上式より一旦 DFT をしてから掛算をして、そして IDFT で戻す方法もある。DFT の高速アルゴリズムである FFT を介してこのように計算すると "O"("N" log "N") の計算量で済む。
formula_1とformula_14の相互相関formula_19は以下のように定義される。
formula_16が上記の周期性を持てば、
応用上は、実数値関数を対象とすることが多いが、このとき、
(formula_21はformula_22の複素共役)。そのため出力formula_23の半分(formula_24)で全ての情報を持っていることになる。
デジタル画像処理では2次元変換が画像の周波数成分を解析するのに使われる。
変換は以下のように定義される。
そして逆変換は次のようになる。
2次元DFT は行列を用いて簡単に記述できる。
2次元DFT を行列計算によって以下のように変形できる。以下上式の 1 - 7 を解説すると、
formula_45の行はformula_25の"x"行目の行を1次元DFTしたものである。ゆえにformula_45はformula_25の各行の1次元DFTした結果の行ベクトルを集めたものになる。"F"="WF"における、"F"を後から掛ける作用素はformula_45の列の1次元DFTしたものと同じと考えて良い。
つまり、2次元DFT（2次元フーリエ変換も同様だが）はformula_25を、各行ごとに1次元DFTし、その結果をさらに各列ごとに1次元DFTする事と等価である。ここで、1次元DFTの計算はFFTのアルゴリズムで高速に計算できる。そのため実用上は2次元DFTも、2次元FFTとして計算される。
表中で、
formula_51
DFTは多くの広い分野で利用されている。ここでは、その中の一部を示しているだけに過ぎない。これらの応用は高速フーリエ変換(FFT)とその逆変換(IFFT)で高速に計算できることを前提としていて、定義通りにDFTを計算しているのではない。
信号"x"("t")を解析するのに使われる。ここで"t"は時間で[0,"T"]の範囲をとるものとする。例えば、音声信号の場合は、"x"("t")は時刻"t"での空気の圧力を表現することになる。
この信号は"N"個の等間隔の点で標本化されて、"x", "x", "x", ... , "x" の実数列になる。但し標本化の間隔を Δ"x"(="T"/"N") とすると "x"="x"("k" Δ"x") である。これのDFTである "f", ..., "f" をFFTで計算できる。ただし標本化定理からこれの半分("N"が偶数とすると、"f", ..., "f")は冗長であるので捨てるか無視する。
DFT から得られる |"f"|/"N" は信号の周波数 "j"/"T" 成分の振幅の半分の値であり、振幅スペクトルと呼ばれる。また、この偏角である arg("f") はこの周波数成分の位相を表す。また、|"f"|はパワースペクトルと呼ばれ、この周波数成分のエネルギーを表している。
"f"は信号"x"("t")のフーリエ級数の係数に相当するものと考えることができる。そのために、無限に広がるフーリエ級数計算を、有限のサンプル点に対しての DFT を使って近似するという形になる。連続信号の場合はこれをスペクトル推定(spectral estimation)と呼び、色々な推定法がある。(例えば、DFT が有限サンプル点を扱うことに起因するスペクトル漏れの弊害を少しでも和らげるために窓関数(窓))を使うことがよく行われる。)
信号処理の分野では周波数領域（フーリエ変換）で処理をすることも少なくない。例えば、画像の非可逆圧縮や音声圧縮技術などでは離散フーリエ変換の考えが用いられている。信号に対して DFT (実装上ではFFT) を行い、人間が知覚しづらい周波数成分の情報を取り除くことで、正味の情報量を削減（圧縮）する。最も単純な方法では、IDFTの際にその取り除いた周波数情報（フーリエ係数）を0にすることにより、通常のIDFTを実現する。実装の単純化（計算の効率化）のために、実数演算のみで可能な離散コサイン変換を使って2次元情報を圧縮した例がJPEGである。
大きな数や多項式のにおいて、DFTを使う高速なアルゴリズムとして1971年にショーンハーゲ・ストラッセン法が発見された。数字や多項式の係数の列は畳み込み演算の対象のベクトルと見なす。するとそれぞれのベクトルを DFT して、その結果同士を掛けて、そして逆変換することで掛算の結果が得られる（つまり畳み込み定理を使う）。2007年にショーンハーゲ・ストラッセン法より理論的に高速なアルゴリズム（）が見付かった。