Harmonic Analysis on



Harmonic Analysis on Zn

Tomomi Haynes

Math 4495

Dr. Derado

December 14, 2005

Harmonic analysis is the branch of mathematics which studies the representation of functions or signals as the superposition of basic waves. It investigates and generalizes the notions of Fourier series and Fourier transforms. Also, the basic waves are called “harmonics”, hence the name “harmonic analysis.”

Since the name of the field is taken after the great French mathematician Jean Baptiste Joseph Fourier, one may think that the area of study was developed mainly by him. However, nothing is farther from the case. Fourier may be the prominent figure who is directly responsible for the development of Harmonic Analysis in the last two centuries, but he owes his achievements to the mathematicians before him. When describing his achievement in physics and astronomy, Newton once dedicated his achievement to Galileo and Kepler by noting, “If I have seen further [than certain other men] it is by standing upon the shoulders of giants.” This may well apply to the case of Fourier. There were indeed many contributions made by other mathematicians and scientists whose ideas helped Fourier to formulate his idea of decomposing a function into a sum of sinusoids or “waves.” In Trigonometric Delight (1998), Eli Maor eloquently describes the mathematical movement in the 17th and 18th centuries that influenced Fourier’s formulation of the theorem.

One of the movements that influenced Fourier’s theorem is the shift in the treatment of trigonometry. Trigonometry had begun to assume its modern and analytic character with the great French mathematician, Francois Viete (1540-1603). With Viete, trigonometry underwent important changes, one of which is admitting infinite processes. In 1593, he discovered the famous infinite product

[pic]

It was the first time an infinite process was explicitly written as a mathematical formula, and this was the beginning of modern analysis. In England, substantial contributions to trigonometry were also made in the first half of the seventeenth century. One of contributions which had an impact on Fourier’s theorem may be John Wallis’s (1616-1703) work on infinite series that is an immediate forerunner to Newton’s discoveries in the same field. Wallis, more than anyone else up to his time, realized the importance of analytic methods in mathematics: he was the first to treat conic sections as quadratic equations rather than geometric objects. His most famous formula is the infinite product

[pic]

which together with Viete’s product are regarded as the most beautiful formulas in mathematics.

There was another reason for the rise of analytic trigonometry in the first half of the seventeenth century. Instead of applying trigonometry to heavens (spherical problems), mathematicians and scientists were interested in the mechanical world of daily life. The science of artillery was also developed during the century. Another branch of mechanics studied in the seventeenth and eighteenth centuries was oscillations. Due to the great sea voyages of the era, ever more accurate clocks of ever greater precision were heavily in demand. This led scientists to study the oscillations of pendulums and springs of various kinds. On another level, the increased skill and sophistication in building musical instruments motivated scientists to study the vibrations of sound-producing bodies such as strings, membranes, bells and air pipes. What is so significant about all these developments is that they all underscored the role of trigonometry in describing periodic phenomena which resulted in trigonometric functions---one of the essences of Fourier’s theorem.

It was not until Euler that trigonometry was fully incorporated with complex numbers for Fourier to later utilize it in his work. With Euler, the subject became truly analytic. Euler’s formula,

[pic],

which appeared in his great work, Analysin infinitorum (1748) expresses a deep relationship between trigonometric functions and the complex exponential function.

These developments moved trigonometry ever farther from its original connection with a triangle.

The outstanding problem in the second half of the eighteenth century was the vibrating string. Pythagoras, in the sixth century B.C., already discovered some of the laws governing the vibrations of a string. However, it was not until after the time of Newton and Leibniz that a full investigation of the problem was possible. This was due to the absence of partial differential equations. For the vibrating string the relevant equation is

[pic],

