Discrete Fourier Transform as a rotation of Coordinates -

My intent in this article is to help engineers to gain more insight about Fourier Transform by emphasizing the geometrical aspect of the transform. I only consider the discrete case, where data is sampled and is of finite length. Besides its ubiquitous appearance in practical situations, finite discrete data is easier to work with. To treat the infinite case (whether discrete or continuous), we need concepts from the field of Functional analysis which may be quite complex and will probably distract the reader.

I show here that the Discrete Fourier Transform (DFT) of a signal represents the same signal in a rotated coordinate system embedded in the complex mathematical space $\mathbb{C}^N$ . This representation is definitely not new, but is usually not emphasized in typical engineering curricula. In my personal opinion, it is very helpful in strengthening that signals can be considered as an entity and its time domain image is just one (convenient) representation.

We consider a sampled data, possibly collected through measurement. The data will be labelled as follows

(1) $\begin{equation*} \mathbf{c}=[c_0, c_1, c_2,\cdots,c_{N-1}]. \end{equation*}$

The data can be visualized to be a vector $\mathbf{c}$ in the complex space containing all $N$ tuples $\mathbb{C}^N$ . Note that we used a zero indexing to label the data sequence. Usually $\mathbf{c}$ is a sequence of real numbers. The figure below shows $\mathbf{c}$ in the two dimensional space.

Rendered by QuickLaTeX.com

The sampled data $\mathbf{c}$ appears in the \emph{natural} coordinate system $\mathbf{e_0},\mathbf{e_1}$ , where $\mathbf{e_0}=[1, 0]$ and $\mathbf{e_1}=[0,1]$ . In a general space $\mathbb{C}^N$ , there are $N$ such vectors $\mathbf{e_0}, \mathbf{e_1}, \mathbf{e_2}, \cdots, \mathbf{e_{N-1}}$ ,

$\begin{align*} \mathbf{e_0}&=[1, 0, \cdots, 0]\\ \mathbf{e_1}&=[0, 1, \cdots, 0]\\ \vdots\\ \mathbf{e_{N-1}}&=[0, 0, \cdots, 1]. \end{align*}$

In the 2D case, a simple signal $\mathbf{c}=[c_0, c_1]$ can be represented in terms of $\mathbf{e_0}$ and $\mathbf{e_1}$ as

(2) $\begin{equation*} \mathbf{c}=[c_0, c_1]=c_0\mathbf{e_0}+c_1\mathbf{e_1} \end{equation*}$

The signal strengths $c_0$ and $c_1$ can be interpreted as the projections of the vector $\mathbf{c}$ onto $\mathbf{e_0}$ and $\mathbf{e_1}$ .

