DTU 02471 · Problem set 2

Filters, estimators and adaptive systems

Seven problems, one thread: a filter is a weighted sum, and choosing the weights well is an estimation problem.

Problem 2.1

Signal processing is linear algebra

Write the output of a length-$L$ FIR filter on a length-$N$ signal as $\boldsymbol y = X\boldsymbol\theta$. How are $X$ and $\boldsymbol\theta$ built?

Each output sample of an FIR filter is a weighted sum of the last $L$ inputs, i.e. one inner product $\boldsymbol\theta^{\mathsf T}\boldsymbol x_n$. Stack one such row per output sample and the whole convolution becomes a single matrix–vector product. That is why least squares and the rest of linear algebra apply directly to filtering.

$$\begin{gathered}y_n=\sum_{l=0}^{L-1}\theta_l\,x_{n-l}=\boldsymbol\theta^{\mathsf T}\boldsymbol x_n\\ \boldsymbol x_n=[x_n,x_{n-1},\dots,x_{n-L+1}]^{\mathsf T}\end{gathered}$$Eq. (2.126) and Eqs. (2.127)–(2.129), p. 48

Row $n$ of $X$ times $\boldsymbol\theta$ is exactly the flipped kernel sitting under $x_n, x_{n-1}, x_{n-2}$ in the sliding view. Here $\boldsymbol\theta=[2,1,-1]^{\mathsf T}$ and $N=6$, $L=3$.

Solution

Filter vector: $\boldsymbol\theta=[\theta_0,\dots,\theta_{L-1}]^{\mathsf T}\in\mathbb R^{L}$.

Row $n$ of $X$ is $\boldsymbol x_n^{\mathsf T}$, with $x_k=0$ for $k<0$ and $k\ge N$, so $X_{n,l}=x_{n-l}$:

$$X=\begin{bmatrix}x_0&0&\cdots&0\\ x_1&x_0&\cdots&0\\ \vdots&&\ddots&\vdots\\ 0&\cdots&0&x_{N-1}\end{bmatrix}\in\mathbb R^{(N+L-1)\times L}$$

Column $l$ is $x$ delayed by $l$ samples, so $X$ is Toeplitz (constant diagonals).

All $N+L-1$ rows give the full convolution; the first $N$ rows give a same-length causal output; rows $L-1,\dots,N-1$ are the $N-L+1$ outputs without zero padding.

$\boldsymbol y=X\boldsymbol\theta,\ \ X_{n,l}=x_{n-l}$

Order matters. $\theta_0$ multiplies the newest sample $x_n$, so each row lists the samples newest-first. That reversal is the "flip" in convolution; build the rows oldest-first and you compute a correlation instead.

Problem 2.2

Biased versus unbiased estimation

Show that $\mathrm{MSE}=\mathbb E[(\hat\theta-\theta_o)^2]$ splits into bias and variance, and argue whether a biased or an unbiased estimator is better for minimizing the MSE.

An estimator is a random variable: repeat the experiment and $\hat\theta$ changes. Its error has two sources, how far its average sits from the truth (bias) and how much it scatters (variance). Being unbiased removes only the first, so a small bias that buys a large drop in variance lowers the MSE.

$$\mathrm{MSE}=\underbrace{\mathbb E\big[(\hat\theta-\mathbb E[\hat\theta])^2\big]}_{\text{variance}}+\underbrace{(\mathbb E[\hat\theta]-\theta_o)^2}_{\text{bias}^2}$$Eq. (3.22), p. 79 Shrunk MVU estimator $\hat\theta_b=(1+\alpha)\hat\theta_{\mathrm{MVU}}$, with $v=\operatorname{Var}(\hat\theta_{\mathrm{MVU}})$: $$\begin{gathered}\mathrm{MSE}(\alpha)=(1+\alpha)^2v+\alpha^2\theta_o^2\\ \alpha^\ast=-\frac{v}{v+\theta_o^2}\end{gathered}$$Eqs. (3.24)–(3.27), p. 80