where [pic]is the displacement from equilibrium of a point at a distance[pic]from one endpoint of the string at time[pic], and [pic]is a constant that depends on the physical parameters of the string, which is its tension and linear density. This equation, known as the one-dimensional wave equation, excited the best mathematical minds of the time. Euler and D’Alembert expressed their solutions in terms of arbitrary functions representing two waves. On the other hand, Daniel Bernoulli found a solution involving an infinite series of trigonometric functions. These two types of solution to the same problem looked so different, the question arose whether they could be reconciled, and if not, to find out which was the more general. This question was answered by Fourier in his most important work, Theorie analytique de la chaleur (Analytic theory of heat, 1822). He showed that almost any function, when regarded as a periodic function over a given interval, can be represented by a trigonometric series of the form

[pic]

[pic]

where the coefficients [pic]and [pic]can be found from [pic]by computing certain integral.

We would like to see what he means by it by observing his study on heat propagation through Eli Maor’s account.

Fourier was particularly interested in the manner in which heat flows from a region of high temperature to one of lower temperature. The Law of cooling, previously discovered by Newton governed only the temporal rate of change of temperature, not its spatial rate of change. To deal with this problem, one must use the analytic tools of the continuum, in particular partial differential equations. Fourier showed that to solve such an equation, one must express the initial temperature distribution as a sum of infinitely many sine and cosine terms, which is now called Fourier series. This moment was the beginning of Harmonic Analysis.

The most remarkable advancement made in Harmonic Analysis in the last century is probably the invention of Cooley-Tukey fast Fourier transform algorithm known as FFT. It re-expresses the discrete Fourier transform (DFT) of an arbitrary composite size n = n1n2 in terms of smaller DFTs of sizes n1 and n2 recursively, in order to reduce the computation time to O(n log n) for highly-composite n (called smooth numbers). This algorithm, including its recursive application, was already known around 1805 to Carl Friedrich Gauss who used it to interpolate the trajectories of the asteroids Pallas and Juno, but unfortunetely, his work was not widely recognized. The effect of Cooley and Tukey’s algorithm was particularly significant in the area of signal processing, probably the best-known application of Fourier analysis. We would like to see some basic examples of signal processing at the end of the paper.

Applications of the use of Fourier transform are endless, for instance, Radon transform was advanced in the early 1900s by the mathematician from whom it takes its name. Fourier analysis are also found in x-ray crystallography, computerized tomography known as CT scanners, in the field of nuclear magnetic resonance, and in radioastronomy and modern Cosmology.

The next section of this paper explores the connections between Fourier’s transform and the notions that are essential to the development of Fourier transform.

Harmonic Analysis on Zp

I Let G[pic]= {e[pic],[pic]}.

(1) Show that G[pic] is a commutative group.

(2) For which p G[pic] is a cyclic group.

(3) Find a relation to the modular arithmetic.

Before answering the questions above, we would like to revisit the notion of roots of unit and a concept of group introduced in abstract algebra; in particular, we want to review the properties of group[pic]. The first reason to this is that [pic]is the set of roots of unity and the second reason is that the operation of [pic]is twofold. That is,[pic]has a complex multiplication as its binary operation; however, multiplying a complex number means adding exponents of [pic]which ultimately leads us to addition modulo p.

A. [pic]th Roots of Unity

n th roots of unity are the solutions to the equation[pic]. As the consequence of the fundamental theorem of algebra, we are guaranteed to have n different nth roots of unity.

[pic] (k = 0, 1, 2, 3, …, n-1)

Recall an important property of roots of unity: the sum of roots of unity is 0; that is,

[pic]

B. The properties of group[pic]

[pic]is a group under addition modulo p. We will show that it is a group by showing that the following properties hold:

a) Closure

b) Associative laws

c) Identity

d) Inverse

(a) Closure:

Before proving that [pic]is closed in general term, let us look at the case with p = 3. Let [pic]and [pic].

When[pic], [pic].

When[pic], [pic]

When[pic][pic].

When [pic][pic].

