The Filter Problem
Suppose we have input data f [ t ] f[t] f [ t ] h [ t ] h[t] h [ t ] m m m
Our goal is to match a desired output d [ t ] d[t] d [ t ]
The convolution of the inpulse response with the input data produces an output given by:
y [ t ] = ∑ i = 0 m − 1 h [ i ] f [ t − i ] \begin{align*} y[t] &= \sum_{i=0}^{m-1} h[i]f[t-i] \end{align*} y [ t ] = i = 0 ∑ m − 1 h [ i ] f [ t − i ] We'd like d [ t ] = y [ t ] d[t] = y[t] d [ t ] = y [ t ] e [ t ] e[t] e [ t ]
Therefore,
d [ t ] = y [ t ] + e [ t ] ⟹ e [ t ] = d [ t ] − y [ t ] = d [ t ] − ∑ i = 0 m − 1 h [ i ] f [ t − i ] \begin{align*} d[t] &= y[t] + e[t] \\ \implies e[t] &= d[t] - y[t] \\ &= d[t] - \sum_{i=0}^{m-1} h[i]f[t-i] \end{align*} d [ t ] ⟹ e [ t ] = y [ t ] + e [ t ] = d [ t ] − y [ t ] = d [ t ] − i = 0 ∑ m − 1 h [ i ] f [ t − i ] Consider minimizing the error over some interval i 1 i_1 i 1 i 2 i_2 i 2
We can construct an error vector as
e = [ d [ i 1 ] − ∑ i = 0 m − 1 h [ i ] f [ i 1 − i ] d [ i 1 + 1 ] − ∑ i = 0 m − 1 h [ i ] f [ i 1 + 1 − i ] d [ i 1 + 2 ] − ∑ i = 0 m − 1 h [ i ] f [ i 1 + 2 − i ] ⋮ d [ i 2 ] − ∑ i = 0 m − 1 h [ i ] f [ i 2 − i ] ] = [ d [ i 1 ] ⋮ d [ i 2 ] ] − [ ∑ i = 0 m − 1 h [ i ] f [ i 1 − i ] ⋮ ∑ i = 0 m − 1 h [ i ] f [ i 2 − i ] ] = d − y \begin{align*} \pmb e &= \begin{bmatrix} d[i_1] - \sum_{i=0}^{m-1} h[i] f[i_1 -i] \\ d[i_1 + 1] - \sum_{i=0}^{m-1} h[i] f[i_1 + 1 -i] \\ d[i_1 + 2] - \sum_{i=0}^{m-1} h[i] f[i_1 + 2 -i] \\ \vdots \\ d[i_2] - \sum_{i=0}^{m-1} h[i] f[i_2 -i] \\ \end{bmatrix} \\[40pt] &= \begin{bmatrix} d[i_1] \\ \vdots \\ d[i_2]\end{bmatrix} - \begin{bmatrix}\sum_{i=0}^{m-1} h[i] f[i_1 -i] \\ \vdots \\ \sum_{i=0}^{m-1} h[i] f[i_2 -i]\end{bmatrix} \\ &= \pmb d - \pmb y \end{align*} e e = ⎣ ⎡ d [ i 1 ] − ∑ i = 0 m − 1 h [ i ] f [ i 1 − i ] d [ i 1 + 1 ] − ∑ i = 0 m − 1 h [ i ] f [ i 1 + 1 − i ] d [ i 1 + 2 ] − ∑ i = 0 m − 1 h [ i ] f [ i 1 + 2 − i ] ⋮ d [ i 2 ] − ∑ i = 0 m − 1 h [ i ] f [ i 2 − i ] ⎦ ⎤ = ⎣ ⎡ d [ i 1 ] ⋮ d [ i 2 ] ⎦ ⎤ − ⎣ ⎡ ∑ i = 0 m − 1 h [ i ] f [ i 1 − i ] ⋮ ∑ i = 0 m − 1 h [ i ] f [ i 2 − i ] ⎦ ⎤ = d d − y y Now, the way that formulate this problem is dependent on how we choose i 1 i_1 i 1 i 2 i_2 i 2 i 1 i_1 i 1 i 2 i_2 i 2 m m m
Depending on the assumptions we're willing to make, the values of i 1 i_1 i 1 i 2 i_2 i 2 i 1 < m i_1 < m i 1 < m f [ i 1 − i ] f[i_1 - i] f [ i 1 − i ] i 2 > N i_2 > N i 2 > N
This may be a little confusing right now but the following discussion will make this clear.
Constructing A A A
There are various ways we can factorize y \pmb y y y
Once we factorize y \pmb y y y e = d − A h \pmb e = \pmb d - A \pmb h e e = d d − A h h l 2 l_2 l 2 h = ( A H A ) − 1 A H d \pmb h = (A^HA)^{-1}A^H \pmb d h h = ( A H A ) − 1 A H d d
Finally we pick A A A
The "Covariance" Method
Let i 1 = m i_1 = m i 1 = m i 2 = N i_2 = N i 2 = N
A = [ f [ m ] f [ m − 1 ] … f [ 1 ] f [ m + 1 ] f [ m ] … f [ 2 ] ⋮ ⋮ ⋱ ⋮ f [ N ] f [ N − 1 ] … f [ N − m + 1 ] ] \begin{align} A = \begin{bmatrix}f[m] & f[m-1] & \dots & f[1] \\ f[m+1] & f[m] & \dots & f[2] \\ \vdots & \vdots & \ddots & \vdots \\ f[N] & f[N-1] & \dots & f[N-m+1]\end{bmatrix} \end{align} A = ⎣ ⎡ f [ m ] f [ m + 1 ] ⋮ f [ N ] f [ m − 1 ] f [ m ] ⋮ f [ N − 1 ] … … ⋱ … f [ 1 ] f [ 2 ] ⋮ f [ N − m + 1 ] ⎦ ⎤ This A A A N − m + 1 N-m+1 N − m + 1
Note that this matrix used all samples without any assumptions.
The "Autocorrealtion" Method
Assume that f [ i ] = 0 f[i] = 0 f [ i ] = 0 i > N i > N i > N i < 1 i < 1 i < 1
Let i 1 = 1 i_1 = 1 i 1 = 1 i 2 = N + m − 1 i_2 = N+m -1 i 2 = N + m − 1 A A A
A = [ f [ 1 ] 0 … 0 f [ 2 ] f [ 1 ] … 0 ⋮ ⋮ ⋱ 0 f [ m ] f [ m − 1 ] … f [ 1 ] f [ m + 1 ] f [ m ] … f [ 2 ] ⋮ ⋮ ⋱ ⋮ f [ N ] f [ N − 1 ] … f [ N − m + 1 ] 0 f [ N ] … f [ N − m + 2 ⋮ ⋮ ⋱ ⋮ 0 … … f [ N ] ] \begin{align*} A = \begin{bmatrix} f[1] & 0 & \dots & 0 \\ f[2] & f[1] & \dots & 0 \\ \vdots & \vdots & \ddots & 0 \\ f[m] & f[m-1] & \dots & f[1] \\ f[m+1] & f[m] & \dots & f[2] \\ \vdots & \vdots & \ddots & \vdots \\ f[N] & f[N-1] & \dots & f[N-m+1] \\ 0 & f[N] & \dots & f[N-m+2 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & \dots & \dots & f[N] \end{bmatrix} \end{align*} A = ⎣ ⎡ f [ 1 ] f [ 2 ] ⋮ f [ m ] f [ m + 1 ] ⋮ f [ N ] 0 ⋮ 0 0 f [ 1 ] ⋮ f [ m − 1 ] f [ m ] ⋮ f [ N − 1 ] f [ N ] ⋮ … … … ⋱ … … ⋱ … … ⋱ … 0 0 0 f [ 1 ] f [ 2 ] ⋮ f [ N − m + 1 ] f [ N − m + 2 ⋮ f [ N ] ⎦ ⎤ This matrix has N + m − 1 N+m-1 N + m − 1
The "Pre-windowing" method
Assume f [ i ] = 0 f[i] = 0 f [ i ] = 0 i < 1 i < 1 i < 1
Let i 1 = 1 i_1 = 1 i 1 = 1 i 2 = N i_2 = N i 2 = N
Then A A A
A = [ f [ 1 ] 0 … 0 f [ 2 ] f [ 1 ] … 0 ⋮ ⋮ ⋱ 0 f [ m ] f [ m − 1 ] … f [ 1 ] f [ m + 1 ] f [ m ] … f [ 2 ] ⋮ ⋮ ⋱ ⋮ f [ N ] f [ N − 1 ] … f [ N − m + 1 ] ] \begin{align*} A = \begin{bmatrix} f[1] & 0 & \dots & 0 \\ f[2] & f[1] & \dots & 0 \\ \vdots & \vdots & \ddots & 0 \\ f[m] & f[m-1] & \dots & f[1] \\ f[m+1] & f[m] & \dots & f[2] \\ \vdots & \vdots & \ddots & \vdots \\ f[N] & f[N-1] & \dots & f[N-m+1] \end{bmatrix} \end{align*} A = ⎣ ⎡ f [ 1 ] f [ 2 ] ⋮ f [ m ] f [ m + 1 ] ⋮ f [ N ] 0 f [ 1 ] ⋮ f [ m − 1 ] f [ m ] ⋮ f [ N − 1 ] … … ⋱ … … ⋱ … 0 0 0 f [ 1 ] f [ 2 ] ⋮ f [ N − m + 1 ] ⎦ ⎤ A A A N N N
The "Post-windowing" method
For this method we let f [ i ] = 0 f[i] = 0 f [ i ] = 0 i > N i> N i > N
Let let i 1 = m i_1 = m i 1 = m i 2 = N + m − 1 i_2 = N+m -1 i 2 = N + m − 1
Now A A A
A = [ f [ m ] f [ m − 1 ] … f [ 1 ] f [ m + 1 ] f [ m ] … f [ 2 ] ⋮ ⋮ ⋱ ⋮ f [ N ] f [ N − 1 ] … f [ N − m + 1 ] 0 f [ N ] … f [ N − m + 2 ⋮ ⋮ ⋱ ⋮ 0 … … f [ N ] ] \begin{align*} A = \begin{bmatrix} f[m] & f[m-1] & \dots & f[1] \\ f[m+1] & f[m] & \dots & f[2] \\ \vdots & \vdots & \ddots & \vdots \\ f[N] & f[N-1] & \dots & f[N-m+1] \\ 0 & f[N] & \dots & f[N-m+2 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & \dots & \dots & f[N] \end{bmatrix} \end{align*} A = ⎣ ⎡ f [ m ] f [ m + 1 ] ⋮ f [ N ] 0 ⋮ 0 f [ m − 1 ] f [ m ] ⋮ f [ N − 1 ] f [ N ] ⋮ … … … ⋱ … … ⋱ … f [ 1 ] f [ 2 ] ⋮ f [ N − m + 1 ] f [ N − m + 2 ⋮ f [ N ] ⎦ ⎤ A A A N N N