Mathematics desk
< November 20	<< Oct \| November \| Dec >>	November 22 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 21

Inverse fourier transforms

So fourier tranforms give you a function that's sort of a histogram of how often each frequency occurs.. how can there possibly be an inverse transform? How does the inverse transform function know where a certain frequency occured in the original function? Is this information in the complex part of the transform? Or does the inverse transform give you a family of functions? .froth. (talk) 04:08, 21 November 2008 (UTC)[reply]

If by "where" you mean phase (waves), yes, that's "in the complex part": the argument describes a rotation about the time-axis. (If the original function is real-valued, the imaginary parts of the positive and negative frequencies will cancel.) —Tamfang (talk) 05:34, 21 November 2008 (UTC)[reply]

Can't you just imagine The Doctor saying "a rotation about the time-axis"? —Tamfang (talk) 05:36, 21 November 2008 (UTC)[reply]

Well what I mean is.. say you have a function that's high-frequency at first, then low-frequency. The frequency distribution is roughly a flat line, so how can you know from the frequency distribution that in the original function the high-frequency was first and not the low-frequency? I suspect your answer is exactly what I'm looking for but I'm not sure. If you ONLY have that flat-line graph, will the inverse transform actually give you an exact solution for the original function or does it give you a function of the phase function, whatever it is? .froth. (talk) 06:22, 21 November 2008 (UTC)[reply]

Or do I have it completely wrong and the result of Fourier transforms is more than two-dimensional? .froth. (talk) 06:31, 21 November 2008 (UTC)[reply]

Froth, the inverse Fourier transform does "know" where the high frequency parts are relative to the low frequency parts because of the data carried in the complex parts of the transformation; this is because complex coefficients are associated with information about the phase (i.e. how much one signal is shifted in time with respect to another). However, you shouldn't use terms like "before" and "after" as they relate to Fourier series and discrete Fourier transforms, since the assumption is made that the signal is periodic. RayAYang (talk) 06:51, 21 November 2008 (UTC)[reply]

You can take the Fourier transform of a nonperiodic function. What happens is that some of the frequencies cancel out part of the time (beat (acoustics) is a simple form of the effect). So the information you want is there, but not in a form that you can easily extract. You might be interested in wavelets. —Tamfang (talk) 08:56, 21 November 2008 (UTC)[reply]

Fascinating thanks! I suppose I really should take a class instead of staring at articles :) .froth. (talk) 14:47, 21 November 2008 (UTC)[reply]

Some small remarks: talking about injectivity or surjectivity we should specify the functional domain we are considering. As a matter of fact the FT is a bijection of a very large functional domain into itself; this is the space of all tempered distributions (in this big pot you may find functions but also measures, distributional derivatives of measures, etc). Then, some subspaces are sent bijectively into themselves: maybe the most relevant case is the Hilbert space

L^{2}(\mathbb {R} ^{n})

, on which the FT is even unitary, that is, it acts in much the same way as a rotation of a finite dimensional spaces does. Other space are sent into some other spaces; now, what's the image of a given space can be an easy or very difficult question. You'll find a list of correspondences in the Fourier transform article. As to the other aspect of the question: where in

\scriptstyle {\hat {f}}(\xi )

it is stored the information needed to reconstruct

f(x)

, I'd say, I can't see it: maybe eyes are just not the right organ to see it, but in fact Maths is also a way to see things that we can't see otherwise (but your question is very important because sometimes things could be visualized and we just ignore it, in an abstraction's frenzy. But visualization is important as Dmcq recalls to us)--PMajer (talk) 15:10, 21 November 2008 (UTC)[reply]

A histogram is a reasonable analogy, but it's a very incomplete description. As has been said above in other ways, each element in the Fourier transform is a complex number, which for practical reasons is usually visualized as just its magnitude (though I have seen a few programs that show magnitude and phase). For audio work, phase is usually unimportant to the user, so the program will probably only display magnitude. Under the hood, obviously you can't get your original signal back if you discard part of the information, so phase has to be stored and dealt with, but the user doesn't need to see it. - Rainwarrior (talk) 16:39, 21 November 2008 (UTC)[reply]

The first step in understanding fourier transforms is this variant of the discrete fourier transform.

Let $x=(x_{1},\cdots ,x_{N})=(t\mapsto x_{t})\,$ be a time series defined for the times $t=1\cdots N.$
Let $1^{1/N}=e^{2\pi i/N}=\cos(2\pi /N)+i\sin(2\pi /N)\,$ be a primitive N 'th root of unity.
Let ${\overline {z}}$ signify the complex conjugate of the complex number $z.\,$
Note that ${\overline {1^{1/N}}}=1^{-1/N}.\,$
Define the transform ${\begin{aligned}{\mathcal {F}}&=(x\mapsto {\mathcal {F}}x)&=((t\mapsto x_{t})\mapsto (\nu \mapsto N^{-1/2}\sum _{t=1}^{N}{\overline {x_{t}}}1^{t\nu /N}))\,\end{aligned}}$ for the frequencies $\nu =1\cdots N.$

