Consider processing a signal
x∈ℂN
x
N
with system represented by a normal matrix
A
A
y=Ax
y
A
x
(1)
Now consider representation
A=VΛVH
A
V
Λ
V
(3)
This is implemented by a three-step procedure:
y=Ax=VΛVHx
y
A
x
V
Λ
V
x
(4)
-
α=VHx
α
V
x
This computes the coefficients
α
α that build up
x
x in terms of eigenbasis
vi
v
i
:
x=Vα
x
V
α
(ie:
VH
V
takes
x x from the
"time-domain" to the "eigenbasis domain".
-
Λα
Λ
α
with
Λ
Λ a diagonal matrix
Λ=
λ
0
0000
λ
1
0000
...
...
000...
λ
N
-
1
Λ
λ
0
0
0
0
0
λ
1
0
0
0
0
...
...
0
0
0
...
λ
N
-
1
ie: we just do element-wise multiplication
λ
i
α
i
λ
i
α
i
(super easy and no coupling
between
α
i
α
i
's)
-
VΛα=y
V
Λ
α
y
takes the vector
Λα
Λ
α
back to the time-domain.
- Once we transform
x x to the eigenbasis
domain of
A A, we can perform an
operation equivalent to
A A but
independently on each
α
i
α
i
.
- This works for any normal matrix
A
A.
- Most of the systems studied in DSP are "linear
shift-invariant":
- all correspond to normal matrices
- all share the same
V
V: DFT basis
All LSI processing
y=Ax
y
A
x
can be done through:
-
α=fftx
α
fft
x
-
α
~
=λα
α
~
λ
α
where
λ
λis diagonal of eigen matrix
Λ
Λ
-
y=ifft
α
~
y
ifft
α
~
The Cost:
- Step 1:
ONlogN
O
N
N
- Step 2:
ON
O
N
- Step 3:
ONlogN
O
N
N
- total:
ONlogN
O
N
N
ONlogN>ON2
O
N
N
O
N
2
(5)
ie: It is faster/more efficient than
y=Ax
y
A
x
directly!!!
A=VΛVH=v0v1v2...v
N
-
1
λ
0
0000
λ
1
0000
...
...
000...
λ
N
-
1
VH0VH1VH2...VH
N
-
1
A
V
Λ
V
v
0
v
1
v
2
...
v
N
-
1
λ
0
0
0
0
0
λ
1
0
0
0
0
...
...
0
0
0
...
λ
N
-
1
V
0
V
1
V
2
...
V
N
-
1
(6)