Sharp stability bounds for perturbed Fourier interpolation
For an integer $N \ge 2$ let $m = 2N + 1$ and $h = 2\pi/m$. Fix $0 < \alpha < 1/2$, call real numbers $s_{-N}, \dots, s_N$ admissible if $|s_k| \le \alpha$ for every $k$, and let $x_k = (k + s_k)h$, taken modulo $2\pi$; these nodes are distinct. Let $$F_N(s) = m^{-1/2} \bigl[e^{i j x_k}\bigr]_{k,j=-N}^{N}$$ be the normalised Fourier matrix of the nodes, and for $y \in \mathbb{C}^m$ let $T_N y$ be the trigonometric polynomial of degree at most $N$ with $(T_N y)(x_k) = y_k$ for every $k$. Put $$\Lambda_N(s) = \sup_{\|y\|_\infty \le 1} \|T_N y\|_{L^\infty[-\pi, \pi]}, \qquad \Gamma_N(s) = \|F_N(s)^{-1}\|_2.$$ Thus $\Lambda_N(s)$ is the Lebesgue constant of interpolation in the nodes, and $\Gamma_N(s)$ is Austin's 2-norm Lebesgue constant, the norm of $y \mapsto T_N y$ from $\mathbb{C}^m$ with the norm $m^{-1/2}\|y\|_2$ to $L^2$ with the measure $dx/2\pi$. Austin and Trefethen proved the first bound below with $N^{4\alpha}$ in place of $N^{2\alpha}$. For $\alpha < 1/4$, Yu and Townsend proved $\Gamma_N(s) \le (\cos \pi\alpha - \sin \pi\alpha)^{-1}$ for every $N$ and admissible $s$. For $1/4 < \alpha < 1/2$, Chen, Lin and Zhang proved $\Gamma_N(s) \le C_\alpha N^{4\alpha - 1} \log N$, and exhibited admissible $s$ with $\Gamma_N(s) \ge c_\alpha N^{4\alpha - 1}$, where $C_\alpha, c_\alpha > 0$ do not depend on $N$.
Problem. Do both of the following hold? First, there is an absolute constant $C > 0$ such that $$\Lambda_N(s) \le C\, \frac{N^{2\alpha} - 1}{\alpha(1 - 2\alpha)}$$ for every $N \ge 2$, every $0 < \alpha < 1/2$ and every admissible $s$. Second, for every fixed $1/4 < \alpha < 1/2$ there is a constant $C_\alpha > 0$, independent of $N$ and $s$, such that $$\Gamma_N(s) \le C_\alpha N^{4\alpha - 1}$$ for every $N \ge 2$ and every admissible $s$.
Source: Austin and Trefethen (2017): the conjectured improvement of their bound (12) from N^{4α} to N^{2α} (pp. 2115–2116), and the conjecture Λ^{(2)}_N = O(N^{4α−1}) for α ∈ (1/4, 1/2) (p. 2119); first in Austin's D.Phil. thesis (2016), Conjectures 3.5 and 3.10, in other forms. Stated together, with the normalised Fourier matrix, by OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- CA
- Keywords
- Lebesgue constants, nonuniform Fourier matrices, OpenProblemsInNLA, trigonometric interpolation
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@article{austin2017,
author = {Austin, Anthony P. and Trefethen, Lloyd N.},
title = {Trigonometric interpolation and quadrature in perturbed points},
journal = {SIAM J. Numer. Anal.},
volume = {55},
number = {5},
year = {2017},
pages = {2113--2122},
doi = {10.1137/16M1107760},
eprint = {1612.04018},
archivePrefix = {arXiv},
}
@phdthesis{austin2016,
author = {Austin, Anthony P.},
title = {Some New Results on and Applications of Interpolation in Numerical Computation},
school = {University of Oxford},
type = {D.Phil. thesis},
year = {2016},
doi = {10.5287/ora-dqjx80ezd},
url = {https://ora.ox.ac.uk/objects/uuid:11c16937-4a59-494d-a06f-6d27b634e2f3},
}
@article{yu2023,
author = {Yu, Annan and Townsend, Alex},
title = {On the stability of unevenly spaced samples for interpolation and quadrature},
journal = {BIT Numer. Math.},
volume = {63},
number = {2},
year = {2023},
pages = {Paper No. 23},
doi = {10.1007/s10543-023-00965-z},
eprint = {2202.04722},
archivePrefix = {arXiv},
}
@misc{chen2026,
author = {Chen, Liang and Lin, Rongrong and Zhang, Haizhang},
title = {Smallest Singular Value Estimates for Nonuniform {F}ourier Matrices via Periodic Nonuniform Sampling},
year = {2026},
eprint = {2608.21960},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ie26,
author = {Townsend, Alex},
title = {{IE-26}: Sharp stability bounds for perturbed Fourier interpolation},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/linear-systems-and-elimination/IE-26/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
The manuscript proves two bounds conjectured by Austin and Trefethen for trigonometric interpolation of degree $N$ in $m = 2N + 1$ points, each displaced from the equispaced grid by at most $\alpha$ grid spacings: the Lebesgue constant is at most $C(N^{2\alpha} - 1)/(\alpha(1 - 2\alpha))$ with $C$ absolute, for all $N \ge 2$ and $0 < \alpha < 1/2$, …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Needs verification → Solution claimed | clemens-admin | Listed with the record of its solution, unreviewed. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00227, "Sharp stability bounds for perturbed Fourier interpolation", clopen.solutions.