Optimal Extrapolation Bounds for Sparse Fourier Sums

DOI10.48550/arXiv.2607.10501MaRDI QIDQ7283989arXivFDO

Authors Ruizhe Zhang

Publication date 11 July 2026

Published in arXiv

Tldr We derive an optimal bound on extrapolation error for k-sparse trigonometric polynomials over arbitrary real frequencies without separation assumptions. We improve previous results with a better growth rate and prove that our scaling is best possible up to constant factors and polynomial terms in k, leading to improved algorithms and bounds for sparse Fourier regression.

Full work available at URL https://doi.org/10.48550/arXiv.2607.10501

arXiv classification

cs.DSmath.CAmath.NA

Cites work

• (Nearly) sample-optimal sparse Fourier transform in any dimension; RIPless and filterless
• (Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless
• A Note on Fourier Transforms
• A robust sparse Fourier transform in the continuous setting
• A universal sampling method for reconstructing signals with simple Fourier transforms
• Combinatorial sublinear-time Fourier algorithms
• Estimating the frequency of a clustered signal
• Fourier Sparse Leverage Scores and Approximate Kernel Learning
• Fourier-sparse interpolation without a frequency gap
• Inequalities for exponential sums
• Model spaces: a survey
• Near-optimal sparse fourier representations via sampling
• Nearly optimal sparse Fourier transform
• Nikolskii-type inequalities for shift invariant function spaces
• Norming sets and related Remez-type inequalities
• Pointwise Remez- and Nikolskii-type inequalities for exponential sums
• Quartic samples suffice for Fourier interpolation
• Sample-optimal Fourier sampling in any constant dimension
• Sparse Fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time
• Stability and super-resolution of MUSIC and ESPRIT for multi-snapshot spectral estimation
• Stability and Super-resolution of MUSIC and ESPRIT for Multi-snapshot Spectral Estimation
• Super-Resolution Limit of the ESPRIT Algorithm
• Super-resolution, extremal functions and the condition number of Vandermonde matrices
• Superresolution via Sparsity Constraints
• The recoverability limit for superresolution via sparsity
• Towards a Mathematical Theory of Super‐resolution

This page was built for publication: Optimal Extrapolation Bounds for Sparse Fourier Sums

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7283989)