betaFeedback

WorksMathematics

Fourier Ratio Bounds and Sensitivity to Sensor Placement

Abstract

We study how the regularity of a continuous function controls the Fourier ratio of its sampled values, and how errors in sensor placement affect recovery from incomplete measurements. For a periodic function on the square sampled on an NN by NN grid, we show that Hölder regularity C0,γC^{0,γ} with 0<γ<10<γ<1 leads to a bound of order N1−γN^{1-γ}, that Lipschitz regularity leads to the critical bound 1+log⁡N\sqrt{1+\log N}, and that fractional Sobolev regularity Ws,pW^{s,p} with 0<s<10<s<1 and sp>2sp>2 leads to a bound of order N1−sN^{1-s}, where both polynomial exponents are sharp. A common translation of the grid removes the hypothesis on the sampled mass needed on a fixed grid and yields an estimate in terms of the L2L^2 norm of the gradient, and with two derivatives the bound is independent of the grid size. We extend the energy argument behind these results to compact Riemannian manifolds and prove that the critical square-root logarithm is necessary on every compact surface. Finally, we treat separate sensor displacements as measurement error and combine the analytic bounds with random sampling to obtain stable recovery of the sampled vector on the square and of bandlimited functions on compact manifolds, where the number of samples depends on the suprema of the chosen eigenfunctions.

The third author was supported in part by NSF grant DMS-2506858 and a Simons Fellowship in Mathematics in 2026.

Introduction

The purpose of this paper is to study how the regularity of a continuous function controls the concentration of the Fourier coefficients of its samples, and what happens to the recovery of the function from incomplete measurements when the sensors that take those samples are moved. The recovery of a signal from incomplete measurements has been studied extensively in harmonic analysis, sampling theory, compressed sensing, and inverse problems (see, for example, [5, 6, 7, 9, 13, 15, 16]), and the underlying principle is that if the Fourier coefficients of a signal are sufficiently concentrated, then stable recovery may be possible from a small portion of its spatial samples.

A convenient way to measure this concentration is the Fourier ratio [2, 5]. Let ZN=Z/NZ\mathbb{Z}_N = \mathbb{Z}/N\mathbb{Z}, where N≥2N \ge2 is an integer, and given g:ZNd→Cg : \mathbb{Z}_N^d \to\mathbb{C} define the Fourier transform of gg by

g^(m)=1Nd/2∑x∈ZNde−2πix⋅mNg(x).\widehat{g}(m) = \frac{1}{N^{d/2}} \sum_{x \in\mathbb{Z}_N^d} e^{-\frac{2\pi i x \cdot m}{N}} g(x).

With this normalization the Fourier transform is unitary, which is to say that ∥g^∥2=∥g∥2\|\widehat{g}\|_2 = \|g\|_2, where ∥⋅∥1\|\cdot\|_1 and ∥⋅∥2\|\cdot\|_2 denote the ℓ1\ell^1 and ℓ2\ell^2 norms on ZNd\mathbb{Z}_N^d. If gg is not identically zero, its Fourier ratio is defined by

FR(g)=∥g^∥1∥g^∥2.FR(g) = \frac{\|\widehat{g}\|_1}{\|\widehat{g}\|_2}.

If precisely kk Fourier coefficients of gg are nonzero, then FR(g)≤kFR(g) \le\sqrt{k} by Cauchy–Schwarz, but the ratio remains meaningful when many coefficients are nonzero and most of them are small. On an NN by NN grid one always has 1≤FR(g)≤N1 \le FR(g) \le N, so a Fourier ratio substantially smaller than NN indicates spectral concentration, and existing recovery theorems turn such a bound into a guarantee for reconstruction from incomplete random measurements [5, 6, 9, 13].

Suppose now that the discrete data comes from sensors that sample a continuous function. It is natural to ask what the regularity of this function tells us about its sampled Fourier coefficients, and what happens if the sensors are moved. We shall see that Hölder and Sobolev regularity control the Fourier ratio on finite grids, that averaging over a common translation of the grid strengthens the estimates, and that separate placement errors can be included in the recovery argument as measurement noise.

