Fourier analysis (MS-C1420)

(1)

Fourier analysis (MS-C1420)

Ville Turunen

Aalto University

15.10.2013

Ville Turunen Fourier analysis (MS-C1420)

(2)

Classification of signals

In this course, we divide signals into two classes:

(A) Analog s :R→C (continuous time t∈R), (D) Digital s :Z→C (discrete time t ∈Z).

Moreover, we split these classes into two parts: a signal can be either (0) non−periodic

or (1) periodic: s(t+p) =s(t).

We shall study the connections between cases (A0),(A1),(D0),(D1).

Fourier methods in this course:

Fourier integrals (A0), Fourier coefficients (A1), Fourier series (D0), DFT or FFT (D1).

Examples: sound, pictures, video; physical measurements;

technology and sciences (1-dimensional signals in these notes).

(3)

Reminder: operations with complex numbers

Identify the point(x,y)∈R×Rin plane

and the complex numberx +iy ∈C, where iis the imaginary unit.

Interpretation: real numberx ∈Ris same asx +i0∈C. Real part Re(x +iy) :=x ∈R.

Imaginary part Im(x +iy) :=y ∈R.

Complex conjugate (x +iy)^∗ =x +iy :=x −iy ∈C. Absolute value |x +iy|:= (x²+y²)^1/2∈R⁺. Operations: e.g.−(a+ib) :=−a+i(−b) and

(a+ib) + (x +iy) := (a+x) +i(b+y), (a+ib)(x +iy) := (ax−by) +i(ay+bx), especiallyi² = (0+i1)² = (0+i1)(0+i1) =−1.

Euler’s formulaeît=cos(t) +isin(t), and theneî(α+β)=eîαeîβ.

(4)

Analog non-periodic world (A0)

Continuous time(t∈R) signals :R→C has “energy”

E(s) :=ksk² = Z

R

|s(t)|² dt = Z ∞

−∞

|s(t)|² dt. (1) Denotes ∈L²(R) ifksk<∞.

For example,t∈Rtime (or position), and s(t)∈C pressure/temperature/luminosity/position/wave function...

TheFourier (integral) transformof signals :R→C is signal F_R(s) =bs :R→C,

bs(ν) :=

Z

R

e^−i2πt·ν s(t) dt = Z +∞

−∞

e^−i2πt·ν s(t) dt. (2) Variableν ∈R is called “frequency”.

Notice that|bs(ν)| ≤ Z

R

|s(t)|dt.

(5)

Example: differentiation and Fourier transform

Fourier transform changes differentiation to polynomial

multiplication (and vice versa), because ifr(t) =t s(t) jabr = t sc then

bs⁰(ν) = −i2π t sc(ν), (3) sb⁰(ν) = +i2πνbs(ν). (4) Let us prove the latter formula (assumings(t)→0 as|t| → ∞):

cs⁰ (ν) =

Z

R

s⁰(t)e^−i2πt·ν dt

integrate by parts

= −

Z

R

s(t) d

dte^−i2πt·ν dt

= −

Z

R

s(t)e^−i2πt·ν(−i2πν) dt

= +i2πνbs(ν).

(6)

Example: Fourier transform of Gaussian

Gauss’ normal distributionϕµ,σ

(meanµ∈R, standard deviation σ >0):

ϕµ,σ(t) := 1

√2π σ exp −1 2

t−µ σ

2! .

Lets(t) :=ϕ0,σ(t), so that

s⁰(t) = −t σ² s(t)

previous example

=⇒ i2πνbs(ν) = 1

i2πσ²bs⁰(ν)

⇐⇒ bs⁰(ν) =−(2πσ)²νbs(ν)

⇐⇒ bs(ν) =bs(0)e^−2(πσν)². Now we must findbs(0)...

(7)

... Gaussian example continues...

bs(0) =

Z

R

s(t) dt

=

Z

R

Z

R

s(t)s(u) dt du 1/2

=

Z

R

Z

R

1