So we can say that [pic]is closed under addition modulo 3. This also implies that any number in[pic], we can find a number in [pic] that is congruent to that number. Notice also that [pic]is a cyclic group. That is, [pic]and[pic], i.e., 1 and -1 [pic] are generators of[pic]. Because of this property, no matter what integer we use for[pic] to do the operation, all the results of the operation belong to[pic]. This confirms the fact that [pic] is closed under modulo arithmetic. Let us look at the examples to see what it means by a group being cyclic. By definition, when the operation is addition, [pic]is interpreted as [pic] when [pic]is positive. [pic]is interpreted as [pic] when [pic]is negative.

[pic][pic]

[pic][pic]

[pic][pic]

[pic][pic]

[pic],[pic]

[pic][pic]

[pic][pic]

So basically, if a group is cyclic, any number in Z can be expressed in terms of elements in[pic]since we can always find a number in [pic]that is congruent to that number. In other words, all [pic]belong to one of class representatives, {0}, {1}, {2},…, {p-1}.

For example, with our case p=3, every number in Z belongs to either

{…,-3p, -2p, -1p, 0, p, 2p, 3p,…},

{…, 1-3p, 1-2p, 1-p, 1, 1+p, 1+2p, 1+3p,…}, or

{2-3p, 2-2p, 2-p, 2, 2+p, 2+2p, 2+3p,…}.

Therefore, [pic]is closed under modular arithmetic.

(b) Associative laws:

Associative laws hold under addition modulo p because of the fact that associative laws hold under addition..

Let [pic]. Then[pic]

This implies that [pic][pic]

(c) Identity:

[pic]is the identity of [pic], if for any k in [pic], [pic]. So if [pic] is a group under addition modulo p, there is a unique element [pic] in [pic] such that [pic] for all k in[pic]. Since the operation involves addition, the identity of [pic]is 0 just as the identity of [pic]is 0 under addition.

For example, when p = 3.

[pic][pic]since 0 and 3 are congruent.

[pic][pic][pic]since 4 and 1 are congruent.

[pic][pic], [pic][pic]since 2 and 5 are congruent.

In general,[pic] = k for all[pic].

(d) Inverse:

For each element k in[pic], there is an element m in[pic], called the inverse of k, such that [pic]. Let us find the inverse of each element in[pic]when p = 3 and derive the generalization from it.

[pic]. So -1 is the inverse of 1. The equivalent relation we are dealing with is addition modulo p, so we have to express -1 in terms of one of class representatives. We do so by applying modular arithmetic. [pic]. Since 2 is congruent to -1, we can replace -1 with 2 which is in[pic]. Applying addition modulo 3, we get, [pic] So 1 and 2 are inverse of each other just as 1 and -1 are.

0 + (-0) = 0 and[pic]. So we can say that 0 is the inverse of itself just as integers such as -3n, 3n are inverses of 0 for any[pic].

So in general, we can say that k and p-k are inverse of each other because k + (p – k) = p[pic]mod p = 0.

Now we are ready to prove that G[pic] is a group. First, G[pic] is non-empty because [pic]. The binary operation for the set is the complex multiplication which is ultimately the operation under addition modulo p.

Now, we need to show that:

(a) G[pic] is closed under complex multiplication.

(b) Associative laws hold;

(c) Identity exists;

(d) And inverse exists.

(a) Closure:

We are going to look at a few examples before proving the general case. Let us begin with the case when p = 2, that is[pic][pic]. Let k, [pic]=[pic]. Then [pic]. For G[pic]to be a group, it must be closed under complex multiplication. What it means is that [pic]must be in G[pic]. So it ultimately means that[pic]. From our observation on[pic], we claim that G[pic] is closed if exponents of each element in G[pic]are closed under modular arithmetic.

Let us examine this claim with examples using p = 2, and p = 3.

When p=2, G[pic]=[pic][pic], for k = 0, 1.

Let [pic] and[pic], then [pic] [pic][pic].

