next up previous
Next: Signal Through System in Up: Fourier Transforms and Signal Previous: Vector Space and Orthogonal

Orthogonal transform as rotation of basis vectors

The discrete Fourier transform, as one of many possible orthogonal transforms (e.g., discrete cosine transform, etc.), can be considered as a rotation of the standard basis vectors. A signal as a N-D vector ${\bf x}=[x[0],\cdots,x[N-1]]^T$ is represented implicitly by the standard basis. It can be equivalently represented by any other basis, some rotated version of the standard basis. This idea can be illustrated by the following example of an N=2 dimensional vector space.

A 2-D vector space is spanned by two standard basis vectors:

\begin{displaymath}{\bf e}_0=\left[\begin{array}{c}1 0\end{array}\right],\;\;\;\;\;
{\bf e}_1=\left[\begin{array}{c}0 1\end{array}\right] \end{displaymath}

A vector ${\bf x}=[x[0],x[1]]^T=[2,1]^T$ can be represented by these basis vectors as:

\begin{displaymath}{\bf x}=\left[\begin{array}{c}2 1\end{array}\right]=x[0]{\b...
...{array}\right]
+1\left[\begin{array}{c}0 1\end{array}\right] \end{displaymath}

This 2-D vector space can also be spanned by another basis composed of two vectors, such as the standard basis rotated clockwise by $\theta=45^\circ$. This rotation is represented by a $2 \times 2$ rotation matrix:

\begin{displaymath}{\bf R}=\left[ \begin{array}{rr}\cos\theta&\sin\theta -\sin...
...{\sqrt{2}}\left[ \begin{array}{cr}1&1 -1&1\end{array}\right] \end{displaymath}

Obviously this matrix is orthogonal:

\begin{displaymath}{\bf R}^T{\bf R}
=\frac{1}{2}\left[ \begin{array}{cr}1&-1 1...
...ght]
\;\;\;\;\;\;\mbox{i.e.}\;\;\;\;\;
{\bf R}^{-1}={\bf R}^T
\end{displaymath}

The new basis vectors can then be obtained as:

\begin{displaymath}{\bf b}_1={\bf R}{\bf e}_0=\frac{1}{\sqrt{2}}\left[ \begin{ar...
...frac{1}{\sqrt{2}}\left[\begin{array}{r}1 1\end{array}\right] \end{displaymath}

The same vector ${\bf x}$ can also be represented by the new basis:

\begin{displaymath}{\bf x}=c_0{\bf b}_0+c_1{\bf b}_1 \end{displaymath}

The coefficients $c_0$ and $c_1$ can be obtained as the projections of ${\bf x}$ onto the two basis vectors:

\begin{displaymath}c_0=<{\bf x},{\bf b}_0>=\frac{1}{\sqrt{2}}[2,1]\left[\begin{a...
...t[\begin{array}{r}1 -1\end{array}\right]
=\frac{1}{\sqrt{2}}
\end{displaymath}

Now the same vector can also be expressed as:

\begin{displaymath}{\bf x}=c_0{\bf b}_0+c_1{\bf b}_1
=\frac{3}{2}\left[\begin{ar...
...d{array}\right]
=\left[\begin{array}{c}2 1\end{array}\right] \end{displaymath}

We see that the vector ${\bf x}$ can be equivalently represented by either $x[0]=2$ and $x[1]=1$, or $c_0=3/\sqrt{2}=2.121$ and $c_1=1/\sqrt{2}=0.707$, depending on which basis is used.

e102rotation.gif

The vector ${\bf x}=[2,1]^T$ can be considered as a discrete signal of $N=2$ samples:

\begin{displaymath}x[n]=\sum_{k=0}^{N-1} x[k]\delta[n-k]=x[0]\delta[n]+x[1]\delt...
...\left\{ \begin{array}{ll} 2 & n=0 1 & n=1\end{array} \right. \end{displaymath}

In fact, this rotation is the discrete Fourier transform of signal of $N=2$ samples:


\begin{displaymath}x[n]=\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} c_k e^{j2\pi kn/N}
=\...
...\left\{ \begin{array}{ll} 2 & n=0 1 & n=1\end{array} \right. \end{displaymath}

Conclusion:

The N-point Discrete Fourier transform is essentially a rotation of the standard basis vectors to a set of new basis vectors representing different frequencies. More generally, each of the infinitely many possible rotations of the standard basis vectors corresponds to a certain orthogonal transform, and the Fourier transform is only one of these transforms. Also as an orthogonal transform is simply a rotation of the basis of the vector space, it does not change the norm (length) of a vector, i.e., the energy contained in a signal is conserved before and after the transform, this is the Parseval's identity.

e102rotation1.gif


next up previous
Next: Signal Through System in Up: Fourier Transforms and Signal Previous: Vector Space and Orthogonal
Ruye Wang 2010-01-16