Our starting point is the work of Iosevich, Palsson, and Yavicoli [13], who studied discretization and sampling through the Fourier ratio. For a C2C^2 periodic function sampled on an NN by NN grid they obtained a bound of order log⁡N\log N and used it in a recovery theorem for random samples on ZN2\mathbb{Z}_N^2, and they also considered bandlimited functions on S2S^2 by means of quadrature and spherical harmonic expansions. The Fourier ratio has also been connected to recovery, localization, learning, PDE propagation, spectral synthesis, and uncertainty principles in [2, 5, 10, 11, 12, 14]. We keep the point of view of [13], but in place of separate pointwise estimates for the Fourier coefficients we use an energy argument.

Our first result shows that differentiability is not required. Let ff be a periodic function on [0,1]2[0,1]^2 and let g(x)=f(xN)g(x) = f\left(\frac{x}{N}\right), x∈ZN2x \in\mathbb{Z}_N^2, denote its samples on the NN by NN grid. If ff belongs to the Hölder class C0,γ([0,1]2)C^{0,\gamma}([0,1]^2) with 0<γ<10 < \gamma< 1, then for sufficiently fine grids

FR(g)≤Cγ∥f∥C0,γ∥f∥L2N1−γ,FR(g) \le C_\gamma\frac{\|f\|_{C^{0,\gamma}}}{\|f\|_{L^2}}N^{1-\gamma},

where the Hölder norm, like the other norms that appear in this introduction, is defined in Section 3. In particular, every positive Hölder exponent improves on the universal bound FR(g)≤NFR(g) \le N. At the endpoint γ=1\gamma= 1 we obtain

FR(g)≤C∥f∥C0,1∥f∥L21+log⁡N.FR(g) \le C \frac{\|f\|_{C^{0,1}}}{\|f\|_{L^2}}\sqrt{1+\log N}.

which means that Lipschitz regularity already reaches the critical estimate for one derivative. For C2C^2 functions an argument with second differences yields a bound independent of NN on sufficiently fine fixed grids, or on a suitable translated grid for every N≥2N \ge2. The energy calculation thus lowers the regularity needed for a nontrivial estimate, and it also improves the bound at the regularity considered in [13].

The Hölder result has a fractional Sobolev counterpart. Suppose that 0<s<10 < s < 1, 1<p<∞1 < p < \infty, and sp>2sp > 2. A local form of the Morrey inequality, used inside the same dyadic argument, shows that for sufficiently fine grids

FR(g)≤Cs,p∥f∥Ws,p∥f∥L2N1−s.FR(g) \le C_{s,p}\frac{\lVert f\rVert_{W^{s,p}}}{\lVert f\rVert_{L^2}}N^{1-s}.

The condition sp>2sp > 2 is there to provide the continuous representative needed for point sampling, and it does not affect the exponent. A sampled discrete chirp shows that neither 1−γ1-\gamma nor 1−s1-s can be lowered in bounds that are uniform over the corresponding regularity classes.

Let us describe why energy enters the picture. A finite difference of the sampled signal multiplies its Fourier coefficients by a discrete frequency, so Parseval’s identity controls a weighted ℓ2\ell^2 sum of those coefficients, and Cauchy–Schwarz then reduces the ℓ1\ell^1 estimate to a sum of inverse frequency weights. In dimension two, one derivative leaves a square-root logarithm. Below the Lipschitz endpoint we apply differences at the scale of each frequency annulus, which avoids an unnecessary logarithmic loss, and above the critical number of derivatives the inverse weights are summable.

The estimates on a fixed grid require a hypothesis which prevents the sampled L2L^2 mass from becoming too small. For a C1C^1 function a common translation of the grid removes this issue. Averaging the sampled mass and the difference energy together produces, for every N≥2N \ge2, a translation tt such that the translated samples gt(x)=f(x+tN)g_t(x)=f\left(x+\frac{t}{N}\right) satisfy