If[pic] and [pic] [pic] [pic][pic].

If [pic] and[pic], then [pic][pic][pic].

If [pic]and [pic], then [pic][pic][pic].

[pic]is closed under complex multiplication because the operation is ultimately the addition modulo p.

When p = 3, G[pic]=[pic][pic], for k = 0, 1, 2.

Let [pic] and[pic]. Then, [pic][pic][pic].

If [pic] and[pic], then [pic][pic][pic].

If [pic]and[pic], then [pic][pic][pic].

If [pic]and[pic], then [pic][pic][pic].

If [pic]and[pic], then [pic][pic][pic].

So again, [pic]is closed under complex multiplication because the operation on exponents is modular arithmetic. Generalizing this, we can say that [pic]is closed under complex multiplication because [pic] for p ≥ 1 is a group under modular arithmetic.

So for any [pic],[pic].

(b) Associativity:

Let[pic]. We need to show that

[pic] that is, it is equivalent to showing that [pic].

[pic]

[pic]

[pic]

[pic]

[pic].

Therefore, the associative law holds for[pic].

(c) Identity:

Let [pic]be the identity of[pic]. By definition of identity, [pic]is the identity of [pic]if [pic] for any[pic]in[pic] for any[pic]. This implies that we simply need to find some[pic], such that [pic]for any [pic] for the exponent of [pic]. From the preliminary observation made on[pic], we know that k must be 0. So adding the inverse of[pic], which is[pic], to both sides, we obtain[pic].

Thus,[pic]if [pic]. So 1 is the identity of[pic], where k = 0 is the identity of[pic] .

d) Inverses:

By definition of inverse under multiplication, [pic]is the inverse of [pic]if [pic]*[pic][pic]=[pic]. This means that we have to find some number [pic]which satisfy the modular arithmetic (k + k[pic]) mod p = 0. But this has been shown in the preliminary investigation showed that for any k, p-k is the inverse of k. So we know that[pic] and [pic]for any [pic] are the inverse of each other, since

[pic]*[pic]=[pic]

Let us look at some examples using p = 3.

[pic], for k = 0, 1, 2.

The inverse of [pic] is itself since k = 0 and p-k = 3-0 = 3, k-(p-k) = 0 + 3 = 3, and [pic], so [pic] = 1 = [pic].

The inverse of [pic]is [pic]since k = 1 and p – k = 3 – 1 = 2 and[pic].

So generally speaking, for any[pic], if[pic], then [pic] and [pic] are inverse of each other.

Finally, we are ready to answer the questions listed at the beginning of this section.

(1) Show that [pic]is a commutative group.

What needs to be shown here is that [pic] is Abelian. But this is obvious because the binary operation used for [pic]is the multiplication of complex numbers and multiplication is commutative. Under this operation, we need to apply modular arithmetic on exponents of [pic] but this operation is also commutative under addition modulo p. So we have,

[pic].

(2) For which p [pic]is a cyclic group.

[pic]is a cyclic group if an element in [pic]generates every element in[pic], that is,

[pic]= [pic]. This ultimately means that k must be a number that generates all elements of [pic] when multiplied by[pic]. Let us look at a few examples to see what we can conjecture about the relation between p and k.

When p = 2, [pic]for k = 0, 1.

When k = 0.

[pic] for any[pic]. So, k = 0 fails to be a number for which [pic]is a generator of[pic]. The relation between 0 and 2 are not clear. So we proceed with more observation on[pic].

When k = 1.

[pic]. So k = 1 is a number where [pic] generates all elements of [pic] when raised to[pic] power where [pic].

For example,

[pic], [pic], [pic],

[pic],[pic]and so forth. So [pic] is a generator of[pic]. It looks like [pic] is the relation we need for generating all elements of[pic], but what is the relation? We take a look at one more example since this example does not seem to be sufficient to conjecture any thing for the relation between k and p. So let us look at another example with p = 3. When p = 3, [pic]for k = 0, 1, and 2.