The same 40 experiments, before and after shrinking by $1+\alpha$ ($\theta_o=1$). Shrinking moves the mean off target but pulls the cloud together. The MSE curve dips below $v$ for $-2v/(v+\theta_o^2)<\alpha<0$.

Solution

Add and subtract $\mathbb E[\hat\theta]$ inside the square:

$$\begin{aligned}\mathrm{MSE}&=\mathbb E\big[(\hat\theta-\mathbb E\hat\theta)^2\big]+(\mathbb E\hat\theta-\theta_o)^2\\&\quad+2(\mathbb E\hat\theta-\theta_o)\underbrace{\mathbb E[\hat\theta-\mathbb E\hat\theta]}_{=0}\end{aligned}$$

$\mathbb E\hat\theta-\theta_o$ is a constant, so the cross term vanishes: MSE = Var + bias²

Shrink the MVU estimator (variance $v$): bias $=\alpha\theta_o$, variance $=(1+\alpha)^2v$.

$\mathrm{MSE}(\hat\theta_b)<v \iff -\tfrac{2v}{v+\theta_o^2}<\alpha<0$; at $\alpha^\ast$: $\mathrm{MSE}=\tfrac{v\theta_o^2}{v+\theta_o^2}<v$.

a suitably biased estimator beats the best unbiased one

The catch. $\alpha^\ast$ depends on the unknown $\theta_o$, so you cannot compute it directly. In practice the bias is introduced through regularization, as in ridge regression (Example 3.4, pp. 89–90).

Problem 2.3

Norms are convex

Using the definition in Section 8.2, prove that every norm $\|\cdot\|_p:\mathbb R^l\to[0,\infty)$ is a convex function.

Convex means: along any straight segment, the function stays below the chord between its end values. Then every local minimum is global, which is why convex losses and penalties ($\ell_2$, $\ell_1$) are so popular. For a norm, the proof is just the triangle inequality plus scaling.

$$\begin{aligned}f\big(\lambda\boldsymbol\theta_1+(1-\lambda)\boldsymbol\theta_2\big)&\le\lambda f(\boldsymbol\theta_1)+(1-\lambda)f(\boldsymbol\theta_2)\\ &\forall\,\boldsymbol\theta_1,\boldsymbol\theta_2,\ \lambda\in[0,1]\end{aligned}$$Definition 8.2, Eq. (8.2), p. 345

The segment from $\boldsymbol\theta_2$ to $\boldsymbol\theta_1$, with the norm ball through the moving point. Along the segment the norm (violet) never rises above the chord (dashed); the green bar is the gap.

Solution

$\mathbb R^l$ is a convex set (Definition 8.1, Eq. (8.1), p. 345). For $\lambda\in[0,1]$, both $\lambda\ge0$ and $1-\lambda\ge0$:

$$\begin{aligned}&\|\lambda\boldsymbol\theta_1+(1-\lambda)\boldsymbol\theta_2\|_p\\&\le\|\lambda\boldsymbol\theta_1\|_p+\|(1-\lambda)\boldsymbol\theta_2\|_p &&\text{(prop. 3)}\\&=\lambda\|\boldsymbol\theta_1\|_p+(1-\lambda)\|\boldsymbol\theta_2\|_p&&\text{(prop. 2)}\end{aligned}$$

This is Eq. (8.2) with $f=\|\cdot\|_p$. Property 1 is not needed.

every norm is convex

Convex, not strictly convex. If $\boldsymbol\theta_2=c\,\boldsymbol\theta_1$ with $c>0$, equality holds for every $\lambda$: the norm is a straight line along a ray. Pick "same direction" in the animation to see the gap vanish.

Problem 2.4

Correlation of an AR(1) process with an offset

$x_n=a x_{n-1}+v_n$ with $|a|<1$ and white noise of variance $\sigma_v^2$; $y_n=x_n+b$ with $\mathbb E[x_n]=0$. Find $r_y(k)$ and compute $r_y(-2)$ for $a=0.8$, $b=0.5$, $\sigma_v^2=1$.

