2
$\begingroup$

At this point in a lecture by MIT Professor Strang the idea of gaining insight into a filter by studying its eigenvectors is introduced. The idea is clear with the example chosen in the lecture: an signal-averaging 2-tap filter (running average) expressed in matrix form as

$$F=\tiny \begin{bmatrix} &&\ddots&\ddots&&&&&&&\\&&&\frac 1 2&\frac 1 2&&&\\ &&&&\frac 1 2&\frac 1 2&&&&\\ &&&&&\frac 1 2&\frac 1 2&&&&\\ &&&&&&\frac 1 2&\frac 1 2&&&&\\ &&&&&&&\ddots&\ddots \end{bmatrix}$$

where the vector $\small\begin{bmatrix}\cdots,1,1,1,1,\cdots\end{bmatrix}^\top$ as an input (corresponding to a frequency of $\omega =0$) is passed unaltered - as it corresponds to a low-pass filter - and hence, it is an eigenvector of $F$ with eigenvector $1.$ And, similarly, the alternating vector $\small\begin{bmatrix}\cdots,-1,1,-1,1,\cdots\end{bmatrix}^\top$ (corresponding to a frequency of $\omega =\pi$) is in the null space of $F.$

The idea is thus exemplified, and the intuition is left implicit.

I am asking here for an explicit statement and explanation of the importance and role of the study of eigenvectors in the setting of filters.


Possibly the answer may lie in the generalization to the effect of the matrix on the pure frequencies

$$x_\omega(n)=e^{i\omega n},$$

i.e.

$$\frac 1 2 e^{i\omega n} + \frac 1 2 e^{i\omega (n-1)}=\underset{\text{eigenvalue}}{\underbrace{\left(\frac 1 2 + \frac 1 2 e^{-i\omega}\,\right )}}\;\underset{\text{eigenvector}}{\underbrace{\,e^{i\omega n}}}$$

If this is the correct idea, the matrix expression would be

$$\tiny \begin{bmatrix} &&\ddots&\ddots&&&&&&&\\&&&\frac 1 2&\frac 1 2&&&\\ &&&&\frac 1 2&\frac 1 2&&&&\\ &&&&&\frac 1 2&\frac 1 2&&&&\\ &&&&&&\frac 1 2&\frac 1 2&&&&\\ &&&&&&&\ddots&\ddots \end{bmatrix}\small \begin{bmatrix} \vdots\\ e^{i\omega (n-2)}\\ e^{i\omega (n-1)}\\ e^{i\omega (n)}\\ e^{i\omega (n+1)}\\ e^{i\omega (n+2)}\\ \vdots \end{bmatrix}=\left(\frac 1 2 + \frac 1 2 e^{-i\omega}\right) \begin{bmatrix} \vdots\\ e^{i\omega (n-2)}\\ e^{i\omega (n-1)}\\ e^{i\omega (n)}\\ e^{i\omega (n+1)}\\ e^{i\omega (n+2)}\\ \vdots \end{bmatrix}$$

with $H(\omega) = \frac 1 2 + \frac 1 2 e^{-i\omega}$ corresponding to the frequency response function, which generalizes to

$$H(\omega) = \sum_{k=0}^N h(k) e^{-ik\omega}$$

with $h(k)$ corresponding to the $k$-th coefficient of the $N$ number of taps, and $H(\omega)$ being the Fourier transform. The actual filter being the convolution $y(n) =\sum_{k=0}^n h[k]\, x[n-k].$

In the case of $N=2,$

$$\tiny \begin{bmatrix} &&\ddots&\ddots&&&&&&&\\&&&h(0)&h(1)&&&\\ &&&&h(0)&h(1)&&&&\\ &&&&&h(0)&h(1)&&&&\\ &&&&&&h(0)&h(1)&&&&\\ &&&&&&&\ddots&\ddots \end{bmatrix}\small \begin{bmatrix} \vdots\\ e^{i\omega (n-2)}\\ e^{i\omega (n-1)}\\ e^{i\omega (n)}\\ e^{i\omega (n+1)}\\ e^{i\omega (n+2)}\\ \vdots \end{bmatrix}=\tiny\left(h(0)\,e^{-i\,0\,\omega} + h(1)\, e^{-i\,1\,\omega}\right) \small\begin{bmatrix} \vdots\\ e^{i\omega (n-2)}\\ e^{i\omega (n-1)}\\ e^{i\omega (n)}\\ e^{i\omega (n+1)}\\ e^{i\omega (n+2)}\\ \vdots \end{bmatrix}$$


Following up on the first comment...

$$\left(\tiny\begin{bmatrix} \frac 1 2&\frac 1 2\\&\frac 1 2&\frac 1 2\\ &&\frac 1 2&\frac 1 2\\ &&&\frac 1 2&\frac 1 2\\ \end{bmatrix} - \tiny\begin{bmatrix} \left(\frac 1 2 + \frac 1 2 e^{-i\omega}\right)\\ &\left(\frac 1 2 + \frac 1 2 e^{-i\omega}\right)\\ &&\left(\frac 1 2 + \frac 1 2 e^{-i\omega}\right)\\ &&&\left(\frac 1 2 + \frac 1 2 e^{-i\omega}\right)\\ \end{bmatrix}\right)\begin{bmatrix} e^{i\omega (n-2)}\\ e^{i\omega (n-1)}\\ e^{i\omega (n)}\\ e^{i\omega (n+1)}\\ e^{i\omega (n+2)}\\ \end{bmatrix}=\begin{bmatrix} 0\\0\\0\\0\\0\end{bmatrix}$$

$\endgroup$
  • $\begingroup$ Considerig your F matrix, how do you compute its (matrix) eigenvalue and eigenvectors based on $|F - \lambda I|=0$? $\endgroup$ – Fat32 Oct 25 '18 at 19:34
  • $\begingroup$ @Fat32 I added this calculation, which seems to show that the idea of the effect on pure frequencies is indeed the case. I still think that some sort of summary in English would be pertinent as a formal answer... $\endgroup$ – Antoni Parellada Oct 26 '18 at 13:49
  • $\begingroup$ Hello... What I meant was, can you show that the eigenvalues of the F matrix are = $0.5 + 0.5 e^{j\omega}$ without assuming that they are the eigenvalues? Your added calculations indicate that $0.5 + 0.5 e^{j\omega }$ are eigenvalues of F (for the eigenvectors $e^{j \omega n}$) but not the converse; i.e. do not assume that $e^{j\omega n}$ as eigenvectors and $0.5 + 0.5 e^{j\omega}$ as the corresponding eigenvalues? may be I missed a point. $\endgroup$ – Fat32 Oct 26 '18 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.