This transform ${\mathcal {F}}\,$ has the nice property that ${\mathcal {F}}{\mathcal {F}}x=x\,$ because

{\begin{aligned}{\mathcal {F}}{\mathcal {F}}x&=(u\mapsto ({\mathcal {F}}(\nu \mapsto ({\mathcal {F}}(t\mapsto x_{t}))_{\nu }))_{u})\\&=(u\mapsto N^{-1/2}\sum _{\nu }{\overline {N^{-1/2}\sum _{t}{\overline {x_{t}}}1^{t\nu /N}}}1^{\nu u/N})\\&=(u\mapsto N^{-1/2}\sum _{\nu }{N^{-1/2}\sum _{t}{x_{t}}{\overline {1^{t\nu /N}}}}1^{\nu u/N})\\&=(u\mapsto N^{-1}\sum _{t}{x_{t}}\sum _{\nu }1^{\nu (u-t)/N})\\&=(u\mapsto N^{-1}\sum _{t}{x_{t}}N[u=t])\\&=(u\mapsto x_{u})\\&=x\\\end{aligned}}\,

where [u=t] is an Iverson bracket. So, the inverse transform is the same thing as the transform.

{\mathcal {F}}^{-1}={\mathcal {F}}\,

but in general $x\,$ and ${\mathcal {F}}x\,$ have complex components $x_{t}\,$ and $({\mathcal {F}}x)_{\nu }\,.$ The fourier series and the fourier integrals may be considered limiting cases of the discrete fourier transform for large values of N. Bo Jacoby (talk) 19:52, 21 November 2008 (UTC).[reply]

What on earth is your point with all that? I just feel annoyed reading it. Dmcq (talk) 22:28, 21 November 2008 (UTC)[reply]

Simplifying and clarifying the inverse fourier transform. How come you are annoyed? Bo Jacoby (talk) 22:43, 21 November 2008 (UTC).[reply]

You stuck in the complex conjugate, that's no part of a standard definition of the FT of a DFT. Lots of strange notations and ways of doing things. About the only one of those I can go with is the Iverson notation which I think should be incorporated as a standard tool but I see no point here. This is supposed to be a reference desk to help people not a place to confuse them. Dmcq (talk) 23:13, 21 November 2008 (UTC)[reply]

The complex conjugate is necessary in order to obtain ${\mathcal {F}}{\mathcal {F}}x=x\,.$ The standard definitions of the FT and DFT do not have that simple property. If the articles on FT and DFT were good enough the OP did not have to ask. The standard definitions are contaminated by transcendental expressions involving e and π, or cos and sin, obscuring the fact that the discrete fourier transform is strictly algebraic. The notation y=f(x) for a function confuses the function f and the function value f(x). The notation $f=(x\mapsto y)$ indicate the function. Beginners need simpler explanations, which surprise those accustomed to traditional presentations. The point of the Iverson bracket is to express the orthogonality condition $\sum _{\nu =1}^{N}{\overline {1^{\nu t/N}}}1^{\nu u/N}=N\cdot [u=t]$ (where 1≤t≤N and 1≤u≤N). Bo Jacoby (talk) 09:23, 22 November 2008 (UTC).[reply]

Well I guess that's a good enough explanation for beginners to judge for themselves if they really want to bother looking at what you wrote. Dmcq (talk) 10:07, 22 November 2008 (UTC)[reply]

You are welcome to provide a constructive contribution of your own. Bo Jacoby (talk) 10:30, 22 November 2008 (UTC).[reply]

It's sad when someone like Bo Jacoby uses their time (unpaid and voluntarily) to add useful material to the discussion and Dmcq adds only criticism and no new information. Dmcq, have consideration for Bo's feelings - Adrian Pingstone (talk) 11:59, 23 November 2008 (UTC)[reply]

Probability vs Common Sense

I'm no mathematician but there is something that has been puzzling me for a while and that is probability regarding lotter numbers. To make my point clear pretend there are ten lotter numbers and three are draw each week. Probability says that as each draw is an independent even, no draw has an effect on the outcome on the next draw - yeah Ok, I get that. But if in weeke one the numbers 1,2,3 are drawn then surely the following week it is less likely that 1,2,3 will be drawn again. Maybe 1,4,7 but does mathematics really say that if if 1,2,3 is drawn for three weeks in a row it is just as likely that 1,2,3 will be drawn the following week? I know maths says so but this seems to completely contradics common sense. I know I am probably missing a huge piece of the argument! Thanks for any advice - kirk uk —Preceding unsigned comment added by 87.82.79.175 (talk) 19:11, 21 November 2008 (UTC)[reply]