$r_y(k)=\mathbb E[y_ny_{n-k}]$ measures how much a sample still "remembers" the one $k$ steps back. An AR(1) process forgets geometrically, by a factor $a$ per step. A constant offset $b$ adds $b^2$ at every lag, because this course's correlation is unnormalized: the mean is not subtracted.

$$r_x(k)=\frac{\sigma_v^2\,a^{|k|}}{1-a^2},\qquad r_y(k)=\frac{\sigma_v^2\,a^{|k|}}{1-a^2}+b^2$$definition Eq. (2.101), p. 42; agrees with Eq. (4.55), p. 142

Sample path with the circled pair $y_n,\,y_{n+2}$, then the theory bars ($b^2$ floor + AR part) and the running average of the products (black ticks), which settles on the bars as $n$ grows.

Solution

$x_n=\sum_{i\ge0}a^iv_{n-i}$ uses only present and past noise, so $\mathbb E[v_nx_{n-k}]=0$ for $k\ge1$ and $=\sigma_v^2$ for $k=0$. Multiply $x_n=ax_{n-1}+v_n$ by $x_{n-k}$ and take $\mathbb E$:

$k\ge1$: $r_x(k)=a\,r_x(k-1)\Rightarrow r_x(k)=a^kr_x(0)$

$k=0$: $r_x(0)=a\,r_x(1)+\sigma_v^2=a^2r_x(0)+\sigma_v^2\Rightarrow r_x(0)=\frac{\sigma_v^2}{1-a^2}$

Symmetry $r_x(-k)=r_x(k)$ (Eq. (2.113), p. 45) gives $a^{|k|}$. Offset: $r_y(k)=r_x(k)+b\,\mathbb E[x_n]+b\,\mathbb E[x_{n-k}]+b^2=r_x(k)+b^2$.

$r_y(-2)=\frac{0.8^2}{1-0.8^2}+0.5^2=\frac{16}{9}+\frac14=$ $\tfrac{73}{36}\approx2.028$

Unnormalized means no mean subtraction. With the covariance convention you would get $16/9\approx1.778$ and lose the $b^2$ floor. This course (and the problem set) uses $r_y(k)=\mathbb E[y_ny_{n-k}]$.

Problem 2.5

Wiener filtering

Explain desired and error signal. With $x_n=s_n+w_n$ ($f_s=8$ kHz) as input, estimate a Wiener filter of a well-argued length, plot the frequency responses and evaluate.

The Wiener filter is the FIR filter whose output is closest, in mean square, to a desired signal. Here the input is the noisy $x_n$ and the desired signal is the clean $s_n$. In frequency terms it keeps the bands where the signal dominates and turns down the bands where the noise dominates.

$$\begin{gathered}\Sigma_x\boldsymbol\theta_\ast=\boldsymbol p,\quad[\Sigma_x]_{ij}=r_x(i-j),\quad[\boldsymbol p]_i=r_{sx}(i)\\ J_{\min}=r_s(0)-\boldsymbol p^{\mathsf T}\boldsymbol\theta_\ast\end{gathered}$$Eq. (4.5), p. 121 (filtering form p. 133); Eq. (4.9), p. 121

Output PSD = input PSD × $|H|^2$ (in dB: add). Short filters cannot follow the ideal non-causal response $S_s/(S_s+S_w)$ (Eq. (4.52), p. 137); from about $L=20$ the gain flattens out.

clean $s_n$

noisy $x_n$ (3.17 dB)

Wiener output, $L=22$ (8.79 dB)

Solution

Desired $d_n$: what the output $\hat d_n=\boldsymbol\theta^{\mathsf T}\boldsymbol x_n$ should reproduce (here $s_n$). Error $e_n=d_n-\hat d_n$ (Fig. 4.5, p. 133). Wiener minimizes $\mathbb E[e_n^2]$ (Eq. (4.2), p. 120).

