Basis Selection in Function Decomposition

10 Apr 2009 17:40

Fourier analysis, as every schoolchild knows, is a way of taking arbitrary functions of time (or space; but let's stick to time) and re-writing them as sums of trigonometric functions. These functions extend evenly, with constant amplitude, over all time, but they have unique, definite frequencies. The reason physicists and engineers are drilled to death in Fourier analysis is this: it's very easy to figure out how a linear, time-invariant system will respond to an input consisting of a single pure frequency, so to see how it responds to a more complex signal, we resolve that signal into its Fourier components, calculate the response to each of them, and then sum up. (This is important in quantum mechanics, too, because that's a fundamentally linear theory, and time-invariant if we're right about conservation of energy, which we are.)

The trigonometric functions form a basis for the space of functions --- a set of primitives, such that any (reasonable) function is a sum of functions from the basis. To specify a function, then, we can just give the weight for each basis component in its decomposition. Fourier components, as I said, extend with equal amplitude over all time, but have a definite frequency. Their direct counterparts are Dirac delta functions, which are localized to a single unique time, but, when Fourier transformed, evenly cover all frequencies. The Dirac delta functions are another basis, but not usually a very convenient one, since it just amount to specifying the value of the function at each point!

The last paragraph is meant to suggest two ideas. First, it might be possible to find bases which are localized in both time and frequency. (It turns out that you can't have a basis which is completely localized, down to points, in both time and frequency, and in fact there's a trade-off between the two, which, in the context of quantum mechanics, basically is the Heisenberg uncertainty principle.) If you like to think about frequencies at particular times, or at least particular regions of time, this would be a Nice Thing. The best known venture in this direction are wavelets, but there are many, many, many others.

Second, some bases allow for more efficient description of some signals than others. If your signal is a combination of a few pure tones, you just say what those tones are (and their amplitudes). If your signal is a few isolated spikes, you use the Dirac basis and say when the spikes happen. If it's not at either of these extremes, in general you'll have an infinite number of components in both the Fourier and Dirac bases. Sometimes, we can get by while ignoring all but a (reasonably) small number of components --- these are signals which are well-approximated by finite Fourier representations, or finite Dirac representations. But there's no general guarantee that your favorite signals can be handled in this way. You might, in fact, ask yourself whether it's not possible to automatically find a basis in which your signals have a "sparse" representation, i.e., one where all but a few components have zero weight and can be ignored. This is the question of basis selection or basis pursuit, which I'd like to understand better, because I currently don't.

Finally, it's worth noting that a given basis might let us represent our signal sparsely, but at the same time it might not mesh well with the dynamics we're interested in. You can always Fourier transform your signal, but if you then run it through some nonlinear transducer, that's not going to help you much. What to do about that, I have even less idea. Linear transducers can be characterized by saying how they respond to Fourier components; what one would like would be some analogous characterization for nonlinear systems. Norbert Wiener had a very clever proposal along these lines, which was basically to say how they respond to white noise. (The fact that he invented the mathematical theory of white noise probably played a role here.) Unfortunately, there's no particular reason to think that the resulting "Wiener kernel expansion" is the most efficient way of represent the system...