Abstract

Contents

This page follows the manuscript closely. It is written as mathematical exposition rather than as a summary page.

1 Introduction

Recovering a signal from incomplete measurements is an extremely important problem connecting harmonic analysis, sampling theory, compressed sensing, and inverse reconstruction [10, 11, 12, 13, 15, 7, 1]. A large body of work has shown that when the spectral information of a signal is sufficiently concentrated, stable recovery can remain possible even when only a small portion of the available measurements are observed [10, 11, 12, 13, 15]. The Fourier Ratio has recently emerged as a particularly powerful way to quantify this concentration, with applications to recovery, localization, learning, uncertainty principles, PDE propagation, sampling, and spectral analysis on manifolds [2, 7, 1, 8, 3, 4, 9]. For a discrete function \(g\) with Fourier transform \(\widehat g\), it is defined by \[FR(g) \ = \ \frac{\norm{\widehat g}_1}{\norm{\widehat g}_2}.\] The ratio behaves like the square root of an effective Fourier support size, so it measures how many frequencies contribute significantly without requiring a sparsity assumption [7]. On an \(N\) by \(N\) grid one always has \[1 \ \leq \ FR(g) \ \leq \ N.\] Thus a Fourier Ratio substantially smaller than \(N\) gives indicates a form of spectral concentration, and existing recovery results can turn that concentration directly into guarantees for reconstruction from incomplete random measurements [7, 1, 10, 15].

The situation becomes particularly interesting however when the discrete data is not arbitrary, but instead comes from physical sensors sampling an underlying continuous function. In that setting the geometry and regularity of the continuous signal should influence the complexity of the sampled data, while the locations of the sensors themselves may be translated, perturbed, randomly chosen, or missing altogether. This creates a direct bridge between analysis and sensing: if regularity forces the Fourier Ratio of the sampled signal to be small, then smoothness information can be converted into an explicit sampling parameter and ultimately into a reconstruction guarantee. We show that Hölder and Sobolev regularity control the Fourier Ratio on finite grids and that averaging over sensor translations can substantially strengthen the resulting estimates. Further, we determine that small placement errors remain compatible with stable recovery, and that this also extends from the discrete torus to compact Riemannian manifolds.

We start with the work of Iosevich, Palsson, and Yavicoli [1], who studied discretization and sampling through the Fourier Ratio. For a \(C^2\) periodic function sampled on an \(N\) by \(N\) grid, they obtained a Fourier Ratio bound of order \(\log N\) and used it in a random-sampling recovery theorem on \(\mathbb Z_N^2\). They also considered bandlimited functions on \(S^2\), where an exact quadrature rule connects sampled values with spherical harmonic coefficients and a spherical sampling theorem gives recovery from random point evaluations. Related recent work has developed the Fourier Ratio as a broader measure of signal complexity and connected it to recovery, localization, learning, PDE propagation, and uncertainty phenomena [2, 7, 8, 3, 9]. We retain this point of view, but replace separate pointwise estimates for Fourier coefficients by an energy argument. That change both improves the resulting bounds and makes it possible to ask how little regularity is necessary before returning to trivial bounds.

Our first result shows that differentiability is not required. If \(f\in C^{0,\gamma}([0,1]^2)\) with \(0<\gamma\leq1\), then sampling \(f\) on an \(N\) by \(N\) grid gives, up to the zero-frequency and lower-order quadrature terms, \[FR(g) \ \lesssim \ N^{1-\gamma}\sqrt{1+\log N}.\] Since the universal estimate is \(FR(g)\leq N\), every positive Hölder exponent gives an asymptotic improvement: \[N^{1-\gamma}\sqrt{1+\log N} \ = \ o(N).\] Thus even a small amount of Hölder regularity forces nontrivial concentration of the Fourier spectrum. At the endpoint \(\gamma=1\), the polynomial growth disappears and the estimate becomes \[FR(g) \ \lesssim \ \sqrt{1+\log N},\] up to the lower-order quadrature term. In particular, Lipschitz regularity already reaches the one-derivative critical rate, and every \(C^1\) function is automatically covered. Compared with [1], this lowers the regularity assumption from \(C^2\) to Lipschitz regularity while replacing \(\log N\) by \(\sqrt{\log N}\).