2πσ²e^−(t²^+u²^)/(2σ²⁾ dt du 1/2

polar coordinates

=

Z ∞ 0

Z 2π 0

1

2πσ²e^−r²^/(2σ²⁾ rdθdr 1/2

=

Z ∞ 0

r

σ²e^−r²^/(2σ²⁾ dr 1/2

= 1, where we changed to the polar coordinates(r, θ), where (t,u) = (rcos(θ),rsin(θ)). Thus

[ϕ0,σ(ν) =e^−2(πσν)². (5)

(8)

Normal distribution and point values of signal

We calculated ϕ0,σ(t) := 1

√2π σe^−(t/σ)²^/2 =⇒ ϕd0,σ(ν) =e^−2(πσν)², so that for a “nice enough” s :R→C, we have

s(t) = lim

0<σ→0

Z

R

s(u) ϕ0,σ(u−t) du

= lim

0<σ→0

Z

R

s(u) Z

R

e−i2π(u−t)·ν e^−2(πσν)² dν du

= lim

0<σ→0

Z

R

e^−2(πσν)² Z

R

s(u)e−i2π(u−t)·ν du dν

= lim

0<σ→0

Z

R

e^−2(πσν)² bs(ν) e^+i2πt·ν dν

= Z

R

bs(ν)e^+i2πt·ν dν.

(9)

Inverse Fourier transform

We just found that the Fourier transform bs(ν) =

Z

R

s(t)e^−i2πt·ν dν. (6) has Fourier inverse transform

s(t) = Z

R

bs(ν)e^+i2πt·ν dν. (7) By these formulas, we can present signals

as well in timet as in frequencyν, whatever is most convenient!

(10)

Vector space of signals

Given signalsr,s :R→C and scalarλ∈C, we obtain new signalsr+s, λs :R→Cby

(r+s)(t) = r(t) +s(t), (λs)(t) = λs(t).

The space of “all signals” is a vector space, withinner product

hr,si= Z

R

r(t)s(t) dt ∈ C, andnorm

ksk=p

hs,si= Z

R

|s(t)|²dt 1/2

∈ R⁺.

Remember: energy isksk² =hs,si.

(11)

Fourier transform preserves energy

Inner product between signalsr,s :R→Cis hr,si:=

Z

R

r(t) s(t) dt ∈ C. Fourier transform preserves this inner product, because

hbr,bsi = Z

R

br(ν)bs(ν) dν

= Z

R

br(ν) Z

R

e^−i2πt·ν s(t) dt dν

= Z

R

Z

R

e^+i2πt·ν br(ν) dν s(t) dt

= Z

R

r(t)s(t) dt = hr,si.

Puttingr =s, we see that Fourier transform preserves energy:

kbsk²=ksk². (8)

(12)

Symmetries of time and frequency

Time translationof signals :R→Cby time-lagp ∈Ris signal T_ps :R→C, where

T_ps(t) :=s(t−p). (9) Frequency modulationof s :R→C by frequency-lagα∈Ris signalM_αs :R→C, where

M_αs(t) :=e^+i2πt·αs(t). (10) After Fourier transforms:Md_αs =T_αbs andTdps =M−pbs, that is

Md_αs(ν) = T_αbs(ν), Tdps(ν) = M−pbs(ν).

(13)

Integral operators

We want to transform input signals :R→C to output signalLs =L(s) :R→C.

SupposeLis linear, i.e.

L(r+s) = L(r) +L(s) and L(λs) = λL(s)

for all signalsr,s :R→Cand constantsλ∈C. Linear transformL presented as anintegral operator:

Ls(t) = Z

R

K_L(t,u) s(u) du, (11) whereK_L is thekernel ofL.

Remark: integral operatorLhas “essentially unique” kernelK_L!

(14)

Time-invariant operators

Let operatorLbe time-invariant:T_pL=LT_p for allp ∈R, i.e.

T_pLs(t) =LT_ps(t) (12) for all signalss :R→Cand for all times t,p∈R;

in other words,L=T−pLT_p, which means Z

R

K_L(t,u) s(u) du = Ls(t) = T−pLT_ps(t) = LT_ps(t+p)

= Z

R

K_L(t+p,u) T_ps(u) du

= Z

R

K_L(t+p,u) s(u−p) du

= Z

R

K_L(t+p,u+p) s(u) du.

ThusK_L(t,u) =K_L(t+p,u+p) for all p,t,u ∈R, especially K_L(t,u) =K_L(t−u,0) =r(t−u) for some signalr :R→C...

(15)

Convolution

Convolutionof signalsr,s :R→Cis signalr∗s :R→Cgiven by r∗s(t) :=

Z

R

r(t−u) s(u) du. (13) Remark: time-invariant operatorLis of form Ls(t) =r∗s(t), where its kernel satisfiesK_L(t,u) =r(t−u).

Exercise:show that

rd∗s =br bs, (14)

that is

rd∗s(ν) =br(ν)bs(ν).

Thus “convolution in time” is “multiplication in frequency”.

This is one of the most important properties in Fourier analysis!

(16)

Convolution smoothing

r∗s is smooth ifr is smooth:

(r∗s)⁰ =r⁰∗s, (15) because

(r∗s)⁰(t) = d dt

Z

R

r(t−u)s(u)du = Z

R

r⁰(t−u)s(u)du =r⁰∗s(t).

Example:

ϕσ(t) := 1

√2π σe^−(t/σ)²^/2 =⇒ ϕcσ(ν) =e^−2(πσν)²

=⇒ ϕ\_σ∗s(t) = ϕc_σ(ν)bs(ν)

= e^−2(πσν)² bs(ν)

0<σ→0

−→ bs(ν).

(17)

Dirac delta signalδp at timep∈Rsatisfies Z

R

s(t)δp(t) dt=s(p) (16) for all continuous signalss :R→C.

Interpretation: Dirac deltaδp is the sudden unit impulse at timep, δ_p= lim

0<σ→0ϕ_p,σ. Fourier transform of Dirac delta:

δbp(ν) = Z

R

e^−i2πt·ν δp(t) dt =e^−i2πp·ν. Remark: Energy

kδ_pk² =kδbpk²= Z

R

|e^−i2πp·ν|² dν= Z

R

1dν =∞.

δ_p cannot be a function in any ordinary sense! We may think that δp(t) =0 if t 6=p, but writingδp(p) =∞ would be dubious! Such a weird entityδp is called a(tempered) distribution.

(18)

Fourier meets Dirac:

s(t) = Z

R

e^+i2πt·ν bs(ν)dν

= Z

R

Z

R

e^{i2π(t−u)·ν} s(u)du dν

= Z

R

Z

R

e^{i2π(t−u)·ν} dν

s(u) du

= Z

R

δ0(t−u)s(u) du

= δ0∗s(t),

as it should be. More generally,δ_p∗s =T_ps: δp∗s(t) =

Z

R

δp(t−u) s(u) du

= s(t−p) = T_ps(t).

(19)

Fourier integral in dimension d ∈ Z

⁺

= {1, 2, 3, 4, 5, · · · }

Fourier transformbs :R^d →Cfor signals :R^d →Cis given by bs(ν) :=

Z

R^d

e^−i2πt·ν s(t) dt, (17) wheret = (t₁,· · ·,t_d)∈R^d,ν= (ν1,· · · , ν_d)∈R^d,

t·ν =Pd

k=1t_k ·ν_k =t₁ν₁+· · ·+t_dν_d ∈R, Z

R^d

· · · dt= Z

R

· · · Z

R

· · · dt1 · · · dt_d. Energyksk² :=R

R^d |s(t)|²dt, and for example s(t) =

Z

R^d

e^+i2πt·ν bs(ν) dν, ksk² = kbsk²,

r∗s(t) :=

Z

R^d

r(t−u) s(u)du, rd∗s(ν) = br(ν)bs(ν).

(20)

Analog periodic world (A1)

Signals :R→Cisp-periodicifT_ps =s, meanings(t−p) =s(t) for allt∈R: in this case, we denotes :R/pZ→C.Without losing generality, we deal with 1-periodic signals

s :R/Z→C

for whichs(t−1) =s(t)for all t∈R; then theFourier coefficient transformF_R_/_Zs =bs :Z→Cis defined by

bs(ν) :=

Z

R/Z

e^−i2πt·ν s(t) dt = Z 1

0

e^−i2πt·ν s(t) dt. (18) Exercise: show thatbs(ν) =c_ν ∈C, whens :R/Z→Cis given by

s(t) :=X

k∈Z

c_ke^i2πt·k =

∞

X

k=−∞

c_ke^i2πt·k

(naturally, provided that signals is “nice enough”).

(21)

For periodic signals :R/Z→C, Fourier coefficients bs(ν) =

Z

R/Z

e^−i2πt·νs(t) dt ∈ C.

It turns out that “nice enough” s :R/Z→Ccan be recovered from its Fourier coefficients byFourier series

s(t) =X

ν∈Z

e^+i2πt·ν bs(ν) =

+∞

X

ν=−∞

e^+i2πt·ν bs(ν). (19) Thusperiodic analog signal s :R/Z→C has the same

information content asnon-periodic digital signalbs :Z→C; using the signal classification presented in the beginning of the course, this means that classes (A1) and (D0) are dual to each other by Fourier transform, so that properties in (A1) have corresponding “mirrored” properties in (D0), and vice versa.

(22)

(A1) Where do Fourier series come from?

Poisson kernelϕ_r, for which 0< ϕ_r(t)<∞ and Z 1

0

ϕ_r(t) dt=1:

ϕ_r(t) :=X

ν∈Z

r^|ν|e^i2πt·ν = 1−r²

1+r²−2rcos(2πt), (20) where 0<r <1. Then for smooth s :R/Z→Cwe have

s(t) = lim

r→1⁻

Z 1 0

s(u) ϕr(t−u) du

= lim

r→1⁻

Z 1 0

s(u)X

ν∈Z

r^|ν|e^{i2π(t−u)·ν} du

= lim

r→1⁻

X

ν∈Z

bs(ν) r^|ν|e^i2πt·ν

= X

ν∈Z

bs(ν) e^i2πt·ν.

(23)

Energy conservation in Fourier coefficients and series

Letr,s :R/Z→C, so thatbr,bs :Z→C. Then hbr,bsi := X

ν∈Z

br(ν)bs(ν)

= X

ν∈Z

br(ν) Z

R/Z

e^−i2πt·ν s(t) dt dν

= Z

R/Z

X

ν∈Z

e^+i2πt·ν br(ν)s(t) dt

= Z

R/Z

r(t) s(t) dt =: hr,si.

We see that Fourier coefficient/series transform preserves energy ksk² :=hs,si=hbs,bsi=:kbsk². (21)

(24)

(A1) Convolution of periodic signals

Convolutionr∗s :R/Z→Cof periodic signalsr,s :R/Z→Cis defined by

r∗s(t) :=

Z

R/Z

r(t−u) s(u) du. (22) By easy computation, we see thatrd∗s =brbs:

rd∗s(ν) =br(ν)bs(ν).

Naturally, periodic convolution has smoothing properties:

(r∗s)⁰(t) =r⁰∗s(t).

Thus, convolution works in similar manner for both periodic and non-periodic signals!

(25)

Periodization and Poisson summation formula

Periodizationof signals :R→C isPs :R/Z→C, where Ps(t) :=X

k∈Z

s(t−k).

Their Fourier transformsbs :R→CandPcs :Z→Csatisfy Pcs(ν) =

Z 1 0

e^−i2πt·νX

k∈Z

s(t−k) dt

= X

k∈Z

Z 1 0

e−i2π(t−k)·ν s(t−k)dt

=

Z +∞

−∞

e^−i2πt·ν s(t) dt = bs(ν).

ResultPcs(ν) =bs(ν) yieldsPoisson summation formula X

ν∈Z

bs(ν) =^Exercise· · · = X

k∈Z

s(k).

(26)

Digital non-periodic world (D0), or DTFT

Fourier transform of digital signals :Z→C is periodic signal F_Z(s) =bs :R/Z→Cdefined by

bs(ν) :=X

t∈Z

e^−i2πt·ν s(t). (23)

This is calledDiscrete Time Fourier Transform(DTFT).

Remark:this is essentially similar to the previous Fourier series case (apart from the sign of the imaginary uniti).

For digital signalsr,s :Z→C, we define the convolution r∗s :Z→Cby

r∗s(t) :=X

u∈Z

r(t−u)s(u). (24)

The reader may check thatrd∗s =brbs, that is rd∗s(ν) =br(ν)bs(ν).

(27)

Inverse transform to DTFT

Fors :Z→C we have DTFTbs :R/Z→C, where bs(ν) :=X

t∈Z

e^−i2πt·ν s(t).

The inverse transform is verified by a direct calculation:

Z

R/Z

e^+i2πt·ν bs(ν)dν = Z

R/Z

e^+i2πt·νX

u∈Z

e^−i2πu·νs(u) dν

= X

u∈Z

s(u) Z 1

0

e^{i2π(t−u)·ν} dν

= s(t).

Well, no wonder: this is just because signal classes (A0) and (D1) are dual to each other by Fourier transform! Thus, no need to check conservation of energy again.

(28)

From Poisson summation to sampling

Poisson summation formulaX

ν∈Z

bs(ν) =X

k∈Z

s(k) is equivalent to X

α∈Z

bs(ν−α) =X

k∈Z

s(k) e^−i2πk^·ν. (25) Now suppose thatsb₁(ν) =0 whenever |ν| ≥1/2: then

sb₁(ν) = 1]−1/2,+1/2[(ν)X

α∈Z

sb₁(ν−α)

(25)= 1]−1/2,+1/2[(ν)X

k∈Z

s₁(k) e^−i2πk·ν

= X

k∈Z

s₁(k) e^−i2πk^·ν 1]−1/2,+1/2[(ν),

leading tonormalized Whittaker–Shannon sampling formula s1(t) =X

k∈Z

s1(k) sinc(t−k). (26)

(29)

Nyquist–Shannon sampling theorem

... From this, we getWhittaker–Shannon sampling formula s(t) =X

k∈Z

s( k

2B) sinc(2Bt−k), (27) which is valid ifbs(ν) =0 whenever |ν| ≥B.

Related to this formula,Nyquist–Shannon sampling theorem says: If analog signals :R→Cis band-limited (meaning bs(ν) =0 whenever|ν| ≥B), then we are able to reconstruct it from its equispaced sampled values, i.e. from the corresponding digital signalr :Z→C, where

r(k) :=s(k/(2B)).

In other words, Whittaker–Shannon formula builds a bridge between non-periodic analog signals and non-periodic digital signals!

(30)

Digital periodic world (D1), or DFT

N-periodic digital signals :Z→Csatisfiess(t−N) =s(t) for all t∈Z: then we denote

s :Z/NZ→C. (28)

Itsdiscrete Fourier transform(DFT)bs :Z/NZ→Cis defined by

bs(ν) :=

N

X

t=1

e^{−i2πt·ν/N} s(t). (29) Notice that in the exponential we havet·ν/N instead oft·ν.

Exercise: show that the inversebs 7→s of DFT is given by s(t) = 1

N

X

ν=1

e^+i2πt·ν/N bs(ν). (30) Notice the factor _N¹ in this formula!

(31)

Energy and convolution

Exercise: defining hereenergyksk² :=

n

X

t=1

|s(t)|², find constant c_N such that for all signalss :Z/NZ→C

ksk²=c_Nkbsk². (31) Hence “energy is conserved up to a constant”.

For digital signalsr,s :Z/NZ→C, we define the discrete convolutionr∗s :Z/NZ→Cby

r∗s(t) :=

N

X

u=1

r(t−u)s(u). (32)

The reader may check thatrd∗s =brbs, that is rd∗s(ν) =br(ν)bs(ν).

(32)

DFT related to DTFT (D1 vs. D0)

For “nice” non-periodics :Z→C, defines_N :Z/NZ→Cby s_N(t) :=X

k∈Z

s(t−kN).

Thencs_N :Z/NZ→Cis naturally related tobs :R/Z→C:

sc_N(ν) =

N

X

t=1

e^{−i2πt·ν/N} s_N(t)

=

N

X

t=1

e^{−i2πt·ν/N}X

k∈Z

s(t−kN)

= X

u∈Z

e^{−i2πu·ν/N} s(u) = bs(ν/N).

Hencesc_N(ν) =bs(ν/N) for allν.

(33)

DFT related to Fourier series/coefficients (D1 vs. A1)

For “nice” periodics :R/Z→C, define s_N :Z/NZ→C by s_N(t) :=s(t/N).

Thencs_N :Z/NZ→Cis naturally related tobs :Z→C:

sc_N(ν) =

N

X

t=1

e^{−i2πt·ν/N} s(t/N)

=

N

X

t=1

e^{−i2πt·ν/N}X

α∈Z

bs(α) e+i2π(t/N)·α

= X

α∈Z

bs(α)

N

X

t=1

ei2πt·(α−ν)/N = NX

k∈Z

bs(ν−kN).

Hencesc_N(ν) =NX

k∈Z

bs(ν−kN) for all ν∈Z.

(34)

FFT (Fast Fourier Transform)...

FFT(Fast Fourier Transform) is a fast method for computing DFT.

It is a divide-and-conquer algorithm, one of the most important tools in engineering and applied mathematics. Idea: Given signal s :Z/NZ→C, we want to findF_Ns =bs :Z/NZ→C, where N =2^k. Split computation into two smaller size DFTs:

F_Ns(ν) =

N

X

t=1

e^{−i2πt·ν/N} s(t)

= X

t∈{1,3,5,···,N−1}

e^{−i2πt·ν/N} s(t) + X

t∈{2,4,6,···,N}

=

N/2

X

t=1

e−i2π(2t−1)·ν/Ns(2t−1) +

N/2

X

t=1

e−i2π(2t)·ν/Ns(2t)

= e^+i2πν/NF_N/2s_Odd(ν) +F_N/2s_Even(ν).

Hence we just need to calculateF_N/2s_Odd andF_N/2s_Even...

(35)

Why FFT requires only about N log(N) time units?

We say that thecomplexityof algorithm F_N is the “essential number” M_N of multiplications needed in computation. Obviously

F_Ns(ν) =

N

X

t=1

yieldsM₁ =1 andM_N ≤N². However,

F_Ns(ν) =e^+i2πν/NF_N/2s_Odd(ν) +F_N/2s_Even(ν) (33) implies recursively

M_N

(33)

≤ N+2M_N/2

(33)

≤ N+2(N/2+2M_N/4) = 2N +4M_N/4

(33)

≤ 2N+4(N/4+2M_N/8) = 3N +8M_N/8

· · · ⁽³³⁾≤ log₂(N)N +N M_N/N = Nlog(N) +N ≈ Nlog(N).

(36)

Fast convolution via FFT

Direct calculation of discrete convolutionr∗s :Z/NZ→Cof signalsr,s :Z/NZ→C would requireN² multiplications, as

r∗s(t) =

N

X

u=1

r(t−u) s(u).

However,

rd∗s(ν) =br(ν)bs(ν),

where findingbrbs takes only N multiplications. Computing each of r 7→br, s 7→bs, brbs 7→r∗s

takes only aboutNlog(N) multiplications by FFT. Thus,

computation(r,s)7→r∗s has essential complexityNlog(N), too!

(37)

Matlab computing FFT

Matlabcommandfft(Fast Fourier Transform) works as follows:

vectorX=fft(x) for vectorx= [x(1) x(2) . . . x(N)]is given by X(m) =

N

X

k=1

e−i2π(k−1)(m−1)/N x(k), (34) instead of our more natural definition

bx(m) :=

N

X

k=1

e^{−i2πk·m/N} x(k). (35) That is,Matlabshifts both time and frequency by 1 always, and such a weird definition does not match well e.g. with convolution!

So, you have been warned!!!

Otherwise,Matlabis fine for computational Fourier analysis.

(38)

Time-frequency analysis

Next we try to understand behavior of signals simultaneously in both time and frequency. Applications of such time-frequency analysis include audio signal processing (phonetics, treating speech defects, speech synthesis, analyzing animal sounds, music), medical visualizations of EEG and ECG (ElectroEncephaloGraphy and ElectroCardioGraphy), sonar and radar imaging, seismology, quantum physics etc.

A time-frequency distribution for signals :R→Cis typically As :R×R→C,

whereAs(t, ν) is “intensity of s at time-frequency(t, ν)”.

There are many different time-frequency distributions to choose from, notably members of Leon Cohen’s class, which includes e.g.

all spectrograms and so-called Born–Jordan distribution.

(39)

Windowed Fourier Transform

(STFT, Short-Time Fourier Transform)

For signalss,w :R→C,w-windowed Fourier transform (STFT, Short-Time Fourier Transform)F(s,w) :R×R→Cis

F(s,w)(t, ν) :=s wd_t(ν), (36) wherewt(u) =w(u−t). That is,

F(s,w)(t, ν) = Z

R

s(u) w(u−t) e^−i2πu·ν du.

Idea: Fourier transformbs(ν) measures “content” ofs at frequency ν∈Rover all times. F(s,w)(t, ν) measures “content” ofs at time-frequency(t, ν)∈R×R(when viewings through windoww).

(40)

Spectrogram (Sonogram)

Spectrogramrelated to thew-windowed Fourier transform is

|F(s,w)|² :R×R→R⁺. (37) Idea:|F(s,w)(t, ν)|² ≥0 is the “energy intensity” of signal

s :R→Cat time-frequency (t, ν)∈R×R (when viewings through windoww).

For signals :R→C, choosing windoww influences heavily the correspondingw-STFT andw-spectrogram!

InMatlab, try experimenting:

help spectrogram

Or, program your own spectrogram as in Exercises, implementing

|F(s,w)(t, ν)|²= Z

R

s(u) w(u−t) e^−i2πu·ν du

2

.

(41)

Born–Jordan time-frequency distribution

For signalsr,s :R→C, theBorn–Jordan transform Q(r,s) :R×R→C is defined by

Q(r,s)(t, ν) :=

Z

R

e^−i2πu·ν 1 u

Z t+u/2 t−u/2

r(z+u/2) s(z−u/2) dz du

= Z

R

e^−i2πu·ν 1 u

Z t+u t

r(z) s(z−u)dz du.

TheBorn–Jordan distributionofs :R→Cis

Qs =Q(s) :=Q(s,s) :R×R→R. (38) Interpretation:Qs(t, ν)∈Ris the “energy intensity” of s :R→C at time-frequency(t, ν)∈R×R.

(42)

Properties of Born–Jordan distribution

Marginals:

Z

R

Qs(t, ν)dt =|bs(ν)|², Z

R

Qs(t, ν)dν =|s(t)|². Thus energy

Z

R

Z

R

Qs(t, ν)dtdν =ksk².

Natural Fourier symmetries:Qbs(ν,t) =Qs(−t, ν).

Ifr(t) :=s(t−t₀)andq(t) :=e^i2πt·ν⁰s(t) then Qr(t, ν) = Qs(t−t₀, ν), Qq(t, ν) = Qs(t, ν−ν₀).

Qδt0(t, ν) =δt0(t).

Qe_ν₀(t, ν) =δ_ν₀(ν), where e_ν₀(t) :=e^i2πt·ν⁰. Forα < β:Q(λe_α+µe_β)(t, ν) =

|λ|²δα(ν) +|µ|²δβ(ν) +2Re(λ µe_α−β(t))1_[α,β](ν) β−α .

(43)

Born–Jordan filter design...

Atime-frequency symbolis functionσ:R×R→C. Now we design an integral operatorL_σ such that we get a “best possible Born–Jordan approximation”

Q(L_σs)(t, ν)≈σ(t, ν)Qs(t, ν)

for all signalss :R→Cand for all (t, ν)∈R×R. Namely,

hr,L_σsi=hQ(r,s), σi (39) for all signalsr,s :R→C: herehr,L_σsi=hQ(r,s), σi=

= Z

R

Z

R

Q(r,s)(z, ν) σ(z, ν) dz dν

= Z

R

Z

R

Z

R

e^−i2πw·ν 1 w

Z z+^w₂ z−^w₂

r(˜t+w

2)s(˜t−w

2)d˜tdwσ(z, ν)dzdν

= Z

R

r(t) Z

R

Z

R

e^{i2π(t−u)·ν}s(u) 1 u−t

Z u t

σ(z, ν)dzdudν ∗

dt.

(44)

... Born–Jordan filter design

... Hence

L_σs(t) = Z

R

Z

R

e^{i2π(t−u)·ν}s(u)a(t,u, ν)du dν, (40) wherea(t,t, ν) =σ(t, ν), and fort 6=u we have amplitude

a(t,u, ν) = 1 u−t

Z u t

σ(z, ν)dz. (41)

We obtained

L_σs(t) = Z

R

K_L_σ(t,u) s(u) du,

where kernelK_Lσ :R×R→Cof integral operatorL_σ is given by K_L_σ(t,t) =

Z

R

σ(t, ν) dν, and fort 6=u by K_L_σ(t,u) = 1

u−t Z u

t

Z

R

e^{i2π(t−u)·ν} σ(z, ν) dν dz. (42)

(45)

Filtering examples

On previous page, suppose time-invarianceσ(t, ν) =ψ(ν)b for all (t, ν)∈R×R. Naturally, then L_σs =ψ∗s, because

L_σs(t) = Z

R

Z

R

e^{i2π(t−u)·ν} s(u) 1 u−t

Z u t

ψ(ν)b dz du dν

= Z

R

Z

R

e^{i2π(t−u)·ν} s(u) ψ(ν)b du dν

= Z

R

e^i2πt·ν bs(ν) ψ(ν)b dν = ψ∗s(t).

On previous page, suppose frequency-invarianceσ(t, ν) =ϕ(t) for all(t, ν)∈R×R. Then a(t,u, ν) =b(t,u)so thatL_σs =ϕs:

L_σs(t) = Z

R

Z

R

e^{i2π(t−u)·ν} s(u) b(t,u) du dν

= s(t) b(t,t) = ϕ(t)s(t).

(46)

Time-limited signal which is band-limited, too?

Letksk²<∞, where s :R→Cis limited in time-frequency:

s(t) =0=bs(ν)

whenever|t|>M and|ν|>M for some constant M <∞.

Then define analytic functionh :C→Cby h(z) :=

Z M

−M

e^−i2πt·z s(t) dt.

Due to analyticity, for anya∈Cwe have power series h(z) =

∞

X

k=0

1

k! h^(k⁾(a) (z−a)^k.

IfM <a∈Rthenh(a) =bs(a) =0, yieldingh(z)≡0 for allz ∈C. But herebs(ν) =h(ν)≡0 for allν ∈R, so s(t)≡0 for allt ∈R. [Remark: Schwartz test functionss ∈ S(R)⊂C^∞(R)

(e.g. Gaussian signals) are “almost time- and frequency-limited”, becauses(t),bs(t)→0 rapidly as |t| → ∞.]

(47)

Heat flow: historical origin of Fourier analysis

Letu:R×R⁺→R satisfy so-calledheat equation

∂

∂tu(x,t) =α ∂

∂x 2

u(x,t), (43)

with initial conditionu(x,0) =f(x), whereα >0 is the thermal diffusivity constant. Hereu_t(x) =u(x,t) is “temperature at point x at timet”. Taking Fourier transform in thex-variable, we get

∂

∂tub_t(ξ) =−(2πξ)²α ub_t(ξ) and ub₀(ξ) =bf(ξ), so that

ub_t(ξ) = e^−(2πξ)²^αt bf(ξ), u(x,t) =

Z

R

e^i2πx·ξ e^−(2πξ)²^αt bf(ξ) dξ.

Fourier found this reasoning for periodicx case in 1807, but already Daniel Bernoulli and Leonhard Euler considered vibrating strings as trigonometric series in 1753; and Gauss invented FFT in 1805.

(48)

Review: how are different Fourier transforms related?

Time spaceG (continuous RandR/Z; discrete ZandZ/NZ).

Frequency spaceGb is dual to the time spaceG. Signals :G →C has Fourier transformbs :Gb →C,

bs(ν) = Z

G

e^−iht,νi s(t) dt, s(t) =

Z

Gb

e^+iht,νi bs(ν) dν,

“energy conservation” E(bs) =E(s) (except for DFT), where E(s) =ksk²=

Z

G

|s(t)|² dt (for DFT, energy conservation needed a constant...).

Convolutionr∗s :G →Cof signals r,s :G →C, r∗s(t) =

Z

G

r(t−u)s(u) du, which can be in finite case computed efficiently by FFT.

(49)

Review problems and questions

In your field of science/engineering, find examples of signals s :R→C, s :R/Z→C,

s :Z→C, s :Z/NZ→C. In each of these cases:

I How is Fourier transform defined? Which kind of signal is it?

I How is energy defined? Interpretation of energy?

I How does the inverse Fourier transform look like?

I How is convolution defined? Applications to signal processing?

How are these different Fourier transforms related to each other?

Why is FFT fast?

What do time-frequency distributions tell us?