When k = 0.

[pic]for any[pic]. So, k = 0 again fails to be the number for which [pic]is a generator of[pic].

When k=1.

[pic]. So k = 1 is again a number where [pic]generates all elements of[pic].

For example,[pic],[pic], [pic],

[pic], [pic], [pic]and so on.

So it appears that [pic] is the relation between k and p for which [pic]is a generator of

[pic]. What about[pic], where[pic]?

[pic] ,[pic], [pic],

[pic], and [pic].

From these two examples, it appears that when [pic] and [pic]are relatively prime,[pic] generates every element of[pic]. So our conjecture is

[pic]is a generator of[pic][pic][pic]

Now we prove that the conjecture is true. Suppose that k and p are not relatively

prime. Then there exists a number other than 1 that is the greatest common divisor of [pic]and[pic]. This means that [pic] and [pic] for some[pic]. Then [pic] is a generator of[pic], call it[pic]. Since [pic]is a generator of[pic],[pic]. Notice that [pic]. So if we let [pic][pic]should generate an element of [pic]other than [pic]itself since[pic]. So[pic] which implies that [pic] by theorem. This is true only when[pic]. So [pic]cannot be a generator of[pic].

Suppose that [pic] is not a generator of[pic]. Then there exists j in Z such that [pic] is not a generator of[pic]. Since k and p are relatively prime, there is no common factor other than 1. That means that [pic] generates all elements in [pic] since [pic] for all[pic]. This is a contradiction to our hypothesis that [pic] is not a generator of[pic].

Thus [pic]is a generator of [pic][pic][pic] Q.E.D.

(3) Find a relation to the modular arithmetic.

We observed that the operation on[pic]is twofold. Multiplying complex numbers means applying addition modulo p on the set. So if we describe the relation between [pic]and [pic]in terms of function, we can say that [pic]is a homomorphism. A homomorphism is a mapping that preserves the operation of the group that is used as a domain of the function: that is, [pic]:[pic][pic] is called a homomorphism if [pic]for all[pic]. We need to show that this claim is valid. To do so, we first need to define the function and show that [pic]for all[pic]. [pic]

Define[pic]: Z[pic][pic] by

[pic]

We show that [pic] is a homomorphism.

[pic]

[pic]

[pic]

Thus[pic] is a homomorphism of Z[pic] into[pic]. Now we want to see if [pic] is an isomorphism. By definition, [pic] is an isomorphism if it is a bijection. So we first check to see whether [pic] is an injection then check to see if it is a surjection. The function [pic] is injective if[pic]. We prove this by proving the contrapositive statement of the original statement. That is if [pic]then

[pic]. Let [pic]and[pic]. Then,[pic].

This means that [pic]and [pic].

So we proved that if [pic]then[pic].

To prove that [pic] is surjective, we need to show that if for any [pic]there exists a [pic] for which[pic]. Let[pic], then there exists [pic] for which [pic]and [pic]since all integers are congruent to one of the members of [pic]. Furthermore, [pic]for [pic]for the same reason. Thus [pic] is an isomorphism.

II Let Z[pic]= {0, 1, 2,…, p-1}.

Let H be a set of all functions on [pic]into C.

Define

[pic]

(4) Show that [pic]is an inner (dot) product.

To show that [pic]is an inner product, we need to show that the following axioms are satisfied for all [pic]and [pic]in[pic], and[pic].

(a) [pic]=[pic]

(b) [pic]

(c) [pic]

(d) [pic]and[pic]if and only if [pic]

Properties used in proofs are as follow, and we will refer to them by the numbers corresponding to them:

For any complex numbers[pic],

[pic]---------- (1)

[pic]----------------------- (2)

[pic]------------------- (3)

[pic]----------------- (4)

Proof of (a)

[pic][pic]

[pic]

[pic]

[pic], by (1)