FR(gt)≤1+121+log⁡N∥∇f∥L2([0,1]2)∥f∥L2([0,1]2).FR(g_t) \le1+\frac{1}{\sqrt{2}}\sqrt{1+\log N}\frac{\lVert\nabla f\rVert_{L^2([0,1]^2)}}{\lVert f\rVert_{L^2([0,1]^2)}}.

The translation may depend on ff, so this is an existence theorem for a favorable grid and not a procedure for finding that grid from incomplete observations.

A common translation and a separate error in each sensor position play different roles, as illustrated in Figure 1. A common translation preserves the grid, while separate displacements are treated as measurement noise. We prove a recovery theorem for random grid indices and arbitrary displacements inside the translated cells, with an error controlled by the Fourier ratio and by 1N∥f∥C1\frac{1}{N}\lVert f\rVert_{C^1}. If the positions are chosen uniformly inside these cells, the result is a collection of independent uniform sensors on the torus. The reconstruction theorem concerns the sampled vector, and a piecewise constant extension leads to an L2L^2 estimate on the torus with the same placement scale.

Grid points under one common translation and separate perturbations

Figure 1. The open circles are the reference grid points. In (a) every point is moved by the same vector, so the translated points still form a grid, while in (b) each sensor is displaced separately inside its cell and the displacements are treated as measurement errors.

The discrete calculation has a spectral analogue. On a connected compact Riemannian manifold of dimension dd, weighted Cauchy–Schwarz and Weyl’s law lead to the critical Sobolev index s=d2s = \frac{d}{2}. We use Λ\Lambda for an eigenvalue cutoff and LL for a spherical harmonic degree. On a compact surface, coefficients proportional to 1λj\frac{1}{\lambda_j}, where the λj\lambda_j are the positive eigenvalues of the Laplace–Beltrami operator, show that the factor 1+log⁡Λ\sqrt{1+\log\Lambda} is necessary in the estimate involving the L2L^2 norm of the gradient. This establishes sharpness for the critical Sobolev energy, but not for estimates involving the stronger C1C^1 norm.

For recovery we use the bounded orthonormal system theorem of Brugiapaglia, Dirksen, Jung, and Rauhut [3], together with the stable ℓ1\ell^1 theory in [7, 9], and we refer to [5] for the formulation in terms of the Fourier ratio. On a manifold the L∞L^\infty bound for the eigenfunctions enters the sample count. Moreover, when an eigenvalue has multiplicity, the ℓ1\ell^1 norm of the coefficients depends on the basis chosen in that eigenspace, and for this reason all the statements on manifolds are made relative to one fixed orthonormal eigenbasis.

This paper is organized as follows. In Section 2 we prove the discrete energy estimate and state the bounded orthonormal system theorem. Section 3 contains the estimates on the square, first for Hölder and fractional Sobolev regularity and then for translated grids and two derivatives. In Section 4 we treat compact manifolds and the sharp critical estimate on surfaces, and in Section 5 we combine these bounds with sensor placement estimates and stable reconstruction on the square and on compact manifolds.

Throughout the paper the grid size N≥2N \ge2, the dimension d≥1d \ge1, and all sample counts are integers, and the error parameter ε\varepsilon is positive. We write A≍BA \asymp B if cB≤A≤CBcB \le A \le CB with positive constants cc and CC independent of the grid size or the spectral cutoff, and subscripts on constants indicate what they are allowed to depend on. We also write ∥⋅∥ℓ2\lVert\cdot\rVert_{\ell^2} in place of ∥⋅∥2\lVert\cdot\rVert_2 when it is helpful to distinguish the discrete norm from an L2L^2 norm.

Tools

We begin with the two tools that are used throughout the paper. The discrete energy estimate controls the Fourier ratio, and the bounded orthonormal system theorem turns this control into recovery from random measurements.

Discrete Fourier energy

