Hacker News Reader

The isolated phrase "spinning a signal in a circle" is confusing, but the accompanying visualization of tracking a point on a spinning speaker cone is something that can be visualized.

More generally, your explanation may make sense to you, but it makes no sense to a layperson (i.e. me). But the linked short description, along with the speaker cone visualization, does make a reasonable amount of sense.

I've also seen a similar description in the past with accompanying animated GIFs illustrating the point, instead of the prose about a spinning speaker cone. I thought the animated GIFs made it even easier to understand. Sadly, I don't remember where I saw that.

Agreed a layperson could benefit, but karpathy insight is also very nice, it allows to leapfrog from elementary linear methods to a good intuition of the real thing.

Oh sure, I bet karpathy's explanation is great for the people it makes sense to. It just assumes a lot more specialized knowledge on the part of the reader, knowledge that I personally don't have.

Let me try a (hopefully unspecialized) basis view explanation. I think this is more of an explanation of Fourier Series, but hopefully it gets the idea across:

Consider the space around you. Pick some frame of reference with a fixed origin point in space. To specify an object, you must specify the distance along each independent direction (x, y, and z in 3d space) to arrive at the object from the fixed origin. These independent directions are referred to as a basis for the space. Often these independent bases are perpendicular (or orthogonal).

For higher dimensional spaces its the same idea. It turns out we can even have infinite dimensional spaces whose bases are functions that can be perpendicular in a certain sense. It also turns out that complex exponentials (waves) are an orthogonal basis for a certain space of functions. This is really cool! It means we can refer to any function in this space using the complex exponential basis functions just like we referred to objects in 3d space using three independent directions.

Why is this useful? The magnitude in a particular independent direction in this space tells us about frequency content of that function. So instead of the first coordinate telling you how much x distance there is, it says how much of a certain frequency there is.

That helps, thanks. But while that's an explanation that may make a certain amount of intellectual sense, it still doesn't make any intuitive sense. Perhaps if I'd worked with basis views a lot more, then it would become intuitive, but I haven't. The nice thing about the spinning signal idea is I can visualize the speaker, and it makes some intuitive sense that if I spin it at a given frequency, and the speaker cone's average movement is zero, then the signal has no content at that frequency.

OK, I'm curious about how well this explanation works for you. I came up with it, and I want to know if someone like you thinks it's any good:

The Fourier transform is usually used to flip from the time domain representation to the frequency domain representation.

"Time domain representation" means when you plot that information, the x-axis is in units of time; seconds or fractions of seconds, usually, for something humans can perceive as sound. The line tells us how loud the signal is at a given instant of time.

"Frequency domain representation" means when you plot that information, the x-axis is in units of frequency; hertz or kilohertz, usually, for something humans can perceive as sound. The line tells us how loud the signal is at a given frequency.

Here's the bit about basis vectors: The frequency domain representation is possible because we can make any graph by adding enough sine functions, assuming we're allowed to do things like increase or decrease their magnitude, increase or decrease their frequency, and shift them left or right relative to each other (adjust their phase).

Therefore, we can describe the graph were interested in using only sine waves, which are pure frequencies, and when we've done that, we'll know which specific frequencies contributed most to the information we represented in the original graph.

There is, of course, an inverse Fourier transform, which takes a frequency domain representation to the time domain, so we can do things like record a sound (time domain), take it into the frequency domain, remove certain frequencies (typically all frequencies above and/or below some cutoff) by zeroing parts of the graph, and take the result back into the time domain, so it can be played back as a recording.

Well this helped me! I'm trying to wrap my head around FFT (or DFT) for my course in speech recognition, and while I still wouldn't be able to derive FFT or understand maths, I now have an idea what it does ;) Thanks!

Sure, I agree. Its a mathematical sort of intuition - one on abstract objects (in particular Hilbert spaces). This abstraction provides something sort of fundamental and poetic. Of course, this is better motivated by something concrete or physical I think before stepping in this direction.

One small note is that independent vectors are ALWAYS orthogonal in their space. That's by definition of linear independence. If they were not mutually orthogonal, then at minimum you could remove 1 vector from the set and still have the same space representation.

[1, 0] and [1, 1] are linearly independent but not mutually orthogonal. Unless I am understanding what you mean by "in their space".

I don't see how it is so specialized. It is an inner product, which can be seen as analogous to a dot product that pretty much everybody sees at some point in high school.

Is it this https://upload.wikimedia.org/wikipedia/commons/1/1a/Fourier_...

I've seen that before, and it's neat, but I don't think that's what I'm remembering.

I think it's this one, which was also posted on HN:

http://nautil.us/blog/the-math-trick-behind-mp3s-jpegs-and-h...

> Fourier Transform became trivial to me when I noticed that it's just a basis transform

