Why does this work? Fourier coefs. of function with min energy in window is eigenvector of window coef. matrix.

Question

Let me begin with saying I have never got a good handle on eigenvectors and eigenvalues. My best hunch is that the eigenvectors are the 'best' basis for a linear transform along which the transform space varies the least(?).

Anyway, I am reading a paper at the moment and trying to work out how the following works. Paraphrasing from the paper:

Let $w(\theta) \in \mathbb{R}, \theta \in [-\pi,\pi)$ be a symmetric window function, and

$$p(\theta) = \sum_{n=-N}^{N} u_n e^{i n \theta}, \qquad u_{-n} = \bar{u}_n$$

be a real valued function made from the first $N$ Fourier series components, ($N$-th order trig. polynomial.) with $\mathbf{u}^H\mathbf{u} = 1.$

We want to find the values of $\mathbf{u}$ that minimise the energy of $p(\theta)$ within the window $w(\theta)$. This energy functional is

$$\sum_{n'=-N}^{N}\sum_{n=-N}^{N} \bar{u}_{n'}u_n \int_{-\pi}^{\pi} e^{i (n-n') \theta} w(\theta)\,d\theta = \mathbf{u}^H\mathbf{W}\mathbf{u}$$

where $W_{n,n'} = \int_{-\pi}^{\pi} e^{i (n-n') \theta} w(\theta)\,d\theta$

The paper then goes on to say that the best choice for $\mathbf{u}$ is the eigenvector of $\mathbf{W}$ corresponding to the smallest eigenvalue.

Why?

Edit: $w(\theta)$ is symmetric.

Answer 1

Here we have eigenvalues in a very specific context. We have got an inner product space (the span of the complex exponentials $\theta\mapsto e^{n\mathbf i\theta}$ for $-N\leq n\leq N$) with the standard inner product on the basis of those exponentials (that is, in coordinate vectors $\def\u{\mathbf u}\def\v{\mathbf v}(\u,\v)=\u^H\v$). The window $w$ is in fact used to describe a second form $\def\W{\mathbf W}(\u,\v)_w=\u^H \W\v$, which is symmetric: $\W^H = \W$. Then a spectral theorem says that $\W$ is unitarily diagonalisable (that is, with an orthonormal set of eigenvectors) and real eigenvalues. In matrix terms $\def\R{\mathbf R}\def\D{\mathbf D}\W=\R^H\D\R$ where $\D$ is a real diagonal matrix and $\R$ is an unitary matrix: $\R^H\R=I$.

This means one has an eigenvector basis $\mathcal B$ that is at the same time orthonormal for the standard inner product, and orthogonal for $(,)_w$. This means that if now $\u'=\R\u$ and $\v'=\R\v$ are the new coordinates of $\u,\v$ with respect to the eigenvector basis $\mathcal B$, then one still has $(\u,\v)=\u^H\mathbf v=(\u')^H\v'$, but also $(\u,\v)_w=\u^H\W\v=\u^H\R^h\D\R\v=(\u')^H \D\v'$. Now it is very easy to see that if one wants to minimize $(\u')^H \D\u'$ relative to the constraint of the unit sphere $(\u')^H \u'=1$, then one should take for $\u'$ the vector with a coordinate $1$ at the position to the smallest diagonal entry of$~\D$, and $0$ elsewhere. Indeed the constraint reads $\sum_i|u_i'|^2=1$ while $(\u')^H \D\u'=\sum_i\lambda_i|u_i'|^2$ where the $\lambda_i$ are the diagonal entries of$~\D$ (which are the eigenvalues of$~\W$). One obtains $\min_i(\lambda_i)\leq \sum_i\lambda_i|u_i'|^2 \leq\max_i(\lambda_i)$ by simple estimation of each term $\min_i(\lambda_i)|u_i'|^2\leq \lambda_i|u_i'|^2 \leq\max_i(\lambda_i)|u_i'|^2$, and adding the inequalities.

Answer 2

If you want an intuitive understanding, consider first the case where $W$ is a diagonal matrix, say $W = \begin{pmatrix} \lambda_1 & 0 & 0 \\ 0 & \lambda_2 & 0 \\ 0 & 0 & \lambda_3 \end{pmatrix}$ with $\lambda_1 < \lambda_2 < \lambda_3$.

Let $u = (u_1, u_2, u_3)^T$ with $u^T u = 1$, then $u^T W u = u_1^2 \lambda_1 + u_2^2 \lambda_2 + u_3^2 \lambda_3$. In order to minimize this value, we need to maximize $u_1$ and minimize $u_2$ and $u_3$, therefore $u = (1,0,0)^T$ which is the eigenvector corresponding to the lowest eigenvalue.

If $W$ is not diagonal but diagonalizable, the same argument goes through: $W = R^T \tilde W R$ for a diagonal $\tilde W$, then $u^T W u = (Ru)^T \tilde W (Ru)$. We have to choose $Ru$ to be the eigenvector of the lowest eigenvalue of $\tilde W$, this corresponds to $u$ being the eigenvector of that eigenvalue of $W$.

The paper probably assumes that $w(\theta)$ is a symmetric function, then $W$ is a symmetric matrix (substitute $\theta\mapsto -\theta$ in the integral) and hence diagonalizable. If $W$ wasn't, we'd get a similar result but we'd have to talk about generalized eigenspaces.