Overview

When there is a choice of bases for the representation of a signal, then it is possible to seek the best one by some criterion. If the choice algorithm is sufficiently cheap, then it is possible to assign each signal its very own adapted basis, or basis of adapted waveforms. The chosen basis carries substantial information about the signal; the chosen waveforms are a good match for the signal. If the basis description is efficient, then that information has been compressed.

Let be a collection of (countable) bases for a (separable) Hilbert space X. Some desirable properties for to have are:

• Speedy computation of inner products with the basis functions in to keep the expansion complexity low;

• Speedy superposition of the basis functions, to keep the reconstruction complexity low;

• Good spatial localization, so we can identify the portion of a signal which contributes a large component;

• Regularity, or good frequency localization, so we can identify oscillations in the signal;

• Independence, so that not too many basis elements match the same portion of the signal.

The first property makes sense for finite-rank approximations; it holds for factored, recursive transformations like "fast" DFT or the wavelet transform. The second property holds for fast orthogonal transformations, whose inverses have identical complexity. The spatial localization property requires compactly supported or at least rapidly decreasing functions; in the sampled finite-rank case, good spatial localization means that each basis element is supported on just a few clustered samples. Good frequency...