Using Data to Learn a More Sparse Fourier Basis

2026-08-17 signal-processing machine-learning

The classical Fourier transform is a fixed basis: sines and cosines, chosen once, independent of the data. This post aims to answer one question: What happens when you learn the basis to better sparsify your data?

Fourier Advantages

There are a few reasons why the Fourier basis is the dominant one today.

First, they are the Eigenvectors of any shift invariant operator. A shift invariant operator is any operator which has the same behavior at any shift of the input signal. In matrix form, these operators can be written as circulant matricies. For example, the second derivative discrete matrix is:

D_2 = \frac{1}{h^2} \begin{pmatrix} -2 & 1 & 0 & 1 \\ 1 & -2 & 1 & 0 \\ 0 & 1 & -2 & 1 \\ 1 & 0 & 1 & -2 \end{pmatrix}

Each column is just the previous one, shifted down, wrapping around at the ends. Sines and cosines are the only functions who, when passed into a shift invariant operator as input, responds without a shape change (only a coefficient scaling). This, of course, results in the convolution theorem, as well as their ubiquity in linear PDEs.

The other reason they are so popular is because of the speed of the transform. The Fast Fourier Transform (FFT) enables you to transform to the frequency domain with just /O(N log N)/ multiplications. This makes the DFT practical for actual computation.

Finally, the fourier basis has naturally ordered eigenvectors, with a meaningfully defined truncation. This means that we can keep up to $k_{max}$ frequencies, and Parseval ensures that our approximation preserves most of the energy.

What does better mean?

The Fourier basis tends to struggle with sudden jumps, and non periodic data. For example, a single chirp will be distributed equally across the frequency bins, meaning that you need to keep far more coefficients to accurately reconstruct your signal. For example:

[Insert Time Domain to Frequency Domain pic]

To make a "better" Fourier basis, we need to preserve the three properties from above, while also making sure that the basis is able to represent our specific dataset with fewer coefficients than the Fourier basis.

fPCA is technically the optimal /linear/ basis for the average case on our dataset, however that comes with some pretty huge asterisks. Firstly, fPCA doesn't have an O(N log N) transform, instead it is O(nN) to project onto a PCA basis. Secondly, PCA just gives us a vector, not a function, which means that it is not resolution invariant like Fourier (which gives us a formula for any resolution).

Thus, our goals are the following (for a given dataset of signals): 1) More sparse than Fourier 2) O(N log N) transform 3) Orthogonal Basis 4) Resolution Invariant Function

Sturm-Liouville Eigenvalue Problem

The Sturm-Liouville Eigenvalue Problem gives us the most general second-order operator that is symmetric (meaing

\langle Au, v \rangle \langle u, Av \rangle

Sturm-Liouville:

-\frac{d}{dt}\left(p(t) u'\right) + q(t) u = \lambda w(t) u

p(t)- Stiffness or tension. High p resists bending, so modes stretch out
q(t) - Local restoring pull. High q is expensive to occupy(?) so modes avoid it
w(t) - Mass Density. High $w$slows waves down, so modes bunch up