The Hölder result also gives a fractional Sobolev theorem which says that suppose that \(0<s<1\), \(1<p<\infty\), and \(sp>2\). The fractional Sobolev–Morrey embedding gives \[W^{s,p}([0,1]^2) \ \hookrightarrow \ C^{0,s-2/p}([0,1]^2).\] Taking \[\gamma \ = \ s-\frac{2}{p}\] in the Hölder estimate therefore gives \[FR(g) \ \lesssim \ \frac{\left|\int f\right|}{\norm{f}_2}+ \frac{\norm{f}_{W^{s,p}}}{\norm{f}_2}N^{1-s+2/p}\sqrt{1+\log N},\] up to a lower-order quadrature term. The condition \[sp \ > \ 2\] is therefore the natural fractional Sobolev threshold produced by this argument. Above this threshold, Sobolev regularity forces the Fourier Ratio to grow strictly slower than the universal \(O(N)\) bound.

In these estimates we use a discrete energy argument, and further we consider the finite difference of the sampled signal controls a weighted \(\ell^2\) norm of its Fourier coefficients, and Cauchy-Schwarz reduces the problem to a sum of inverse powers of the discrete frequency. This also continues to work in every dimension and gives three familiar regimes: below the critical Sobolev index there is polynomial growth, at the critical index there is a \(\sqrt{\log N}\) loss, and above the critical index the bound is independent of \(N\). Notably, the case on the unit square with exactly one derivative is then the critical case.

Within the fixed-grid Hölder and Sobolev estimates, we require the assumption of a hypothesis that prevents the sampled \(L^2\) mass from becoming too small. To do so, we average over a common translation of the grid and control the sampled mass, discrete difference energy, and the zero Fourier coefficient such that for some translation \(t\) \[FR(g_t) \ \leq \ 1+C\sqrt{1+\log N}\frac{\norm{\nabla f}_{L^2([0,1]^2)}}{\norm{f}_{L^2([0,1]^2)}}.\] Notably, there is no lower bound on \(N\), and the main regularity term now involves the \(L^2\) energy of the gradient rather than its supremum norm. This is the strongest square estimate in the paper.

A common translation and an individual error in each sensor position play different roles. A common translation preserves the grid, whereas independent displacements are more naturally treated as measurement noise.

Figure 1 shows this distinction. After giving deterministic placement estimates and a coupon-collector description, we prove an end-to-end theorem for random grid indices and arbitrary within-cell displacements. The reconstruction error is controlled by the Fourier Ratio and by \(\frac{1}{N}\norm{f}_{C^1}\). Uniform within-cell positions produce independent uniform sensors on the torus.

The discrete calculation also has a direct spectral analogue. On a compact Riemannian manifold, weighted Cauchy-Schwarz and Weyl’s law give the same three Sobolev regimes, with critical index \[s \ = \ \frac{d}{2}.\] On every compact surface, coefficients proportional to \(\frac{1}{\lambda_j}\) show that the \(\sqrt{\log L}\) factor is necessary. Therefore, it can easily be seen that the critical logarithmic loss is not an artifact of the discrete proof and that the sphere result is an explicit continuous coefficient estimate rather than a new quadrature theorem.

The recovery arguments use the bounded orthonormal system framework formulated in Fourier Ratio language by Burstein, Iosevich, and Nathan [7], together with the standard restricted-isometry theory in [10, 15]. We apply this existing mechanism first to the finite Fourier basis and then to a fixed Laplace-Beltrami eigenbasis. On a manifold, the eigenfunction \(L^\infty\) bound appears as the coherence parameter, and perturbing the sample locations contributes an explicit geodesic placement error. When an eigenvalue has multiplicity, the \(\ell^1\) norm of the coefficient vector depends on the basis selected inside that eigenspace. All manifold statements are therefore made relative to one fixed eigenbasis.

The paper is organized as follows: we begin with the discrete energy estimate and the bounded orthonormal system theorem that serve as the two main tools used throughout the paper. We then develop the Fourier Ratio bounds on the periodic square, first for Hölder and fractional Sobolev regularity and then for a suitably translated grid. We next pass to compact manifolds, where this same energy mechanism is expressed spectrally and the critical logarithmic loss is shown to be sharp on surfaces, with the sphere as an explicit example. Finally, we combine these analytic estimates with deterministic sensor-placement bounds, random placement through coupon-collector arguments, and stable \(\ell^1\) reconstruction on the square and on compact manifolds.

[top]

2 Preliminaries

Two ingredients are used repeatedly. The first is a weighted Fourier-energy estimate, recorded on finite groups in arbitrary dimension, whose critical logarithmic regime reappears on surfaces. The second is the standard bounded-orthonormal-system recovery theorem, which converts a Fourier Ratio bound into approximate sparsity and stable recovery from random measurements. We record both in the normalizations used below.

