実離散フーリエ変換(前編)-基底変換-
前編：ここ
中編：
実離散フーリエ変換(中編)-離散三角関数の直交性-
後編：
実離散フーリエ変換(後編)-実離散フーリエ変換の証明-
自然数$\mathbb{N}$は0を含まないものとする。
連続フーリエ変換は連続かつ非周期関数のフーリエ変換を指し、フーリエ変換は広義の、時間の関数から周波数の関数への変換を指すものとする。
はじめに
実離散フーリエ変換とは
離散フーリエ変換は離散時間の関数を離散周波数の関数に変換するものです。
有限のデータを扱うため、音声や画像などのデータ処理において重宝されます。
また、フーリエ変換は三角関数や複素指数関数の基底変換(後述)として捉えることができます。
この場合、連続関数や無限次元ベクトル空間であれば収束条件や積分と極限の入れ替えなどの解析的な議論が必要となるため、無限次元のフーリエ級数展開から連続フーリエ変換を導出するよりも、有限次元の離散フーリエ変換からフーリエ変換を導出した方が分かりやすいと思われます。
一方で、一般的に離散フーリエ変換は複素数を用いて以下のように表現されます。
関数$f(x)$の複素離散フーリエ変換は
\begin{align}
F(m)= \sum_{n=0}^{N-1}f(n) \exp(-i\dfrac{m}{N} n\tau)
\end{align}
複素離散逆フーリエ変換は
\begin{align}
f(n)= \dfrac{1}{N}\sum_{m=0}^{N-1}F(m) \exp(i\dfrac{m}{N} n)
\end{align}
フーリエ級数展開や連続フーリエ変換が実数から複素数に拡張したように、離散フーリエ変換も実数から考える方が直感的理解につながると思われます。
そこで、このシリーズでは離散フーリエ変換の実数表現、つまり実離散フーリエ変換を、基底変換として導出し、最後にフーリエ級数展開と複素離散フーリエ変換の対応について見ていきます。
このシリーズの道筋
- 数ベクトル空間・基底変換とは何かを説明する。(前編)
正規直交基底により任意のベクトルが展開できることなどを示す。 - 離散三角関数の直交性を示す。(中編)
前編の議論から離散三角関数が正規直交基底になることが示せる。 - 正規直交基底の離散三角関数から実離散フーリエ変換を導出し、フーリエ級数展開や複素離散フーリエ変換との対応を調べる。(後編)
数ベクトルと直交
$\mathbb{R}^n = \left\{ \begin{bmatrix} x_1 \\ x_2\\ \vdots \\ x_n \end{bmatrix} \middle| x_1, x_2, \cdots, x_n \in \mathbb{R} \right\} $とする。
$\mathbf{a}= \begin{bmatrix} a_1 \\ \vdots \\ a_n \end{bmatrix},\ \mathbf{b}= \begin{bmatrix} b_1 \\ \vdots \\ b_n \end{bmatrix} \in \mathbb{R}^n,\ k \in \mathbb{R}^n$に対して，和と実数倍を
$\mathbf{a}+\mathbf{b}= \begin{bmatrix} a_1+b_1 \\ \vdots \\ a_n+b_n \end{bmatrix},\ k\mathbf{a} =\begin{bmatrix} ka_1 \\ \vdots \\ ka_n \end{bmatrix},\ k\mathbf{b} =\begin{bmatrix} kb_1 \\ \vdots \\ kb_n \end{bmatrix}$
と定義したとき、$\mathbb{R}^n$を実$n$次元数ベクトル空間または単に数ベクトル空間といい、その各元を実$n$次元数ベクトル、または単に数ベクトルという。
$\mathbf{0} =\begin{bmatrix} 0 \\ \vdots \\ 0 \end{bmatrix}$を零ベクトルという
これから説明することは一般のベクトル空間でも定義できますが、情報を減らすために実離散フーリエ変換に関わる実$n$次元数ベクトル空間に絞って説明します。
数ベクトル$\mathbf{a}_1, \cdots, \mathbf{a}_m \in \mathbb{R}^n$と実数$c_1, \cdots, c_m \in \mathbb{R}$に対して
\begin{align}
\sum_{k=1}^{m}c_k \mathbf{a}_k
= c_1 \mathbf{a}_1 + \cdots c_n \mathbf{a}_n
\end{align}
を$\mathbf{a}_1, \cdots, \mathbf{a}_m$の一次結合という。
$\mathbf{a}_1, \cdots, \mathbf{a}_m$の一次結合で表されるベクトル全体の集合を$\mathbf{a}_1, \cdots, \mathbf{a}_m$のスパンといい、
\begin{align}
\mathrm{span}(\mathbf{a}_1, \cdots, \mathbf{a}_m)
=\left\{ \sum_{k=1}^{m}c_k \mathbf{a}_k \middle|
\mathbf{a}_1, \cdots, \mathbf{a}_m \in \mathbb{R}^n,\
c_1, \cdots, c_m \in \mathbb{R} \right\}
\end{align}
と表す。また、
\begin{align}
\sum_{k=1}^{m}c_k \mathbf{a}_k=0
\implies
c_1 = \cdots = c_n =0
\end{align}
となるとき、$\mathbf{a}_1, \cdots, \mathbf{a}_m$は一次独立であるという。
一次独立な数ベクトル$\mathbf{a}_1, \cdots, \mathbf{a}_n$に対して
\begin{align}
\sum_{k=1}^{n}c_k \mathbf{a}_k
=\sum_{k=1}^{n}d_k \mathbf{a}_k
\implies
c_k = d_k \ (1 \leq k \leq n,\ k \in \mathbb{N})
\end{align}
となる。つまり一次独立なら一次結合の表し方は一通りしかない。
仮定より
\begin{align}
\sum_{k=1}^{n}c_k \mathbf{a}_k - \sum_{k=1}^{n}d_k \mathbf{a}_k
= \sum_{k=1}^{n}(c_k-d_k) \mathbf{a}_k=0
\end{align}
$\mathbf{a}_1, \cdots, \mathbf{a}_n$は一次独立であるから定義より$c_k-d_k=0$
よって$c_k=d_k$
数ベクトル$\mathbf{a}_1, \cdots, \mathbf{a}_n$が一次独立ならば$\mathbf{a}_m \neq \mathbf{0}\ (0 \leq m \leq n)$
数ベクトル$\mathbf{a}_1, \cdots, \mathbf{a}_n$が一次独立であるとする。
$\mathbf{a}_j = \mathbf{0}$となる$j$が少なくとも一つ存在すると仮定すると、
\begin{align}
\sum_{k=1}^{n}c_k \mathbf{a}_k=0
\end{align}
としたときに$c_j \neq 0$が解の一つになるから、$\mathbf{a}_1, \cdots, \mathbf{a}_n$が一次独立であることと矛盾する。よって、
$\mathbf{a}_m \neq \mathbf{0}\ (0 \leq m \leq n)$
数ベクトル$\mathbf{a}=(a_1, \cdots a_n),\ \mathbf{b}=(b_1, \cdots b_n) \in \mathbb{R}^n$に対して
\begin{align}
\mathbf{a} \cdot \mathbf{b}=\sum_{i=1}^{n}a_i b_i
\end{align}
を$\mathbf{a}$と$\mathbf{b}$の内積という。また、
\begin{align}
\|\mathbf{a}\| =\sqrt{\mathbf{a} \cdot \mathbf{a}}= \sqrt{\sum_{i=1}^{n}a_i^2}
\end{align}
を$\mathbf{a}$のノルムという。
$\mathbf{a} \cdot \mathbf{b}=0$となるとき、$\mathbf{a}$と$\mathbf{b}$が直交するという。
数ベクトル$\mathbf{a}_1, \cdots, \mathbf{a}_n$が互いに直交するとき、つまり
\begin{align}
i \neq j \implies \mathbf{a}_i \cdot \mathbf{a}_j=0
\end{align}
となるとき、$\{ \mathbf{a}_1, \cdots, \mathbf{a}_n \}$を直交系という。
また、基底$\mathbf{a}_1, \cdots, \mathbf{a}_n$が互いに直交してそれぞれのノルムが1のとき、つまり
\begin{align}
\mathbf{a}_i \cdot \mathbf{a}_j=
\begin{cases}
0 & (i \neq j) \\
1 & (i = j)
\end{cases}
\end{align}
となるとき、$\{ \mathbf{a}_1, \cdots, \mathbf{a}_n \}$を正規直交系という。
数ベクトル$\mathbf{a}_1, \cdots,\mathbf{a}_n$が直交系でそれぞれ零ベクトルでなければ線形独立である。
$$\sum_{k=1}^{n}c_k \mathbf{a}_k=\mathbf{0}$$とおき、係数$c_k\ (1 \leq k \leq n)$が全て$0$になることを示す。
一般に任意の$m\ (1 \leq m \leq n)$に対して$\mathbf{a}_m \cdot \mathbf{0}=0$となるから
\begin{align}
0
&= \mathbf{a}_m \cdot \mathbf{0}\\
&= \mathbf{a}_m \cdot \sum_{k=1}^{n} c_k \mathbf{a}_k\\
&= \sum_{k=1}^{n} c_k (\mathbf{a}_m \cdot \mathbf{a}_k)
\end{align}
数ベクトル$\mathbf{a}_1, \cdots , \mathbf{a}_{n}$が互いに直交するとき、$k \neq m$ならば$\mathbf{a}_m \cdot \mathbf{a}_k=0$であるため、
\begin{align}
0 &= \sum_{k=1}^{n} c_k (\mathbf{a}_m \cdot \mathbf{a}_k)\\
&= c_m (\mathbf{u}_m \cdot \mathbf{u}_m)
\end{align}
仮定より$\mathbf{a}_m$は零ベクトルでないため、$(\mathbf{a}_m \cdot \mathbf{a}_m) \neq 0$より
$c_k = 0 \quad (1 \leq k \leq n)$
よって$\mathbf{a}_1, \cdots , \mathbf{a}_{n}$は線形独立である。
基底変換
数ベクトル$\mathbf{a}_1, \cdots, \mathbf{a}_n \in \mathbb{R}^n$が
- 一次独立かつ
- 任意の数ベクトル$\mathbf{x} \in \mathbb{R}^n$をその一次結合で表せる、
つまり$\mathbf{a}_1, \cdots, \mathbf{a}_n$のスパンが$\mathbb{R}^n$となるとき
$\{ \mathbf{a}_1, \cdots, \mathbf{a}_n \}$を$\mathbb{R}^n$の基底という。
基底の一次結合による数ベクトルの表し方は一通りしかない。
基底は一次独立であるから補題1より明らか。
任意の数ベクトルを、ある基底の一次結合から別の基底の一次結合で表すとき、これを基底変換という。
$\{ \mathbf{a}_1, \cdots, \mathbf{a}_n \}$が直交系かつ基底となるとき、$\{ \mathbf{a}_1, \cdots, \mathbf{a}_n \}$を直交基底という。
また、$\{ \mathbf{a}_1, \cdots, \mathbf{a}_n \}$が正規直交系かつ基底となるとき、$\{ \mathbf{a}_1, \cdots, \mathbf{a}_n \}$を正規直交基底という。
任意のベクトル$\mathbf{x} \in \mathbb{R}^n$は、$\mathbb{R}^n$の正規直交基底$\{ \mathbf{a}_1, \cdots, \mathbf{a}_n \}$によって次のように表せる。
\begin{align}
\mathbf{x} = \sum_{i=1}^{n}(\mathbf{a}_i \cdot \mathbf{x})\mathbf{a}_i
\end{align}
このように与えられたベクトル$\mathbf{x}$を正規直交基底$\{ \mathbf{a}_1, \cdots, \mathbf{a}_n \}$の一次結合で表すことを、$\mathbf{x}$の$\mathbf{a}_1, \cdots, \mathbf{a}_n$による展開という。
$\{ \mathbf{a}_1, \cdots, \mathbf{a}_n \}$が$\mathbb{R}^n$の基底であるため、任意のベクトル $\mathbf{x} \in \mathbb{R}^n$を次のように線形結合で表せる。
\begin{align}
\mathbf{x} = \sum_{i=1}^{n} c_i \mathbf{a}_{i}\quad (c_1, \cdots, c_m \in \mathbb{R})
\end{align}
さらに$\{ \mathbf{a}_1, \cdots, \mathbf{a}_n \}$は正規直交基底であるため、$\mathbf{a}_j\ (1 \leq j \leq n)$と$\mathbf{x}$の内積は次のようになる。
\begin{align}
\mathbf{a}_j \cdot \mathbf{x}
&= \mathbf{a}_j \cdot \sum_{i=1}^{n} c_i \mathbf{a}_i\\
&= \sum_{i=1}^{n} c_i (\mathbf{a}_j \cdot \mathbf{a}_{i} ) \\
&= \sum_{i=1}^{n} c_i \delta_{j,i}\\
&= c_j
\end{align}
よって$c_i=\mathbf{a}_i \cdot \mathbf{x} \ (1 \leq i \leq n)$となるから$\mathbf{x}$は次のように表せる。
\begin{align}
\mathbf{x} = \sum_{i=1}^{n} c_i \mathbf{a}_{i}
=\sum_{i=1}^{n}(\mathbf{a}_i \cdot \mathbf{x})\mathbf{a}_i
\end{align}
数ベクトル$\mathbf{a}_1, \mathbf{a}_2, \cdots,\mathbf{a}_M$のスパンを$V$とする。つまり
$V=\rm{span}(\mathbf{a}_1, \mathbf{a}_2, \cdots,\mathbf{a}_M)$
$\mathbf{b}_1, \mathbf{b}_2, \cdots,\mathbf{b}_N \in V \ (N \leq M)$が一次独立のとき、$\mathbf{a}_1, \mathbf{a}_2, \cdots,\mathbf{a}_M$の内、ある$N$個を$\mathbf{b}_1, \mathbf{b}_2, \cdots,\mathbf{b}_N$に置き換えてもそれらのスパンが$V$となる。
つまり、$1 \leq i_{N+1}<\cdots< i_M\leq M$とすると$V=\rm{span}(\mathbf{b}_1,\cdots,\mathbf{b}_N, \mathbf{a}_{i_{N+1}}, \mathbf{a}_{i_M})$
数学的帰納法で示す。
まず$N=1$の場合を考える。
$\mathbf{b}_1$が一次独立であるから補題2より$\mathbf{b}_1 \neq \mathbf{0}$
$\mathbf{a}_1, \mathbf{a}_2, \cdots,\mathbf{a}_M$のスパンは$V$だから$\mathbf{b}_1 \in V$を次のように表せる。
$$\mathbf{b}_1=\sum_{m=1}^{M}c_m \mathbf{a}_m$$
仮に$c_m=0\ (1 \leq m \leq M)$とすると$\mathbf{b}_1 \neq \mathbf{0}$と矛盾するから$c_m \neq 0$となる$m$が存在する。
$c_k \neq 0$とすると、$k$以外の番号を$1 \leq i_2 < \cdots < i_M \leq M$となるように定める。
このとき、$\mathbf{a}_1$を次のように$\mathbf{b}_1$と$\mathbf{a}_{i_m}$($2 \leq m \leq M$)の線形結合で表せる。
\begin{align} \mathbf{b}_1 &= c_k \mathbf{a}_k + \sum_{m=2}^{M}c_{i_m} \mathbf{a}_{i_m}\\ \mathbf{a}_k &= \dfrac{1}{c_k} \left( \mathbf{b}_1 - \sum_{m=2}^{M}c_{i_m} \mathbf{a}_{i_m}\right) \end{align}
よって
\begin{align}
V&=\rm{span}(\mathbf{a}_1, \mathbf{a}_2, \cdots,\mathbf{a}_M)\\
&=\rm{span}(\mathbf{a}_k, \mathbf{a}_{i_2}, \cdots,\mathbf{a}_{i_M})\\
&=\rm{span}(\mathbf{b}_1, \mathbf{a}_{i_2}, \cdots,\mathbf{a}_{i_M}, \mathbf{a}_{i_2}, \cdots,\mathbf{a}_{i_M})\\
&=\rm{span}(\mathbf{b}_1, \mathbf{a}_{i_2}, \cdots,\mathbf{a}_{i_M})
\end{align}
より、$\mathbf{b}_1$と$\mathbf{a}_k$を置き換えられた。
次に$N\geq 2$で$N-1$個のときに成り立つとして、$N$個でも成り立つことを示す。仮定より
\begin{align}
\mathbf{b}_N
&=\rm{span}(\mathbf{b}_1,\cdots,\mathbf{b}_{N-1}, \mathbf{a}_{i_N}, \mathbf{a}_{i_M})\\
&=\sum_{n=1}^{N-1}(c_n \mathbf{b}_n) + \sum_{m=N}^{M}(d_{i_m} \mathbf{a}_{i_m})
\end{align}
$d_{i_m}=0\ (N \leq m \leq M)$と仮定すると、
\begin{align}
&\mathbf{b}_N
=\sum_{n=1}^{N-1}(c_n \mathbf{b}_n)\\
&\mathbf{b}_N - \sum_{n=1}^{N-1}(c_n \mathbf{b}_n) = 0\\
\end{align}
これは$\mathbf{b}_1, \cdots , \mathbf{b}_N$が一次独立であることと矛盾するため、$d_{k}=0$となる$k$が少なくとも一つ存在する。
$k$を除く$i_N$から$i_M$を$1 \leq j_{N+1} < \cdots < j_M \leq M$となるように番号を定めると、$\mathbf{a}_k$を次のように$\mathbf{b}_n (1 \leq n \leq N)$と$\mathbf{a}_{j_m}$($N+1 \leq m \leq M$)の線形結合で表せる。
\begin{align}
\mathbf{b}_N
&= \sum_{n=1}^{N-1}(c_n \mathbf{b}_n)
+ d_k \mathbf{a}_{k}
+ \sum_{m=N+1}^{M}(d_{i_m} \mathbf{a}_{i_m})\\
\mathbf{a}_{k}
&= \dfrac{1}{d_k}\left(
\mathbf{b}_N -
\sum_{n=1}^{N-1}(c_n \mathbf{b}_n)
- \sum_{m=N+1}^{M}(d_{i_m} \mathbf{a}_{i_m})
\right)
\end{align}
よって
\begin{align}
V
&=\rm{span}(\mathbf{b}_1,\cdots,\mathbf{b}_{N-1},
\mathbf{a}_{i_{N}}, \cdots,\mathbf{a}_{i_M})\\
&=\rm{span}(\mathbf{b}_1,\cdots,\mathbf{b}_{N-1},
\mathbf{a}_{k},
\mathbf{a}_{j_{N+1}}, \cdots,\mathbf{a}_{j_M})\\
&=\rm{span}(\mathbf{b}_1,\cdots,\mathbf{b}_{N-1},
\mathbf{b}_{N},
\mathbf{b}_1,\cdots,\mathbf{b}_{N-1},
\mathbf{a}_{j_{N+1}}, \cdots,\mathbf{a}_{j_M},
\mathbf{a}_{j_{N+1}}, \cdots,\mathbf{a}_{j_M})\\
&=\rm{span}(\mathbf{b}_1,\cdots,\mathbf{b}_{N-1},
\mathbf{b}_{N},
\mathbf{a}_{j_{N+1}}, \cdots,\mathbf{a}_{j_M})\\
\end{align}
よって$\mathbf{b}_N$と$\mathbf{a}_k$を置き換えられた。
数学的帰納法より、全ての$1 \leq N \leq M$で示された。
$N$個の$N$次ベクトルは線形独立なら$N$次ベクトル空間の基底になる。
定理5の取り換え定理で$\mathbf{a}_m$を$N$次基底ベクトルとして$\mathbf{b}_n$を$N$個の$N$次ベクトルとすると、基底になることが分かる。
$N$個の$N$次ベクトルは互いに直交するなら$N$次ベクトル空間の基底になる。
補題3と補題7より明らか
中編で離散三角関数の直交性を示し、命題7より基底となることを示します。
参考文献
この記事を高評価した人
この記事に送られたバッジ
投稿者
