Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2601.16345 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908783262826496 |
|---|---|
| author | Burstein, Will Iosevich, Alex Nathan, Hari Sarang |
| author_facet | Burstein, Will Iosevich, Alex Nathan, Hari Sarang |
| contents | We introduce a generalized Fourier ratio, the \(\ell^1/\ell^2\) norm ratio of coefficients in an \emph{arbitrary} orthonormal system, as a single, basis-invariant measure of \emph{effective dimension} that governs fundamental limits across signal recovery, localization, and learning. First, we prove that functions with small Fourier ratio can be stably recovered from random missing samples via \(\ell^1\) minimization, extending and clarifying compressed sensing guarantees for general bounded orthonormal systems. Second, we establish a sharp \emph{localization obstruction}: any attempt to localize recovery to subslices of a product space necessarily inflates the Fourier ratio by a factor scaling with the square root of the slice count, demonstrating that global complexity cannot be distributed locally. Finally, we show that the same parameter controls key complexity-theoretic measures: it provides explicit upper bounds on Kolmogorov rate-distortion description length and on the statistical query (SQ) dimension of the associated function class. These results unify analytic, algorithmic, and learning-theoretic constraints under a single complexity parameter, revealing the Fourier ratio as a fundamental invariant in information-theoretic signal processing. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_16345 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Fourier Ratio: A Unifying Measure of Complexity for Recovery, Localization, and Learning Burstein, Will Iosevich, Alex Nathan, Hari Sarang Classical Analysis and ODEs Information Theory Functional Analysis We introduce a generalized Fourier ratio, the \(\ell^1/\ell^2\) norm ratio of coefficients in an \emph{arbitrary} orthonormal system, as a single, basis-invariant measure of \emph{effective dimension} that governs fundamental limits across signal recovery, localization, and learning. First, we prove that functions with small Fourier ratio can be stably recovered from random missing samples via \(\ell^1\) minimization, extending and clarifying compressed sensing guarantees for general bounded orthonormal systems. Second, we establish a sharp \emph{localization obstruction}: any attempt to localize recovery to subslices of a product space necessarily inflates the Fourier ratio by a factor scaling with the square root of the slice count, demonstrating that global complexity cannot be distributed locally. Finally, we show that the same parameter controls key complexity-theoretic measures: it provides explicit upper bounds on Kolmogorov rate-distortion description length and on the statistical query (SQ) dimension of the associated function class. These results unify analytic, algorithmic, and learning-theoretic constraints under a single complexity parameter, revealing the Fourier ratio as a fundamental invariant in information-theoretic signal processing. |
| title | The Fourier Ratio: A Unifying Measure of Complexity for Recovery, Localization, and Learning |
| topic | Classical Analysis and ODEs Information Theory Functional Analysis |
| url | https://arxiv.org/abs/2601.16345 |