Estimate $r_x$, $r_{sx}$ from $N=32\,000$ samples and solve the normal equations for $L=1,\dots,100$.

Length: SNR rises steeply up to $L\approx5$, then flattens (8.96 dB at $L=100$). Smallest $L$ within 0.2 dB: $L=22$, $J_{\min}=0.0110$. Check: band ≈ 400 Hz wide, resolution ≈ $f_s/L$ ⇒ $L\gtrsim8000/400=20$.

Evaluation: passband (0.75–1.25 kHz) at ≈ 0 dB, rest attenuated 10–20 dB.

$L=22$: SNR 3.17 → 8.79 dB

In-band noise stays. Where signal and noise share frequencies, no linear filter can separate them. That caps the gain however large $L$ is (and with $L=3$ the response is nearly flat: only 5.80 dB).

Problem 2.6

Time–frequency analysis of a drum loop

Plot a spectrogram of problem2_6.wav, argue for window size, overlap and window function, find the time between beats and the spectral signature of each "instrument".

A spectrogram cuts the signal into short overlapping frames, multiplies each by a window and takes its FFT; each frame becomes one column of the picture. The frame length $N$ is a trade-off: short frames pin events down in time, long frames separate nearby frequencies.

$$\begin{gathered}X(m,k)=\sum_{n=0}^{N-1}x_{mR+n}\,w_n\,e^{-j2\pi kn/N}\\ \text{plot }|X(m,k)|^2,\qquad \Delta t=\frac{N}{f_s},\qquad \Delta f=\frac{f_s}{N}\end{gathered}$$course note 02471_lec7_time_frequency, slides 27 and 34; trade-off Section 10.6, p. 506 and slide 29

The Hann window (green) slides over the waveform; its FFT (plotted sideways at the right) becomes the next column. Try $N=128$ (lines blur) and $N=2048$ (strikes smear). Dotted lines: the 0.237 s grid; L = low drum, S = snare, H = hi-hat.

drum loop ($f_s=22.05$ kHz)

Solution

Window size $N=512$: 23 ms and 43 Hz. Strikes come every 0.237 s and decay within ≈ 50 ms, so frames must be well under 0.1 s; 43 Hz still resolves lines 0.78 kHz apart.

Overlap 75 % (hop 128 = 5.8 ms): onsets located to ≈ 6 ms. Window: Hann.

Rhythm: onsets on a grid of $(3.878-0.081)/16=0.237$ s, 17 slots, exactly one instrument each; L every 4th slot ⇒ pattern repeats every 0.949 s.

L (slots 0, 4, 8, 12, 16): short, tonal, lines at odd harmonics of 0.78 kHz.
S (slots 1, 5, 7, 9, 13, 15): short, odd harmonics of 1.55 kHz on a noise floor ≈ 20 dB above L's.
H (slots 2, 3, 6, 10, 11, 14): broadband noise, no lines, ≈ 0.19 s long.

Hann, $N=512$, 75 % overlap; beat grid 0.237 s

Why Hann, not rectangular? Hann's first sidelobe is at −31 dB versus −13 dB (slides 29–30), so the strong harmonic lines leak far less into the quiet bands between them.

Problem 2.7

Adaptive noise cancelling

Identify the signals $a,b,c,d,h,w$ in the figure, explain the principle and why speech and noise must be uncorrelated, then build LMS, NLMS and RLS cancellers and evaluate them.

A second microphone hears only the noise. An adaptive filter learns how that noise reaches the primary microphone and subtracts its prediction. The speech cannot be predicted from the noise, so it is what remains: the error signal is the cleaned output.