[pic], by (2)

[pic]

[pic]

Proof of (b)

[pic]=[pic]

[pic] [pic] [pic]+…+ [pic]

[pic]

[pic]

=[pic]

Proof of (c)

[pic]

[pic])

[pic], by definition.

Proof of (d)

[pic]

=[pic], by (3)

[pic]

[pic]if and only if [pic]

[pic]=0[pic][pic][pic]

[pic][pic]

[pic][pic]

[pic][pic].

Notice: The roots of unity could be understood as functions in H. Precisely,

[pic]is defined by

[pic]

[pic]

(5) Show that [pic] are orthogonal i.e., [pic] if [pic]and[pic].

Let us compute[pic] when p = 3.

[pic]

[pic]

[pic]

Let us compute[pic].

[pic]

=[pic]

[pic]

Let us compute [pic]

[pic]

[pic]

[pic]

Now we would like to compute general case of[pic].

[pic]

[pic]

If [pic]

[pic]

If[pic] then[pic]. Since [pic]the exponents of each term is distinct. So, [pic]

This implies that we are adding the sum of roots of unity. By the theorem we learned, know that the sum of roots of unity is 0. Thus,

[pic]

If[pic], then [pic]. So the sum of all terms would be

[pic] because we would have to add 1 for p times. Thus, [pic]are orthogonal, that is, [pic] if [pic] Below is the computation of [pic]which is the case when[pic].

[pic]

[pic]

[pic]

= [pic][pic]. This implies that[pic].

In general,

[pic]

where [pic]is the Kronecker delta.

We can look at the same result in terms of matrix. The [pic] roots of unity can be used to form an [pic] x [pic] matrix whose [pic]entry is

[pic]

When [pic]

[pic]

From above, the columns of this matrix are orthonormal and thus the matrix is unitary. In fact, this matrix is precisely the discrete Fourier transform.

III Define

[pic]

(6) Show [pic]is a norm.

In complex inner product spaces, the norm of a complex-valued function f is defined by

[pic]

To show [pic] is a norm, we must show that:

(a) [pic] [pic]

(b) [pic]

(c) [pic]

(d) [pic]

Proof of (a):

[pic], by definition

[pic].

Proof of (b):

[pic], by definition

[pic]

[pic], by definition

[pic], by property of complex number [pic]

[pic]

[pic], by property of complex number [pic] and [pic]is constant.

[pic]

Taking a square root of both sides,

[pic]

[pic], by the property of square root,[pic], iff[pic].

[pic].

Proof of (c):

[pic]

Prove[pic].

[pic]

[pic]

[pic]

[pic].

Prove[pic].

[pic]

[pic][pic]

[pic].

Proof of (d):

[pic]and[pic]are complex valued functions and can be viewed just as a regular complex number [pic]and [pic]. From the properties of inner product on a complex vector space, we know that

[pic]

[pic]

[pic]

Cauchy-Schwarz Inequality for complex inner product spaces

[pic]

[pic]

[pic], by (1)

[pic], by (2)

[pic], by (3)

Since [pic]is a conjugate of[pic], when these complex number are summed, imaginary part of [pic]and [pic] would be equal to 0 and the outcome is composed of twice the real part of the complex number. So we can rewrite [pic] as

[pic][pic]

[pic]

By (4), [pic]

[pic]

Therefore, [pic], by (4)

[pic]

Take a square root of both sides, we obtain,

[pic]

IV Now we define Fourier transform of the functions in H.

Definition: Fourier transform of f is defined

[pic]

where[pic]and[pic]vary from 0 to p-1 because the domain of function in H is [pic].

Show

[pic]

Before proving above statement, we would like to do some preliminary computation using p = 3, we compute [pic]and[pic]assuming [pic]is true.

[pic]

[pic]

[pic]

[pic]

By the properties of [pic] we can rewrite the above expression as

[pic]

[pic]

[pic]

