Module 10: Linear Combinations of Other Objects

We'll start with a little re-writing, in a more convenient form:

• Although we used the notation \(f(j)\) to indicate a function on the integers \(j\), we will rename the numbers $$ f(0),f(1),\ldots, f(j),\ldots,f(N-1) $$ to $$ f_0,f_1,\ldots, f_j,\ldots,f_{N-1} $$

• Then, for notational symmetry, we'll rename the coefficients $$ c_0^\prime, c_1^\prime, \ldots, c_{N-1}^\prime $$ to $$ F_0, F_1, \ldots, F_{N-1} $$ so that the sum can be written $$ f_j \eql \sum_{n=0}^{N-1} F_n e^{\frac{2\pi i nj}{N}} $$

• Now, because we allow the \(F_n\)'s to be complex, we must, for symmetry, let the \(f_j\)'s be complex as well.
        \(\rhd\) This is because a complex linear combation can end up being complex.
  • In practice, of course, actual data is real-valued.
  • We can always write the real number \(x\) as the complex number \(x + i0\).
  • We will in fact get complex "data" when we change the \(F_n\)'s to achieve some goal (like noise removal).
  • So, henceforth, we'll assume that the \(f_j\)'s (the data) are complex.

• Next, use the symbol \(\omega\) to denote the complex number $$ \omega \eql e^{\frac{2\pi i}{N}} $$

• With this slight change in notation, the linear combinations become (one for each \(f_j\)): $$ f_j \eql \sum_{n=0}^{N-1} F_n \omega^{nj} $$

  In-Class Exercise 11: Suppose \(N=4\). Write out the unfolded sum for \(f_3\).

• Notice that each \(f_j\) is a linear combination of numbers (complex numbers).

• However, all our theory so far has been developed for:
  • Linear combinations of vectors
  • Linear combinations of functions (polynomials).

• One possibility: extend the theory to make it work for numbers.

  In-Class Exercise 12: What would the theory look like for this extension to linear combinations of numbers? Explore the meaning of span, independence, basis, dimension in this context.

• Let's try putting the numbers into vectors to see if we can make that work.

• The data can be put into a vector quite easily: $$ {\bf f} \eql \vecfour{f_0}{f_1}{\vdots}{f_{N-1}} $$

• Next, let's write the linear combinations for each \(f_j\) one below another: $$\eqb{ f_0 & \eql & \sum_{n=0}^{N-1} F_n \omega^{n\times 0} & \eql & F_0 + F_1 + F_2 + + F_3 + \ldots + F_{N-1} \\ f_1 & \eql & \sum_{n=0}^{N-1} F_n \omega^{n\times 1} & \eql & F_0 + F_1 \omega^1 + F_2 \omega^2 + F_3 \omega^3 + \ldots + F_{N-1} \omega^{N-1} \\ f_2 & \eql & \sum_{n=0}^{N-1} F_n \omega^{n\times 2} & \eql & F_0 + F_1 \omega^{2} + F_2 \omega^4 + F_3 \omega^6 + \ldots + F_{N-1} \omega^{2(N-1)} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ f_{N-1} & \eql & \sum_{n=0}^{N-1} F_n \omega^{n\times (N-1)} & \eql & F_0 + F_1 \omega^{N-1} + F_2 \omega^{2(N-1)} + F_3 \omega^{3(N-1)} + \ldots + F_{N-1} \omega^{(N-1)(N-1)} }$$

  In-Class Exercise 13: Fill in the equation for \(f_3\) above.

• Clearly, this is the same as $$ \mat{f_0 \\ f_1 \\ f_2 \\ \vdots \\ f_{N-1} } \eql F_0 \mat{ 1 \\ 1 \\ 1 \\ \vdots \\ 1} + F_1 \mat{ 1 \\ \omega \\ \omega^2 \\ \vdots \\ \omega^{N-1}} + F_2 \mat{ 1 \\ \omega^2 \\ \omega^4 \\ \vdots \\ \omega^{2(N-1)}} + \ldots + F_{N-1} \mat{ 1 \\ \omega^{N-1} \\ \omega^{2(N-1)} \\ \vdots \\ \omega^{(N-1)(N-1)}} $$ (Think of the above as equations in the \(F_k\) variables.)

• Let's name the vectors above: $$ {\bf d}_0 \eql \mat{ 1 \\ 1 \\ 1 \\ \vdots \\ 1} \;\;\;\;\;\; {\bf d}_1 \eql \mat{ 1 \\ \omega \\ \omega^2 \\ \vdots \\ \omega^{N-1}} \;\;\;\;\;\; {\bf d}_2 \eql \mat{ 1 \\ \omega^2 \\ \omega^4 \\ \vdots \\ \omega^{2(N-1)}} \;\;\;\;\;\; \ldots \;\;\;\;\;\; {\bf d}_{N-1} \eql \mat{ 1 \\ \omega^{N-1} \\ \omega^{2(N-1)} \\ \vdots \\ \omega^{(N-1)(N-1)}} $$

  In-Class Exercise 14: Write out the elements of \({\bf d}_3\).

• We've now expressed the (complex) data vector \({\bf f}\) as a linear combination of the (complex) vectors \({\bf d}_n\): $$ {\bf f} \eql F_0 {\bf d}_0 + F_1 {\bf d}_1 + F_2 {\bf d}_2 + F_3 {\bf d}_3 + \ldots + F_{N-1} {\bf d}_{N-1} $$

