The Fourier Ratio and complexity of signals

We study the Fourier ratio of a signal $f:{\mathbb{Z}}_N\to \mathbb{C}$, $$\mathrm{F}\mathrm{R}(f):=\sqrt{N}\frac{\mathrm{\parallel }\widehat{f}{\mathrm{\parallel }}_{L^1(\mu )}}{\mathrm{\parallel }\widehat{f}{\mathrm{\parallel }}_{L^2(\mu )}}=\frac{\mathrm{\parallel }\widehat{f}{\mathrm{\parallel }}_1}{\mathrm{\parallel }\widehat{f}{\mathrm{\parallel }}_2},$$ as a simple scalar parameter governing Fourier-side complexity, structure, and learnability. Using the Bourgain–Talagrand theory of random subsets of orthonormal systems, we show that signals concentrated on generic sparse sets necessarily have large Fourier ratio, while small $\mathrm{F}\mathrm{R}(f)$ forces $f$ to be well-approximated in both $L^2$ and $L^{\mathrm{\infty }}$ by low-degree trigonometric polynomials. Quantitatively, the class $\{f:\mathrm{F}\mathrm{R}(f)\le r\}$ admits degree $O(r^2)$ $L^2$-approximants, which we use to prove that small Fourier ratio implies small algorithmic rate–distortion, a stable refinement of Kolmogorov complexity.