$$\begin{aligned}\text{LMS: }&\boldsymbol w_n=\boldsymbol w_{n-1}+\mu\,b_n\boldsymbol d_n\\ \text{NLMS: }&\boldsymbol w_n=\boldsymbol w_{n-1}+\frac{\tilde\mu}{\epsilon+\|\boldsymbol d_n\|^2}\,b_n\boldsymbol d_n\\ \text{RLS: }&\text{forgetting factor }\beta,\ \text{memory }\tfrac{1}{1-\beta}\end{aligned}$$ Misadjustment $\mathcal M$ (excess error relative to the minimum error): $$\begin{gathered}\mathcal M_{\mathrm{LMS}}\approx\tfrac{\mu}{2}\operatorname{tr}(\Sigma_d),\qquad \mathcal M_{\mathrm{NLMS}}\approx\tfrac{\tilde\mu}{2}\\ \mathcal M_{\mathrm{RLS}}\approx\tfrac{(1-\beta)M}{2}\end{gathered}$$Algorithm 5.1, p. 196; Algorithm 5.3, p. 209; Algorithm 6.1, p. 266; misadjustment Table 6.1, p. 272

The problem-set figure, running on the real signals (low-pass path $h$). Watch the bars in $w$ grow onto the red outline of $h$ during the silent first 0.3 s (slow motion), after which $b$ looks like the speech.

Power of the residual noise $b_n-s_n$. All three converge in the speech-free first 0.3 s, cancelling 50–60 dB; afterwards the residual follows the speech envelope.

output SNR (dB)	primary	LMS	NLMS	RLS
low-pass $h$	2.9	11.0	9.2	16.1
high-pass $h$	2.9	11.9	10.1	16.2
band-pass $h$	3.0	13.8	11.2	19.3
misadjustment $\mathcal M$		0.05	0.075	0.016
predicted $-10\log_{10}\mathcal M$		13.0	11.2	18.0

primary mic (2.9 dB)

LMS output

NLMS output

RLS output

Solution

$d$: reference mic = noise $v_n$, the filter input.
$h$: unknown acoustic path noise → primary mic; the primary signal $s_n+(h*v)_n$ is the desired signal.
$w$: adaptive FIR filter ($M$ taps), estimates $h$.
$a$: filter output $a_n=\boldsymbol w_{n-1}^{\mathsf T}\boldsymbol d_n\approx(h*v)_n$.
$b$: error $b_n=s_n+(h*v)_n-a_n$, fed back and also the system output ($\approx s_n$).
$c$: the weight correction $\boldsymbol w_{n-1}\to\boldsymbol w_n$ from $b_n$ and $\boldsymbol d_n$.

Principle: minimize output power,

$$\begin{aligned}\mathbb E[b_n^2]&=\mathbb E[s_n^2]+\mathbb E\big[((h-w)*v)_n^2\big]\\&\quad+2\,\mathbb E\big[s_n((h-w)*v)_n\big]\end{aligned}$$

First term is fixed, last is 0 ⇒ $\boldsymbol w\to h$, $b_n\to s_n$ (Fig. 4.9, p. 138; after Eq. (4.54), p. 139).

Setup: white noise at 3 dB primary SNR, $M=32$; LMS $\mu$ = 5 % of the bound $2/\operatorname{tr}(\Sigma_d)$ (Eq. (5.43), p. 199); NLMS $\tilde\mu=0.15$; RLS $\beta=0.999$.

Speech is the irreducible error, so $\mathrm{SNR}_{\text{out}}\approx-10\log_{10}\mathcal M$: same order as measured, ≈ 2 dB lower (speech is not stationary).

RLS 16–19 dB > LMS 11–14 dB > NLMS 9–11 dB

Why speech and noise must be uncorrelated. Otherwise the cross term $2\mathbb E[s_n((h-w)*v)_n]$ survives and $\boldsymbol p$ in the normal equations picks up $r_{sv}\neq0$. The optimum moves away from $h$ and the filter also cancels the part of the speech it can predict from the noise: the speech comes out attenuated and distorted.

NLMS is not worse than LMS. It loses here only because $\tilde\mu=0.15$ is a larger effective step ($\mathcal M=0.075$ vs $0.05$). RLS wins on misadjustment at equal speed, at $O(M^2)$ cost per sample instead of $O(M)$ (Remarks 6.2, p. 266).