As I will discuss in a different article, an important class of dynamic systems is the class of linear time invariant systems. The response of these systems can be described convolving the signal $\mathbf{c}$ with the impulse response. Additionally, for a discrete system the convolution operation can be described by a circulant matrix (operator). Circulant matrices have a very interesting property: they all have eigenvectors that form another basis (coordinates in $\mathbb{C}^N$ \{ $\mathbf{e_0'}, \mathbf{e_1'}, \cdots, \mathbf{e_{N-1}'}\}$ that can be written as

$\begin{align*} \mathbf{e_k'}=\left[\frac{1}{\sqrt{N}}e^{\frac{2\pi ink}{N}}\right]_{n=0}^{N-1}. \end{align*}$

It can be shown that such set indeed form a complete orthonormal basis. As usual, the inner product of two vectors $\mathbf{u}$ and $\mathbf{v}$ is defined as

(3) $\begin{equation*} (\mathbf{u},\mathbf{v})=\sum_{k=0}^{N-1}u_k^*v_k, \end{equation*}$

where $u_k^*$ is the complex conjugate of $u_k$ .

As mentioned above, the set $\{\mathbf{e_0'}, \mathbf{e_1'}, \cdots, \mathbf{e_{N-1}'}\}$ forms an orthonormal basis that spans $\mathbb{C}^N$ . This means that we can equally express any signal ( $\mathbf{c}$ for example) as a linear combination of the set $\{\mathbf{e'}\}$ . Therefore, we can write

(4) $\begin{align*} \mathbf{c}&=\sum_{k=0}^{N-1}C_k\mathbf{e'_k}. \end{align*}$

The coefficients $C_k$ appearing in the above equation are nothing but the projections of $\mathbf{c}$ onto the coordinates $\{\mathbf{e_k'}\}$ .

In 2D, $\mathbf{e_0'}$ and $\mathbf{e_1'}$ become

$\begin{align*} \mathbf{e_0'}&=\frac{1}{\sqrt{2}}[1, 1]\\ \mathbf{e_1'}&=\frac{1}{\sqrt{2}}[1, -1], \end{align*}$

which is equivalent to rotating $\mathbf{e_0}$ and $\mathbf{e_1}$ by -45 degrees as shown below

Rendered by QuickLaTeX.com

In $\mathbb{C}^3$ $\mathbf{e_1'}, \mathbf{e_2'}$ are complex. Please see the figure below

Rendered by QuickLaTeX.com

To find $C_k$ appearing in (4) we use the important concept that $\mathbf{c}$ is a unique entity regardless of the representation. This means that

(5) $\begin{equation*} \sum_{k=0}^{N-1}c_k\mathbf{e_k}=\sum_{k=0}^{N-1}C_k\mathbf{e_k'}. \end{equation*}$

We then exploit the orthogonality of the different $\mathbf{e_k'}$ and take the inner product of both sides of the above equation by $\mathbf{e_m'}$ . This means that all the terms at the right hand side vanish except for $\mathbf{e_m'}$ . Therefore,

(6) $\begin{equation*} \sum_{k=0}^{N-1}(\mathbf{e_m'},\mathbf{e_k})c_k=C_m. \end{equation*}$

Note that $e_k(i)=0$ unless $i=k$ . Therefore it is straightforward to show that

(7) $\begin{equation*} (\mathbf{e_m'},\mathbf{e_k})=\frac{1}{\sqrt{N}}e^{-\frac{2\pi i mk}{N}}. \end{equation*}$

Therefore, we can write $C_m$ as

(8) $\begin{equation*} C_m=\frac{1}{N}\sum_{k=0}^{N-1}c_ke^{-\frac{2\pi i mk}{N}}. \end{equation*}$

The above expression is precisely the discrete Fourier transform (DFT) of the sequence $\{c_k\}$ ‘. From a geometric point of view, it is the formula to calculate the components of the vector $\mathbf{c}$ onto the coordinate system $\mathbf{e_k'}$ . Therefore,

The projections of $\mathbf{c}$ in the $\mathbf{e}$ coordinate system represent the original sequence, while the projections in the $\mathbf{e'}$ system are the DFT components.

In 2D, the relation between the signal and its DFT can be plotted as shown below

Rendered by QuickLaTeX.com

Plancherel and Parseval’s theorem

The norm of the vector $\mathbf{c}$ is an invariant quantity. This means that it does not depend on the coordinate system. Accordingly

(9) $\begin{equation*} \sum_{k=0}^{N-1}|c_k|^2=\frac{1}{N}\sum_{k=0}^{N-1}|C_k|^2, \end{equation*}$

which is known as Plancherel theorem. Similarly the inner product of any two vectors $\mathbf{u}$ and $\mathbf{v}$ in $\mathbb{C}^N$ is invariant. Therefore,

(10) $\begin{equation*} (v,u)=\sum_{k=0}^{N-1}v_k^*u_k=\sum_{k=0}^{N-1}V_k^*U_k, \end{equation*}$

which is Parseval’s theorem.

Uncertainty Relation

One of the most important properties of Fourier transforms is the uncertainty principle. The uncertainty principle is a fundamental concept in Quantum mechanics.

Assume for now that $\mathbf{c}=\mathbf{e_n}$ . Geometrically this means that $\mathbf{c}$ is in the direction of the basis vector $\mathbf{e_n}$ and orthogonal to other $\mathbf{e_k}$ , where $k\neq n$ . Using \label{eq:dft}, it is easy to show that such vector has projections of equal strength in the $e'$ coordinate system. This means that being aligned with one of the coordinate axes of $e$ (localized) implies that $\mathbf{c}$ is “equally distributed” over $e_k'$ vectors. This is an emphasis of the uncertainty principle. In Quantum mechanics for example, if the particle state (think of it as the vector $\mathbf{c}$ ) is aligned with one of the vectors that represent position (the $e$ system of coordinates) then its momentum (the Fourier transform of position ) has equal projections onto all $\mathbf{e_k'}$ and hence not determined.

PDF version of the current article: Fourier Transform.