Now let [pic]

[pic]

Let us look at the exponents of [pic]whose terms involve[pic]

[pic][pic]

[pic] [pic]

[pic]

This means that the terms 1,[pic], and [pic] are distinct roots. Therefore, by theorem, the sum of roots of unity is zero. The same can be said with the terms that involve[pic]. So the above expression becomes,

[pic]

[pic]

Next, let [pic]

[pic][pic]

[pic]

[pic]

[pic]

Let us look at the exponents of [pic] whose terms involve[pic].

[pic]

[pic] [pic]

[pic]

Again, each term in the equation turned out to be distinct. The same can be said with the terms with[pic]. So the equation with [pic] becomes,

[pic]

[pic].

Lastly, we let[pic].

[pic]

[pic]

[pic]

Let us look at the exponents of [pic] whose terms involve[pic].

[pic]

[pic] [pic]

[pic]

So each term that involves [pic]is distinct; therefore, the sum of roots of unity is zero: that is, [pic]. Expressing the term [pic] in terms of trigonometric function, we get

[pic] [pic]

[pic]

[pic]

Since the same can be said with the terms with[pic], our equation becomes,

[pic]

[pic]

[pic]

Now we are ready to work on the general case.

Fourier transform of [pic]is defined

[pic]

By the properties of [pic]we can rewrite the expression as,

[pic]

[pic]

[pic]

[pic]

[pic]

Notice that if[pic], terms that involve[pic] become zero as we have seen in example. For example, each term that involves[pic]is distinct because operation involved here is modular arithmetic: therefore, the sum of the root of unity with order p becomes zero. The same thing can be said for the terms with[pic]. Thus, [pic]. When[pic], the terms that involve[pic] become zero for the same reason, leaving only [pic]terms of[pic]. Therefore, [pic].

Thus,[pic].

(8) Show[pic]

Let[pic]. Then, [pic] So

[pic]

[pic]

[pic]

Notice that[pic].

So [pic]

[pic]

(9) Show Parseval identity, i.e., [pic].

[pic]

[pic]

[pic]

Let [pic]

Then, [pic] if [pic]

[pic] if [pic]

Hence,[pic].

(10) Show a few numerical examples. [pic]

Here we would like to present how the concept of Fourier Transform is used in signal processing through a technique called denoising. The problem in signal processing is that during the transportation of the signal through the devices or air, a signal picks up some noise. The result is well known to all of us who have had problems with cell phone signals. Denoising is a procedure of eliminating the noise from signals. In our examples, we analyze the known signal to which random noise was added. Applying Fourier transform to the noisy data, we reconstruct the original example by first keeping only the highest frequencies and discarding other frequencies by setting them to 0. This procedure is what we call denoising.

Example 1: In this example, we took signals which are a superposition of two waves with frequencies at 3 and 37. P is 512. Figure 1 shows the noisy data.

[pic]

Figure 1

Figure 2 below shows the Fourier transform of the data (FFT). Observe high peaks at the frequencies 3 and 37 and symmetrically at 475 and 509, which indicate the main parts of the signal to be cosine waves with frequencies 3 and 37. All the other Fourier transform values are small, and they are coming from the noise. We set them to 0, and then we reconstruct the signal by using the inverse of FFT.

[pic]

Figure 2

Figure 3 below shows the reconstructed signal (in blue) together with original data. Notice that the reconstructing signal avoids high peaks and outliners.

[pic]

Figure 3

Figure 4 shows the reconstructing signal alone. Notice regularity in signal and patterns.

[pic]

Figure 4

The next two figures, Figure 5 and Figure 6, show the reconstruction of the signal without denoising (in red) and the comparison of two signals respectively.

[pic]

Figure 5

[pic]

Figure 6

We can easily see irregularities in the noisy reconstruction and the lack of uniform patterns. The denoising procedure is quite an effective method in eliminating noise from signals when the noise is not substantial, i.e., when in FFT figure, one can easily read the frequencies of the original signal. But sometimes that is not possible. When that is the case, different methods have to be used.

