• ## Discussion Feed

Vanilla 1.1.9 is a product of Lussumo. More Information: Documentation, Community Support.

• CommentAuthorYemon Choi
• CommentTimeJan 29th 2010

Put another way: it's all very well to get people thinking Maths Is Cool, rather than Maths is What Kids We Thump Are Into. However, appearing to promise the moon on a stick is only going to end poorly for all concerned. Nor do I think we have a responsibility to supplant teaching, and it is teaching which some questioners seem to hope we provide. (Deane Yang's remarks on the books thread, while somewhat more forceful than those I'd espouse, have some truth.)

• CommentAuthorAnweshi
• CommentTimeJan 30th 2010 edited

@bwebster. There was no need to re-open it.

Here's why. I feel that the question first belonged to stackoverflow. Somebody there would have been able to tell the OP that there is no problem in implementing FFT(=fast fourier transform, algorithms for effectively computing the discrete fourier transform) with the existing processors. I suspect that the OP's problem was that he didn't want to get into the "complicated" FFT algorithm and wanted something simpler instead. However that is not an issue since there were tailor-made FFT routines available on the web.

Shannon's sampling theorem is quite intuitive and nobody who are actually beginner programmers in DSP(=digital signal processing, to fix matters) really bothers about getting more into it. Also it is quite evident that you cannot achieve anything more than what Shannon proved. To capture a signal with frequency f, you need a sampling rate of at least 2f. It simply does not make sense to reconstruct an analog signal from digital samples with less information than this. So the sampling rate had to be above double the maximum frequency the OP was dealing with. If the OP needs higher fidelity, he should use higher sampling rates. For instance, the mp3 files you used to play all throughout the 2000's have a sampling rate of 128k as opposed to the 44 or so k he mentions. The professional systems have even higher sampling rates. The motto seems to be, "sample really well, so that we do not lose anything of value", and do the rest in DSP. Computing FFT will not take so much time. For a processor with a clock speed of 100Mhz, all these are just routine work done in a fraction of a second. I programmed on the age-old "ADSP-2181" processor in 2003, and let me assure that even this rather primitive one would have been enough to handle the task. Its speed was something like 40MIPS(Million instructions per second).

Now, if the OP was willing to put time into understanding FFT and the available microprocessors, he could have done it by himself. However he would not have got that information from MO.

Shannon's sampling theorem etc., would be more interesting to the guy who designs the person who reconstructs the analog signal from the analog output, for feeding to the speaker. However again here it is impossible to go beyond the mathematical bound of Shannon and Nyquist, and what can be done to reach it is more or less already done. There are ready-made "Digital to Analog converters" -- DAC ICs-- available from ages ago. Maybe for some cutting-edge military or so application one needs to nitpick further. But it didn't seem like that from the OP's post. If I were the OP, I would just use some ready-made stuff and get the application done. This appears like an elementary DSP question. Nobody who spent a little bit of time on DSP would have asked it.

For programming questions, I make the following proposition. First the questioner must find out from stackoverflow. If there is really a mathematical issue that they cannot address, then possibly it can be asked here.

This could be made into official policy. This can encompass issues like the "long lines of code" problem mentioned in another thread.

The strong reaction against the closing of this question was quite unexpected for me. There was no issue at all in closing this one. However I must complain of a few other closed questions. .

1.
@ Anweshi, even if you know there is a way to make the FFT algorithms work in this situation, that doesn't mean it isn't mathematically interesting to look at other, simpler algorithms, or to understand why they do or do not work. That just means there should be at least one answer which says that the FFT algorithms should work for that step of the problem, and that the FFT takes surprisingly little computational power, as I mentioned in http://mathoverflow.net/questions/8741/justifying-a-theory-by-a-seemingly-unrelated-example/12022#12022. If you think all of the other algorithms are just bad approximations of the FFT, that is a mathematically interesting statement!

MO is expressly "not the right place to ask open problems," according to the FAQ. A mathematical answer which reduces the problem to a programming exercise is actually a good sign. I definitely want to be able to see you give such answers to similar questions so that I can learn from them.
• CommentAuthorAnweshi
• CommentTimeJan 30th 2010 edited

@Douglas Zare.

Well, the only thing I used here was that the Fourier transform of a signal is its frequency spectrum. When you have the frequency spectrum in front of you, you can do what ever you want. Beat matching, frequency filtration, etc., and whatever involving frequency are very easy. And when you are done, take the inverse Fourier transform. The only difficulties of implementation are the delays in computing Fourier transform and its inverse. This is most obvious.

Actually here I did not contribute any mathematics at all. This was engineering. All I did was to speak from my memory that FFT can be done efficiently(for this stated problem) on existing microprocessors. It is the "engineering intuition". If you ask me justification how I reached the conclusion, I have no answer to give except that it is the result of fiddling around with this stuff for a while and the resulting experience. When I was an engineering student, I was not so much bothered by mathematical questions, just like any usual engineer. I did not compute using the MIPS ability of the processor and complexity of the problem or whatever; I just knew that whatever I wanted could be done on such-and-such processors, and how approximately speedy they were for the task.