I always thought this was the definition of Fourier transform, and all the stuff with integrals was just to express the change of basis in an explicit form. What else would the word "transform" mean?

How is it even possible for someone to learn about the Fourier transform without it being very explicitly said that it is a change of basis to a different set of orthogonal functions? Did they just introduce the integral expression for it and hope people would memorize it? I don't understand.

> Did they just introduce the integral expression for it and hope people would memorize it?

Unfortunately, yes. The linked article even avoids this language at all costs. And that's just how people work in physics and engineering. They want to talk about spinning functions and all this nonsense instead of just doing some basic linear algebra.

That's sad. It reminds me of "maths phobia", which is apparently a thing people can have. Also "maths anxiety".

I think part of it is also that physicists and engineers are the ones primarily teaching the subject. So it might not be that they can't handle the mathematics, but that they simply prefer to think entirely in intuition land where they can spin functions around without anyone protesting.

That's because it's important that people understand the meaning of the Fourier Transform and what it actually calculates. It's not just some random basis you throw in an equation without understanding what you're doing.

You can't "throw a basis in an equation", that's not a known mathematical procedure.

Once you learn enough about mathematics, and here linear algebra, you will start to reduce more complicated concepts to more simple concepts to build the complex ideas up from simple ones. In this case, the notion of a change of basis is definitely much simpler than the notion of an integral transform, so it makes sense to express it that way.

"What it actually calculates" can be a tricky topic in mathematics. It calculates what we want it to calculate, that's how people came up with the definition. So the way to understand "what it calculates" is to understand "what do I want it to calculate". Somewhat like programming, really. If we want to calculate a function's representation in a convenient basis, then that's what we'll make Fourier transform do.

Thanks for the response! I've always wanted to have math explained to me by a 21-24 year old that spent too much time with Rudin and Axler in undergrad.

Were you planning on bringing anything of substance to this discussion?

Can't we just appreciate that both points of views are helpful? Instead of thinking that one is better, and saying that therefore, the other sucks.