If I say that "the next THREE lottery numbers will be all 1,2,3, that is highly improbable because it requires three already improbable things to happen together. Suppose it happens twice that the numbers 1,2,3 have been pulled in previous lotteries (yesterday and the day before) Would you say that it is highly improbable that has happened? No. It is now 100% certain that it has happened, you can look in the newspaper and see the winning numbers there printed in unerasable ink. So what is the probability that today's number will again be 1,2,3? The same as always, right? Because it only requires one improbable thing to happen, regardless of any previous formerly-improbable-but-now-certain events, because lotteries (and coin flips, and dice rolls etc) have no memory! (unless your lottery is rigged, which you might suspect after the same results come up three times in a row...)

Duomillia (talk) 19:34, 21 November 2008 (UTC)[reply]

If the draw is the same three weeks in a row, you may legitimately suspect that something is wrong with the apparatus; so if it happens twice I'd be more likely to bet on its happening again. But if the machine really is fair, it has no memory. If the lottery runs for enough weeks, all improbable runs will occur eventually.

Perhaps evolutionary psychology can tell us why this "completely contradicts common sense". —Tamfang (talk) 20:14, 21 November 2008 (UTC)[reply]

It's because repeated events which are important to us are rarely completely independent in real life. And, in cases where they were, that didn't help our ancestors much. For example, knowing where the first rain drop will fall in a thunder storm isn't very important, even though it should be completely random. Knowing where prey animals are likely to be is quite important, but not completely random. StuRat (talk) 22:48, 21 November 2008 (UTC)[reply]

This reminds me of a hypothesis about oracle bones, to wit: Ancient hunters would heat up large flattish bones of their prey, like the scapula, until they cracked; and then read the cracks as representing the path they should follow to find prey; thus keeping themselves from habitually looking for prey in places they had already depleted. —Tamfang (talk) 03:58, 22 November 2008 (UTC)[reply]

This is called the Gambler's Fallacy. Imagine rolling a (fair, unbiased) die and getting a six three times in a row. Intuitively, it seems that getting a six again is less likely than getting a three, even though mathematically we know that they are equally likely. This is because the human brain is not a perfect probability computer. There are several potential confusions that can cause this intuitive mistake:

The pattern (6,6,6,6) seems more 'ordered' than the pattern (6,6,6,3), and we intuitively believe that random process tend toward disorder. Patterns that seem ordered, like (1,2,3,4), make up a small minority of the total space of possible patterns - most patterns will appear disordered. Hence we intuitively conclude, "randomness leads to disorder".
Our brains are confused by the known fact, "throwing four sixes in a row is very unlikely". Even though we have hypothesised that the first three throws were sixes and we got those ones "for free", we intuitively have trouble disconnecting the known unlikely nature of four sixes in a row from the supposed situation of three free sixes and a shot at the fourth.

There may be other biases at work here, too. Whatever the cause, this is another cognitive bias that we need to try to avoid falling victim to. In a genuinely independent set of trials, past results really do have no effect on future results, regardless of whatever our intuition says. For another example of where our in-built intuitive probability estimation functionality can fail us, check out the Monty Hall problem. Maelin (Talk | Contribs) 18:22, 22 November 2008 (UTC)[reply]

That problem is pretty intuitive once one realizes that the host is forced to avoid opening certain doors. The question of repeated events affecting probability, on the other hand... --Bowlhover (talk) 04:27, 24 November 2008 (UTC)[reply]

If one believes that drawing 1,2,3 next week is less likely when 1,2,3 is drawn this week, then one must also believe that most of the things happening in the universe today are improbable because, given multi-billions of years, all the probable things have already occurred. In short, if the cosmos has a memory then it applies to all random events -- not simply lottery numbers. Wikiant (talk) 19:29, 22 November 2008 (UTC)[reply]

You really think that those little balls remember that they dropped last week and decide that they probably shouldn't drop again this week? Matt 05:21, 23 November 2008 (UTC). —Preceding unsigned comment added by 86.134.53.78 (talk)

Without even considering successive draws, very few people would choose the numbers 1, 2, 3, 4, 5, 6 in a 6-number game, because they believe that that set of numbers is inherently less likely to be drawn than, say, 1, 8, 11, 23, 31, 38. It's too ... "neat", and our brain believes that random draws don't produce "neat" results. The fact is, it's not less likely. They're both equally extremely unlikely. Any set of 6 numbers you could possibly name is extremely unlikely to actually be drawn, and none of them is any more or any less likely than any of the others. Whatever happens with one draw has no relationship whatsoever with the next draw. Thus, it's possible for the same set of numbers to be drawn 2, 3, 4, ... 50 games in a row, but the longer it goes on, the higher the likelihood that there's some rigging going on. But they could have come out that way purely by chance. -- JackofOz (talk) 04:49, 24 November 2008 (UTC)[reply]