2.
Anweshi, technically the Fourier transform regardless of implementation isn't a solution to the problem. Take a look at the Sethares paper to get a sense for the complexity of the problem -- a track doesn't neccessarily have a consistent beat. The beat may change, there may be conflicting beats, and so on. That's why Sethares uses Bayesian statistics in an attempt to seek a most relevant beat to track.
• CommentAuthorAnweshi
• CommentTimeFeb 1st 2010

@Ryan. I had been aware that there is more to do even after taking FFT. But the OP seemed to have something in mind after taking FFT, and was worried only about the complications of doing an FFT. So I answered that FFT can be done in any case.

I was not such a good engineer; had it been so I would not have dropped it after years of effort and taken up math(given that I am not a great mathematician either). In any case I did not provide an answer in the original thread, for the above reasons.

• CommentAuthorKevin Lin
• CommentTimeFeb 1st 2010 edited

A random comment: Let's not forget that one of the best mathematicians in recent history started out in electrical engineering: Raoul Bott. I believe he even got his PhD in EE, or at least his PhD thesis was about EE.

3.

I'll just note: I didn't unilaterally reopen the question. Four other people voted to reopen.

4.
@Kevin: I say this without any particular motive (except that I had the privilege of knowing Raoul Bott, a little bit, so I'd like him to be remembered accurately). Although it is true that Bott's PhD was awarded in the area of EE, I think it's a bit misleading to say that he started out as an electrical engineer and switched careers to mathematics. For instance, by the age of 24 he had completed his thesis, which contained a result now called the Bott-Duffin Theorem. Yes, it concerns electrical networks, but electrical networks as mathematical objects. How many mathematicians have proved a significant theorem by the age of 24? (Not me!) So he was hardly a late bloomer, any more than Paul Halmos, who switched from philosophy to mathematics, but did so at about the age of 20.

http://www-history.mcs.st-and.ac.uk/Biographies/Bott.html
5.
Bott produced at least one EE grad student, but I don't know how many in total. Dave Delchamps in Cornell's EE department is a Bott student.
• CommentAuthorAnweshi
• CommentTimeFeb 2nd 2010

Bott's example was mentioned to me when I announced to my friends that I intend to take up math. However he seemed to be theoretician of electrical engineering, somewhat removed from the practical aspects, and it was also pointed out to me that his would be a bad example for me to emulate, and I should rather take up courses in pure math like math students. Which is what I did..

6.

I'm way late to the party because I was out of town, and I've just given up on the idea of trying to carefully read the whole thread before saying anything.

I think Scott and I might disagree a fair amount on when you should leave a comment, so I'll try to flesh out my position a bit more. I think I almost always leave a comment when I downvote or vote to close (even if I weren't casting the final vote, though I guess never happens), or I vote up a comment that says what I'd like to say. Here are the main reasons:

1. Negative feedback (in the form of downvotes or votes to close) hurts a little bit, and a comment can mitigate that.
2. Constructive feedback is really useful. It helps people make better posts in the future, it can help them improve the current post, and it feels good to get it. If the question is salvageable, I try to say how you would salvage it.
3. Writing a comment explaining my downvote/vote to close forces me to actually have a good reason (that I can at least partially explain) for downvoting/voting to close. The better I can put my reason into words, the more confident I am that I'm not being an elitist snob, the more likely the person is to improve in some way, and the easier it is for other people to explain to me what they disagree with if they disagree.

Please DO NOT follow the rule "always leave a comment when downvoting/voting to close", but rather follow the reasons. Leaving a nasty comment, or even a more neutral comment like "Doesn't belong on MO" does not accomplish any of the goals of leaving a comment and only exacerbates the negative side effects of not leaving a comment (i.e. it's bad enough when somebody downvotes you, it's worse when they pretend to give you a reason for it).

Writing constructive comments is hard, and I admit that I sometimes don't do it. The FAQ and the How to Ask have lots of specific anchors you can link to, which should make the job a little easier, but please don't make a comment consist entirely of a link. A good constructive comment should go something like this (let's assume you're voting to close because the question is too vague)

I'm voting to close. As stated, it's not clear what you're trying to accomplish and there are too many ways to interpret your question. [examples of different valid interpretations]. I shouldn't have to guess what your question is before answering it. See http://mathoverflow.net/howtoask#specific. If you edit the question to make it clearer what you want, I'll vote to reopen.

Of course, the more specific you can be about what's wrong with the question and how it can be fixed, the better. It's hard to write a good comment for a bad question that doesn't exist.

7.

By the way, I've reopened http://mathoverflow.net/questions/12147/how-can-i-tell-if-x-is-a-function-of-y, the question David Speyer shook his finger at me for closing. I still agree with my original criticism that it wasn't very clear what the asker wanted or what information he had (and I thought I made my objections pretty clear in the comment I left), so I edited the question to ask essentially the version of the question David asked.

• CommentAuthorHarry Gindi
• CommentTimeFeb 2nd 2010 edited

If it means anything, I agree with your original judgement.
8.

@Harry: I do appreciate the reassurance. You actually made the same judgement before I did. Your comment (which I hadn't voted up until now for some reason) contained the bulk of my objection. My edit doesn't explain what a "complicated function" is, but at least now it's clear that some measure of complexity is needed.