Both of them explain different things. The "it's just a basis transformation" makes invertibility, additivity, etc. obvious. The spinning function things makes it clear why we want to do it and what it means to say, approximate by only the small frequencies. (The basis thing tells you nothing about why looking at just the low coefficients is helpful, sometimes. A basis doesn't care about ordering)

Except for orientability, I guess.

I agree- the Discrete Fourier Transform can be easily explained in terms of basic linear algebra. And that explanation is usually included in an introduction-level DSP book. Both Oppenheim and Proakis have a section devoted to this view- understanding the DFT as matrix multiplication starts you on the road to the FFT algorithm.

But most ECE undergrads will first see the Fourier transform in a continuous setting. Then it isn't so much an issue of "basic linear algebra"- students have almost certainly never talked about the space of square integrable functions, the inner product on this space, a basis for continuous functions, what it means for an infinite collection of objects to be orthogonal, etc... That is, if they have even taken any linear algebra yet!

Students learn to associate "Fourier Transform" with "complicated math" and then are discouraged when they learn about the DFT. At least, that has been my experience when TAing signal processing classes.

I have no idea about engineering, but I don't see how a physicist would not know this. Basis transformations in infinitely dimensional Hilbert spaces are an integral part of quantum mechanics. The Fourier-transform in particular is used for transformation between space |r> and momentum |p> representations, but it's also common to use energy representations |E_n> where the orthonormal basis is typically somewhat more exotic (e.g. given by a Gaussian multiplied with Hermite polynomials, as is the case for the QHO).

You could learn about it from looking at and understanding a harmonic analyser: http://www.sciencemuseum.org.uk/objects/mathematics/1946-343... Or more likely the reverse mechanism, Kelvin's tide predictor being a good example: http://www.sciencemuseum.org.uk/objects/oceanography/1876-11...

Honestly that is more important to my mental model of the 1D Fourier transform than the algebraic description. It may be slightly inaccurate (are we talking projection or decomposition when calculating the settings on that tide predictor? for example).

2D Fourier transform is more interesting to me as it has applications in graphics. For example, you can synthesise ocean wave-like patterns in a height field by generating a noise image, shaping the noise into a slightly modified disc around the origin, and doing an IFFT. Intuitively you get random wavelength components within a given range, with random orientations. I couldn't write you a formula for that. You can imagine that a 12 year old could understand it, thought. Old paper is here: http://www.computer.org/csdl/mags/cg/1987/03/mcg1987030016.p... Another intuitively comprehensible 2D trick is to use an FFT to implement a simulation of fluid dynamics. That's a more complex one but again, it can be understood without algebra. http://www.dgp.toronto.edu/people/stam/reality/Research/pdf/...

I think he meant the 'decomposition' definition. You're decomposing your signal into other signals, that's the fundamental aspect. This decomposition is a linear, so you can also make it so your new components have certain nice properties -- they can be orthogonal, unitary, etc. Then you naturally get waves (complex exponentials) as the components.

And then you realize -- hey, those are exponentials -- so the rule that integrating/differentiating each component is trivial allows you to solve linear ODE really quickly.

I don't think algebra gets in the way at all -- it just makes this decomposition crystal clear. It makes generalizing easy also -- there are other nice basis like cosine basis, and so on. You can choose any N functions to decompose your N-point function, as long as they are linearly independent, you're guaranteed perfect reconstruction.

I don't know who you mean by "he" as I was talking about the machine built by Kelvin. As far as the difference goes, my uncertainty comes from knowing a tiny bit about wavelets. A decomposition means that you can reconstruct the signal by adding all the (independent) components, whereas a projection gives you more of a spectrum picture involving non-orthogonal bases? I guess this doesn't apply to the Fourier basis.

Algebra is definitely necessary and useful here, but the concepts can be learnt without knowing algebra, which means they are open to a lot more people.

If anyone wants to visualize how a variety of basis transforms (including Fourier/DFT, Eigenvectors/PCA, Haar Wavelets, Random basis, and Identity basis) can be applied to images, I created this a few years ago which seems to have become the #2 google result for "basis transform":

http://www.cc.gatech.edu/~phlosoft/transforms/

It's a bit dated by being a Java applet, but source code is all there, written in Processing. (I should probably update it now that processing.js is a thing. Years pass quickly.)

I think you mean e^(ix) = cos(x) + sin(x) i

What I find useful about Laplace and Fourier transform is there is that applied to differential equations there produce algebraic equations, so is a very useful tool when you are working in problems that are modelled via differential equations.

My introduction for someone totally new to this field is to consider y = cos(x) and y= sin(x) as functions whose second derivative satisfie y'' = -y, and the exponential y = e^(ax) as the solution of y'=ay then you can think of solving this kind of equations trying a solution of the form y=e^(kx) then you realize that the constant k is the solution of a first or second order algebraic equation that you know how to solve. Then if your equation has imaginary solutions you need to know what is the exponential of an imaginary number, exp(ik) = cos(k) + i sin(k), then you say ok but that is not a real function, answer the real part and the imaginary part of that are also solutions. Going this way you find that a complex number z=a+bi is the solution of a differential equation that often constitute a model a physical system. z=a+bi is the solution of the second order equation (z-a)^2+b^2 = 0 and this algebraic equation goes to a differential equation just by replacing z^2 with y'' (second derivative) z with y' (first derivative) and finally you have the solutions y=e^(ax)cos(bx) and y=e^(ax)sin(bx) in which the amplitude of the signal is controlled by the exponential so that if a is negative you have a signal that goes to zero and otherwise a signal that explode.

This is the kind of explanation I was looking to post on here, but couldn't quite formulate it right in my head. Yours is very clear.

Interestingly, it was actually learning quantum mechanics that made me understand the Fourier Transforms much more easily. You're always projecting the wavefunction into some basis, so the cosines and sines are just one particular basis.

Sure, but the hard thing to accept intuitively, for me, is the existence of an alternative representation of a function, particularly for functions with require intricate, data-heavy descriptions to express. It's kinda crazy that you can combine sinusoids such that they look like an arbitrary function; it's only slightly more crazy that there is a way to calculate what those sinusoids are. My intuition is also violated by the fact that you can go back and forth between these representations losslessly. It would seem to me that some functions, even simple ones like a line, would require a great explosion of information to represent as sinusoids. A function requiring two numbers to describe now requires infinite numbers to describe, in the linear case!

My preferred way of looking at the Fourier Transform is that it is evaluating a polynomial at the roots of unity. This is why it is useful for large-integer arithmetic.

This approach is much more clear when you use inner product notation.

Another benefit is you can see exactly how it is similar to other basis like (orthonormal) wavelets, and dis-similar to so-called "over-complete" basis (complex wavelets, various frames). It also becomes easier to see what the projections onto basis vectors are doing, how/why energy is "concentrated" under a wavelet transform of natural signals, etc.

While the "spin it around" explanation is useful at a certain level, this "basis understanding" is useful in a different domain - quantum physics. Position and momentum are two such dual bases, as are energy and time. In other words, time and energy (for example) are perspectives. If you try to narrow a signal from one perspective, it will look spread out from the other perspective.

Agreed, I've taken classes in linear algebra, analysis, and harmonic analysis...and I can't grok what "spinning a signal around a circle" is or why we would do that, but the change of basis realization was also my lightbulb moment.

I completely agree with you. Especially after my work with numerical techniques to partial differential equations, I honestly cannot see why Fourier transforms keep getting people confused. Hell, even Laplace transforms trip people up...

I agree, the "magic" part is the proof that the sine and cos signal vectors in the Fourier basis are orthogonal. But it's actually a very simple proof.