On the eigenstructure of dft matrices(in japanese only)
2 likes7,209 views
DFT 行列の固有値とその構造について Signal processing magazine 2011/03 の記事紹介です。
![DFT行列
? （Discrete) Fourier Transformとは
? 時間領域から周波数領域への直交変換
exp( 2 ) ( )fX i ft x t dtπ= ?? [ ] exp( 2 ) [ ]
H
f
X f i fn x nπ= ?
=
?
a x有限?離散化
[exp( 2 0),...,exp( 2 ( 1))]
2 {0,2 / , ,2 ( 1) / }
f N i f i f N
f N N N
π π
π π π
= ?
= … ?
a ?
周波数ベクトル
まとめて
0 ( 1)/, ,...,H
N N?
? ?= = ? ?X F x F a a
DFT行列
要素で書くと
k, n = {0, …, N-1}](https://image.slidesharecdn.com/ontheeigenstructureofdftmatrices-150206005835-conversion-gate01/85/On-the-eigenstructure-of-dft-matrices-in-japanese-only-3-320.jpg)
![Fの固有値
? J=F2を考える
? これはpermutation matrix（というか、要素
をひっくり返す行列) x[n] -> x[(-n)N]
? であるので、JJは、 (-(-n)N )N=nなので、
JJ=I
(?)Nはmod(?, N)](https://image.slidesharecdn.com/ontheeigenstructureofdftmatrices-150206005835-conversion-gate01/85/On-the-eigenstructure-of-dft-matrices-in-japanese-only-5-320.jpg)
More Related Content
Viewers also liked (20)
On the eigenstructure of dft matrices(in japanese only)
- 1. 社内教育用 鈴木幸一郎 ON THE EIGEN-STRUCTURE OF DFT MATRICES BY
- 2. やること ? 元ネタ ? Mar 2011のSignal Prcessing Magazine内 記事 ? DFT行列と遊んでみよう
- 3. DFT行列 ? （Discrete) Fourier Transformとは ? 時間領域から周波数領域への直交変換 exp( 2 ) ( )fX i ft x t dtπ= ?? [ ] exp( 2 ) [ ] H f X f i fn x nπ= ? = ? a x有限?離散化 [exp( 2 0),...,exp( 2 ( 1))] 2 {0,2 / , ,2 ( 1) / } f N i f i f N f N N N π π π π π = ? = … ? a ? 周波数ベクトル まとめて 0 ( 1)/, ,...,H N N? ? ?= = ? ?X F x F a a DFT行列 要素で書くと k, n = {0, …, N-1}
- 5. Fの固有値 ? J=F2を考える ? これはpermutation matrix（というか、要素 をひっくり返す行列) x[n] -> x[(-n)N] ? であるので、JJは、 (-(-n)N )N=nなので、 JJ=I (?)Nはmod(?, N)
- 6. Fの固有値 ? Fの固有ベクトルの一つをekとおくと、 2 4 4 4 , ( ) , 1 {1, 1, , } k k k k k k k k k k k k k i i λ λ λ λ λ λ = = = = = = = ? ? kFe e FFe F e e F e e e であるので こうなって Fの固有値はNがどれだけ増えようともこの4つだけ！ でもそう言われればそんな気もする なんとなくだけど。。。
- 7. それぞれの固有値がSPANする空間 を考えよう ? Fをスペクトル展開 ? 固有値別に分類。E1, E2,E3,E4 ? それぞれへの射影行列はPi=EiEi H、だけどこい つはそれぞれのiで直交しない。。。Fは正値 対称じゃないから。。。 ? 気持ちわるいので別の方法を考える。
- 8. ケイリー?ハミルトン的な展開 4 1 1 1 0 ( 1)( 1)( )( ) 0 k i ii i λ λ λ λ λ? ? ? = ? + ? + = 前掲の特性多項式=0 1( )p λ なる多項式として、 1( ) ( 1)( )( ) / 4p i iλ λ λ λ= + ? + を考える 1 3 2 ( 1)( )( ) / 4 ( ) / 4 i i= + ? + = + + + P F F F F F F I λをFに置き替えて ?P1は１以外の固有値を持つ固有ベクトルと直交する！ ?P1=P1 H, P1P1=P1 ??e1:Fe1=e1にて、P1e1=e1 P1はE1への射影行列！ スペクトル展開なしでできた！ 林修に似とるな。。
- 9. 他の固有値についても とできる 4 1 1 1 0 ( 1)( 1)( )( ) 0 k i ii i λ λ λ λ λ? ? ? = ? + ? + = ← これを使うと
- 10. その性質（ざっと） ■ さっきやった ■ これも ■ Fが直交変換であることを考えると、 まーそりゃそーだろう ■ 固有ベクトルにバラして考えると、 そりゃそうなるわな ■ P1とP-1でローパス(正解じゃないが)！ 確かに！！ ■ PiとP-iでハイパス(正解じゃないが) ！ なるほど！！
- 11. さらにまとめると 任意N次ベクトル x Forward と backwardで引き算 Forward と backwardで足し算 こんな風にそれぞれの固有値の張る空間へ射影されます BCの行列もこんな風にまとめられる、、、と面白いな。。。 x Jx
- 12. 固有ベクトルの本数は？ ? {1,-1,i,-i}な固有値があることはわかったけど、 じゃあそれぞれ何本あるの？ ? DFT matrix って別に次元は任意だし。。。 ? 2nな必要ないし。。。
- 14. 固有ベクトルは？ ? Fからは直で正規直交な固有ベクトルを求め るのは難しい ? projection matrix Pkを直交化する EiはP1内で正規直交で、Ei≠i HEi=0！
- 15. CONVENTIONAL DFT からの拡張 ? Offset DFT ? 特別なケースのみ固有値についてよく知ら れている ? 多次元の場合 ? 個別にやっておk
- 16. 他の変換との関係 ? Hartley transform ? Fractional Fourier Transform (Fのsqrt) ? F1/2=P1+iP2+(1+i)/2Pi+(1-i)/2P-i とすると、 F1/2F1/2=F フーリエ Hartley 恒等 flipud
- 17. まとめ ? DFT行列の性質 ? 単なる直交変換と思いきや、興味深い幾何学的な 性質を持つ ? 興味深すぎてついていけない。。。 ? DFTライクな変換はDFT行列のprojection matricesに帰着することで変換の直感的な理解を 与えることができる(ことがある）。 ? Hadamard変換もきっとできる、、、か？ ? いやちょっとムリかもな。。