Example 2: In this example, we took a signal which consists of cosine wave with frequency 45. P is 512. Figure 7 shows the noisy data.

[pic]

Figure 7

Figure 8 below shows the Fourier transform of the data. Observe high peaks at the frequencies 45 and symmetrically at 465, which indicate the main part of the signal to be cosine waves with frequencies 45. All the other Fourier transform values are small, and they are coming from the noise. We set them to 0 and reconstruct the signal using the inverse of Fourier Transform.

[pic]

Figure 8

Figure 9 below shows the reconstructed signal together with original data. Notice that the reconstructing signal avoids high peaks and outliners.

[pic]

Figure 9

Figure 10 shows the reconstructing signal alone. Notice regularity in signal and patterns.

[pic]

Figure 10

The next two figures, Figure 11 and Figure 12, show the reconstruction of the signal without denoising and the comparison of two signals respectively.

[pic]

Figure 11

[pic]

Figure 12

Summary

In I, we reviewed what the roots of unity is and the properties of [pic]before plunging into the main problems. As we walked through the problems, we realized that these two notions are essential parts of Fourier Transform and its inverse. When we investigated the properties of[pic], which is a set of roots of unity, we discovered that [pic]is not only a group but also isomorphic to[pic]. In II, we found that [pic]is an inner product in the complex vector space where[pic], which is a set of all functions on [pic]into[pic]. When we viewed the roots of unity as a member of H, we discovered that they are orthogonal and in terms of matrices, it formed an orthonormal matrix which is precisely the discrete Fourier transform. At the end of II, we learned that [pic] is a norm. In III, we defined the Fourier transform and its inverse and showed some important properties: [pic][pic]and[pic]. These are the consequence of the fact that [pic].are orthogonal.

Implication to high school mathematics education

Main notions that are strongly related to high school mathematics education are:

1) Modular arithmetic

When we learn division in school, we tend to put too much emphasis on the quotient itself or the procedure itself. Through this experience, we realize the importance of encouraging students to interpret division in many different ways. For example, it would be more eye opening and interesting if we viewed division as another way of subtraction just as multiplication can be seen as another way of addition. Moreover, it is even more fun to introduce the notion of modular arithmetic by giving students every day problems such as “What month will it be 25 months from now if it is now December? Modular arithmetic is an abstraction of a method of counting that we often use. It may be a little difficult for students to systematically understand this concept; however, it would benefit them greatly when they pursue higher mathematics.

2) What [pic] means

For students to understand Euler’s formula, we need to encourage students to view trigonometry not only as the tool to find out the measures of sides of polygons as we often do, but also to relate it to cords, angles, and points on the unit circle.

3) complex numbers

We ought to rigorously study what [pic] means. Also, to deepen the understanding of complex numbers, we might want to assign students similar reading projects we have conducted in our class.

Bibliography

Anton, Howard. Elementary Linear Algebra. 7th ed. New York: John Wiley & Sons, Inc., 1994

Edwards, Charles Henry. Penney, David E. Differential Equations & Linear Algebra. New Jersey: Prentice-Hall Inc., 2001.

Gallian, Joseph A. Contemporary Abstract Algebra. 5th ed. New York: Houghton Mifflin Company, 1996.

Herstein, I.N. Abstract Algebra. 3rd ed. New Jersey: Prentice-Hall, Inc., 1996.

Maor, Eli. Trigonometric Delights. New Jersey: Princeton University Press, 1998.

Nahin, Paul J. An Imaginary Tale. New Jersey: Princeton University Press, 1998.

Prestini, Elena. The Evolution of Applied Harmonic Analysis. New York: Birkhauser, 1996.

Walker, James S. Fast Fourier Transforms. 2nd ed. New York: CRC press, 1996









................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download