2.1 Discrete Fourier Energy

The argument used later on the square is not peculiar to two dimensions. It is useful to record the underlying finite-group statement first. This also makes clear why dimension two is critical for one derivative.

For a function \(g:\mathbb Z_N^d\to\mathbb C\), we use the unitary Fourier transform \[\widehat g(m) = \frac{1}{N^{\frac{d}{2}}} \sum_{x\in\mathbb Z_N^d} e^{-\frac{2\pi i x\cdot m}{N}}g(x).\] For \(m\in\mathbb Z_N^d\), set \[\rho(m)^2 = \sum_{j=1}^d \left|e^{\frac{2\pi i m_j}{N}}-1\right|^2.\] The quantity \(\rho(m)\) is zero only at \(m=0\). It plays the role of frequency magnitude on the finite group.

The three regimes have a simple interpretation. A discrete derivative of order \(s\) contributes a factor of approximately \(\frac{1}{N^s}\) when a smooth function is sampled. After this scaling is taken into account, the Fourier ratio is bounded independently of \(N\) above the critical index, grows like \(\sqrt{\log N}\) at the critical index, and grows like \(N^{\frac{d}{2}-s}\) below it. In the square section we push the argument below one derivative using Hölder increments and fractional Sobolev–Morrey embedding; the endpoint \(\gamma=1\) is the critical two-dimensional case and already contains \(C^1\) functions.

2.2 Bounded Orthonormal System Recovery

We first state the standard result that will be used. Let \(a=(a_1,\ldots,a_D)\in\mathbb C^D\). For \(1\leq s\leq D\), its best \(s\)-term approximation error in \(\ell^1\) is \[\sigma_s(a)_1 = \inf\left\{\left\|a-b\right\|_1: b\text{ has at most }s\text{ nonzero coordinates}\right\}.\] Equivalently, one obtains a minimizer by retaining the \(s\) largest coordinates of \(a\) in absolute value. The quantity \(\sigma_s(a)_1\) measures how close \(a\) is to being \(s\)-sparse.

Suppose that \(\phi_1,\ldots,\phi_D\) are orthonormal in \(L^2(\Omega,\mu)\) and satisfy \[\left\|\phi_j\right\|_{L^\infty(\Omega)}\leq K.\] Choose \(x_1,\ldots,x_q\) independently according to \(\mu\) and form the sampling matrix \[A_{ij}=\frac{1}{\sqrt q}\phi_j(x_i).\] The factor \(\frac{1}{\sqrt q}\) makes the expected squared norm of \(Aa\) equal to \(\left\|a\right\|_2^2\).

A vector is called \(s\)-sparse if at most \(s\) of its coordinates are nonzero. The matrix \(A\) has the restricted isometry property of order \(s\) if there is a number \(0<\delta<1\) such that \[(1-\delta)\left\|a\right\|_2^2 \leq \left\|Aa\right\|_2^2 \leq (1+\delta)\left\|a\right\|_2^2\] for every \(s\)-sparse vector \(a\). Thus \(A\) acts almost like an isometry on every coordinate subspace of dimension at most \(s\). This is the property that permits sparse, and approximately sparse, coefficient vectors to be reconstructed from incomplete measurements.

The proposition combines two standard results. Random sampling of a bounded orthonormal system gives the required restricted isometry property, and the restricted isometry property gives stable recovery by \(\ell^1\) minimization. Proofs of these statements, with several versions of the logarithmic factors and failure probabilities, can be found in [15]. We state the input explicitly so that the normalization used in the manifold application is transparent.

[top]

3 Fourier Ratio Bounds on the Periodic Square

We write \(\mathbb Z_N=\mathbb Z/N\mathbb Z\). We begin with a Riemann-sum estimate. Throughout this section, functions on \([0,1]^2\) are understood to extend periodically to \(\mathbb R^2\), and we use \[\left\|f\right\|_{C^1([0,1]^2)} = \max\left\{ \left\|f\right\|_{L^\infty}, \left\|\frac{\partial f}{\partial x_1}\right\|_{L^\infty}, \left\|\frac{\partial f}{\partial x_2}\right\|_{L^\infty} \right\}.\] For \(0<\gamma\leq1\), we also write \[_{C^{0,\gamma}} = \sup_{u\neq v} \frac{|f(u)-f(v)|}{d_{\mathbb T^2}(u,v)^\gamma}, \qquad \|f\|_{C^{0,\gamma}} = \|f\|_{L^\infty}+[f]_{C^{0,\gamma}},\] where \(d_{\mathbb T^2}\) denotes the periodic distance on the square.