The argument that we use on the square in Section 3 is not special to two dimensions, so we first prove the underlying statement on the finite group ZNd\mathbb{Z}_N^d, which also makes it clear why dimension two is critical for one derivative. Let e1,…,ede_1,\ldots,e_d be the standard coordinate vectors, and for m∈ZNdm \in\mathbb{Z}_N^d define ρ(m)≥0\rho(m) \ge0 by

ρ(m)2=∑j=1d∣e2πimjN−1∣2.\rho(m)^2 = \sum_{j=1}^{d}\left|e^{\frac{2\pi i m_j}{N}}-1\right|^2.

The quantity ρ(m)\rho(m) is zero only at m=0m=0, and it plays the role of the size of the frequency mm on the finite group.

References

  1. [1]R. A. Adams and J. J. F. Fournier, Sobolev Spaces, second edition, Pure and Applied Mathematics 140, Academic Press, Amsterdam, 2003.
  2. [2]K. Aldaleh, W. Burstein, G. Garza, G. Hart, A. Iosevich, J. Iosevich, A. Khalil, J. King, N. Kulkarni, T. Le, I. Li, A. Mayeli, B. McDonald, K. Nguyen, and N. Shaffer, The Fourier ratio and complexity of signals, arXiv:2511.19560, 2025.arxiv.org/abs/2511.19560
  3. [3]S. Brugiapaglia, S. Dirksen, H. C. Jung, and H. Rauhut, Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs, Applied and Computational Harmonic Analysis 53 (2021), 231–269.arxiv.org/abs/2005.06994
  4. [4]N. Burq, S. Dyatlov, R. Ward, and M. Zworski, Weighted eigenfunction estimates with applications to compressed sensing, SIAM Journal on Mathematical Analysis 44 (2012), 3481–3501.DOI
  5. [5]W. Burstein, A. Iosevich, and H. S. Nathan, The Fourier Ratio: A Unifying Measure of Complexity for Recovery, Localization, and Learning, arXiv:2601.16345, 2026.arxiv.org/abs/2601.16345
  6. [6]E. J. Candès, J. Romberg, and T. Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Transactions on Information Theory 52, no. 2 (2006), 489–509.arxiv.org/abs/math/0409186
  7. [7]E. J. Candès, J. Romberg, and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Communications on Pure and Applied Mathematics 59 (2006), 1207–1223.
  8. [9]S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing, Birkhäuser, New York, 2013.DOI
  9. [10]A. Iosevich, J. Iosevich, E. Palsson, and A. Yavicoli, PDE propagation, sampling, and the Fourier ratio, arXiv:2603.07851, 2026.arxiv.org/abs/2603.07851
  10. [11]A. Iosevich, A. Mayeli, and E. Wyman, Fourier Uncertainty Principles on Riemannian Manifolds, arXiv:2411.09057, 2024.arxiv.org/abs/2411.09057
  11. [12]A. Iosevich, A. Mayeli, and E. Wyman, Spectral synthesis on Riemannian manifolds, arXiv:2603.21451, 2026.arxiv.org/abs/2603.21451
  12. [13]A. Iosevich, E. Palsson, and A. Yavicoli, Discretization, sampling, and the Fourier ratio, arXiv:2601.17493, 2026.arxiv.org/abs/2601.17493
  13. [14]A. Iosevich and C. Park, Uncertainty principles, spectral localization, and singular Schrödinger operators on compact manifolds, arXiv:2605.26264, 2026.arxiv.org/abs/2605.26264
  14. [15]H. Rauhut, Stability results for random sampling of sparse trigonometric polynomials, IEEE Transactions on Information Theory 54, no. 12 (2008), 5661–5670.arxiv.org/abs/math/0609630
  15. [16]M. Rudelson and R. Vershynin, On sparse reconstruction from Fourier and Gaussian measurements, Communications on Pure and Applied Mathematics 61, no. 8 (2008), 1025–1045.DOI
  16. [17]C. D. Sogge, Fourier Integrals in Classical Analysis, second edition, Cambridge University Press, Cambridge, 2017.

Paper details

vlnc:W_2aj5nuvy
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents