> You could just tell them a handful of numbers—the sizes of the different circles in the picture above.
Maybe I'm crazy and just missing something, but this feels a little too good to be true. This would put the set of smooth curves in 1-1 correspondence with the set of finite sets (since each curve is being specified completely by a finite set of numbers). But the set of finite sets is countably infinite since it's a countable union (this may require the axiom of choice) and the set of smooth curves is uncountably infinite, a contradiction.
(Disclaimer: I know nothing about Fourier analysis.)
First of all, there are four kinds of "Fourier transforms" in common use, so the cardinality problem that you have observed cannot really be discussed until we pick one to talk about. For instance, the FT maps uncountable to uncountable and the DFT maps finite to finite (and can be understood with intro Linear Algebra as a change of basis). The things we are calling countable and uncountable are actually dimensionalities of vector spaces, since real multiples of a single function would produce an uncountable set. Anyway, here are the types of transforms:
The cardinality mismatch shows up for FS and DTFT. It is resolved through a different notion of equality than you may be used to. The "distance" between two functions can be measured using several norms, and when this distance is zero we claim two functions are equal. L1, L2, and Linf are the common ones. Linf corresponds to pointwise equality, which is what you assumed (not unreasonably) that they meant. L1 and L2 do not.
L1 norm: d(f,g)=integrate(abs(f(x)-g(x)),a,b)
L2 norm: d(f,g)^2=integrate(abs(f(x)-g(x))^2,a,b)
Linf norm: d(f,g)=max(f(x)-g(x)) over the interval (a,b)
Fourier Series only guarantee reproduction (take the transform and then take the inverse to get the reproduced curve) up to the L2 norm. This makes physicists and engineers happy, since L2 norms correspond to energy measurements, and if the difference between two physical quantities has no energy then it's effectively irrelevant to physical processes.
The remaining hurdles for mathematicians are to show that
1) The reproduction coefficients found by the transform are the best possible coefficients (the curve they generate is closer to the original than for any other set of coefficients of the same size). This is a trivial proof using inner products that usually goes by a name like "best approximation theorem" or "generalized pythagorean theorem."
2) Reproducible curves are dense in the space of actual curves. That is, there is always a reproducible curve that has zero L2 difference from an arbitrary input curve. If this is true, then by #1 we know that the transforms will find it. Unfortunately, this proof is quite involved. A "quick and dirty" method uses the Stone-Wierstrass theorem (polynomials can reproduce continuous functions with arbitrary L1 or L2 fidelity + the FS can reproduce polynomials with arbitrary L2 fidelity). A better method arises in the context of Sturm-Liouville theory that generalizes "density" to solutions of a large class of differential equations. This is important for physicists and engineers because it justifies normal mode expansions even when the normal modes aren't perfect sinusoids.
If you want to know more, any linear algebra book that discusses inner products should hit on #1. For #2 you want an Analysis textbook. Analysis is a tough subject so it's far more important to be sure that the book starts at your level and has an understandable proof of Stone-Wierstrass than it is to be sure that it covers this exact topic. If it doesn't, supplement it with the first few chapters from "Completeness and Basis Properties of Sets of Special Functions" by Higgins and you'll be set.
The things we are calling countable and uncountable are actually dimensionalities of vector spaces...
The dimensionality of L^2(R) is still countable. Proof: f(k,j,x) = e^{2 pi i k x}, x in [j,j+1], k and j both integers forms a basis. So does H_n(x) exp(-x^2/2), for H_n the Hermite polynomials.
The Fourier transform merely does not map L^2(R) -> l^2(Z) in this case - it maps L^2(R) -> L^2(R).
That is, there is always a reproducible curve that has zero L2 difference from an arbitrary input curve.
This isn't what density means. Density means that for any epsilon, there is a reproducible curve with L2 distance < epsilon to that curve.
Linf norm: d(f,g)=max(f(x)-g(x)) over the interval (a,b)
By most standard definitions, this is only true almost everywhere. A typical definition is ||f(x)||_{\infty}= Lim_{p -> infty} ||f(x)||_p, and this allows two functions to differ on a set of measure zero.
As an example, consider f(x)=1 and g(x)={0 on rational numbers, 1 on irrational numbers}. These two functions are equal in any L^p space, and are hence equal in L^infty as well.
>> The dimensionality of L^2(R) is still countable.
At this point I was implicitly talking about Linf(R). Does it still have countable dimension? With the sup norm I'm pretty sure the answer is no, but with Lp taken at p->inf maybe it does?
In any case, thanks for cleaning up the rough edges.
Don't know off the top of my head. I suspect it does have countable dimension but I don't know how to prove it.
The space of continuous functions with the sup norm is actually a much smaller space than the space of L^\infty - the former is not even dense in the latter.
I suspect actual functions on R with the max norm probably is uncountable, but that's also a very weird space. The overwhelming majority of functions in there are unmeasurable.
If I remember my "history of the Fourier transform" correctly, before the difference between the sup-norm and L2 norms were fully understood by everyone (e.g., by the late 1800s), the sense of convergence of a Fourier series to a square wave was confusing. In what sense did the Fourier series represent the square wave? When was it a good model and when would it fail?
> Fourier Series only guarantee reproduction (take the transform and then take the inverse to get the reproduced curve) up to the L2 norm
This completely resolved the confusion. Thanks very much for typing this up.
This is one of those details which is probably pretty unimportant for the lay reader, but for someone with some mathematical training (outside of this specific domain) its omission threw a big red flag for me.
In the article I described the discrete fourier transform, but there is a continuous version, where a signal is represented by an infinite sum (really an integral) of component frequencies. This is the version that is more generally useful. Here's a great animation by LucasVB of the continuous fourier transform in action:
http://upload.wikimedia.org/wikipedia/commons/a/a3/Continuou...
I don't know much more about Fourier analysis than you, but theoretically it's an infinite series. So to describe an arbitrary smooth curve, you need a potentially infinite number of circles (or sin terms). I'm not sure if it's a countably infinite series or not. I think in principle you could have a component for every number in the real line.
For a periodic input, it's countably infinite (Fourier series [1]). For aperiodic, its uncountably infinite ((continuous) Fourier transform).
I don't think this implies that there are a countably infinite number of smooth, periodic curves though, because the each one of the parameters is a real.
I'm not a mathematician though, so I could be abusing these concepts...
There are two more major Fourier transforms: the discrete Fourier transform, which maps a discrete aperiodic function to a continuous periodic (i.e. band-limited) frequency domain representation [3], and the discrete-time Fourier transform [4], which maps a discrete period (i.e. time-limited) function to a discrete period (i.e. band-limited) frequency representation.
Notably, in the applications mentioned in the article, what's really being described is the short-time discrete-time Fourier transform (STFT [5]). In this most useful variation, you chop the input signal of arbitrary duration into fixed-sized (and possibly overlapping) chunks, (usually) apply a windowing function to temper down the edges of the chunks, and then apply DTFT to each chunk. The result is a sort of spectrogram -- a time-frequency representation of the input. In image processing this is done in two dimensions.
The famous FFT [6] is a O(n * log(n)) algorithm for calculating DTFTs.
Maybe I'm crazy and just missing something, but this feels a little too good to be true. This would put the set of smooth curves in 1-1 correspondence with the set of finite sets (since each curve is being specified completely by a finite set of numbers). But the set of finite sets is countably infinite since it's a countable union (this may require the axiom of choice) and the set of smooth curves is uncountably infinite, a contradiction.
(Disclaimer: I know nothing about Fourier analysis.)