3.1 Hölder and Fractional Sobolev Bounds

The next estimate records what remains of the discrete energy argument below the \(C^1\) threshold. The loss \(N^{1-\gamma}\) comes from the fact that a Hölder increment across one grid cell has size \(N^{-\gamma}\) rather than \(N^{-1}\).

For \(0<s<1\) and \(1<p<\infty\), we use the periodic Sobolev–Slobodeckij norm \[\|f\|_{W^{s,p}}^p = \|f\|_{L^p}^p + \int_{[0,1]^2}\int_{[0,1]^2} \frac{|f(u)-f(v)|^p} {d_{\mathbb T^2}(u,v)^{2+sp}}\,du\,dv.\] The fractional Morrey inequality states that if \(sp>2\) and \[\alpha=s-\frac2p,\] then \[\|f\|_{C^{0,\alpha}([0,1]^2)} \leq M_{s,p}\|f\|_{W^{s,p}([0,1]^2)};\] see, for example, [17].

The same Hölder proposition applies to any higher-order Sobolev class for which Sobolev–Morrey embedding supplies a positive Hölder exponent; the theorem above isolates the genuinely fractional range in which the threshold is exactly \(sp>2\).

3.2 A Translated Grid

The fixed-grid Hölder estimate requires a quantitative hypothesis keeping the sampled \(L^2\) norm from becoming too small. For \(C^1\) functions, a translation of the grid removes this issue. More importantly, averaging over the translation parameter allows us to replace the \(C^1\) norm in the main term by the \(L^2\) norm of the gradient.

[top]

4 Fourier Ratio Bounds on Compact Manifolds