• We now cannot resist the urge to put these vectors into a matrix (as columns, of course). Define $$ {\bf D} \eql \mat{ 1 & 1 & 1 & \vdots & 1 \\ 1 & \omega & \omega^2 & \vdots & \omega^{N-1} \\ 1 & \omega^2 & \omega^4 & \vdots & \omega^{2(N-1)} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 1 & \omega^{N-1} & \omega^{2(N-1)} & \ldots & \omega^{(N-1)(N-1)} } $$

  In-Class Exercise 15: What is the fourth column of \({\bf D}\)?

• With which the linear combination of vectors can now be written as $$ {\bf f} \eql {\bf D} {\bf F} $$ where \({\bf F}\) is the vector $$ {\bf F} \eql \vecfour{F_0}{F_1}{\vdots}{F_{N-1}} $$

• Or, when expanded out: $$ \mat{f_0 \\ f_1 \\ f_2 \\ \vdots \\ f_{N-1} } \eql \mat{ 1 & 1 & 1 & \vdots & 1 \\ 1 & \omega & \omega^2 & \vdots & \omega^{N-1} \\ 1 & \omega^2 & \omega^4 & \vdots & \omega^{2(N-1)} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 1 & \omega^{N-1} & \omega^{2(N-1)} & \ldots & \omega^{(N-1)(N-1)} } \mat{F_0 \\ F_1 \\ F_2 \\ \vdots \\ F_{N-1} } $$

• In which case, if \({\bf D}^{-1}\) exists, $$ {\bf F} \eql {\bf D}^{-1} {\bf f} $$

• Terminology:
  • The computation of \({\bf F} = {\bf D}^{-1} {\bf f}\) is called the Discrete Fourier Transform (DFT).
  • Going the other way, \({\bf f} = {\bf D} {\bf F}\) is called the Inverse Discrete Fourier Transform (I-DFT).

• More terminology:
  • The matrix \({\bf D}^{-1}\) is called the DFT matrix.
  • The matrix \({\bf D}\) is called the inverse-DFT matrix.

Let's step back for a moment and summarize:

• We started with a function \(f(t)\) and its Fourier representation $$ f(t) \eql \sum_{n=-\infty}^{\infty} c_n e^{\frac{2\pi i n t}{T}} $$

• Two reasons led us to discretization:
  • The computation of the coefficients is complicated and inefficient.
  • Actual data in applications tends to be discrete
          \(\rhd\) Example: sound is sampled in digital form.

• Then, with \(N\) discrete data or a function discretized at \(N\) points, we have \(N\) values (numbers): \(f(0),f(1),f(2),\ldots, f(N-1)\).

• We showed that, because of the properties of sine's and cosine's the discretized infinite linear combination becomes finite $$ f(j) \eql \sum_{n=0}^{N-1} c_n^\prime e^{\frac{2\pi i nj}{N}} $$ which we rewrote (change of notation) as: $$ f_j \eql \sum_{n=0}^{N-1} F_n \omega^{nj} $$

• Let's write out the equation for each \(j\): $$\eqb{ f_0 & \eql & \sum_{n=0}^{N-1} F_n \omega^{n\times 0} & \eql & F_0 + F_1 + F_2 + + F_3 + \ldots + F_{N-1} \\ f_1 & \eql & \sum_{n=0}^{N-1} F_n \omega^{n\times 1} & \eql & F_0 + F_1 \omega^1 + F_2 \omega^2 + F_3 \omega^3 + \ldots + F_{N-1} \omega^{N-1} \\ f_2 & \eql & \sum_{n=0}^{N-1} F_n \omega^{n\times 2} & \eql & F_0 + F_1 \omega^{2} + F_2 \omega^4 + F_3 \omega^6 + \ldots + F_{N-1} \omega^{2(N-1)} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ f_{N-1} & \eql & \sum_{n=0}^{N-1} F_n \omega^{n\times (N-1)} & \eql & F_0 + F_1 \omega^{N-1} + F_2 \omega^{2(N-1)} + F_3 \omega^{3(N-1)} + \ldots + F_{N-1} \omega^{(N-1)(N-1)} }$$

• Then, we put this in vector form $$ {\bf f} \eql F_0 {\bf d}_0 + F_1 {\bf d}_1 + F_2 {\bf d}_2 + F_3 {\bf d}_3 + \ldots + F_{N-1} {\bf d}_{N-1} $$ with the understanding that \({\bf f}\) is the data in complex form (zero imaginary part).

• This expresses a complex vector as a linear combination of the special vectors $$ {\bf d}_0 \eql \mat{ 1 \\ 1 \\ 1 \\ \vdots \\ 1} \;\;\;\;\;\; {\bf d}_1 \eql \mat{ 1 \\ \omega \\ \omega^2 \\ \vdots \\ \omega^{N-1}} \;\;\;\;\;\; {\bf d}_2 \eql \mat{ 1 \\ \omega^2 \\ \omega^4 \\ \vdots \\ \omega^{2(N-1)}} \;\;\;\;\;\; \ldots \;\;\;\;\;\; {\bf d}_{N-1} \eql \mat{ 1 \\ \omega^{N-1} \\ \omega^{2(N-1)} \\ \vdots \\ \omega^{(N-1)(N-1)}} $$

We are now led to some burning questions:

• Are the special vectors \({\bf d}_0,{\bf d}_1,\ldots,{\bf d}_{N-1}\) independent?

• Do they form a basis? A basis for what space?

• How do we compute the coefficients \({\bf F}=(F_0,F_1,\ldots,F_{N-1})\)?

• Why are we doing all this? Why is this useful?

Let's look into some of these questions next.