Let \((M,g)\) be a connected compact \(d\)-dimensional Riemannian manifold without boundary, and write \(|M|\) for its Riemannian volume. Fix an orthonormal basis \(\{e_j\}_{j=0}^\infty\) of \(L^2(M)\) consisting of Laplace-Beltrami eigenfunctions, \[-\Delta_ge_j=\lambda_je_j, \quad \text{and} \quad 0=\lambda_0<\lambda_1\leq\lambda_2\leq\cdots.\] We take \(e_0=\frac{1}{\sqrt{|M|}}\). For \(L\geq 1\), let \[V_L=\operatorname{span}\{e_j:\lambda_j\leq L\}, \quad \text{and} \quad D_L=\#\{j:\lambda_j\leq L\}.\] For \(f\in V_L\), define \[\widehat f(j)=\int_Mf(x)\overline{e_j(x)}dV_g(x), \quad \text{and} \quad FR_L(f)=\frac{\sum_{\lambda_j\leq L}|\widehat f(j)|}{\left(\sum_{\lambda_j\leq L}|\widehat f(j)|^2\right)^{\frac{1}{2}}}.\] The spectral decomposition also defines fractional powers of the Laplace-Beltrami operator. If \(s>0\) and \(f\in V_L\), then \[(-\Delta_g)^{\frac{s}{2}}f = \sum_{0<\lambda_j\leq L} \lambda_j^{\frac{s}{2}}\widehat f(j)e_j.\] The constant mode is omitted because its eigenvalue is zero. Parseval’s identity gives \[\left\|(-\Delta_g)^{\frac{s}{2}}f\right\|_{L^2(M)}^2 = \sum_{0<\lambda_j\leq L}\lambda_j^s|\widehat f(j)|^2.\] When \(s=1\), integration by parts on a compact manifold without boundary yields the Dirichlet-energy identity \[\left\|(-\Delta_g)^{\frac{1}{2}}f\right\|_{L^2(M)}^2 = \left\langle-\Delta_gf,f\right\rangle_{L^2(M)} = \left\|\nabla_gf\right\|_{L^2(M)}^2.\] Thus Proposition 9 is the spectral counterpart of the discrete-gradient calculation on \(\mathbb Z_N^2\).

4.1 Sharpness on Compact Surfaces

The square-root logarithm in Corollary 10 is not merely a loss caused by the proof. The next result shows that it is forced by the distribution of the eigenvalues.

4.2 The Sphere

On \(S^2\), the eigenvalues are \(\lambda_\ell=\ell(\ell+1)\) with multiplicity \(2\ell+1\). The critical estimate can therefore be written with an explicit constant. Here \(\left\|f\right\|_{C^1(S^2)}\) is the maximum of the \(L^\infty\) norms of \(f\) and its spherical gradient.

[top]

5 Sampling and Reconstruction

We combine the analytic bounds with the effect of moving the sensors and with the bounded orthonormal system input from the Tools section. The square and manifold settings have the same overall structure: first the displacement of a sensor is converted into measurement error, then random physical locations are related to random reference locations when needed, and finally the Fourier Ratio bound controls the approximation term in stable \(\ell^1\) recovery.

5.1 Sensor Placement and Random Sensors on the Square

We allow the sampling location in each cell to vary independently. These perturbations do not preserve the Fourier structure exactly, so it is better to regard them as measurement errors relative to the uniform grid.

We finish the square case by recording what happens when the sensors themselves are placed uniformly at random.

5.2 Recovery on the Periodic Square

The placement and coupon-collector results above provide the measurement-error and random-index pieces. We can now combine them with the bounded orthonormal system theorem and the Fourier Ratio estimate to obtain an end-to-end reconstruction statement on the square.

We can now combine the square Fourier ratio estimate, the placement-error estimate, and Proposition 2. This gives a complete recovery statement rather than leaving the three ingredients separate.

5.3 Sensor Stability on Compact Manifolds

The pointwise estimate can be read directly as a tolerance condition on how far the actual sensor may move while keeping the total measurement error at a prescribed relative scale.

When a sensor is only known to lie in the same geometric cell as its intended location, the cell diameter supplies the displacement parameter automatically.

If the partition comes from a family of cells whose diameters decay at the natural \(K^{-1/d}\) scale, the same condition can instead be stated directly as a lower bound on the number of cells.

Equal-volume partitions also let us pass from uniformly random physical sensors to uniformly random subsets of reference cells, exactly as on the square.

5.4 Sensors on the Sphere

On the sphere the general geodesic placement estimate has a particularly simple form, and an equal-area partition gives the same coupon-collector description of random physical sensors as in the square case.

5.5 Recovery in the Laplace-Beltrami Eigenbasis

The preceding results control the sensor locations themselves. We return to the Laplace-Beltrami eigenbasis and combine that placement control with the manifold Fourier Ratio bounds and the bounded orthonormal system theorem.

For the spectral space \(V_L\), let \[K_L = |M|^{\frac{1}{2}} \sup_{\lambda_j\leq L}\|e_j\|_{L^\infty(M)}.\] This is the boundedness parameter of the normalized orthonormal system \[\phi_j=|M|^{\frac{1}{2}}e_j\] in \(L^2\left(M,\frac{1}{|M|}dV_g\right)\).

[top]

6 Concluding Remarks

The estimates in this paper all come from the same energy principle. On \(\mathbb Z_N^d\), the dimension and the number of controlled derivatives determine whether the inverse-frequency weight is summable, logarithmically divergent, or polynomially divergent. In dimension two, one derivative is critical and leaves a square-root logarithm. The spectral argument on a compact manifold has exactly the same three regimes.

The common translation does more than prevent the sampled mass from vanishing. Averaging the mass and the discrete-gradient energy together produces a grid controlled by the continuous \(H^1\) energy. Averaging the aliased zero frequency at the same time keeps the mean term under control. This is why the translated theorem is both cleaner and stronger than the fixed-grid estimate.

The example with coefficients \(\frac{1}{\lambda_j}\) shows that the critical square-root logarithm on a compact surface is unavoidable. The upper bound and the example therefore identify the correct growth rate for the energy method. It remains possible that additional structure of a particular function class could improve the Fourier ratio, but such an improvement would have to use information beyond the critical Sobolev norm.

Independent sensor displacements do not preserve the Fourier transform, but they enter naturally as measurement noise. The square recovery theorem makes this precise for random grid indices and arbitrary within-cell errors. The manifold corollary gives the same conclusion for geodesically displaced sensors. These statements are applications of the bounded orthonormal system theorem, but putting the analytic estimate and the placement error into one conclusion is useful: it shows exactly how grid resolution, spectral complexity, and sensor accuracy interact.

On a general manifold, the remaining obstacle is coherence. Uniform point sampling can be expensive when the selected eigenfunctions concentrate. Weighted sampling, a different eigenbasis, or geometry-specific eigenfunction estimates may improve this part of the result. Any such improvement must also keep track of the basis dependence of the Fourier ratio.

[top]

References