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 Z N = Z / N Z \mathbb{Z}_N = \mathbb{Z}/N\mathbb{Z} Z N = Z / N Z , where N ≥ 2 N \ge2 N ≥ 2 is an integer, and given g : Z N d → C g : \mathbb{Z}_N^d \to\mathbb{C} g : Z N d → C define the Fourier transform of g g g by
g ^ ( m ) = 1 N d / 2 ∑ x ∈ Z N d e − 2 π i x ⋅ m N g ( 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). g ( m ) = N d /2 1 x ∈ Z N d ∑ e − N 2 π i x ⋅ m g ( x ) .
With this normalization the Fourier transform is unitary, which is to say that ∥ g ^ ∥ 2 = ∥ g ∥ 2 \|\widehat{g}\|_2 = \|g\|_2 ∥ g ∥ 2 = ∥ g ∥ 2 , where ∥ ⋅ ∥ 1 \|\cdot\|_1 ∥ ⋅ ∥ 1 and ∥ ⋅ ∥ 2 \|\cdot\|_2 ∥ ⋅ ∥ 2 denote the ℓ 1 \ell^1 ℓ 1 and ℓ 2 \ell^2 ℓ 2 norms on Z N d \mathbb{Z}_N^d Z N d . If g g g is not identically zero, its Fourier ratio is defined by
F R ( g ) = ∥ g ^ ∥ 1 ∥ g ^ ∥ 2 . FR(g) = \frac{\|\widehat{g}\|_1}{\|\widehat{g}\|_2}. F R ( g ) = ∥ g ∥ 2 ∥ g ∥ 1 .
If precisely k k k Fourier coefficients of g g g are nonzero, then F R ( g ) ≤ k FR(g) \le\sqrt{k} F R ( g ) ≤ k by Cauchy–Schwarz, but the ratio remains meaningful when many coefficients are nonzero and most of them are small. On an N N N by N N N grid one always has 1 ≤ F R ( g ) ≤ N 1 \le FR(g) \le N 1 ≤ F R ( g ) ≤ N , so a Fourier ratio substantially smaller than N N N 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 C 2 C^2 C 2 periodic function sampled on an N N N by N N N grid they obtained a bound of order log N \log N log N and used it in a recovery theorem for random samples on Z N 2 \mathbb{Z}_N^2 Z N 2 , and they also considered bandlimited functions on S 2 S^2 S 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 f f f be a periodic function on [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 and let g ( x ) = f ( x N ) g(x) = f\left(\frac{x}{N}\right) g ( x ) = f ( N x ) , x ∈ Z N 2 x \in\mathbb{Z}_N^2 x ∈ Z N 2 , denote its samples on the N N N by N N N grid. If f f f belongs to the Hölder class C 0 , γ ( [ 0 , 1 ] 2 ) C^{0,\gamma}([0,1]^2) C 0 , γ ([ 0 , 1 ] 2 ) with 0 < γ < 1 0 < \gamma< 1 0 < γ < 1 , then for sufficiently fine grids
F R ( g ) ≤ C γ ∥ f ∥ C 0 , γ ∥ f ∥ L 2 N 1 − γ , FR(g) \le C_\gamma\frac{\|f\|_{C^{0,\gamma}}}{\|f\|_{L^2}}N^{1-\gamma}, F R ( g ) ≤ C γ ∥ f ∥ L 2 ∥ f ∥ C 0 , γ N 1 − γ ,
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 F R ( g ) ≤ N FR(g) \le N F R ( g ) ≤ N . At the endpoint γ = 1 \gamma= 1 γ = 1 we obtain
F R ( g ) ≤ C ∥ f ∥ C 0 , 1 ∥ f ∥ L 2 1 + log N . FR(g) \le C \frac{\|f\|_{C^{0,1}}}{\|f\|_{L^2}}\sqrt{1+\log N}. F R ( g ) ≤ C ∥ f ∥ L 2 ∥ f ∥ C 0 , 1 1 + log N .
which means that Lipschitz regularity already reaches the critical estimate for one derivative. For C 2 C^2 C 2 functions an argument with second differences yields a bound independent of N N N on sufficiently fine fixed grids, or on a suitable translated grid for every N ≥ 2 N \ge2 N ≥ 2 . 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 < 1 0 < s < 1 0 < s < 1 , 1 < p < ∞ 1 < p < \infty 1 < p < ∞ , and s p > 2 sp > 2 s p > 2 . A local form of the Morrey inequality, used inside the same dyadic argument, shows that for sufficiently fine grids
F R ( g ) ≤ C s , p ∥ f ∥ W s , p ∥ f ∥ L 2 N 1 − s . FR(g) \le C_{s,p}\frac{\lVert f\rVert_{W^{s,p}}}{\lVert f\rVert_{L^2}}N^{1-s}. F R ( g ) ≤ C s , p ∥ f ∥ L 2 ∥ f ∥ W s , p N 1 − s .
The condition s p > 2 sp > 2 s p > 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 1 − γ nor 1 − s 1-s 1 − 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 ℓ 2 sum of those coefficients, and Cauchy–Schwarz then reduces the ℓ 1 \ell^1 ℓ 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 L 2 L^2 L 2 mass from becoming too small. For a C 1 C^1 C 1 function a common translation of the grid removes this issue. Averaging the sampled mass and the difference energy together produces, for every N ≥ 2 N \ge2 N ≥ 2 , a translation t t t such that the translated samples g t ( x ) = f ( x + t N ) g_t(x)=f\left(x+\frac{t}{N}\right) g t ( x ) = f ( x + N t ) satisfy
F R ( g t ) ≤ 1 + 1 2 1 + log N ∥ ∇ f ∥ L 2 ( [ 0 , 1 ] 2 ) ∥ f ∥ L 2 ( [ 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)}}. F R ( g t ) ≤ 1 + 2 1 1 + log N ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) ∥ ∇ f ∥ L 2 ([ 0 , 1 ] 2 ) .
The translation may depend on f f f , 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 1 N ∥ f ∥ C 1 \frac{1}{N}\lVert f\rVert_{C^1} N 1 ∥ f ∥ 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 L 2 L^2 L 2 estimate on the torus with the same placement scale.
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 d d d , weighted Cauchy–Schwarz and Weyl’s law lead to the critical Sobolev index s = d 2 s = \frac{d}{2} s = 2 d . We use Λ \Lambda Λ for an eigenvalue cutoff and L L L for a spherical harmonic degree. On a compact surface, coefficients proportional to 1 λ j \frac{1}{\lambda_j} λ j 1 , where the λ j \lambda_j λ j are the positive eigenvalues of the Laplace–Beltrami operator, show that the factor 1 + log Λ \sqrt{1+\log\Lambda} 1 + log Λ is necessary in the estimate involving the L 2 L^2 L 2 norm of the gradient. This establishes sharpness for the critical Sobolev energy, but not for estimates involving the stronger C 1 C^1 C 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 ℓ 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 L ∞ bound for the eigenfunctions enters the sample count. Moreover, when an eigenvalue has multiplicity, the ℓ 1 \ell^1 ℓ 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 ≥ 2 N \ge2 N ≥ 2 , the dimension d ≥ 1 d \ge1 d ≥ 1 , and all sample counts are integers, and the error parameter ε \varepsilon ε is positive. We write A ≍ B A \asymp B A ≍ B if c B ≤ A ≤ C B cB \le A \le CB c B ≤ A ≤ C B with positive constants c c c and C C C 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} ∥ ⋅ ∥ ℓ 2 in place of ∥ ⋅ ∥ 2 \lVert\cdot\rVert_2 ∥ ⋅ ∥ 2 when it is helpful to distinguish the discrete norm from an L 2 L^2 L 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 Z N d \mathbb{Z}_N^d Z N d , which also makes it clear why dimension two is critical for one derivative. Let e 1 , … , e d e_1,\ldots,e_d e 1 , … , e d be the standard coordinate vectors, and for m ∈ Z N d m \in\mathbb{Z}_N^d m ∈ Z N d define ρ ( m ) ≥ 0 \rho(m) \ge0 ρ ( m ) ≥ 0 by
ρ ( m ) 2 = ∑ j = 1 d ∣ e 2 π i m j N − 1 ∣ 2 . \rho(m)^2 = \sum_{j=1}^{d}\left|e^{\frac{2\pi i m_j}{N}}-1\right|^2. ρ ( m ) 2 = j = 1 ∑ d e N 2 π i m j − 1 2 .
The quantity ρ ( m ) \rho(m) ρ ( m ) is zero only at m = 0 m=0 m = 0 , and it plays the role of the size of the frequency m m m on the finite group.
Proposition 2.1. Let g : Z N d → C g:\mathbb{Z}_N^d \to\mathbb{C} g : Z N d → C be nonzero, and let s > 0 s>0 s > 0 . Then
F R ( g ) ≤ ∣ g ^ ( 0 ) ∣ ∥ g ∥ 2 + ( ∑ m ≠ 0 1 ρ ( m ) 2 s ) 1 2 ( ∑ m ρ ( m ) 2 s ∣ g ^ ( m ) ∣ 2 ) 1 2 ∥ g ∥ 2 . FR(g) \le\frac{|\widehat{g}(0)|}{\lVert g\rVert_2}+\left(\sum_{m\ne0}\frac{1}{\rho(m)^{2s}}\right)^{\frac{1}{2}}\frac{\left(\sum_m \rho(m)^{2s}|\widehat{g}(m)|^2\right)^{\frac{1}{2}}}{\lVert g\rVert_2}. F R ( g ) ≤ ∥ g ∥ 2 ∣ g ( 0 ) ∣ + m = 0 ∑ ρ ( m ) 2 s 1 2 1 ∥ g ∥ 2 ( ∑ m ρ ( m ) 2 s ∣ g ( m ) ∣ 2 ) 2 1 . Moreover,
( ∑ m ≠ 0 1 ρ ( m ) 2 s ) 1 2 ≤ C d , s { N s , s > d 2 , N d 2 1 + log N , s = d 2 , N d 2 , 0 < s < d 2 . \left(\sum_{m\ne0}\frac{1}{\rho(m)^{2s}}\right)^{\frac{1}{2}}
\le C_{d,s}
\begin{cases}
N^s, & s>\frac{d}{2},\\
N^{\frac{d}{2}}\sqrt{1+\log N}, & s=\frac{d}{2},\\
N^{\frac{d}{2}}, & 0<s<\frac{d}{2}.
\end{cases} m = 0 ∑ ρ ( m ) 2 s 1 2 1 ≤ C d , s ⎩ ⎨ ⎧ N s , N 2 d 1 + log N , N 2 d , s > 2 d , s = 2 d , 0 < s < 2 d .
and when d = 2 d=2 d = 2 and s = 1 s=1 s = 1 one may take the more explicit estimate
∑ m ≠ 0 1 ρ ( m ) 2 ≤ N 2 2 ( 1 + log N ) . \sum_{m\ne0}\frac{1}{\rho(m)^2}\le\frac{N^2}{2}(1+\log N). m = 0 ∑ ρ ( m ) 2 1 ≤ 2 N 2 ( 1 + log N ) .
Finally, if s = 1 s=1 s = 1 and Δ j g ( x ) = g ( x + e j ) − g ( x ) \Delta_jg(x)=g(x+e_j)-g(x) Δ j g ( x ) = g ( x + e j ) − g ( x ) , then
∑ m ρ ( m ) 2 ∣ g ^ ( m ) ∣ 2 = ∑ j = 1 d ∥ Δ j g ∥ 2 2 . \sum_m \rho(m)^2|\widehat{g}(m)|^2=\sum_{j=1}^{d}\|\Delta_jg\|_2^2. m ∑ ρ ( m ) 2 ∣ g ( m ) ∣ 2 = j = 1 ∑ d ∥ Δ j g ∥ 2 2 .
Proof. We begin with the energy identity. A change of variables shows that
Δ j g ^ ( m ) = 1 N d / 2 ∑ x e − 2 π i x ⋅ m N g ( x + e j ) − g ^ ( m ) = ( e 2 π i m j N − 1 ) g ^ ( m ) , \widehat{\Delta_jg}(m)=\frac{1}{N^{d/2}}\sum_x e^{-\frac{2\pi i x\cdot m}{N}}g(x+e_j)-\widehat{g}(m)=\left(e^{\frac{2\pi i m_j}{N}}-1\right)\widehat{g}(m), Δ j g ( m ) = N d /2 1 x ∑ e − N 2 π i x ⋅ m g ( x + e j ) − g ( m ) = ( e N 2 π i m j − 1 ) g ( m ) ,
so by Parseval’s identity
∥ Δ j g ∥ 2 2 = ∑ m ∣ e 2 π i m j N − 1 ∣ 2 ∣ g ^ ( m ) ∣ 2 , \|\Delta_jg\|_2^2=\sum_m\left|e^{\frac{2\pi i m_j}{N}}-1\right|^2|\widehat{g}(m)|^2, ∥ Δ j g ∥ 2 2 = m ∑ e N 2 π i m j − 1 2 ∣ g ( m ) ∣ 2 ,
and summing over j j j we obtain the last identity in the statement.
To prove the main estimate we separate the zero frequency and apply Cauchy–Schwarz to the remaining frequencies, which leads to
∑ m ≠ 0 ∣ g ^ ( m ) ∣ = ∑ m ≠ 0 1 ρ ( m ) s ρ ( m ) s ∣ g ^ ( m ) ∣ ≤ ( ∑ m ≠ 0 1 ρ ( m ) 2 s ) 1 2 ( ∑ m ρ ( m ) 2 s ∣ g ^ ( m ) ∣ 2 ) 1 2 . \sum_{m\ne0}|\widehat{g}(m)|=\sum_{m\ne0}\frac{1}{\rho(m)^s}\rho(m)^s|\widehat{g}(m)|\le\left(\sum_{m\ne0}\frac{1}{\rho(m)^{2s}}\right)^{\frac12}\left(\sum_m\rho(m)^{2s}|\widehat{g}(m)|^2\right)^{\frac12}. m = 0 ∑ ∣ g ( m ) ∣ = m = 0 ∑ ρ ( m ) s 1 ρ ( m ) s ∣ g ( m ) ∣ ≤ m = 0 ∑ ρ ( m ) 2 s 1 2 1 ( m ∑ ρ ( m ) 2 s ∣ g ( m ) ∣ 2 ) 2 1 .
Adding ∣ g ^ ( 0 ) ∣ |\widehat{g}(0)| ∣ g ( 0 ) ∣ and dividing by ∥ g ^ ∥ 2 = ∥ g ∥ 2 \|\widehat{g}\|_2=\|g\|_2 ∥ g ∥ 2 = ∥ g ∥ 2 we arrive at the first assertion.
It remains to estimate the first factor. Represent an element k ∈ Z N k\in\mathbb{Z}_N k ∈ Z N by an integer in { 0 , … , N − 1 } \{0,\ldots,N-1\} { 0 , … , N − 1 } and write ∣ k ∣ ∗ = min { k , N − k } |k|_*=\min\{k,N-k\} ∣ k ∣ ∗ = min { k , N − k } . Since sin u ≥ 2 u π \sin u\ge\frac{2u}{\pi} sin u ≥ π 2 u for 0 ≤ u ≤ π 2 0\le u\le\frac{\pi}{2} 0 ≤ u ≤ 2 π , we have
∣ e 2 π i k N − 1 ∣ = 2 sin ( π ∣ k ∣ ∗ N ) ≥ 4 ∣ k ∣ ∗ N , \left|e^{\frac{2\pi i k}{N}}-1\right|=2\sin\left(\frac{\pi|k|_*}{N}\right)\ge\frac{4|k|_*}{N}, e N 2 π ik − 1 = 2 sin ( N π ∣ k ∣ ∗ ) ≥ N 4∣ k ∣ ∗ ,
and it follows that
ρ ( m ) 2 ≥ 16 N 2 ∑ j = 1 d ∣ m j ∣ ∗ 2 . \rho(m)^2\ge\frac{16}{N^2}\sum_{j=1}^{d}|m_j|_*^2. ρ ( m ) 2 ≥ N 2 16 j = 1 ∑ d ∣ m j ∣ ∗ 2 .
We group the nonzero frequencies according to the value of r = max 1 ≤ j ≤ d ∣ m j ∣ ∗ r=\max_{1\le j\le d}|m_j|_* r = max 1 ≤ j ≤ d ∣ m j ∣ ∗ . The number of frequencies on the shell indexed by r r r is at most ( 2 r + 1 ) d − ( 2 r − 1 ) d ≤ C d r d − 1 (2r+1)^d-(2r-1)^d\le C_dr^{d-1} ( 2 r + 1 ) d − ( 2 r − 1 ) d ≤ C d r d − 1 , and every frequency on that shell satisfies ∑ j = 1 d ∣ m j ∣ ∗ 2 ≥ r 2 \sum_{j=1}^d|m_j|_*^2\ge r^2 ∑ j = 1 d ∣ m j ∣ ∗ 2 ≥ r 2 . Consequently,
∑ m ≠ 0 1 ρ ( m ) 2 s ≤ C d , s N 2 s ∑ r = 1 ⌊ N / 2 ⌋ r d − 1 − 2 s . \sum_{m\ne0}\frac{1}{\rho(m)^{2s}}\le C_{d,s}N^{2s}\sum_{r=1}^{\lfloor N/2\rfloor}r^{d-1-2s}. m = 0 ∑ ρ ( m ) 2 s 1 ≤ C d , s N 2 s r = 1 ∑ ⌊ N /2 ⌋ r d − 1 − 2 s .
The sum on the right is bounded independently of N N N when 2 s > d 2s>d 2 s > d , by C ( 1 + log N ) C(1+\log N) C ( 1 + log N ) when 2 s = d 2s=d 2 s = d , and by C d , s N d − 2 s C_{d,s}N^{d-2s} C d , s N d − 2 s when 2 s < d 2s<d 2 s < d , and the three cases follow upon taking square roots. When d = 2 d=2 d = 2 and s = 1 s=1 s = 1 , the shell indexed by r r r has at most 8 r 8r 8 r points, and the same calculation shows that
∑ m ≠ 0 1 ρ ( m ) 2 ≤ N 2 16 ∑ r = 1 ⌊ N / 2 ⌋ 8 r r 2 ≤ N 2 2 ( 1 + log N ) , \sum_{m\ne0}\frac{1}{\rho(m)^2}\le\frac{N^2}{16}\sum_{r=1}^{\lfloor N/2\rfloor}\frac{8r}{r^2}\le\frac{N^2}{2}(1+\log N), m = 0 ∑ ρ ( m ) 2 1 ≤ 16 N 2 r = 1 ∑ ⌊ N /2 ⌋ r 2 8 r ≤ 2 N 2 ( 1 + log N ) ,
as claimed. □
The three regimes have a simple interpretation. When a smooth function is sampled, a discrete derivative of order s s s contributes a factor of approximately 1 N s \frac{1}{N^{s}} N s 1 . Once this scaling is taken into account, the Fourier ratio is bounded independently of N N N above the critical index, grows like log N \sqrt{\log N} log N at the critical index, and grows like N 1 2 − s N^{\frac{1}{2}-s} N 2 1 − s below it. In Section 3 we push the argument below one derivative using Hölder increments and the fractional Sobolev–Morrey embedding. The endpoint γ = 1 \gamma=1 γ = 1 is the critical case in two dimensions, and it already contains the C 1 C^{1} C 1 functions.
Bounded orthonormal system recovery
We now state the standard recovery result that we shall use. Let a = ( a 1 , … , a D ) ∈ C D a=(a_{1},\ldots,a_{D})\in\mathbb{C}^{D} a = ( a 1 , … , a D ) ∈ C D . Given an integer s ≥ 1 s\geq1 s ≥ 1 , a vector is called s s s -sparse if at most s s s of its coordinates are nonzero, and for 1 ≤ s ≤ D 1\leq s\leq D 1 ≤ s ≤ D the best s s s -term approximation error of a a a in ℓ 1 \ell^{1} ℓ 1 is
σ s ( a ) 1 = inf { ∥ a − b ∥ 1 : b has at most s nonzero coordinates } . \sigma_{s}(a)_{1}=\inf\{\lVert a-b\rVert_{1}:b\text{ has at most }s\text{ nonzero coordinates}\}. σ s ( a ) 1 = inf {∥ a − b ∥ 1 : b has at most s nonzero coordinates } .
A minimizer is obtained by retaining the s s s largest coordinates of a a a in absolute value, and the quantity σ s ( a ) 1 \sigma_{s}(a)_{1} σ s ( a ) 1 measures how close a a a is to being s s s -sparse.
Let μ \mu μ be a probability measure on a set Ω \Omega Ω , and suppose that ϕ 1 , … , ϕ D \phi_{1},\ldots,\phi_{D} ϕ 1 , … , ϕ D are orthonormal in L 2 ( Ω , μ ) L^{2}(\Omega,\mu) L 2 ( Ω , μ ) and satisfy ∥ ϕ j ∥ L ∞ ( Ω ) ≤ K \lVert\phi_{j}\rVert_{L^{\infty}(\Omega)}\leq K ∥ ϕ j ∥ L ∞ ( Ω ) ≤ K , where K ≥ 1 K\geq1 K ≥ 1 necessarily by orthonormality. Choose x 1 , … , x q x_{1},\ldots,x_{q} x 1 , … , x q independently according to μ \mu μ and form the sampling matrix
A i j = 1 q ϕ j ( x i ) , A_{ij}=\frac{1}{\sqrt{q}}\phi_{j}(x_{i}), A ij = q 1 ϕ j ( x i ) ,
where the factor 1 q \frac{1}{\sqrt{q}} q 1 makes the expected squared norm of A a Aa A a equal to ∥ a ∥ 2 2 \lVert a\rVert_{2}^{2} ∥ a ∥ 2 2 . The matrix A A A is said to have the restricted isometry property of order s s s with constant δ \delta δ if 0 < δ < 1 0<\delta<1 0 < δ < 1 and
( 1 − δ ) ∥ a ∥ 2 2 ≤ ∥ A a ∥ 2 2 ≤ ( 1 + δ ) ∥ a ∥ 2 2 (1-\delta)\lVert a\rVert_{2}^{2}\leq\lVert Aa\rVert_{2}^{2}\leq(1+\delta)\lVert a\rVert_{2}^{2} ( 1 − δ ) ∥ a ∥ 2 2 ≤ ∥ A a ∥ 2 2 ≤ ( 1 + δ ) ∥ a ∥ 2 2
for every s s s -sparse vector a a a . In other words, A A A acts almost like an isometry on every coordinate subspace of dimension at most s s s .
Proposition 2.2 (Bounded orthonormal system recovery). Let ϕ 1 , … , ϕ D \phi_{1},\ldots,\phi_{D} ϕ 1 , … , ϕ D and A A A be as above. Fix 1 ≤ s ≤ D 1\leq s\leq D 1 ≤ s ≤ D and γ ≥ 1 \gamma\geq1 γ ≥ 1 . There is a constant C γ C_{\gamma} C γ such that, if
q ≥ C γ K 2 s log 2 ( 2 s K 2 ) log ( 2 D ) , q\geq C_{\gamma}K^{2}s\log^{2}(2sK^{2})\log(2D), q ≥ C γ K 2 s log 2 ( 2 s K 2 ) log ( 2 D ) , then, with probability at least 1 − 1 D γ 1-\frac{1}{D^{\gamma}} 1 − D γ 1 , the following holds simultaneously for all coefficient vectors a a a and all noise vectors e e e . If η ≥ 0 \eta\geq0 η ≥ 0 , y = A a + e y=Aa+e y = A a + e with ∥ e ∥ 2 ≤ η \lVert e\rVert_{2}\leq\eta ∥ e ∥ 2 ≤ η , and a ∗ a^{*} a ∗ minimizes ∥ b ∥ 1 \lVert b\rVert_{1} ∥ b ∥ 1 subject to ∥ A b − y ∥ 2 ≤ η \lVert Ab-y\rVert_{2}\leq\eta ∥ A b − y ∥ 2 ≤ η , then
∥ a ∗ − a ∥ 2 ≤ 3 σ s ( a ) 1 s + 5 η . \lVert a^{*}-a\rVert_{2}\leq3\frac{\sigma_{s}(a)_{1}}{\sqrt{s}}+5\eta. ∥ a ∗ − a ∥ 2 ≤ 3 s σ s ( a ) 1 + 5 η .
Proof. Let k = min { 2 s , D } k=\min\{2s,D\} k = min { 2 s , D } and δ = 1 16 \delta=\frac{1}{16} δ = 16 1 . By Theorem 2.3 of Brugiapaglia, Dirksen, Jung, and Rauhut [3 ] , applied to the orthonormal system above, the matrix A A A has the restricted isometry property of order k k k with constant δ \delta δ provided that
q ≥ C K 2 k log 2 ( 2 k K 2 ) log ( 2 D ) , q\geq CK^{2}k\log^{2}(2kK^{2})\log(2D), q ≥ C K 2 k log 2 ( 2 k K 2 ) log ( 2 D ) ,
with failure probability at most
2 exp ( − c q K 2 k ) , 2\exp\left(-\frac{cq}{K^{2}k}\right), 2 exp ( − K 2 k c q ) ,
where C C C and c > 0 c>0 c > 0 are absolute constants because δ \delta δ is fixed. Since k ≤ 2 s k\leq2s k ≤ 2 s and K ≥ 1 K\geq1 K ≥ 1 , the hypothesis of the proposition implies both this bound on the sample size and the required failure probability after increasing C γ C_{\gamma} C γ .
We include the recovery argument in order to keep track of the constants. We work on the restricted isometry event and write h = a ∗ − a h = a^* - a h = a ∗ − a . Both a a a and a ∗ a^* a ∗ satisfy the measurement constraint, so ∥ A h ∥ 2 ≤ 2 η \lVert Ah\rVert_2 \le2\eta ∥ A h ∥ 2 ≤ 2 η . If 2 s > D 2s > D 2 s > D , restricted isometry holds on all of C D \mathbb{C}^D C D , hence
∥ h ∥ 2 ≤ 2 η 1 − δ ≤ 3 η . \lVert h\rVert_2 \le\frac{2\eta}{\sqrt{1-\delta}} \le3\eta. ∥ h ∥ 2 ≤ 1 − δ 2 η ≤ 3 η .
and this includes the case s = D s = D s = D .
Suppose now that 2 s ≤ D 2s \le D 2 s ≤ D , and let S S S index the s s s largest coordinates of a a a in absolute value. For a subset E E E of the coordinate index set we denote by h E h_E h E the vector equal to h h h on E E E and zero elsewhere, and by E c E^c E c the complement of E E E . The minimizing property of a ∗ a^* a ∗ and the triangle inequality imply that
∥ h S c ∥ 1 ≤ ∥ h S ∥ 1 + 2 σ s ( a ) 1 . \lVert h_{S^c}\rVert_1 \le\lVert h_S\rVert_1 + 2\sigma_s(a)_1. ∥ h S c ∥ 1 ≤ ∥ h S ∥ 1 + 2 σ s ( a ) 1 .
Partition S c S^c S c into sets S 1 , S 2 , … S_1, S_2, \ldots S 1 , S 2 , … of size s s s , except possibly the last, in decreasing order of ∣ h j ∣ \lvert h_j\rvert ∣ h j ∣ . Every coordinate on S j S_j S j is at most 1 s ∥ h S j − 1 ∥ 1 \frac{1}{s}\lVert h_{S_{j-1}}\rVert_1 s 1 ∥ h S j − 1 ∥ 1 when j ≥ 2 j \ge2 j ≥ 2 , and therefore
∑ j ≥ 2 ∥ h S j ∥ 2 ≤ ∥ h S c ∥ 1 s ≤ ∥ h S ∥ 2 + 2 σ s ( a ) 1 s . \sum_{j\ge2}\lVert h_{S_j}\rVert_2 \le\frac{\lVert h_{S^c}\rVert_1}{\sqrt{s}} \le\lVert h_S\rVert_2 + 2\frac{\sigma_s(a)_1}{\sqrt{s}}. j ≥ 2 ∑ ∥ h S j ∥ 2 ≤ s ∥ h S c ∥ 1 ≤ ∥ h S ∥ 2 + 2 s σ s ( a ) 1 .
With T = S ∪ S 1 T = S \cup S_1 T = S ∪ S 1 , H = ∥ h T ∥ 2 H = \lVert h_T\rVert_2 H = ∥ h T ∥ 2 , and u = σ s ( a ) 1 s u = \frac{\sigma_s(a)_1}{\sqrt{s}} u = s σ s ( a ) 1 , this estimate implies that
∑ j ≥ 2 ∥ h S j ∥ 2 ≤ H + 2 u and ∥ h ∥ 2 ≤ 2 H + 2 u . \sum_{j\ge2}\lVert h_{S_j}\rVert_2 \le H + 2u \quad\text{and}\quad\lVert h\rVert_2 \le2H + 2u. j ≥ 2 ∑ ∥ h S j ∥ 2 ≤ H + 2 u and ∥ h ∥ 2 ≤ 2 H + 2 u .
If v v v and w w w are disjointly supported vectors, each with at most s s s nonzero coordinates, then by restricted isometry
∣ ⟨ A v , A w ⟩ ∣ ≤ δ ∥ v ∥ 2 ∥ w ∥ 2 , \lvert\langle Av,Aw\rangle\rvert\le\delta\lVert v\rVert_2\lVert w\rVert_2, ∣⟨ A v , A w ⟩∣ ≤ δ ∥ v ∥ 2 ∥ w ∥ 2 ,
because on the union of their supports the operator A ∗ A − I A^*A-I A ∗ A − I has norm at most δ \delta δ . Applying this estimate separately to h S h_S h S and h S 1 h_{S_1} h S 1 we obtain
∣ ⟨ A h T , A h S j ⟩ ∣ ≤ 2 δ H ∥ h S j ∥ 2 for j ≥ 2 , \lvert\langle Ah_T,Ah_{S_j}\rangle\rvert\le\sqrt{2\delta}H\lVert h_{S_j}\rVert_2 \quad\text{for } j\ge2, ∣⟨ A h T , A h S j ⟩∣ ≤ 2 δ H ∥ h S j ∥ 2 for j ≥ 2 ,
and since A h T = A h − ∑ j ≥ 2 A h S j Ah_T = Ah - \sum_{j\ge2}Ah_{S_j} A h T = A h − ∑ j ≥ 2 A h S j , it follows that
( 1 − δ ) H 2 ≤ 2 1 + δ η H + 2 δ H ∑ j ≥ 2 ∥ h S j ∥ 2 . (1-\delta)H^2 \le2\sqrt{1+\delta}\eta H + \sqrt{2\delta}H\sum_{j\ge2}\lVert h_{S_j}\rVert_2. ( 1 − δ ) H 2 ≤ 2 1 + δ η H + 2 δ H j ≥ 2 ∑ ∥ h S j ∥ 2 .
If H = 0 H = 0 H = 0 , the ordering of the blocks implies that h = 0 h = 0 h = 0 . Otherwise we divide by ( 1 − δ ) H (1-\delta)H ( 1 − δ ) H and use the tail bound. Writing
α = 2 1 + δ 1 − δ and β = 2 δ 1 − δ , \alpha= \frac{2\sqrt{1+\delta}}{1-\delta}
\quad\text{and}\quad
\beta= \frac{\sqrt{2\delta}}{1-\delta}, α = 1 − δ 2 1 + δ and β = 1 − δ 2 δ ,
we have H ≤ α η + β ( H + 2 u ) H \le\alpha\eta+ \beta(H+2u) H ≤ α η + β ( H + 2 u ) , and consequently
∥ h ∥ 2 ≤ 2 ( 1 + β ) 1 − β u + 2 α 1 − β η . \lVert h\rVert_2 \le\frac{2(1+\beta)}{1-\beta}u + \frac{2\alpha}{1-\beta}\eta. ∥ h ∥ 2 ≤ 1 − β 2 ( 1 + β ) u + 1 − β 2 α η .
When δ = 1 16 \delta= \frac{1}{16} δ = 16 1 we have β < 1 10 \beta< \frac{1}{10} β < 10 1 and α < 9 4 \alpha< \frac{9}{4} α < 4 9 , so the two coefficients on the right are less than 3 and 5, respectively, and the proof is complete. □
The sampling input in this proof is the bounded orthonormal system case of [3 Theorem 2.3] , and the recovery argument is the usual restricted isometry proof of stable ℓ 1 \ell^1 ℓ 1 reconstruction. See [9 Chapters 6 and 12] for further background.
Fourier ratio bounds on the periodic square
Throughout this section, functions on [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 are understood to extend periodically to R 2 \mathbb{R}^2 R 2 , and we use the norm
∥ f ∥ C 1 ( [ 0 , 1 ] 2 ) = max { ∥ f ∥ L ∞ , ∥ ∂ f ∂ x 1 ∥ L ∞ , ∥ ∂ f ∂ x 2 ∥ L ∞ } . \lVert f\rVert_{C^1([0,1]^2)}=\max\left\{\lVert f\rVert_{L^\infty},\left\lVert\frac{\partial f}{\partial x_1}\right\rVert_{L^\infty},\left\lVert\frac{\partial f}{\partial x_2}\right\rVert_{L^\infty}\right\}. ∥ f ∥ C 1 ([ 0 , 1 ] 2 ) = max { ∥ f ∥ L ∞ , ∂ x 1 ∂ f L ∞ , ∂ x 2 ∂ f L ∞ } .
For 0 < γ ≤ 1 0<\gamma\leq1 0 < γ ≤ 1 we also write
[ f ] C 0 , γ = sup u ≠ v ∣ f ( u ) − f ( v ) ∣ d T 2 ( u , v ) γ and ∥ f ∥ C 0 , γ = ∥ f ∥ L ∞ + [ f ] C 0 , γ . [f]_{C^{0,\gamma}}=\sup_{u\neq v}\frac{\lvert f(u)-f(v)\rvert}{d_{\mathbb{T}^2}(u,v)^\gamma}
\quad\text{and}\quad
\lVert f\rVert_{C^{0,\gamma}}=\lVert f\rVert_{L^\infty}+[f]_{C^{0,\gamma}}. [ f ] C 0 , γ = u = v sup d T 2 ( u , v ) γ ∣ f ( u ) − f ( v )∣ and ∥ f ∥ C 0 , γ = ∥ f ∥ L ∞ + [ f ] C 0 , γ .
where T 2 = R 2 / Z 2 \mathbb{T}^2=\mathbb{R}^2/\mathbb{Z}^2 T 2 = R 2 / Z 2 is the torus, identified with the periodic square, and d T 2 d_{\mathbb{T}^2} d T 2 is its distance. We begin with an estimate for Riemann sums.
Lemma 3.1 (Hölder quadrature estimate). Let 0 < γ ≤ 1 0<\gamma\leq1 0 < γ ≤ 1 and let h ∈ C 0 , γ ( [ 0 , 1 ] 2 ) h\in C^{0,\gamma}([0,1]^2) h ∈ C 0 , γ ([ 0 , 1 ] 2 ) be 1 1 1 -periodic in each variable. Then
∣ 1 N 2 ∑ x ∈ Z N 2 h ( x N ) − ∫ [ 0 , 1 ] 2 h ( u ) d u ∣ ≤ 2 γ / 2 N − γ [ h ] C 0 , γ . \left|\frac{1}{N^2}\sum_{x\in\mathbb{Z}_N^2}h\left(\frac{x}{N}\right)-\int_{[0,1]^2}h(u)\,\mathrm{d}u\right|\leq2^{\gamma/2}N^{-\gamma}[h]_{C^{0,\gamma}}. N 2 1 x ∈ Z N 2 ∑ h ( N x ) − ∫ [ 0 , 1 ] 2 h ( u ) d u ≤ 2 γ /2 N − γ [ h ] C 0 , γ .
Proof. For each x ∈ Z N 2 x\in\mathbb{Z}_N^2 x ∈ Z N 2 , let
Q x = x N + [ 0 , N − 1 ) 2 , Q_x=\frac{x}{N}+[0,N^{-1})^2, Q x = N x + [ 0 , N − 1 ) 2 ,
with addition understood periodically. These cells partition the torus, each of them has area N − 2 N^{-2} N − 2 , and every u ∈ Q x u\in Q_x u ∈ Q x satisfies d T 2 ( u , x / N ) ≤ 2 N d_{\mathbb{T}^2}(u,x/N)\leq\frac{\sqrt{2}}{N} d T 2 ( u , x / N ) ≤ N 2 . It follows that
∣ 1 N 2 ∑ x h ( x N ) − ∫ h ( u ) d u ∣ = ∣ ∑ x ∫ Q x ( h ( x N ) − h ( u ) ) d u ∣ ≤ ∑ x ∫ Q x [ h ] C 0 , γ d T 2 ( u , x N ) γ d u \begin{aligned}
\left|\frac{1}{N^2}\sum_x h\left(\frac{x}{N}\right)-\int h(u)\,\mathrm{d}u\right|
=\left|\sum_x\int_{Q_x}\left(h\left(\frac{x}{N}\right)-h(u)\right)\,\mathrm{d}u\right| \\
&\leq\sum_x\int_{Q_x}[h]_{C^{0,\gamma}}d_{\mathbb{T}^2}\left(u,\frac{x}{N}\right)^\gamma\,\mathrm{d}u
\end{aligned} N 2 1 x ∑ h ( N x ) − ∫ h ( u ) d u = x ∑ ∫ Q x ( h ( N x ) − h ( u ) ) d u ≤ x ∑ ∫ Q x [ h ] C 0 , γ d T 2 ( u , N x ) γ d u
≤ 2 γ / 2 N − γ [ h ] C 0 , γ , \leq2^{\gamma/2}N^{-\gamma}[h]_{C^{0,\gamma}}, ≤ 2 γ /2 N − γ [ h ] C 0 , γ ,
which is the desired estimate. □
Hölder and fractional Sobolev bounds
The next estimate describes what remains of the discrete energy argument below the C 1 C^1 C 1 threshold. A Hölder increment across one grid cell has size N − γ N^{-\gamma} N − γ rather than N − 1 N^{-1} N − 1 , and when 0 < γ < 1 0<\gamma<1 0 < γ < 1 it is useful to match the size of the increment to the frequencies being estimated, which removes the logarithmic factor from the bound in that range.
Proposition 3.2. Let N ≥ 2 N\geq2 N ≥ 2 and 0 < γ ≤ 1 0<\gamma\leq1 0 < γ ≤ 1 , let f f f be a nonzero function in C 0 , γ ( [ 0 , 1 ] 2 ) C^{0,\gamma}([0,1]^2) C 0 , γ ([ 0 , 1 ] 2 ) which is 1 1 1 -periodic in each variable, and define g ( x ) = f ( x N ) g(x)=f\left(\frac{x}{N}\right) g ( x ) = f ( N x ) for x ∈ Z N 2 x\in\mathbb{Z}_N^2 x ∈ Z N 2 . Write
A γ ( N ) = { N 1 − γ , 0 < γ < 1 , 1 + log N , γ = 1. A_\gamma(N)=
\begin{cases}
N^{1-\gamma}, & 0<\gamma<1,\\
\sqrt{1+\log N}, & \gamma=1.
\end{cases} A γ ( N ) = { N 1 − γ , 1 + log N , 0 < γ < 1 , γ = 1. There exist constants K γ , C γ > 0 K_\gamma,C_\gamma>0 K γ , C γ > 0 , depending only on γ \gamma γ , such that if
N γ ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) 2 ≥ K γ ∥ f ∥ C 0 , γ ( [ 0 , 1 ] 2 ) , N^\gamma\lVert f\rVert_{L^2([0,1]^2)}^2\geq K_\gamma\lVert f\rVert_{C^{0,\gamma}([0,1]^2)}, N γ ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) 2 ≥ K γ ∥ f ∥ C 0 , γ ([ 0 , 1 ] 2 ) , then
F R ( g ) ≤ 2 ∣ ∫ [ 0 , 1 ] 2 f ( u ) d u ∣ ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) + C γ ∥ f ∥ C 0 , γ ( [ 0 , 1 ] 2 ) ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) ( A γ ( N ) + N − γ ) . FR(g)\leq\sqrt{2}\frac{\left|\int_{[0,1]^2}f(u)\,\mathrm{d}u\right|}{\lVert f\rVert_{L^2([0,1]^2)}}
+C_\gamma\frac{\lVert f\rVert_{C^{0,\gamma}([0,1]^2)}}{\lVert f\rVert_{L^2([0,1]^2)}}\left(A_\gamma(N)+N^{-\gamma}\right). F R ( g ) ≤ 2 ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) ∫ [ 0 , 1 ] 2 f ( u ) d u + C γ ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) ∥ f ∥ C 0 , γ ([ 0 , 1 ] 2 ) ( A γ ( N ) + N − γ ) .
Proof. We apply Lemma 3.1 to h = ∣ f ∣ 2 h=|f|^2 h = ∣ f ∣ 2 . Since
∣ ∣ f ( u ) ∣ 2 − ∣ f ( v ) ∣ 2 ∣ ≤ ( ∣ f ( u ) ∣ + ∣ f ( v ) ∣ ) ∣ f ( u ) − f ( v ) ∣ , \bigl||f(u)|^2-|f(v)|^2\bigr|\leq\bigl(|f(u)|+|f(v)|\bigr)|f(u)-f(v)|, ∣ f ( u ) ∣ 2 − ∣ f ( v ) ∣ 2 ≤ ( ∣ f ( u ) ∣ + ∣ f ( v ) ∣ ) ∣ f ( u ) − f ( v ) ∣ ,
we have
[ ∣ f ∣ 2 ] C 0 , γ ≤ 2 ∥ f ∥ L ∞ [ f ] C 0 , γ ≤ 2 ∥ f ∥ C 0 , γ 2 , [|f|^2]_{C^{0,\gamma}}\leq2\|f\|_{L^\infty}[f]_{C^{0,\gamma}}\leq2\|f\|_{C^{0,\gamma}}^2, [ ∣ f ∣ 2 ] C 0 , γ ≤ 2∥ f ∥ L ∞ [ f ] C 0 , γ ≤ 2∥ f ∥ C 0 , γ 2 ,
and therefore
1 N 2 ∥ g ∥ ℓ 2 2 ≥ ∥ f ∥ L 2 2 − 2 1 + γ 2 N − γ ∥ f ∥ C 0 , γ 2 . \frac{1}{N^2}\|g\|_{\ell^2}^2\geq\|f\|_{L^2}^2-2^{1+\frac{\gamma}{2}}N^{-\gamma}\|f\|_{C^{0,\gamma}}^2. N 2 1 ∥ g ∥ ℓ 2 2 ≥ ∥ f ∥ L 2 2 − 2 1 + 2 γ N − γ ∥ f ∥ C 0 , γ 2 .
If K γ K_\gamma K γ is chosen sufficiently large, it follows that
∥ g ^ ∥ ℓ 2 = ∥ g ∥ ℓ 2 ≥ N 2 ∥ f ∥ L 2 . (1) \|\widehat{g}\|_{\ell^2}=\|g\|_{\ell^2}\geq\frac{N}{\sqrt{2}}\|f\|_{L^2}. \tag*{(1)} ∥ g ∥ ℓ 2 = ∥ g ∥ ℓ 2 ≥ 2 N ∥ f ∥ L 2 . (1)
At the zero frequency we have
g ^ ( 0 ) = N ( 1 N 2 ∑ x f ( x N ) ) , \widehat{g}(0)=N\left(\frac{1}{N^2}\sum_x f\left(\frac{x}{N}\right)\right), g ( 0 ) = N ( N 2 1 x ∑ f ( N x ) ) ,
and Lemma 3.1 implies that
∣ g ^ ( 0 ) ∣ ≤ N ∣ ∫ [ 0 , 1 ] 2 f ( u ) d u ∣ + 2 γ 2 N 1 − γ [ f ] C 0 , γ . |\widehat{g}(0)|\leq N\left|\int_{[0,1]^2}f(u)\,du\right|+2^{\frac{\gamma}{2}}N^{1-\gamma}[f]_{C^{0,\gamma}}. ∣ g ( 0 ) ∣ ≤ N ∫ [ 0 , 1 ] 2 f ( u ) d u + 2 2 γ N 1 − γ [ f ] C 0 , γ .
We now turn to the nonzero frequencies, and we first suppose that 0 < γ < 1 0<\gamma<1 0 < γ < 1 . Recall that ∣ m j ∣ ∗ = min { m j , N − m j } |m_j|_*=\min\{m_j,N-m_j\} ∣ m j ∣ ∗ = min { m j , N − m j } , where m j m_j m j is represented by an integer between 0 0 0 and N − 1 N-1 N − 1 , and put ∣ m ∣ ∞ = max { ∣ m 1 ∣ ∗ , ∣ m 2 ∣ ∗ } |m|_\infty=\max\{|m_1|_*,|m_2|_*\} ∣ m ∣ ∞ = max { ∣ m 1 ∣ ∗ , ∣ m 2 ∣ ∗ } . For a power of two R R R with 1 ≤ R ≤ N 2 1\leq R\leq\frac{N}{2} 1 ≤ R ≤ 2 N , let
A R = { m ∈ Z N 2 : R ≤ ∣ m ∣ ∞ < 2 R } A_R=\{m\in\mathbb{Z}_N^2:R\leq|m|_\infty<2R\} A R = { m ∈ Z N 2 : R ≤ ∣ m ∣ ∞ < 2 R }
and choose the integer
h R = max { 1 , ⌊ N 4 R ⌋ } . h_R=\max\left\{1,\left\lfloor\frac{N}{4R}\right\rfloor\right\}. h R = max { 1 , ⌊ 4 R N ⌋ } .
The sets A R A_R A R partition the nonzero frequencies, and each of them contains at most C R 2 CR^2 C R 2 points. The point of this choice of h R h_R h R is that the corresponding difference detects every frequency in A R A_R A R . Indeed, if m ∈ A R m\in A_R m ∈ A R , then ∣ m j ∣ ∗ ≥ R |m_j|_*\geq R ∣ m j ∣ ∗ ≥ R for at least one j j j , and for that coordinate
1 8 ≤ h R ∣ m j ∣ ∗ N ≤ 1 2 . \frac{1}{8}\leq\frac{h_R|m_j|_*}{N}\leq\frac{1}{2}. 8 1 ≤ N h R ∣ m j ∣ ∗ ≤ 2 1 .
To see the lower bound, observe that ⌊ N 4 R ⌋ ≥ N 8 R \left\lfloor\frac{N}{4R}\right\rfloor\geq\frac{N}{8R} ⌊ 4 R N ⌋ ≥ 8 R N when R ≤ N 4 R\leq\frac{N}{4} R ≤ 4 N , while h R = 1 h_R=1 h R = 1 when R > N 4 R>\frac{N}{4} R > 4 N , so the same lower bound holds. The upper bound follows from ∣ m j ∣ ∗ < 2 R |m_j|_*<2R ∣ m j ∣ ∗ < 2 R in the first case and from ∣ m j ∣ ∗ ≤ N 2 |m_j|_*\leq\frac{N}{2} ∣ m j ∣ ∗ ≤ 2 N in the second. Consequently,
∑ j = 1 2 ∣ e 2 π i h R m j N − 1 ∣ 2 ≥ 4 sin 2 ( π 8 ) for m ∈ A R , \sum_{j=1}^{2}\left|e^{\frac{2\pi i h_Rm_j}{N}}-1\right|^2\geq4\sin^2\left(\frac{\pi}{8}\right)\quad\text{for }m\in A_R, j = 1 ∑ 2 e N 2 π i h R m j − 1 2 ≥ 4 sin 2 ( 8 π ) for m ∈ A R ,
and Parseval’s identity implies that
∑ m ∈ A R ∣ g ^ ( m ) ∣ 2 ≤ C ∑ j = 1 2 ∥ g ( ⋅ + h R e j ) − g ∥ ℓ 2 2 . \sum_{m\in A_R}|\widehat{g}(m)|^2\leq C\sum_{j=1}^{2}\|g(\cdot+h_Re_j)-g\|_{\ell^2}^2. m ∈ A R ∑ ∣ g ( m ) ∣ 2 ≤ C j = 1 ∑ 2 ∥ g ( ⋅ + h R e j ) − g ∥ ℓ 2 2 .
By periodicity and Hölder continuity,
∥ g ( ⋅ + h R e j ) − g ∥ ℓ 2 ≤ N ( h R N ) γ [ f ] C 0 , γ ≤ N R − γ [ f ] C 0 , γ , \|g(\cdot+h_Re_j)-g\|_{\ell^2}\leq N\left(\frac{h_R}{N}\right)^\gamma[f]_{C^{0,\gamma}}\leq NR^{-\gamma}[f]_{C^{0,\gamma}}, ∥ g ( ⋅ + h R e j ) − g ∥ ℓ 2 ≤ N ( N h R ) γ [ f ] C 0 , γ ≤ N R − γ [ f ] C 0 , γ ,
where we used h R N ≤ 1 R \frac{h_R}{N} \le\frac{1}{R} N h R ≤ R 1 . It follows from Cauchy–Schwarz on A R \mathcal{A}_R A R that
∑ m ∈ A R ∣ g ^ ( m ) ∣ ≤ C N R 1 − γ [ f ] C 0 , γ , \sum_{m\in\mathcal{A}_R} |\widehat{g}(m)| \le CNR^{1-\gamma}[f]_{C^{0,\gamma}}, m ∈ A R ∑ ∣ g ( m ) ∣ ≤ C N R 1 − γ [ f ] C 0 , γ ,
and summing over the powers of two we conclude that
∑ m ≠ 0 ∣ g ^ ( m ) ∣ ≤ C γ N 2 − γ [ f ] C 0 , γ . \sum_{m\ne0} |\widehat{g}(m)| \le C_\gamma N^{2-\gamma}[f]_{C^{0,\gamma}}. m = 0 ∑ ∣ g ( m ) ∣ ≤ C γ N 2 − γ [ f ] C 0 , γ .
The constant depends on γ \gamma γ because the geometric sum has ratio 2 1 − γ 2^{1-\gamma} 2 1 − γ , and it need not remain bounded as γ \gamma γ approaches 1.
When γ = 1 \gamma=1 γ = 1 we use instead the nearest neighbor differences Δ j g ( x ) = g ( x + e j ) − g ( x ) \Delta_jg(x)=g(x+e_j)-g(x) Δ j g ( x ) = g ( x + e j ) − g ( x ) , j = 1 , 2 j=1,2 j = 1 , 2 , which satisfy ∥ Δ j g ∥ ℓ 2 ≤ [ f ] C 0 , 1 \|\Delta_jg\|_{\ell^2}\le[f]_{C^{0,1}} ∥ Δ j g ∥ ℓ 2 ≤ [ f ] C 0 , 1 . By Proposition 2.1,
∑ m ≠ 0 ∣ g ^ ( m ) ∣ ≤ ( ∑ m ≠ 0 1 ρ ( m ) 2 ) 1 2 ( ∥ Δ 1 g ∥ 2 2 + ∥ Δ 2 g ∥ 2 2 ) 1 2 ≤ C N 1 + log N [ f ] C 0 , 1 . \begin{aligned}
\sum_{m\ne0}|\widehat{g}(m)|\le\left(\sum_{m\ne0}\frac{1}{\rho(m)^2}\right)^{\frac12}\left(\|\Delta_1g\|_2^2+\|\Delta_2g\|_2^2\right)^{\frac12} \\
&\le CN\sqrt{1+\log N}[f]_{C^{0,1}}.
\end{aligned} m = 0 ∑ ∣ g ( m ) ∣ ≤ m = 0 ∑ ρ ( m ) 2 1 2 1 ( ∥ Δ 1 g ∥ 2 2 + ∥ Δ 2 g ∥ 2 2 ) 2 1 ≤ C N 1 + log N [ f ] C 0 , 1 .
In both cases the proposition follows by adding the zero frequency and dividing by the lower bound in (1) .
For 0 < s < 1 0<s<1 0 < s < 1 and 1 < p < ∞ 1<p<\infty 1 < p < ∞ we use the periodic Sobolev–Slobodeckij norm
∥ f ∥ W s , p p = ∥ f ∥ L p p + ∫ [ 0 , 1 ] 2 ∫ [ 0 , 1 ] 2 ∣ f ( u ) − f ( v ) ∣ p d T 2 ( u , v ) 2 + s p d u d v , \|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, ∥ f ∥ W s , p p = ∥ f ∥ L p p + ∫ [ 0 , 1 ] 2 ∫ [ 0 , 1 ] 2 d T 2 ( u , v ) 2 + s p ∣ f ( u ) − f ( v ) ∣ p d u d v ,
and we write [ f ] W s , p [f]_{W^{s,p}} [ f ] W s , p for the periodic seminorm, the p p p -th root of the double integral above, so that [ f ] W s , p ≤ ∥ f ∥ W s , p [f]_{W^{s,p}}\le\|f\|_{W^{s,p}} [ f ] W s , p ≤ ∥ f ∥ W s , p . The fractional Morrey inequality says that if s p > 2 sp>2 s p > 2 and α = s − 2 p \alpha=s-\frac{2}{p} α = s − p 2 , then
∥ f ∥ C 0 , α ( [ 0 , 1 ] 2 ) ≤ M s , p ∥ f ∥ W s , p ( [ 0 , 1 ] 2 ) . \|f\|_{C^{0,\alpha}([0,1]^2)}\le M_{s,p}\|f\|_{W^{s,p}([0,1]^2)}. ∥ f ∥ C 0 , α ([ 0 , 1 ] 2 ) ≤ M s , p ∥ f ∥ W s , p ([ 0 , 1 ] 2 ) .
See, for example, [1 ] . We shall also need a local version of this inequality, and for a ball E ⊂ R 2 E\subset\mathbb{R}^2 E ⊂ R 2 we write
[ f ] W s , p ( E ) = ( ∫ E ∫ E ∣ f ( u ) − f ( v ) ∣ p ∣ u − v ∣ 2 + s p d u d v ) 1 p . [f]_{W^{s,p}(E)}=\left(\int_E\int_E\frac{|f(u)-f(v)|^p}{|u-v|^{2+sp}}\,du\,dv\right)^{\frac1p}. [ f ] W s , p ( E ) = ( ∫ E ∫ E ∣ u − v ∣ 2 + s p ∣ f ( u ) − f ( v ) ∣ p d u d v ) p 1 .
Lemma 3.3 (Local fractional Morrey inequality). Let 0 < s < 1 0<s<1 0 < s < 1 , 1 < p < ∞ 1<p<\infty 1 < p < ∞ , s p > 2 sp>2 s p > 2 , and put α = s − 2 p \alpha=s-\frac{2}{p} α = s − p 2 . There is a constant M s , p ′ M'_{s,p} M s , p ′ such that, for every closed ball B ⊂ R 2 B\subset\mathbb{R}^2 B ⊂ R 2 of radius r > 0 r>0 r > 0 and every continuous f f f on B B B with [ f ] W s , p ( B ) < ∞ [f]_{W^{s,p}(B)}<\infty [ f ] W s , p ( B ) < ∞ ,
∣ f ( u ) − f ( v ) ∣ ≤ M s , p ′ r α [ f ] W s , p ( B ) for all u , v ∈ B . (2) |f(u)-f(v)|\le M'_{s,p}r^\alpha[f]_{W^{s,p}(B)}\quad\text{for all }u,v\in B. \tag*{(2)} ∣ f ( u ) − f ( v ) ∣ ≤ M s , p ′ r α [ f ] W s , p ( B ) for all u , v ∈ B . (2)
Proof. We first take B = B 1 B=B_1 B = B 1 to be the closed unit ball centered at the origin, and we let f B 1 f_{B_1} f B 1 denote the mean of f f f over B 1 B_1 B 1 . By Jensen’s inequality and the fact that ∣ u − v ∣ ≤ 2 |u-v|\le2 ∣ u − v ∣ ≤ 2 ,
∥ f − f B 1 ∥ L p ( B 1 ) p ≤ 1 ∣ B 1 ∣ ∫ B 1 ∫ B 1 ∣ f ( u ) − f ( v ) ∣ p d v d u ≤ 2 2 + s p π [ f ] W s , p ( B 1 ) p . \begin{aligned}
\|f-f_{B_1}\|_{L^p(B_1)}^p\le\frac{1}{|B_1|}\int_{B_1}\int_{B_1}|f(u)-f(v)|^p\,dv\,du \\
&\le\frac{2^{2+sp}}{\pi}[f]_{W^{s,p}(B_1)}^p.
\end{aligned} ∥ f − f B 1 ∥ L p ( B 1 ) p ≤ ∣ B 1 ∣ 1 ∫ B 1 ∫ B 1 ∣ f ( u ) − f ( v ) ∣ p d v d u ≤ π 2 2 + s p [ f ] W s , p ( B 1 ) p .
The fractional Morrey inequality on the unit ball [8, Theorem 8.2], applied to f − f B 1 f-f_{B_1} f − f B 1 , then shows that for u , v ∈ B 1 u,v\in B_1 u , v ∈ B 1
∣ f ( u ) − f ( v ) ∣ ≤ C s , p ( ∥ f − f B 1 ∥ L p ( B 1 ) + [ f ] W s , p ( B 1 ) ) ∣ u − v ∣ α ≤ C s , p ′ [ f ] W s , p ( B 1 ) . \begin{aligned}
|f(u)-f(v)|\le C_{s,p}\left(\|f-f_{B_1}\|_{L^p(B_1)}+[f]_{W^{s,p}(B_1)}\right)|u-v|^\alpha\\
&\le C'_{s,p}[f]_{W^{s,p}(B_1)}.
\end{aligned} ∣ f ( u ) − f ( v ) ∣ ≤ C s , p ( ∥ f − f B 1 ∥ L p ( B 1 ) + [ f ] W s , p ( B 1 ) ) ∣ u − v ∣ α ≤ C s , p ′ [ f ] W s , p ( B 1 ) .
For a ball B B B with center c c c and radius r r r , put f r ( z ) = f ( c + r z ) f_r(z)=f(c+rz) f r ( z ) = f ( c + r z ) . The substitution u = c + r z u=c+rz u = c + r z and v = c + r w v=c+rw v = c + r w shows that
[ f r ] W s , p ( B 1 ) p = r s p − 2 [ f ] W s , p ( B ) p = r α p [ f ] W s , p ( B ) p [f_r]_{W^{s,p}(B_1)}^p=r^{sp-2}[f]_{W^{s,p}(B)}^p=r^{\alpha p}[f]_{W^{s,p}(B)}^p [ f r ] W s , p ( B 1 ) p = r s p − 2 [ f ] W s , p ( B ) p = r α p [ f ] W s , p ( B ) p
and the estimate (2) follows from the case of the unit ball applied to f r f_r f r .
Lemma 3.4 (Sobolev differences on the grid). Let 0 < s < 1 0<s<1 0 < s < 1 , 1 < p < ∞ 1<p<\infty 1 < p < ∞ , and s p > 2 sp>2 s p > 2 . Let f f f be continuous and 1 1 1 -periodic with [ f ] W s , p < ∞ [f]_{W^{s,p}}<\infty [ f ] W s , p < ∞ , and define g ( x ) = f ( x N ) g(x)=f\left(\frac{x}{N}\right) g ( x ) = f ( N x ) for x ∈ Z N 2 x\in\mathbb{Z}_N^2 x ∈ Z N 2 . For every integer 1 ≤ h ≤ N 4 1\le h\le\frac{N}{4} 1 ≤ h ≤ 4 N and j ∈ { 1 , 2 } j\in\{1,2\} j ∈ { 1 , 2 } ,
∥ g ( ⋅ + h e j ) − g ∥ ℓ 2 ≤ 9 1 p M s , p ′ N ( h N ) s [ f ] W s , p . \left\|g(\cdot+he_j)-g\right\|_{\ell^2}\le9^{\frac{1}{p}}M'_{s,p}N\left(\frac{h}{N}\right)^s[f]_{W^{s,p}}. ∥ g ( ⋅ + h e j ) − g ∥ ℓ 2 ≤ 9 p 1 M s , p ′ N ( N h ) s [ f ] W s , p . Proof. Since s < 1 s<1 s < 1 and s p > 2 sp>2 s p > 2 , we have p > 2 p>2 p > 2 . Represent x ∈ Z N 2 x\in\mathbb{Z}_N^2 x ∈ Z N 2 by a point of { 0 , … , N − 1 } 2 \{0,\ldots,N-1\}^2 { 0 , … , N − 1 } 2 , and let B x ⊂ R 2 B_x\subset\mathbb{R}^2 B x ⊂ R 2 be the closed ball of radius h N \frac{h}{N} N h centered at x N + h 2 N e j \frac{x}{N}+\frac{h}{2N}e_j N x + 2 N h e j . This ball contains x N \frac{x}{N} N x and x + h e j N \frac{x+he_j}{N} N x + h e j , and its diameter is 2 h N ≤ 1 2 \frac{2h}{N}\le\frac12 N 2 h ≤ 2 1 , so the quotient map R 2 → T 2 \mathbb{R}^2\to\mathbb{T}^2 R 2 → T 2 is injective on B x B_x B x and ∣ u − v ∣ = d T 2 ( u , v ) |u-v|=d_{\mathbb{T}^2}(u,v) ∣ u − v ∣ = d T 2 ( u , v ) for u , v ∈ B x u,v\in B_x u , v ∈ B x . Applying Lemma 3.3 to the periodic extension of f f f on B x B_x B x we obtain
∣ g ( x + h e j ) − g ( x ) ∣ ≤ M s , p ′ ( h N ) α [ f ] W s , p ( B x ) , |g(x+he_j)-g(x)|\le M'_{s,p}\left(\frac{h}{N}\right)^\alpha[f]_{W^{s,p}(B_x)}, ∣ g ( x + h e j ) − g ( x ) ∣ ≤ M s , p ′ ( N h ) α [ f ] W s , p ( B x ) , where α = s − 2 p \alpha=s-\frac{2}{p} α = s − p 2 as before.
A point u ∈ T 2 u\in\mathbb{T}^2 u ∈ T 2 lies in the image of B x B_x B x only if x x x lies within distance h h h of N u − h 2 e j Nu-\frac{h}{2}e_j N u − 2 h e j in R 2 / N Z 2 \mathbb{R}^2/N\mathbb{Z}^2 R 2 / N Z 2 , and a disc of radius h h h contains at most ( 2 h + 1 ) 2 ≤ 9 h 2 (2h+1)^2\le9h^2 ( 2 h + 1 ) 2 ≤ 9 h 2 integer points. Consequently every pair ( u , v ) ∈ T 2 × T 2 (u,v)\in\mathbb{T}^2\times\mathbb{T}^2 ( u , v ) ∈ T 2 × T 2 is counted for at most 9 h 2 9h^2 9 h 2 indices x x x , and
∑ x ∈ Z N 2 [ f ] W s , p ( B x ) p ≤ 9 h 2 [ f ] W s , p p . \sum_{x\in\mathbb{Z}_N^2}[f]^p_{W^{s,p}(B_x)}\le9h^2[f]^p_{W^{s,p}}. x ∈ Z N 2 ∑ [ f ] W s , p ( B x ) p ≤ 9 h 2 [ f ] W s , p p . Since α p = s p − 2 \alpha p=sp-2 α p = s p − 2 , this implies that
∑ x ∈ Z N 2 ∣ g ( x + h e j ) − g ( x ) ∣ p ≤ 9 ( M s , p ′ ) p h s p N 2 − s p [ f ] W s , p p . \sum_{x\in\mathbb{Z}_N^2}|g(x+he_j)-g(x)|^p\le9(M'_{s,p})^ph^{sp}N^{2-sp}[f]^p_{W^{s,p}}. x ∈ Z N 2 ∑ ∣ g ( x + h e j ) − g ( x ) ∣ p ≤ 9 ( M s , p ′ ) p h s p N 2 − s p [ f ] W s , p p . By Hölder’s inequality on the N 2 N^2 N 2 grid points, ∥ v ∥ ℓ 2 ≤ N 1 − 2 p ∥ v ∥ ℓ p \|v\|_{\ell^2}\le N^{1-\frac{2}{p}}\|v\|_{\ell^p} ∥ v ∥ ℓ 2 ≤ N 1 − p 2 ∥ v ∥ ℓ p , and therefore
∥ g ( ⋅ + h e j ) − g ∥ ℓ 2 ≤ N 1 − 2 p ⋅ 9 1 p M s , p ′ h s N 2 p − s [ f ] W s , p \|g(\cdot+he_j)-g\|_{\ell^2}\le N^{1-\frac{2}{p}}\cdot9^{\frac{1}{p}}M'_{s,p}h^sN^{\frac{2}{p}-s}[f]_{W^{s,p}} ∥ g ( ⋅ + h e j ) − g ∥ ℓ 2 ≤ N 1 − p 2 ⋅ 9 p 1 M s , p ′ h s N p 2 − s [ f ] W s , p = 9 1 p M s , p ′ N ( h N ) s [ f ] W s , p , =9^{\frac{1}{p}}M'_{s,p}N\left(\frac{h}{N}\right)^s[f]_{W^{s,p}}, = 9 p 1 M s , p ′ N ( N h ) s [ f ] W s , p , which completes the proof.
Theorem 3.5. Let 0 < s < 1 0<s<1 0 < s < 1 , 1 < p < ∞ 1<p<\infty 1 < p < ∞ , and s p > 2 sp>2 s p > 2 , and set α = s − 2 p > 0 \alpha=s-\frac{2}{p}>0 α = s − p 2 > 0 . Let f ∈ W s , p ( [ 0 , 1 ] 2 ) f\in W^{s,p}([0,1]^2) f ∈ W s , p ([ 0 , 1 ] 2 ) be nonzero and 1 1 1 -periodic, using its continuous representative, and define g ( x ) = f ( x N ) g(x)=f\left(\frac{x}{N}\right) g ( x ) = f ( N x ) . There exist constants K s , p , C s , p > 0 K_{s,p},C_{s,p}>0 K s , p , C s , p > 0 such that if
N α ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) 2 > K s , p ∥ f ∥ W s , p ( [ 0 , 1 ] 2 ) 2 , (3) N^\alpha\|f\|_{L^2([0,1]^2)}^2>K_{s,p}\|f\|_{W^{s,p}([0,1]^2)}^2, \tag*{(3)} N α ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) 2 > K s , p ∥ f ∥ W s , p ([ 0 , 1 ] 2 ) 2 , (3) then
F R ( g ) ≤ 2 ∣ ∫ [ 0 , 1 ] 2 f ( u ) d u ∣ ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) + C s , p ∥ f ∥ W s , p ( [ 0 , 1 ] 2 ) ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) N 1 − s . (4) FR(g)\le\sqrt{2}\frac{\left|\int_{[0,1]^2}f(u)\,du\right|}{\|f\|_{L^2([0,1]^2)}}+C_{s,p}\frac{\|f\|_{W^{s,p}([0,1]^2)}}{\|f\|_{L^2([0,1]^2)}}N^{1-s}. \tag*{(4)} F R ( g ) ≤ 2 ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) ∫ [ 0 , 1 ] 2 f ( u ) d u + C s , p ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) ∥ f ∥ W s , p ([ 0 , 1 ] 2 ) N 1 − s . (4) Proof. Since p > 2 p>2 p > 2 and [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 has measure one, ∥ f ∥ L 2 ≤ ∥ f ∥ L p ≤ ∥ f ∥ W s , p \|f\|_{L^2}\le\|f\|_{L^p}\le\|f\|_{W^{s,p}} ∥ f ∥ L 2 ≤ ∥ f ∥ L p ≤ ∥ f ∥ W s , p . Let K α K_\alpha K α be the constant of Proposition 3.2 for γ = α \gamma=\alpha γ = α , let M s , p M_{s,p} M s , p be the constant in the global fractional Morrey inequality above, and choose K s , p ≥ max { 4 , K α M s , p 2 } K_{s,p}\ge\max\{4,K_\alpha M_{s,p}^2\} K s , p ≥ max { 4 , K α M s , p 2 } . Then the condition (3) implies that N α ≥ K s , p ≥ 4 N^\alpha\ge K_{s,p}\ge4 N α ≥ K s , p ≥ 4 , hence N ≥ 4 N\ge4 N ≥ 4 because α < 1 \alpha<1 α < 1 . The global Morrey inequality and the condition (3) also imply the
size condition of Proposition 3.2 for γ = α \gamma=\alpha γ = α , so the first part of the proof of that proposition shows that
∥ g ^ ∥ ℓ 2 = ∥ g ∥ ℓ 2 ≥ N 2 ∥ f ∥ L 2 , ∣ g ^ ( 0 ) ∣ ≤ N ∣ ∫ [ 0 , 1 ] 2 f ( u ) d u ∣ + 2 1 2 M s , p N 1 − α ∥ f ∥ W s , p . (5) \begin{aligned}
\|\widehat{g}\|_{\ell^2}&=\|g\|_{\ell^2}\ge\frac{N}{\sqrt{2}}\|f\|_{L^2},\\
|\widehat{g}(0)|&\le N\left|\int_{[0,1]^2}f(u)\,du\right|+2^{\frac12}M_{s,p}N^{1-\alpha}\|f\|_{W^{s,p}}. \tag*{(5)}
\end{aligned} ∥ g ∥ ℓ 2 ∣ g ( 0 ) ∣ = ∥ g ∥ ℓ 2 ≥ 2 N ∥ f ∥ L 2 , ≤ N ∫ [ 0 , 1 ] 2 f ( u ) d u + 2 2 1 M s , p N 1 − α ∥ f ∥ W s , p . (5)
For the nonzero frequencies we follow the dyadic argument in the proof of Proposition 3.2, with A R A_R A R and h R h_R h R as defined there. Since N ≥ 4 N\ge4 N ≥ 4 , we have 1 ≤ h R ≤ N 4 1\le h_R\le\frac{N}{4} 1 ≤ h R ≤ 4 N , so Lemma 3.4 applies with h = h R h=h_R h = h R , and together with the lower bound for the Fourier multiplier from that proof and the inequality h R N ≤ 1 R \frac{h_R}{N}\le\frac{1}{R} N h R ≤ R 1 it shows that
∑ m ∈ A R ∣ g ^ ( m ) ∣ 2 ≤ C ∑ j = 1 2 ∥ g ( ⋅ + h R e j ) − g ∥ ℓ 2 2 ≤ C s , p N 2 R − 2 s [ f ] W s , p 2 . \sum_{m\in A_R}|\widehat{g}(m)|^2\le C\sum_{j=1}^{2}\|g(\cdot+h_Re_j)-g\|_{\ell^2}^2\le C_{s,p}N^2R^{-2s}[f]_{W^{s,p}}^2. m ∈ A R ∑ ∣ g ( m ) ∣ 2 ≤ C j = 1 ∑ 2 ∥ g ( ⋅ + h R e j ) − g ∥ ℓ 2 2 ≤ C s , p N 2 R − 2 s [ f ] W s , p 2 .
Since A R A_R A R has at most C R 2 CR^2 C R 2 points, it follows from Cauchy–Schwarz that
∑ m ∈ A R ∣ g ^ ( m ) ∣ ≤ C s , p N R 1 − s [ f ] W s , p . \sum_{m\in A_R}|\widehat{g}(m)|\le C_{s,p}NR^{1-s}[f]_{W^{s,p}}. m ∈ A R ∑ ∣ g ( m ) ∣ ≤ C s , p N R 1 − s [ f ] W s , p .
Summing over the powers of two R ≤ N 2 R\le\frac{N}{2} R ≤ 2 N , which is a geometric sum with ratio 2 1 − s > 1 2^{1-s}>1 2 1 − s > 1 , we obtain
∑ m ≠ 0 ∣ g ^ ( m ) ∣ ≤ C s , p 1 − 2 s − 1 N 2 − s [ f ] W s , p . \sum_{m\ne0}|\widehat{g}(m)|\le\frac{C_{s,p}}{1-2^{s-1}}N^{2-s}[f]_{W^{s,p}}. m = 0 ∑ ∣ g ( m ) ∣ ≤ 1 − 2 s − 1 C s , p N 2 − s [ f ] W s , p .
The estimate (3.4) now follows by adding the zero frequency from (3.5), dividing by the lower bound for ∥ g ^ ∥ ℓ 2 \|\widehat{g}\|_{\ell^2} ∥ g ∥ ℓ 2 , and using [ f ] W s , p ≤ ∥ f ∥ W s , p [f]_{W^{s,p}}\le\|f\|_{W^{s,p}} [ f ] W s , p ≤ ∥ f ∥ W s , p and N − α ≤ 1 ≤ N 1 − s N^{-\alpha}\le1\le N^{1-s} N − α ≤ 1 ≤ N 1 − s .
Proposition 3.2 applies in the same way to any Sobolev class of higher order which the Sobolev–Morrey embedding places in a Hölder class with a positive exponent. Theorem 3.5 deals with the fractional range, where the condition s p > 2 sp>2 s p > 2 guarantees a continuous representative and the local difference argument is available.
Remark 3.6. The trivial estimate on the group Z N 2 \mathbb{Z}_N^2 Z N 2 , which has N 2 N^2 N 2 points, is F R ( g ) ≤ N FR(g)\le N F R ( g ) ≤ N . Since N 1 − γ = o ( N ) N^{1-\gamma}=o(N) N 1 − γ = o ( N ) for every fixed 0 < γ < 1 0<\gamma<1 0 < γ < 1 , Proposition 3.2 improves on this estimate as soon as the function has any positive Hölder exponent, and Theorem 3.5 does so for every 0 < s < 1 0<s<1 0 < s < 1 in the range s p > 2 sp>2 s p > 2 . We shall see in Remark 3.7 that neither polynomial exponent can be lowered in estimates that are uniform over the corresponding regularity classes. At γ = 1 \gamma=1 γ = 1 the proposition yields the critical 1 + log N \sqrt{1+\log N} 1 + log N bound, which therefore holds for every C 1 C^1 C 1 function.
Remark 3.7. (Sharpness of the exponents). Let 0 < θ < 1 0<\theta<1 0 < θ < 1 , let N ≥ 3 N\ge3 N ≥ 3 be odd, and put
ψ ( x ) = cos ( 2 π ( x 1 2 + x 2 2 ) N ) for x ∈ Z N 2 . \psi(x)=\cos\left(\frac{2\pi(x_1^2+x_2^2)}{N}\right)\quad\text{for }x\in\mathbb{Z}_N^2. ψ ( x ) = cos ( N 2 π ( x 1 2 + x 2 2 ) ) for x ∈ Z N 2 .
Let H ( τ ) = max { 0 , 1 − ∣ τ ∣ } H(\tau)=\max\{0,1-|\tau|\} H ( τ ) = max { 0 , 1 − ∣ τ ∣ } , extend ψ \psi ψ N N N -periodically to Z 2 \mathbb{Z}^2 Z 2 , and let
Φ ( u ) = ∑ x ∈ Z 2 ψ ( x ) H ( N u 1 − x 1 ) H ( N u 2 − x 2 ) \Phi(u)=\sum_{x\in\mathbb{Z}^2}\psi(x)H(Nu_1-x_1)H(Nu_2-x_2) Φ ( u ) = x ∈ Z 2 ∑ ψ ( x ) H ( N u 1 − x 1 ) H ( N u 2 − x 2 )
and f N = 1 + N − θ Φ f_N=1+N^{-\theta}\Phi f N = 1 + N − θ Φ , so that Φ \Phi Φ is the bilinear interpolant of ψ \psi ψ and f N f_N f N is the corresponding perturbation of the constant function. Then f N f_N f N is real, 1 1 1 -periodic, and Lipschitz, and it satisfies ∥ f N ∥ C 0 , θ ≤ 5 \|f_N\|_{C^{0,\theta}}\le5 ∥ f N ∥ C 0 , θ ≤ 5 , ∥ f N ∥ W θ , p ≤ C θ , p \|f_N\|_{W^{\theta,p}}\le C_{\theta,p} ∥ f N ∥ W θ , p ≤ C θ , p for every 1 < p < ∞ 1<p<\infty 1 < p < ∞ , and 2 3 ≤ ∥ f N ∥ L 2 ≤ 2 \frac{2}{3}\le\|f_N\|_{L^2}\le2 3 2 ≤ ∥ f N ∥ L 2 ≤ 2 , while g N ( x ) = f N ( x N ) g_N(x)=f_N\left(\frac{x}{N}\right) g N ( x ) = f N ( N x ) satisfies
F R ( g N ) ≥ N 1 − θ 4 − 1 2 . (6) FR(g_N)\ge\frac{N^{1-\theta}}{4}-\frac{1}{2}. \tag*{(6)} F R ( g N ) ≥ 4 N 1 − θ − 2 1 . (6)
For large N N N the size conditions of Proposition 3.2 and Theorem 3.5 hold, so taking θ = γ \theta=\gamma θ = γ and θ = s \theta=s θ = s we see that the exponents 1 − γ 1-\gamma 1 − γ and 1 − s 1-s 1 − s in these statements are sharp for bounds that are uniform over such families of functions.
To verify the estimate (6) , recall that
∣ ∑ y ∈ Z N e 2 π i ( a y 2 + b y ) N ∣ = N \left|\sum_{y\in\mathbb{Z}_N}e^{\frac{2\pi i(ay^2+by)}{N}}\right|=\sqrt{N} y ∈ Z N ∑ e N 2 π i ( a y 2 + b y ) = N
when N N N is odd and gcd ( a , N ) = 1 \gcd(a,N)=1 g cd( a , N ) = 1 . It follows that the function χ ( x ) = e 2 π i ( x 1 2 + x 2 2 ) N \chi(x)=e^{\frac{2\pi i(x_1^2+x_2^2)}{N}} χ ( x ) = e N 2 π i ( x 1 2 + x 2 2 ) satisfies ∣ χ ^ ( m ) ∣ = 1 |\widehat{\chi}(m)|=1 ∣ χ ( m ) ∣ = 1 for every m m m and
∣ ∑ x ∈ Z N 2 χ ( x ) ∣ 2 = N . \left|\sum_{x\in\mathbb{Z}_N^2}\chi(x)\right|^2=N. x ∈ Z N 2 ∑ χ ( x ) 2 = N .
Since ψ = χ + χ ‾ 2 \psi=\frac{\chi+\overline{\chi}}{2} ψ = 2 χ + χ , we have ∣ ψ ^ ( m ) ∣ ≤ 1 |\widehat{\psi}(m)|\leq1 ∣ ψ ( m ) ∣ ≤ 1 for every m m m and
∥ ψ ∥ ℓ 2 2 = N 2 2 + 1 2 Re ∑ x ∈ Z N 2 χ ( x ) 2 ≥ N 2 − N 2 , \|\psi\|_{\ell^2}^2=\frac{N^2}{2}+\frac{1}{2}\operatorname{Re}\sum_{x\in\mathbb{Z}_N^2}\chi(x)^2\geq\frac{N^2-N}{2}, ∥ ψ ∥ ℓ 2 2 = 2 N 2 + 2 1 Re x ∈ Z N 2 ∑ χ ( x ) 2 ≥ 2 N 2 − N ,
and therefore
∑ m ≠ 0 ∣ ψ ^ ( m ) ∣ ≥ ∑ m ≠ 0 ∣ ψ ^ ( m ) ∣ 2 ≥ N 2 − N 2 − 1. \sum_{m\ne0}|\widehat{\psi}(m)|\geq\sum_{m\ne0}|\widehat{\psi}(m)|^2\geq\frac{N^2-N}{2}-1. m = 0 ∑ ∣ ψ ( m ) ∣ ≥ m = 0 ∑ ∣ ψ ( m ) ∣ 2 ≥ 2 N 2 − N − 1.
Since g N = 1 + N − θ ψ g_N=1+N^{-\theta}\psi g N = 1 + N − θ ψ , we have g N ^ ( m ) = N − θ ψ ^ ( m ) \widehat{g_N}(m)=N^{-\theta}\widehat{\psi}(m) g N ( m ) = N − θ ψ ( m ) for m ≠ 0 m\ne0 m = 0 and ∥ g N ∥ ℓ 2 ≤ ( 1 + N − θ ) N ≤ 2 N \|g_N\|_{\ell^2}\leq(1+N^{-\theta})N\leq2N ∥ g N ∥ ℓ 2 ≤ ( 1 + N − θ ) N ≤ 2 N , which proves (3.6).
On the continuous side, Φ ( u ) \Phi(u) Φ ( u ) is a convex combination of values of ψ \psi ψ , so ∣ Φ ∣ ≤ 1 |\Phi|\leq1 ∣Φ∣ ≤ 1 . On each grid cell Φ \Phi Φ is bilinear with ∣ ∂ j Φ ∣ ≤ 2 N |\partial_j\Phi|\leq2N ∣ ∂ j Φ∣ ≤ 2 N , hence
∣ Φ ( u ) − Φ ( v ) ∣ ≤ min { 2 , 2 2 N d T 2 ( u , v ) } , |\Phi(u)-\Phi(v)|\leq\min\{2,2\sqrt{2}N d_{\mathbb{T}^2}(u,v)\}, ∣Φ ( u ) − Φ ( v ) ∣ ≤ min { 2 , 2 2 N d T 2 ( u , v )} ,
and consequently [ Φ ] C 0 , θ ≤ 2 2 N θ [\Phi]_{C^{0,\theta}}\leq2\sqrt{2}N^\theta [ Φ ] C 0 , θ ≤ 2 2 N θ . Splitting the double integral at d T 2 ( u , v ) = N − 1 d_{\mathbb{T}^2}(u,v)=N^{-1} d T 2 ( u , v ) = N − 1 we see in the same way that [ Φ ] W θ , p ≤ C θ , p N θ [\Phi]_{W^{\theta,p}}\leq C_{\theta,p}N^\theta [ Φ ] W θ , p ≤ C θ , p N θ , and these estimates imply the stated bounds for ∥ f N ∥ C 0 , θ \|f_N\|_{C^{0,\theta}} ∥ f N ∥ C 0 , θ and ∥ f N ∥ W θ , p \|f_N\|_{W^{\theta,p}} ∥ f N ∥ W θ , p . Finally, the integral
∫ [ 0 , 1 ] 2 Φ ( u ) d u = N − 2 ∑ x ∈ Z N 2 ψ ( x ) \int_{[0,1]^2}\Phi(u)\,du=N^{-2}\sum_{x\in\mathbb{Z}_N^2}\psi(x) ∫ [ 0 , 1 ] 2 Φ ( u ) d u = N − 2 x ∈ Z N 2 ∑ ψ ( x )
has absolute value at most N − 1 N^{-1} N − 1 , so ∥ f N ∥ L 2 ≥ ∥ f N ∥ L 1 ≥ 1 − N − 1 − θ ≥ 2 3 \|f_N\|_{L^2}\geq\|f_N\|_{L^1}\geq1-N^{-1-\theta}\geq\frac{2}{3} ∥ f N ∥ L 2 ≥ ∥ f N ∥ L 1 ≥ 1 − N − 1 − θ ≥ 3 2 and ∥ f N ∥ L 2 ≤ ∥ f N ∥ L ∞ ≤ 2 \|f_N\|_{L^2}\leq\|f_N\|_{L^\infty}\leq2 ∥ f N ∥ L 2 ≤ ∥ f N ∥ L ∞ ≤ 2 .
A translated grid
The Hölder estimate on a fixed grid requires a quantitative hypothesis which keeps the sampled L 2 L^2 L 2 norm from becoming too small. For C 1 C^1 C 1 functions a translation of the grid removes this issue, and averaging over the translation parameter allows us to replace the C 1 C^1 C 1 norm in the main term by the L 2 L^2 L 2 norm of the gradient.
Theorem 3.8. Let f f f be a nonzero function in C 1 ( [ 0 , 1 ] 2 ) C^1([0,1]^2) C 1 ([ 0 , 1 ] 2 ) which is 1 1 1 -periodic in each variable, let N ≥ 2 N\geq2 N ≥ 2 , and for t = ( t 1 , t 2 ) ∈ [ 0 , 1 ) 2 t=(t_1,t_2)\in[0,1)^2 t = ( t 1 , t 2 ) ∈ [ 0 , 1 ) 2 let
g t ( x 1 , x 2 ) = f ( x 1 + t 1 N , x 2 + t 2 N ) . g_t(x_1,x_2)=f\left(\frac{x_1+t_1}{N},\frac{x_2+t_2}{N}\right). g t ( x 1 , x 2 ) = f ( N x 1 + t 1 , N x 2 + t 2 ) . There exists t ∈ [ 0 , 1 ) 2 t\in[0,1)^2 t ∈ [ 0 , 1 ) 2 such that
F R ( g t ) ≤ 1 + 1 2 1 + log N ∥ ∇ f ∥ L 2 ( [ 0 , 1 ] 2 ) ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) . FR(g_t)\leq1+\frac{1}{\sqrt{2}}\sqrt{1+\log N}\frac{\|\nabla f\|_{L^2([0,1]^2)}}{\|f\|_{L^2([0,1]^2)}}. F R ( g t ) ≤ 1 + 2 1 1 + log N ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) ∥∇ f ∥ L 2 ([ 0 , 1 ] 2 ) .
There is also a translation t ′ ∈ [ 0 , 1 ) 2 t' \in[0,1)^2 t ′ ∈ [ 0 , 1 ) 2 , not necessarily equal to t t t , such that
F R ( g t ′ ) 2 ≤ 2 ∣ ∫ [ 0 , 1 ] 2 f ( u ) d u ∣ 2 ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) 2 + ( 1 + log N + 1 2 π 2 N 2 ) ∥ ∇ f ∥ L 2 ( [ 0 , 1 ] 2 ) 2 ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) 2 . FR(g_{t'})^2 \le2\frac{\left|\int_{[0,1]^2} f(u)\,du\right|^2}{\|f\|_{L^2([0,1]^2)}^2}+\left(1+\log N+\frac{1}{2\pi^2N^2}\right)\frac{\|\nabla f\|_{L^2([0,1]^2)}^2}{\|f\|_{L^2([0,1]^2)}^2}. F R ( g t ′ ) 2 ≤ 2 ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) 2 ∫ [ 0 , 1 ] 2 f ( u ) d u 2 + ( 1 + log N + 2 π 2 N 2 1 ) ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) 2 ∥∇ f ∥ L 2 ([ 0 , 1 ] 2 ) 2 .
If f ≥ 0 f\ge0 f ≥ 0 and μ = ∫ [ 0 , 1 ] 2 f ( u ) d u > 0 \mu=\int_{[0,1]^2}f(u)\,du>0 μ = ∫ [ 0 , 1 ] 2 f ( u ) d u > 0 , then
F R ( g t ) ≤ 1 + 1 2 1 + log N ∥ ∇ f ∥ L 2 ( [ 0 , 1 ] 2 ) μ . FR(g_t)\le1+\frac{1}{\sqrt{2}}\sqrt{1+\log N}\frac{\|\nabla f\|_{L^2([0,1]^2)}}{\mu}. F R ( g t ) ≤ 1 + 2 1 1 + log N μ ∥∇ f ∥ L 2 ([ 0 , 1 ] 2 ) .
Proof. For t ∈ [ 0 , 1 ) 2 t\in[0,1)^2 t ∈ [ 0 , 1 ) 2 we let D ( t ) = ∥ g t ∥ 2 2 D(t)=\|g_t\|_2^2 D ( t ) = ∥ g t ∥ 2 2 , E ( t ) = ∥ Δ 1 g t ∥ 2 2 + ∥ Δ 2 g t ∥ 2 2 E(t)=\|\Delta_1g_t\|_2^2+\|\Delta_2g_t\|_2^2 E ( t ) = ∥ Δ 1 g t ∥ 2 2 + ∥ Δ 2 g t ∥ 2 2 , and Z ( t ) = ∣ g t ^ ( 0 ) ∣ Z(t)=|\widehat{g_t}(0)| Z ( t ) = ∣ g t ( 0 ) ∣ , and we also write
W N = ∑ m ≠ 0 1 ρ ( m ) 2 . W_N=\sum_{m\ne0}\frac{1}{\rho(m)^2}. W N = m = 0 ∑ ρ ( m ) 2 1 .
By Proposition 2.1, for every t t t with D ( t ) > 0 D(t)>0 D ( t ) > 0 ,
F R ( g t ) ≤ Z ( t ) + W N E ( t ) D ( t ) , FR(g_t)\le\frac{Z(t)+\sqrt{W_N}\sqrt{E(t)}}{\sqrt{D(t)}}, F R ( g t ) ≤ D ( t ) Z ( t ) + W N E ( t ) ,
and the elementary inequality ( a + b ) 2 ≤ 2 a 2 + 2 b 2 (a+b)^2\le2a^2+2b^2 ( a + b ) 2 ≤ 2 a 2 + 2 b 2 shows that
F R ( g t ) 2 ≤ 2 Z ( t ) 2 + 2 W N E ( t ) D ( t ) . FR(g_t)^2\le\frac{2Z(t)^2+2W_NE(t)}{D(t)}. F R ( g t ) 2 ≤ D ( t ) 2 Z ( t ) 2 + 2 W N E ( t ) .
The idea is to average the numerator and the denominator of this last expression over t t t . For each fixed x x x , the change of variables u = x + t N u=\frac{x+t}{N} u = N x + t maps the translation square onto the grid cell indexed by x x x and has Jacobian d t = N 2 d u dt=N^2du d t = N 2 d u , so summing over the cells we obtain
∫ [ 0 , 1 ) 2 D ( t ) d t = N 2 ∥ f ∥ L 2 ( [ 0 , 1 ) 2 ) 2 . \int_{[0,1)^2}D(t)\,dt=N^2\|f\|_{L^2([0,1)^2)}^2. ∫ [ 0 , 1 ) 2 D ( t ) d t = N 2 ∥ f ∥ L 2 ([ 0 , 1 ) 2 ) 2 .
In the same way, for each j j j ,
∫ [ 0 , 1 ) 2 ∥ Δ j g t ∥ 2 2 d t = N 2 ∫ [ 0 , 1 ] 2 ∣ f ( u + e j N ) − f ( u ) ∣ 2 d u , \int_{[0,1)^2}\|\Delta_jg_t\|_2^2dt=N^2\int_{[0,1]^2}\left|f\left(u+\frac{e_j}{N}\right)-f(u)\right|^2du, ∫ [ 0 , 1 ) 2 ∥ Δ j g t ∥ 2 2 d t = N 2 ∫ [ 0 , 1 ] 2 f ( u + N e j ) − f ( u ) 2 d u ,
and by the fundamental theorem of calculus and Cauchy–Schwarz,
∣ f ( u + e j N ) − f ( u ) ∣ 2 = ∣ ∫ 0 1 / N ∂ f ∂ x j ( u + r e j ) d r ∣ 2 ≤ 1 N ∫ 0 1 / N ∣ ∂ f ∂ x j ( u + r e j ) ∣ 2 d r . \left|f\left(u+\frac{e_j}{N}\right)-f(u)\right|^2=\left|\int_0^{1/N}\frac{\partial f}{\partial x_j}(u+re_j)\,dr\right|^2\le\frac{1}{N}\int_0^{1/N}\left|\frac{\partial f}{\partial x_j}(u+re_j)\right|^2dr. f ( u + N e j ) − f ( u ) 2 = ∫ 0 1/ N ∂ x j ∂ f ( u + r e j ) d r 2 ≤ N 1 ∫ 0 1/ N ∂ x j ∂ f ( u + r e j ) 2 d r .
Integrating in u u u and using the translation invariance of the torus we conclude that
∫ [ 0 , 1 ) 2 E ( t ) d t ≤ ∥ ∇ f ∥ L 2 ( [ 0 , 1 ) 2 ) 2 . \int_{[0,1)^2}E(t)\,dt\le\|\nabla f\|_{L^2([0,1)^2)}^2. ∫ [ 0 , 1 ) 2 E ( t ) d t ≤ ∥∇ f ∥ L 2 ([ 0 , 1 ) 2 ) 2 .
These two averaged estimates imply that there is a translation t 0 t_0 t 0 with D ( t 0 ) > 0 D(t_0)>0 D ( t 0 ) > 0 and
E ( t 0 ) D ( t 0 ) ≤ ∥ ∇ f ∥ L 2 ( [ 0 , 1 ] 2 ) 2 N 2 ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) 2 , \frac{E(t_0)}{D(t_0)}\le\frac{\|\nabla f\|_{L^2([0,1]^2)}^2}{N^2\|f\|_{L^2([0,1]^2)}^2}, D ( t 0 ) E ( t 0 ) ≤ N 2 ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) 2 ∥∇ f ∥ L 2 ([ 0 , 1 ] 2 ) 2 ,
because if the reverse strict inequality held whenever D ( t ) > 0 D(t)>0 D ( t ) > 0 , then multiplication by D ( t ) D(t) D ( t ) and integration would contradict them. Since a single Fourier coefficient is at most the full ℓ 2 \ell^2 ℓ 2 norm, we have Z ( t 0 ) ≤ D ( t 0 ) Z(t_0)\le\sqrt{D(t_0)} Z ( t 0 ) ≤ D ( t 0 ) , and the estimate for W N W_N W N from Proposition 2.1 shows that
F R ( g t 0 ) ≤ 1 + W N E ( t 0 ) D ( t 0 ) ≤ 1 + 1 2 1 + log N ∥ ∇ f ∥ L 2 ( [ 0 , 1 ] 2 ) ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) . FR(g_{t_0})\le1+\sqrt{W_N}\sqrt{\frac{E(t_0)}{D(t_0)}}\le1+\frac{1}{\sqrt{2}}\sqrt{1+\log N}\frac{\|\nabla f\|_{L^2([0,1]^2)}}{\|f\|_{L^2([0,1]^2)}}. F R ( g t 0 ) ≤ 1 + W N D ( t 0 ) E ( t 0 ) ≤ 1 + 2 1 1 + log N ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) ∥∇ f ∥ L 2 ([ 0 , 1 ] 2 ) .
This is the first assertion, and the bound for nonnegative f f f follows because μ ≤ ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) \mu\le\|f\|_{L^2([0,1]^2)} μ ≤ ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) when f ≥ 0 f \ge0 f ≥ 0 .
In order to obtain a version which retains the continuous mean, we also average the zero frequency. Let
c ( k ) = ∫ [ 0 , 1 ] 2 f ( u ) e − 2 π i k ⋅ u d u for k ∈ Z 2 c(k)=\int_{[0,1]^2}f(u)e^{-2\pi i k\cdot u}\,du\quad\text{for }k\in\mathbb{Z}^2 c ( k ) = ∫ [ 0 , 1 ] 2 f ( u ) e − 2 π ik ⋅ u d u for k ∈ Z 2
be the continuous Fourier coefficients of f f f . We claim that the function
t ↦ g t ^ ( 0 ) = 1 N ∑ x ∈ Z N 2 f ( x + t N ) t\mapsto\widehat{g_t}(0)=\frac{1}{N}\sum_{x\in\mathbb{Z}_N^2}f\left(\frac{x+t}{N}\right) t ↦ g t ( 0 ) = N 1 x ∈ Z N 2 ∑ f ( N x + t )
has continuous Fourier coefficient N c ( N ℓ ) N c(N\ell) N c ( N ℓ ) at the frequency ℓ ∈ Z 2 \ell\in\mathbb{Z}^2 ℓ ∈ Z 2 . To verify this directly, let Q x Q_x Q x be the grid cell indexed by x x x , as in the proof of Lemma 3.1. Then
∫ [ 0 , 1 ) 2 g t ^ ( 0 ) e − 2 π i ℓ ⋅ t d t = 1 N ∑ x ∈ Z N 2 N 2 ∫ Q x f ( u ) e − 2 π i ℓ ⋅ ( N u − x ) d u = N ∫ [ 0 , 1 ] 2 f ( u ) e − 2 π i N ℓ ⋅ u d u = N c ( N ℓ ) , \begin{aligned}
\int_{[0,1)^2}\widehat{g_t}(0)e^{-2\pi i\ell\cdot t}\,dt=\frac{1}{N}\sum_{x\in\mathbb{Z}_N^2}N^2\int_{Q_x}f(u)e^{-2\pi i\ell\cdot(Nu-x)}\,du \\
&=N\int_{[0,1]^2}f(u)e^{-2\pi iN\ell\cdot u}\,du=Nc(N\ell),
\end{aligned} ∫ [ 0 , 1 ) 2 g t ( 0 ) e − 2 π i ℓ ⋅ t d t = N 1 x ∈ Z N 2 ∑ N 2 ∫ Q x f ( u ) e − 2 π i ℓ ⋅ ( N u − x ) d u = N ∫ [ 0 , 1 ] 2 f ( u ) e − 2 π i N ℓ ⋅ u d u = N c ( N ℓ ) ,
where we used e 2 π i ℓ ⋅ x = 1 e^{2\pi i\ell\cdot x}=1 e 2 π i ℓ ⋅ x = 1 in the second step. By Parseval’s identity in the variable t t t ,
∫ [ 0 , 1 ) 2 Z ( t ) 2 d t = N 2 ∑ ℓ ∈ Z 2 ∣ c ( N ℓ ) ∣ 2 ≤ N 2 ∣ ∫ [ 0 , 1 ] 2 f ( u ) d u ∣ 2 + 1 4 π 2 ∥ ∇ f ∥ L 2 ( [ 0 , 1 ] 2 ) 2 , \int_{[0,1)^2}Z(t)^2\,dt=N^2\sum_{\ell\in\mathbb{Z}^2}|c(N\ell)|^2\le N^2\left|\int_{[0,1]^2}f(u)\,du\right|^2+\frac{1}{4\pi^2}\|\nabla f\|_{L^2([0,1]^2)}^2, ∫ [ 0 , 1 ) 2 Z ( t ) 2 d t = N 2 ℓ ∈ Z 2 ∑ ∣ c ( N ℓ ) ∣ 2 ≤ N 2 ∫ [ 0 , 1 ] 2 f ( u ) d u 2 + 4 π 2 1 ∥∇ f ∥ L 2 ([ 0 , 1 ] 2 ) 2 ,
where the inequality holds because ∣ N ℓ ∣ ≥ N |N\ell|\ge N ∣ N ℓ ∣ ≥ N when ℓ ≠ 0 \ell\ne0 ℓ = 0 and
4 π 2 ∑ k ∈ Z 2 ∣ k ∣ 2 ∣ c ( k ) ∣ 2 = ∥ ∇ f ∥ L 2 ( [ 0 , 1 ] 2 ) 2 . 4\pi^2\sum_{k\in\mathbb{Z}^2}|k|^2|c(k)|^2=\|\nabla f\|_{L^2([0,1]^2)}^2. 4 π 2 k ∈ Z 2 ∑ ∣ k ∣ 2 ∣ c ( k ) ∣ 2 = ∥∇ f ∥ L 2 ([ 0 , 1 ] 2 ) 2 .
Recall from Proposition 2.1 that W N ≤ N 2 2 ( 1 + log N ) W_N\le\frac{N^2}{2}(1+\log N) W N ≤ 2 N 2 ( 1 + log N ) . Since the integral of D ( t ) D(t) D ( t ) is positive, there is a translation t ′ t' t ′ with D ( t ′ ) > 0 D(t')>0 D ( t ′ ) > 0 such that
2 Z ( t ′ ) 2 + 2 W N E ( t ′ ) D ( t ′ ) ≤ ∫ [ 0 , 1 ) 2 ( 2 Z ( t ) 2 + 2 W N E ( t ) ) d t ∫ [ 0 , 1 ) 2 D ( t ) d t , \frac{2Z(t')^2+2W_NE(t')}{D(t')}\le\frac{\int_{[0,1)^2}(2Z(t)^2+2W_NE(t))\,dt}{\int_{[0,1)^2}D(t)\,dt}, D ( t ′ ) 2 Z ( t ′ ) 2 + 2 W N E ( t ′ ) ≤ ∫ [ 0 , 1 ) 2 D ( t ) d t ∫ [ 0 , 1 ) 2 ( 2 Z ( t ) 2 + 2 W N E ( t )) d t ,
since otherwise the strict reverse inequality would remain true after multiplication by D ( t ) D(t) D ( t ) and integration. The squared bound in the theorem follows by substituting the three averaged estimates.
Corollary 3.9 (A C 1 C^1 C 1 estimate on a translated grid). Under the hypotheses of Theorem 3.8, there exists a translation τ ∈ [ 0 , 1 ) 2 \tau\in[0,1)^2 τ ∈ [ 0 , 1 ) 2 such that
F R ( g τ ) ≤ ∣ ∫ [ 0 , 1 ] 2 f ( u ) d u ∣ ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) + ∥ f ∥ C 1 ( [ 0 , 1 ] 2 ) ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) 1 + log N + 2 N ∥ f ∥ C 1 ( [ 0 , 1 ] 2 ) ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) . FR(g_\tau)\le\frac{\left|\int_{[0,1]^2}f(u)\,du\right|}{\|f\|_{L^2([0,1]^2)}}+\frac{\|f\|_{C^1([0,1]^2)}}{\|f\|_{L^2([0,1]^2)}}\sqrt{1+\log N}+\frac{2}{N}\frac{\|f\|_{C^1([0,1]^2)}}{\|f\|_{L^2([0,1]^2)}}. F R ( g τ ) ≤ ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) ∫ [ 0 , 1 ] 2 f ( u ) d u + ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) ∥ f ∥ C 1 ([ 0 , 1 ] 2 ) 1 + log N + N 2 ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) ∥ f ∥ C 1 ([ 0 , 1 ] 2 ) . If f ≥ 0 f\ge0 f ≥ 0 and μ = ∫ [ 0 , 1 ] 2 f ( u ) d u > 0 \mu=\int_{[0,1]^2}f(u)\,du>0 μ = ∫ [ 0 , 1 ] 2 f ( u ) d u > 0 , then
F R ( g τ ) ≤ 1 + ∥ f ∥ C 1 ( [ 0 , 1 ] 2 ) μ 1 + log N + 2 N ∥ f ∥ C 1 ( [ 0 , 1 ] 2 ) μ . FR(g_\tau)\le1+\frac{\|f\|_{C^1([0,1]^2)}}{\mu}\sqrt{1+\log N}+\frac{2}{N}\frac{\|f\|_{C^1([0,1]^2)}}{\mu}. F R ( g τ ) ≤ 1 + μ ∥ f ∥ C 1 ([ 0 , 1 ] 2 ) 1 + log N + N 2 μ ∥ f ∥ C 1 ([ 0 , 1 ] 2 ) .
Proof. The averaged identity
∫ [ 0 , 1 ) 2 ∥ g t ∥ L 2 ( [ 0 , 1 ] 2 ) 2 d t = N 2 ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) 2 \int_{[0,1)^2}\|g_t\|_{L^2([0,1]^2)}^2\,dt=N^2\|f\|_{L^2([0,1]^2)}^2 ∫ [ 0 , 1 ) 2 ∥ g t ∥ L 2 ([ 0 , 1 ] 2 ) 2 d t = N 2 ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) 2
shows that some translation τ \tau τ satisfies ∥ g τ ∥ 2 ≥ N ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) \|g_\tau\|_2 \ge N\|f\|_{L^2([0,1]^2)} ∥ g τ ∥ 2 ≥ N ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) . On the other hand, for every translation, Lemma 3.1 with γ = 1 \gamma=1 γ = 1 and the estimate for the discrete differences coming from the fundamental theorem of calculus show that
∣ g τ ^ ( 0 ) ∣ ≤ N ∣ ∫ [ 0 , 1 ] 2 f ( u ) d u ∣ + 2 ∥ f ∥ C 1 ( [ 0 , 1 ] 2 ) |\widehat{g_\tau}(0)| \le N\left|\int_{[0,1]^2} f(u)\,du\right| + 2\|f\|_{C^1([0,1]^2)} ∣ g τ ( 0 ) ∣ ≤ N ∫ [ 0 , 1 ] 2 f ( u ) d u + 2∥ f ∥ C 1 ([ 0 , 1 ] 2 )
and
∑ m ≠ 0 ∣ g τ ^ ( m ) ∣ ≤ N ∥ f ∥ C 1 ( [ 0 , 1 ] 2 ) 1 + log N . \sum_{m\ne0}|\widehat{g_\tau}(m)| \le N\|f\|_{C^1([0,1]^2)}\sqrt{1+\log N}. m = 0 ∑ ∣ g τ ( m ) ∣ ≤ N ∥ f ∥ C 1 ([ 0 , 1 ] 2 ) 1 + log N .
The first assertion follows by adding these estimates and dividing by the lower bound for ∥ g τ ∥ 2 = ∥ g τ ^ ∥ 2 \|g_\tau\|_2=\|\widehat{g_\tau}\|_2 ∥ g τ ∥ 2 = ∥ g τ ∥ 2 , and the second assertion follows from the first because μ ≤ ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) \mu\le\|f\|_{L^2([0,1]^2)} μ ≤ ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) when f ≥ 0 f\ge0 f ≥ 0 . □
Two derivatives
Two derivatives remove the logarithmic factor in the estimate on the square, and the proof is the same discrete energy argument with second differences in place of first differences. We use the norm
∥ f ∥ C 2 ( [ 0 , 1 ] 2 ) = max β 1 + β 2 ≤ 2 ∥ ∂ β 1 + β 2 f ∂ x 1 β 1 ∂ x 2 β 2 ∥ L ∞ ( [ 0 , 1 ] 2 ) , \|f\|_{C^2([0,1]^2)}=\max_{\beta_1+\beta_2\le2}\left\|\frac{\partial^{\beta_1+\beta_2}f}{\partial x_1^{\beta_1}\partial x_2^{\beta_2}}\right\|_{L^\infty([0,1]^2)}, ∥ f ∥ C 2 ([ 0 , 1 ] 2 ) = β 1 + β 2 ≤ 2 max ∂ x 1 β 1 ∂ x 2 β 2 ∂ β 1 + β 2 f L ∞ ([ 0 , 1 ] 2 ) ,
where β 1 \beta_1 β 1 and β 2 \beta_2 β 2 are nonnegative integers and the derivative of order zero is f f f itself, and we write
Δ f = ∂ 2 f ∂ x 1 2 + ∂ 2 f ∂ x 2 2 \Delta f=\frac{\partial^2f}{\partial x_1^2}+\frac{\partial^2f}{\partial x_2^2} Δ f = ∂ x 1 2 ∂ 2 f + ∂ x 2 2 ∂ 2 f
for the continuous Laplacian.
Proposition 3.10. Let f f f be a nonzero C 2 C^2 C 2 function on [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 which is 1-periodic in each variable, let N ≥ 2 N\ge2 N ≥ 2 , and let g ( x ) = f ( x N ) g(x)=f\left(\frac{x}{N}\right) g ( x ) = f ( N x ) for x ∈ Z N 2 x\in\mathbb{Z}_N^2 x ∈ Z N 2 . There are absolute constants K , C > 0 K,C>0 K , C > 0 such that
N ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) 2 ≥ K ∥ f ∥ C 2 ( [ 0 , 1 ] 2 ) 2 N\|f\|_{L^2([0,1]^2)}^2\ge K\|f\|_{C^2([0,1]^2)}^2 N ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) 2 ≥ K ∥ f ∥ C 2 ([ 0 , 1 ] 2 ) 2 implies
F R ( g ) ≤ 1 + C ∥ f ∥ C 2 ( [ 0 , 1 ] 2 ) ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) . FR(g)\le1+C\frac{\|f\|_{C^2([0,1]^2)}}{\|f\|_{L^2([0,1]^2)}}. F R ( g ) ≤ 1 + C ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) ∥ f ∥ C 2 ([ 0 , 1 ] 2 ) . For every N ≥ 2 N\ge2 N ≥ 2 , without this size condition, there exists a translation t ∈ [ 0 , 1 ) 2 t\in[0,1)^2 t ∈ [ 0 , 1 ) 2 such that g t ( x ) = f ( x + t N ) g_t(x)=f\left(\frac{x+t}{N}\right) g t ( x ) = f ( N x + t ) is nonzero and
F R ( g t ) ≤ 1 + C ∥ Δ f ∥ L 2 ( [ 0 , 1 ] 2 ) ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) . FR(g_t)\le1+C\frac{\|\Delta f\|_{L^2([0,1]^2)}}{\|f\|_{L^2([0,1]^2)}}. F R ( g t ) ≤ 1 + C ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) ∥Δ f ∥ L 2 ([ 0 , 1 ] 2 ) .
Proof. Define the discrete Laplacian with nonnegative Fourier multiplier by
L N g ( x ) = ∑ j = 1 2 ( 2 g ( x ) − g ( x + e j ) − g ( x − e j ) ) . L_Ng(x)=\sum_{j=1}^{2}(2g(x)-g(x+e_j)-g(x-e_j)). L N g ( x ) = j = 1 ∑ 2 ( 2 g ( x ) − g ( x + e j ) − g ( x − e j )) .
Its Fourier transform is ρ ( m ) 2 g ^ ( m ) \rho(m)^2\widehat{g}(m) ρ ( m ) 2 g ( m ) , so Proposition 2.1 with s = 2 s=2 s = 2 implies that
∑ m ≠ 0 ∣ g ^ ( m ) ∣ ≤ ( ∑ m ≠ 0 1 ρ ( m ) 4 ) 1 2 ∥ L N g ∥ 2 ≤ C N 2 ∥ L N g ∥ 2 . (7) \sum_{m\ne0}|\widehat{g}(m)|\le\left(\sum_{m\ne0}\frac{1}{\rho(m)^4}\right)^{\frac12}\|L_Ng\|_2\le CN^2\|L_Ng\|_2. \tag*{(7)} m = 0 ∑ ∣ g ( m ) ∣ ≤ m = 0 ∑ ρ ( m ) 4 1 2 1 ∥ L N g ∥ 2 ≤ C N 2 ∥ L N g ∥ 2 . (7)
Applying the fundamental theorem of calculus twice we see that
∣ 2 f ( u ) − f ( u + e j N ) − f ( u − e j N ) ∣ ≤ 1 N 2 ∥ ∂ 2 f ∂ x j 2 ∥ L ∞ , \left|2f(u)-f\left(u+\frac{e_j}{N}\right)-f\left(u-\frac{e_j}{N}\right)\right|\le\frac{1}{N^2}\left\|\frac{\partial^2f}{\partial x_j^2}\right\|_{L^\infty}, 2 f ( u ) − f ( u + N e j ) − f ( u − N e j ) ≤ N 2 1 ∂ x j 2 ∂ 2 f L ∞ ,
and since there are N 2 N^2 N 2 grid points, ∥ L N g ∥ 2 ≤ C N ∥ f ∥ C 2 \|L_Ng\|_2\le\frac{C}{N}\|f\|_{C^2} ∥ L N g ∥ 2 ≤ N C ∥ f ∥ C 2 . The size condition and the argument for the sampled mass in the proof of Proposition 3.2 show that ∥ g ∥ 2 ≥ N 2 ∥ f ∥ L 2 \|g\|_2\ge\frac{N}{\sqrt{2}}\|f\|_{L^2} ∥ g ∥ 2 ≥ 2 N ∥ f ∥ L 2 . The assertion on the fixed grid follows by dividing the estimate (7) by this lower bound and using ∣ g ^ ( 0 ) ∣ ≤ ∥ g ∥ 2 |\widehat{g}(0)|\le\|g\|_2 ∣ g ( 0 ) ∣ ≤ ∥ g ∥ 2 . For the translated assertion, let D ( t ) = ∥ g t ∥ 2 2 D(t)=\lVert g_t\rVert_{2}^{2} D ( t ) = ∥ g t ∥ 2 2 and E 2 ( t ) = ∥ L N g t ∥ 2 2 E_2(t)=\lVert L_N g_t\rVert_{2}^{2} E 2 ( t ) = ∥ L N g t ∥ 2 2 . The same change of variables as in the proof of Theorem 3.8 shows that
∫ [ 0 , 1 ) 2 D ( t ) d t = N 2 ∥ f ∥ L 2 2 \int_{[0,1)^2}D(t)\,dt=N^2\lVert f\rVert_{L^2}^2 ∫ [ 0 , 1 ) 2 D ( t ) d t = N 2 ∥ f ∥ L 2 2
and
∫ [ 0 , 1 ) 2 E 2 ( t ) d t = N 2 ∥ ∑ j = 1 2 ( 2 f ( ⋅ ) − f ( ⋅ + e j N ) − f ( ⋅ − e j N ) ) ∥ L 2 2 . \int_{[0,1)^2}E_2(t)\,dt=N^2\left\lVert\sum_{j=1}^{2}\left(2f(\cdot)-f\left(\cdot+\frac{e_j}{N}\right)-f\left(\cdot-\frac{e_j}{N}\right)\right)\right\rVert_{L^2}^2. ∫ [ 0 , 1 ) 2 E 2 ( t ) d t = N 2 j = 1 ∑ 2 ( 2 f ( ⋅ ) − f ( ⋅ + N e j ) − f ( ⋅ − N e j ) ) L 2 2 .
In order to estimate the last expression, let
c ( k ) = ∫ [ 0 , 1 ] 2 f ( u ) e − 2 π i k ⋅ u d u for k ∈ Z 2 c(k)=\int_{[0,1]^2}f(u)e^{-2\pi i k\cdot u}\,du\quad\text{for }k\in\mathbb{Z}^2 c ( k ) = ∫ [ 0 , 1 ] 2 f ( u ) e − 2 π ik ⋅ u d u for k ∈ Z 2
as before. The Fourier multiplier of the sum of continuous differences is
4 ∑ j = 1 2 sin 2 ( π k j N ) ≤ 4 π 2 N 2 ∣ k ∣ 2 , 4\sum_{j=1}^{2}\sin^2\left(\frac{\pi k_j}{N}\right)\leq\frac{4\pi^2}{N^2}|k|^2, 4 j = 1 ∑ 2 sin 2 ( N π k j ) ≤ N 2 4 π 2 ∣ k ∣ 2 ,
and it follows from Parseval’s identity that
∫ [ 0 , 1 ) 2 E 2 ( t ) d t ≤ 1 N 2 ∥ Δ f ∥ L 2 2 . \int_{[0,1)^2}E_2(t)\,dt\leq\frac{1}{N^2}\lVert\Delta f\rVert_{L^2}^2. ∫ [ 0 , 1 ) 2 E 2 ( t ) d t ≤ N 2 1 ∥ Δ f ∥ L 2 2 .
Averaging E 2 ( t ) E_2(t) E 2 ( t ) and D ( t ) D(t) D ( t ) together as in the proof of Theorem 3.8 , we obtain a translation t t t with D ( t ) > 0 D(t)>0 D ( t ) > 0 and
E 2 ( t ) D ( t ) ≤ 1 N 4 ∥ Δ f ∥ L 2 2 ∥ f ∥ L 2 2 , \frac{E_2(t)}{D(t)}\leq\frac{1}{N^4}\frac{\lVert\Delta f\rVert_{L^2}^2}{\lVert f\rVert_{L^2}^2}, D ( t ) E 2 ( t ) ≤ N 4 1 ∥ f ∥ L 2 2 ∥ Δ f ∥ L 2 2 ,
and the proof is completed by applying (7) to g t g_t g t and using once again that ∣ g t ^ ( 0 ) ∣ ≤ ∥ g t ∥ 2 |\widehat{g_t}(0)|\leq\lVert g_t\rVert_2 ∣ g t ( 0 ) ∣ ≤ ∥ g t ∥ 2 . □
Fourier ratio bounds on compact manifolds
Let ( M , g ) (M,g) ( M , g ) be a connected compact d d d -dimensional Riemannian manifold without boundary, and write ∣ M ∣ |M| ∣ M ∣ for its Riemannian volume. We fix an orthonormal basis { e j } j = 0 ∞ \{e_j\}_{j=0}^{\infty} { e j } j = 0 ∞ of L 2 ( M ) L^2(M) L 2 ( M ) consisting of eigenfunctions of the Laplace–Beltrami operator, so that
− Δ g e j = λ j e j and 0 = λ 0 < λ 1 ≤ λ 2 ≤ ⋯ , -\Delta_g e_j=\lambda_j e_j\quad\text{and}\quad0=\lambda_0<\lambda_1\leq\lambda_2\leq\cdots, − Δ g e j = λ j e j and 0 = λ 0 < λ 1 ≤ λ 2 ≤ ⋯ ,
and we take e 0 = 1 ∣ M ∣ e_0=\frac{1}{\sqrt{|M|}} e 0 = ∣ M ∣ 1 . For Λ ≥ 1 \Lambda\geq1 Λ ≥ 1 , let
V Λ = span { e j : λ j ≤ Λ } and D Λ = # { j : λ j ≤ Λ } , V_\Lambda=\operatorname{span}\{e_j:\lambda_j\leq\Lambda\}\quad\text{and}\quad D_\Lambda=\#\{j:\lambda_j\leq\Lambda\}, V Λ = span { e j : λ j ≤ Λ } and D Λ = # { j : λ j ≤ Λ } ,
and for a nonzero f ∈ V Λ f\in V_\Lambda f ∈ V Λ define
f ^ ( j ) = ∫ M f ( x ) e j ( x ) ‾ d V g ( x ) and F R Λ ( f ) = ∑ λ j ≤ Λ ∣ f ^ ( j ) ∣ ( ∑ λ j ≤ Λ ∣ f ^ ( j ) ∣ 2 ) 1 2 . \widehat{f}(j)=\int_M f(x)\overline{e_j(x)}\,dV_g(x)\quad\text{and}\quad FR_\Lambda(f)=\frac{\sum_{\lambda_j\leq\Lambda}|\widehat{f}(j)|}{\left(\sum_{\lambda_j\leq\Lambda}|\widehat{f}(j)|^2\right)^{\frac{1}{2}}}. f ( j ) = ∫ M f ( x ) e j ( x ) d V g ( x ) and F R Λ ( f ) = ( ∑ λ j ≤ Λ ∣ f ( j ) ∣ 2 ) 2 1 ∑ λ j ≤ Λ ∣ f ( j ) ∣ .
The spectral decomposition also defines the fractional powers of the Laplace–Beltrami operator. If s > 0 s>0 s > 0 and f ∈ V Λ f\in V_\Lambda f ∈ V Λ , then
( − Δ g ) s 2 f = ∑ 0 < λ j ≤ Λ λ j s 2 f ^ ( j ) e j , (-\Delta_g)^{\frac{s}{2}}f=\sum_{0<\lambda_j\leq\Lambda}\lambda_j^{\frac{s}{2}}\widehat{f}(j)e_j, ( − Δ g ) 2 s f = 0 < λ j ≤ Λ ∑ λ j 2 s f ( j ) e j ,
where the constant mode is omitted because its eigenvalue is zero, and by Parseval’s identity
∥ ( − Δ g ) s 2 f ∥ L 2 ( M ) 2 = ∑ 0 < λ j ≤ Λ λ j s ∣ f ^ ( j ) ∣ 2 . \left\lVert(-\Delta_g)^{\frac{s}{2}}f\right\rVert_{L^2(M)}^2=\sum_{0<\lambda_j\leq\Lambda}\lambda_j^s|\widehat{f}(j)|^2. ( − Δ g ) 2 s f L 2 ( M ) 2 = 0 < λ j ≤ Λ ∑ λ j s ∣ f ( j ) ∣ 2 .
When s = 1 s=1 s = 1 , integration by parts on a compact manifold without boundary leads to the Dirichlet energy identity
∥ ( − Δ g ) 1 2 f ∥ L 2 ( M ) 2 = ⟨ − Δ g f , f ⟩ L 2 ( M ) = ∥ ∇ g f ∥ L 2 ( M ) 2 , \left\|(-\Delta_g)^{\frac{1}{2}}f\right\|_{L^2(M)}^2=\langle-\Delta_gf,f\rangle_{L^2(M)}=\left\|\nabla_gf\right\|_{L^2(M)}^2, ( − Δ g ) 2 1 f L 2 ( M ) 2 = ⟨ − Δ g f , f ⟩ L 2 ( M ) = ∥ ∇ g f ∥ L 2 ( M ) 2 ,
so the following proposition is the spectral counterpart of the discrete gradient calculation on Z 2 \mathbb{Z}^2 Z 2 .
Proposition 4.1. Let f ∈ V Λ f\in V_\Lambda f ∈ V Λ be nonzero. For every s > 0 s>0 s > 0 ,
F R Λ ( f ) ≤ 1 ∣ M ∣ ∣ ∫ M f ( x ) d V g ( x ) ∣ ∥ f ∥ L 2 ( M ) + ( ∑ 0 < λ j ≤ Λ 1 λ j s ) 1 2 ∥ ( − Δ g ) s 2 f ∥ L 2 ( M ) ∥ f ∥ L 2 ( M ) . FR_\Lambda(f)\leq\frac{1}{\sqrt{|M|}}\frac{\left|\int_M f(x)dV_g(x)\right|}{\left\|f\right\|_{L^2(M)}}+\left(\sum_{0<\lambda_j\leq\Lambda}\frac{1}{\lambda_j^s}\right)^{\frac{1}{2}}\frac{\left\|(-\Delta_g)^{\frac{s}{2}}f\right\|_{L^2(M)}}{\left\|f\right\|_{L^2(M)}}. F R Λ ( f ) ≤ ∣ M ∣ 1 ∥ f ∥ L 2 ( M ) ∫ M f ( x ) d V g ( x ) + 0 < λ j ≤ Λ ∑ λ j s 1 2 1 ∥ f ∥ L 2 ( M ) ( − Δ g ) 2 s f L 2 ( M ) . Consequently,
F R Λ ( f ) ≤ 1 ∣ M ∣ ∣ ∫ M f ( x ) d V g ( x ) ∣ ∥ f ∥ L 2 ( M ) + C M , s ∥ ( − Δ g ) s 2 f ∥ L 2 ( M ) ∥ f ∥ L 2 ( M ) { 1 , s > d 2 , ( 1 + log Λ ) 1 2 , s = d 2 , Λ d 4 − s 2 , 0 < s < d 2 . FR_\Lambda(f)\leq\frac{1}{\sqrt{|M|}}\frac{\left|\int_M f(x)dV_g(x)\right|}{\left\|f\right\|_{L^2(M)}}+C_{M,s}\frac{\left\|(-\Delta_g)^{\frac{s}{2}}f\right\|_{L^2(M)}}{\left\|f\right\|_{L^2(M)}}\begin{cases}
1, & s>\frac{d}{2},\\
(1+\log\Lambda)^{\frac{1}{2}}, & s=\frac{d}{2},\\
\Lambda^{\frac{d}{4}-\frac{s}{2}}, & 0<s<\frac{d}{2}.
\end{cases} F R Λ ( f ) ≤ ∣ M ∣ 1 ∥ f ∥ L 2 ( M ) ∫ M f ( x ) d V g ( x ) + C M , s ∥ f ∥ L 2 ( M ) ( − Δ g ) 2 s f L 2 ( M ) ⎩ ⎨ ⎧ 1 , ( 1 + log Λ ) 2 1 , Λ 4 d − 2 s , s > 2 d , s = 2 d , 0 < s < 2 d .
Proof. By Parseval’s identity,
∥ f ∥ L 2 ( M ) 2 = ∑ λ j ≤ Λ ∣ f ^ ( j ) ∣ 2 , \left\|f\right\|_{L^2(M)}^2=\sum_{\lambda_j\leq\Lambda}\left|\widehat f(j)\right|^2, ∥ f ∥ L 2 ( M ) 2 = λ j ≤ Λ ∑ f ( j ) 2 ,
and the zero mode satisfies
∣ f ^ ( 0 ) ∣ = 1 ∣ M ∣ ∣ ∫ M f ( x ) d V g ( x ) ∣ . \left|\widehat f(0)\right|=\frac{1}{\sqrt{|M|}}\left|\int_M f(x)dV_g(x)\right|. f ( 0 ) = ∣ M ∣ 1 ∫ M f ( x ) d V g ( x ) .
For the remaining modes we use weighted Cauchy–Schwarz to see that
∑ 0 < λ j ≤ Λ ∣ f ^ ( j ) ∣ ≤ ( ∑ 0 < λ j ≤ Λ 1 λ j s ) 1 2 ( ∑ 0 < λ j ≤ Λ λ j s ∣ f ^ ( j ) ∣ 2 ) 1 2 = ( ∑ 0 < λ j ≤ Λ 1 λ j s ) 1 2 ∥ ( − Δ g ) s 2 f ∥ L 2 ( M ) , \begin{aligned}
\sum_{0<\lambda_j\leq\Lambda}\left|\widehat f(j)\right|\leq\left(\sum_{0<\lambda_j\leq\Lambda}\frac{1}{\lambda_j^s}\right)^{\frac{1}{2}}\left(\sum_{0<\lambda_j\leq\Lambda}\lambda_j^s\left|\widehat f(j)\right|^2\right)^{\frac{1}{2}} \\
&=\left(\sum_{0<\lambda_j\leq\Lambda}\frac{1}{\lambda_j^s}\right)^{\frac{1}{2}}\left\|(-\Delta_g)^{\frac{s}{2}}f\right\|_{L^2(M)},
\end{aligned} 0 < λ j ≤ Λ ∑ f ( j ) ≤ 0 < λ j ≤ Λ ∑ λ j s 1 2 1 0 < λ j ≤ Λ ∑ λ j s f ( j ) 2 2 1 = 0 < λ j ≤ Λ ∑ λ j s 1 2 1 ( − Δ g ) 2 s f L 2 ( M ) ,
which proves the first estimate.
Let us briefly recall how Weyl’s law enters. Its full asymptotic form is
# { j : λ j ≤ R } = c M R d 2 + o ( R d 2 ) as R → ∞ , \#\{j:\lambda_j\leq R\}=c_MR^{\frac{d}{2}}+o(R^{\frac{d}{2}})\text{ as }R\to\infty, # { j : λ j ≤ R } = c M R 2 d + o ( R 2 d ) as R → ∞ ,
but only the resulting upper bound
# { j : λ j ≤ R } ≤ C M ( 1 + R ) d 2 \#\{j:\lambda_j\leq R\}\leq C_M(1+R)^{\frac{d}{2}} # { j : λ j ≤ R } ≤ C M ( 1 + R ) 2 d
is needed here. The finitely many eigenvalues below 1 1 1 can be absorbed into the constant. On the dyadic shell 2 k ≤ λ j < 2 k + 1 2^k\leq\lambda_j<2^{k+1} 2 k ≤ λ j < 2 k + 1 there are at most C M 2 k d 2 C_M2^{\frac{kd}{2}} C M 2 2 k d eigenvalues, while each weight 1 λ j s \frac{1}{\lambda_j^s} λ j s 1 is at most 1 2 k s \frac{1}{2^{ks}} 2 k s 1 , so the contribution of this shell is bounded by C M 2 k ( d 2 − s ) C_M2^{k(\frac{d}{2}-s)} C M 2 k ( 2 d − s ) . These terms form a convergent geometric series if s > d 2 s>\frac{d}{2} s > 2 d , each shell contributes a bounded amount and there are O ( 1 + log Λ ) O(1+\log\Lambda) O ( 1 + log Λ ) shells if s = d 2 s=\frac{d}{2} s = 2 d , and the final shell dominates and contributes Λ d 2 − s \Lambda^{\frac{d}{2}-s} Λ 2 d − s if s < d 2 s<\frac{d}{2} s < 2 d , so the three cases in the statement follow upon taking square roots. See [17 ] for the spectral estimates used here. □
Corollary 4.2. If M M M is two-dimensional and f ∈ V Λ f\in V_\Lambda f ∈ V Λ is nonzero, then
F R Λ ( f ) ≤ 1 ∣ M ∣ ∣ ∫ M f ( x ) d V g ( x ) ∣ ∥ f ∥ L 2 ( M ) + C M ( 1 + log Λ ) 1 2 ∥ ∇ g f ∥ L 2 ( M ) ∥ f ∥ L 2 ( M ) . FR_\Lambda(f)\leq\frac{1}{\sqrt{|M|}}\frac{\left|\int_M f(x)dV_g(x)\right|}{\left\|f\right\|_{L^2(M)}}+C_M(1+\log\Lambda)^{\frac{1}{2}}\frac{\left\|\nabla_gf\right\|_{L^2(M)}}{\left\|f\right\|_{L^2(M)}}. F R Λ ( f ) ≤ ∣ M ∣ 1 ∥ f ∥ L 2 ( M ) ∫ M f ( x ) d V g ( x ) + C M ( 1 + log Λ ) 2 1 ∥ f ∥ L 2 ( M ) ∥ ∇ g f ∥ L 2 ( M ) .
Sharpness on compact surfaces
It is natural to ask whether the square-root logarithm in Corollary 4.2 is an artifact of the proof. The next result shows that it is not, and that it is forced by the distribution of the eigenvalues.
Theorem 4.3. Let M M M be a connected compact two-dimensional Riemannian manifold without boundary, and fix an orthonormal eigenfunction basis as above. For every sufficiently large Λ \Lambda Λ , define
f Λ = ∑ 0 < λ j ≤ Λ 1 λ j e j . f_\Lambda=\sum_{0<\lambda_j\leq\Lambda}\frac{1}{\lambda_j}e_j. f Λ = 0 < λ j ≤ Λ ∑ λ j 1 e j . There are positive constants c M c_M c M and C M C_M C M , independent of Λ \Lambda Λ , such that
c M log Λ ≤ F R Λ ( f Λ ) ≤ C M log Λ c_M\log\Lambda\leq FR_\Lambda(f_\Lambda)\leq C_M\log\Lambda c M log Λ ≤ F R Λ ( f Λ ) ≤ C M log Λ and
c M log Λ ≤ ∥ ∇ g f Λ ∥ L 2 ( M ) ∥ f Λ ∥ L 2 ( M ) ≤ C M log Λ . c_M\sqrt{\log\Lambda}\leq\frac{\lVert\nabla_g f_\Lambda\rVert_{L^2(M)}}{\lVert f_\Lambda\rVert_{L^2(M)}}\leq C_M\sqrt{\log\Lambda}. c M log Λ ≤ ∥ f Λ ∥ L 2 ( M ) ∥ ∇ g f Λ ∥ L 2 ( M ) ≤ C M log Λ . Consequently,
F R Λ ( f Λ ) ∥ f Λ ∥ L 2 ( M ) ∥ ∇ g f Λ ∥ L 2 ( M ) ≍ log Λ . \frac{FR_\Lambda(f_\Lambda)\lVert f_\Lambda\rVert_{L^2(M)}}{\lVert\nabla_g f_\Lambda\rVert_{L^2(M)}}\asymp\sqrt{\log\Lambda}. ∥ ∇ g f Λ ∥ L 2 ( M ) F R Λ ( f Λ ) ∥ f Λ ∥ L 2 ( M ) ≍ log Λ . In particular, the factor log Λ \sqrt{\log\Lambda} log Λ in the critical energy estimate cannot be replaced by a function that is o ( log Λ ) o(\sqrt{\log\Lambda}) o ( log Λ ) .
Proof. Let
S 1 ( Λ ) = ∑ 0 < λ j ≤ Λ 1 λ j and S 2 ( Λ ) = ∑ 0 < λ j ≤ Λ 1 λ j 2 . S_1(\Lambda)=\sum_{0<\lambda_j\leq\Lambda}\frac{1}{\lambda_j}
\quad\text{and}\quad
S_2(\Lambda)=\sum_{0<\lambda_j\leq\Lambda}\frac{1}{\lambda_j^2}. S 1 ( Λ ) = 0 < λ j ≤ Λ ∑ λ j 1 and S 2 ( Λ ) = 0 < λ j ≤ Λ ∑ λ j 2 1 .
The coefficient of e j e_j e j in f Λ f_\Lambda f Λ is 1 λ j \frac{1}{\lambda_j} λ j 1 for every positive eigenvalue below Λ \Lambda Λ , so ∥ f Λ ^ ∥ 1 = S 1 ( Λ ) \lVert\widehat{f_\Lambda}\rVert_1=S_1(\Lambda) ∥ f Λ ∥ 1 = S 1 ( Λ ) and ∥ f Λ ∥ L 2 ( M ) 2 = S 2 ( Λ ) \lVert f_\Lambda\rVert_{L^2(M)}^2=S_2(\Lambda) ∥ f Λ ∥ L 2 ( M ) 2 = S 2 ( Λ ) , and by the Dirichlet energy identity
∥ ∇ g f Λ ∥ L 2 ( M ) 2 = ∑ 0 < λ j ≤ Λ λ j ∣ 1 λ j ∣ 2 = S 1 ( Λ ) . \lVert\nabla_g f_\Lambda\rVert_{L^2(M)}^2=\sum_{0<\lambda_j\leq\Lambda}\lambda_j\left|\frac{1}{\lambda_j}\right|^2=S_1(\Lambda). ∥ ∇ g f Λ ∥ L 2 ( M ) 2 = 0 < λ j ≤ Λ ∑ λ j λ j 1 2 = S 1 ( Λ ) .
We now estimate the two sums. Weyl’s law in dimension two implies that λ j ≍ j \lambda_j\asymp j λ j ≍ j for the positive eigenvalues, once the index is sufficiently large, and that the number of eigenvalues below Λ \Lambda Λ is comparable to Λ \Lambda Λ . Therefore
S 1 ( Λ ) ≍ ∑ 1 ≤ j ≤ c Λ 1 j ≍ log Λ . S_1(\Lambda)\asymp\sum_{1\leq j\leq c\Lambda}\frac{1}{j}\asymp\log\Lambda. S 1 ( Λ ) ≍ 1 ≤ j ≤ c Λ ∑ j 1 ≍ log Λ.
On the other hand, the convergence of ∑ j = 1 ∞ 1 j 2 \sum_{j=1}^{\infty}\frac{1}{j^2} ∑ j = 1 ∞ j 2 1 shows that S 2 ( Λ ) S_2(\Lambda) S 2 ( Λ ) is bounded above independently of Λ \Lambda Λ , and it is bounded below by a positive constant because it contains the contribution of the first positive eigenvalue, so S 2 ( Λ ) ≍ 1 S_2(\Lambda)\asymp1 S 2 ( Λ ) ≍ 1 . We have shown that
F R Λ ( f Λ ) = S 1 ( Λ ) S 2 ( Λ ) ≍ log Λ FR_\Lambda(f_\Lambda)=\frac{S_1(\Lambda)}{\sqrt{S_2(\Lambda)}}\asymp\log\Lambda F R Λ ( f Λ ) = S 2 ( Λ ) S 1 ( Λ ) ≍ log Λ
and
∥ ∇ g f Λ ∥ L 2 ( M ) ∥ f Λ ∥ L 2 ( M ) = S 1 ( Λ ) S 2 ( Λ ) ≍ log Λ , \frac{\lVert\nabla_g f_\Lambda\rVert_{L^2(M)}}{\lVert f_\Lambda\rVert_{L^2(M)}}=\frac{\sqrt{S_1(\Lambda)}}{\sqrt{S_2(\Lambda)}}\asymp\sqrt{\log\Lambda}, ∥ f Λ ∥ L 2 ( M ) ∥ ∇ g f Λ ∥ L 2 ( M ) = S 2 ( Λ ) S 1 ( Λ ) ≍ log Λ ,
and dividing the first estimate by the second completes the proof. □
The sphere
On S 2 S^2 S 2 the eigenvalues are λ ℓ = ℓ ( ℓ + 1 ) \lambda_\ell=\ell(\ell+1) λ ℓ = ℓ ( ℓ + 1 ) with multiplicity 2 ℓ + 1 2\ell+1 2 ℓ + 1 , so the critical estimate can be written with an explicit constant. Here σ \sigma σ denotes the surface measure on S 2 S^2 S 2 , and ∥ f ∥ C 1 ( S 2 ) \|f\|_{C^1(S^2)} ∥ f ∥ C 1 ( S 2 ) is the maximum of the L ∞ L^\infty L ∞ norms of f f f and its spherical gradient.
Corollary 4.4. Let L ≥ 1 L\geq1 L ≥ 1 be an integer, let H L = V L ( L + 1 ) \mathcal{H}_L=\mathcal{V}_{L(L+1)} H L = V L ( L + 1 ) be the space of spherical harmonics of degree at most L L L on S 2 S^2 S 2 , and use the standard orthonormal basis { Y ℓ m } \{Y_\ell^m\} { Y ℓ m } . For every nonzero f ∈ H L f\in\mathcal{H}_L f ∈ H L ,
F R L ( L + 1 ) ( f ) ≤ 1 4 π ∣ ∫ S 2 f ( ω ) d σ ( ω ) ∣ ∥ f ∥ L 2 ( S 2 ) + 2 ( 1 + log L ) ∥ ∇ S 2 f ∥ L 2 ( S 2 ) ∥ f ∥ L 2 ( S 2 ) . \mathrm{FR}_{L(L+1)}(f)\leq\frac{1}{\sqrt{4\pi}}\frac{\left|\int_{S^2}f(\omega)\,d\sigma(\omega)\right|}{\|f\|_{L^2(S^2)}}+\sqrt{2(1+\log L)}\frac{\|\nabla_{S^2}f\|_{L^2(S^2)}}{\|f\|_{L^2(S^2)}}. FR L ( L + 1 ) ( f ) ≤ 4 π 1 ∥ f ∥ L 2 ( S 2 ) ∫ S 2 f ( ω ) d σ ( ω ) + 2 ( 1 + log L ) ∥ f ∥ L 2 ( S 2 ) ∥ ∇ S 2 f ∥ L 2 ( S 2 ) . In particular,
F R L ( L + 1 ) ( f ) ≤ 1 4 π ∣ ∫ S 2 f ( ω ) d σ ( ω ) ∣ ∥ f ∥ L 2 ( S 2 ) + 8 π ( 1 + log L ) ∥ f ∥ C 1 ( S 2 ) ∥ f ∥ L 2 ( S 2 ) . \mathrm{FR}_{L(L+1)}(f)\leq\frac{1}{\sqrt{4\pi}}\frac{\left|\int_{S^2}f(\omega)\,d\sigma(\omega)\right|}{\|f\|_{L^2(S^2)}}+\sqrt{8\pi(1+\log L)}\frac{\|f\|_{C^1(S^2)}}{\|f\|_{L^2(S^2)}}. FR L ( L + 1 ) ( f ) ≤ 4 π 1 ∥ f ∥ L 2 ( S 2 ) ∫ S 2 f ( ω ) d σ ( ω ) + 8 π ( 1 + log L ) ∥ f ∥ L 2 ( S 2 ) ∥ f ∥ C 1 ( S 2 ) . If f ≥ 0 f\geq0 f ≥ 0 and μ = ∫ S 2 f d σ > 0 \mu=\int_{S^2}f\,d\sigma>0 μ = ∫ S 2 f d σ > 0 , then
F R L ( L + 1 ) ( f ) ≤ 1 + 4 2 π ∥ f ∥ C 1 ( S 2 ) μ 1 + log L . \mathrm{FR}_{L(L+1)}(f)\leq1+4\sqrt{2}\pi\frac{\|f\|_{C^1(S^2)}}{\mu}\sqrt{1+\log L}. FR L ( L + 1 ) ( f ) ≤ 1 + 4 2 π μ ∥ f ∥ C 1 ( S 2 ) 1 + log L .
Proof. Write
f = ∑ ℓ = 0 L ∑ m = − ℓ ℓ f ^ ( ℓ , m ) Y ℓ m , f=\sum_{\ell=0}^{L}\sum_{m=-\ell}^{\ell}\widehat{f}(\ell,m)Y_\ell^m, f = ℓ = 0 ∑ L m = − ℓ ∑ ℓ f ( ℓ , m ) Y ℓ m ,
so that by orthonormality
∑ ℓ = 0 L ∑ m = − ℓ ℓ ∣ f ^ ( ℓ , m ) ∣ 2 = ∥ f ∥ L 2 ( S 2 ) 2 . \sum_{\ell=0}^{L}\sum_{m=-\ell}^{\ell}|\widehat{f}(\ell,m)|^2=\|f\|_{L^2(S^2)}^2. ℓ = 0 ∑ L m = − ℓ ∑ ℓ ∣ f ( ℓ , m ) ∣ 2 = ∥ f ∥ L 2 ( S 2 ) 2 .
The constant spherical harmonic is Y 0 0 = 1 4 π Y_0^0=\frac{1}{\sqrt{4\pi}} Y 0 0 = 4 π 1 , and hence
∣ f ^ ( 0 , 0 ) ∣ = 1 4 π ∣ ∫ S 2 f ( ω ) d σ ( ω ) ∣ . |\widehat{f}(0,0)|=\frac{1}{\sqrt{4\pi}}\left|\int_{S^2}f(\omega)\,d\sigma(\omega)\right|. ∣ f ( 0 , 0 ) ∣ = 4 π 1 ∫ S 2 f ( ω ) d σ ( ω ) .
For ℓ ≥ 1 \ell\geq1 ℓ ≥ 1 we insert the eigenvalue λ ℓ = ℓ ( ℓ + 1 ) \lambda_\ell=\ell(\ell+1) λ ℓ = ℓ ( ℓ + 1 ) and apply Cauchy–Schwarz to obtain
∑ ℓ = 1 L ∑ m = − ℓ ℓ ∣ f ^ ( ℓ , m ) ∣ = ∑ ℓ = 1 L ∑ m = − ℓ ℓ 1 λ ℓ λ ℓ ∣ f ^ ( ℓ , m ) ∣ ≤ ( ∑ ℓ = 1 L ∑ m = − ℓ ℓ 1 λ ℓ ) 1 2 ( ∑ ℓ = 1 L ∑ m = − ℓ ℓ λ ℓ ∣ f ^ ( ℓ , m ) ∣ 2 ) 1 2 . \begin{aligned}
\sum_{\ell=1}^{L}\sum_{m=-\ell}^{\ell}|\widehat{f}(\ell,m)|=\sum_{\ell=1}^{L}\sum_{m=-\ell}^{\ell}\frac{1}{\sqrt{\lambda_\ell}}\sqrt{\lambda_\ell}|\widehat{f}(\ell,m)| \\
&\leq\left(\sum_{\ell=1}^{L}\sum_{m=-\ell}^{\ell}\frac{1}{\lambda_\ell}\right)^{\frac{1}{2}}\left(\sum_{\ell=1}^{L}\sum_{m=-\ell}^{\ell}\lambda_\ell|\widehat{f}(\ell,m)|^2\right)^{\frac{1}{2}}.
\end{aligned} ℓ = 1 ∑ L m = − ℓ ∑ ℓ ∣ f ( ℓ , m ) ∣ = ℓ = 1 ∑ L m = − ℓ ∑ ℓ λ ℓ 1 λ ℓ ∣ f ( ℓ , m ) ∣ ≤ ( ℓ = 1 ∑ L m = − ℓ ∑ ℓ λ ℓ 1 ) 2 1 ( ℓ = 1 ∑ L m = − ℓ ∑ ℓ λ ℓ ∣ f ( ℓ , m ) ∣ 2 ) 2 1 .
The sum in the second factor is the spherical Dirichlet energy, which is to say that
∑ ℓ = 1 L ∑ m = − ℓ ℓ λ ℓ ∣ f ^ ( ℓ , m ) ∣ 2 = ∥ ∇ S 2 f ∥ L 2 ( S 2 ) 2 . \sum_{\ell=1}^{L}\sum_{m=-\ell}^{\ell}\lambda_\ell|\widehat{f}(\ell,m)|^2=\|\nabla_{S^2}f\|_{L^2(S^2)}^2. ℓ = 1 ∑ L m = − ℓ ∑ ℓ λ ℓ ∣ f ( ℓ , m ) ∣ 2 = ∥ ∇ S 2 f ∥ L 2 ( S 2 ) 2 .
As for the first factor, the multiplicity of the eigenvalue λ ℓ \lambda_\ell λ ℓ is 2 ℓ + 1 2\ell+1 2 ℓ + 1 , so
∑ ℓ = 1 L ∑ m = − ℓ ℓ 1 ℓ ( ℓ + 1 ) = ∑ ℓ = 1 L 2 ℓ + 1 ℓ ( ℓ + 1 ) = ∑ ℓ = 1 L ( 1 ℓ + 1 ℓ + 1 ) ≤ 2 ( 1 + log L ) . \sum_{\ell=1}^{L}\sum_{m=-\ell}^{\ell}\frac{1}{\ell(\ell+1)}=\sum_{\ell=1}^{L}\frac{2\ell+1}{\ell(\ell+1)}=\sum_{\ell=1}^{L}\left(\frac{1}{\ell}+\frac{1}{\ell+1}\right)\leq2(1+\log L). ℓ = 1 ∑ L m = − ℓ ∑ ℓ ℓ ( ℓ + 1 ) 1 = ℓ = 1 ∑ L ℓ ( ℓ + 1 ) 2 ℓ + 1 = ℓ = 1 ∑ L ( ℓ 1 + ℓ + 1 1 ) ≤ 2 ( 1 + log L ) .
Combining these identities and dividing by ∥ f ∥ L 2 ( S 2 ) \|f\|_{L^2(S^2)} ∥ f ∥ L 2 ( S 2 ) we obtain the first estimate. Since S 2 S^2 S 2 has surface area 4 π 4\pi 4 π , we have ∥ ∇ S 2 f ∥ L 2 ( S 2 ) ≤ 4 π ∥ f ∥ C 1 ( S 2 ) \|\nabla_{S^2}f\|_{L^2(S^2)}\leq\sqrt{4\pi}\|f\|_{C^1(S^2)} ∥ ∇ S 2 f ∥ L 2 ( S 2 ) ≤ 4 π ∥ f ∥ C 1 ( S 2 ) , which implies the second estimate. Finally, if f ≥ 0 f\geq0 f ≥ 0 , then μ ≤ 4 π ∥ f ∥ L 2 ( S 2 ) \mu\leq\sqrt{4\pi}\|f\|_{L^2(S^2)} μ ≤ 4 π ∥ f ∥ L 2 ( S 2 ) by Cauchy–Schwarz, and using this inequality in both terms we arrive at the final assertion. □
Sampling and reconstruction
We now combine the analytic bounds of the previous two sections with the effect of moving the sensors and with the recovery result from § 2 . A displacement of a sensor is first converted into a measurement error, and the Fourier ratio then bounds the approximation term in stable ℓ 1 \ell^1 ℓ 1 recovery. Partitions into cells of equal volume provide a separate description of the number of random sensors needed to occupy a prescribed number of cells. Whenever a ratio of norms of f f f occurs in this section, we assume that f f f is nonzero.
Sensor placement and random sensors on the square
5.1. Sensor placement and random sensors on the square. We begin by allowing the sampling location in each cell to vary independently. Such perturbations do not preserve the Fourier structure exactly, so it is better to regard them as measurement errors relative to the uniform grid.
Theorem 5.1. Let f ∈ C 1 ( [ 0 , 1 ] 2 ) f \in C^1([0,1]^2) f ∈ C 1 ([ 0 , 1 ] 2 ) be 1 1 1 -periodic, and define g ( x ) = f ( x N ) g(x)=f\left(\frac{x}{N}\right) g ( x ) = f ( N x ) for x ∈ Z N 2 x \in\mathbb{Z}_N^2 x ∈ Z N 2 . Let 0 ≤ δ ≤ 1 0 \le\delta\le1 0 ≤ δ ≤ 1 and let 1 ≤ q ≤ N 2 1 \le q \le N^2 1 ≤ q ≤ N 2 . For each x ∈ Z N 2 x \in\mathbb{Z}_N^2 x ∈ Z N 2 , choose t x ∈ [ 0 , δ ] 2 t_x \in[0,\delta]^2 t x ∈ [ 0 , δ ] 2 and define g t ( x ) = f ( x + t x N ) g_t(x)=f\left(\frac{x+t_x}{N}\right) g t ( x ) = f ( N x + t x ) . Then
∣ g t ( x ) − g ( x ) ∣ ≤ 2 δ N ∥ f ∥ C 1 ( [ 0 , 1 ] 2 ) . |g_t(x)-g(x)| \le\frac{2\delta}{N}\|f\|_{C^1([0,1]^2)}. ∣ g t ( x ) − g ( x ) ∣ ≤ N 2 δ ∥ f ∥ C 1 ([ 0 , 1 ] 2 ) . Consequently, for every set X ⊂ Z N 2 X \subset\mathbb{Z}_N^2 X ⊂ Z N 2 of cardinality q q q ,
( 1 q ∑ x ∈ X ∣ g t ( x ) − g ( x ) ∣ 2 ) 1 2 ≤ 2 δ N ∥ f ∥ C 1 ( [ 0 , 1 ] 2 ) . \left(\frac{1}{q}\sum_{x\in X}|g_t(x)-g(x)|^2\right)^{\frac{1}{2}} \le\frac{2\delta}{N}\|f\|_{C^1([0,1]^2)}. ( q 1 x ∈ X ∑ ∣ g t ( x ) − g ( x ) ∣ 2 ) 2 1 ≤ N 2 δ ∥ f ∥ C 1 ([ 0 , 1 ] 2 ) . In particular, this error is at most ε ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) \varepsilon\|f\|_{L^2([0,1]^2)} ε ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) whenever
δ ≤ ε N 2 ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) ∥ f ∥ C 1 ( [ 0 , 1 ] 2 ) . \delta\le\frac{\varepsilon N}{2}\frac{\|f\|_{L^2([0,1]^2)}}{\|f\|_{C^1([0,1]^2)}}. δ ≤ 2 εN ∥ f ∥ C 1 ([ 0 , 1 ] 2 ) ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) .
Proof. By the fundamental theorem of calculus,
g t ( x ) − g ( x ) = ∫ 0 1 ∇ f ( x + s t x N ) ⋅ t x N d s , g_t(x)-g(x)=\int_0^1 \nabla f\left(\frac{x+st_x}{N}\right)\cdot\frac{t_x}{N}\,ds, g t ( x ) − g ( x ) = ∫ 0 1 ∇ f ( N x + s t x ) ⋅ N t x d s ,
and since both coordinates of t x t_x t x are at most δ \delta δ ,
∣ g t ( x ) − g ( x ) ∣ ≤ δ N ( ∥ ∂ f ∂ x 1 ∥ L ∞ + ∥ ∂ f ∂ x 2 ∥ L ∞ ) , |g_t(x)-g(x)|\le\frac{\delta}{N}\left(\left\|\frac{\partial f}{\partial x_1}\right\|_{L^\infty}+\left\|\frac{\partial f}{\partial x_2}\right\|_{L^\infty}\right), ∣ g t ( x ) − g ( x ) ∣ ≤ N δ ( ∂ x 1 ∂ f L ∞ + ∂ x 2 ∂ f L ∞ ) ,
which proves the pointwise estimate. The averaged estimate and the final assertion follow at once. □
Corollary 5.2. If
N ≥ 2 ε ∥ f ∥ C 1 ( [ 0 , 1 ] 2 ) ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) , N\ge\frac{2}{\varepsilon}\frac{\|f\|_{C^1([0,1]^2)}}{\|f\|_{L^2([0,1]^2)}}, N ≥ ε 2 ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) ∥ f ∥ C 1 ([ 0 , 1 ] 2 ) , then the conclusion of Theorem 5.1 holds with error at most ε ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) \varepsilon\|f\|_{L^2([0,1]^2)} ε ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) for every choice t x ∈ [ 0 , 1 ) 2 t_x\in[0,1)^2 t x ∈ [ 0 , 1 ) 2 .
We complete our discussion of placement on the square by describing what happens when the sensors themselves are placed uniformly at random.
Theorem 5.3. Let f ∈ C 1 ( [ 0 , 1 ] 2 ) f \in C^1([0,1]^2) f ∈ C 1 ([ 0 , 1 ] 2 ) be periodic, and let Y 1 , Y 2 , … Y_1,Y_2,\ldots Y 1 , Y 2 , … be independent uniformly distributed points in [ 0 , 1 ) 2 [0,1)^2 [ 0 , 1 ) 2 . Let Z j ∈ Z N 2 Z_j\in\mathbb{Z}_N^2 Z j ∈ Z N 2 be the unique index such that Y j ∈ Q Z j Y_j\in Q_{Z_j} Y j ∈ Q Z j , where Q x = x N + [ 0 , N − 1 ) 2 Q_x=\frac{x}{N}+[0,N^{-1})^2 Q x = N x + [ 0 , N − 1 ) 2 is the grid cell indexed by x x x , and set X m = { Z 1 , … , Z m } X_m=\{Z_1,\ldots,Z_m\} X m = { Z 1 , … , Z m } . For 1 ≤ q ≤ N 2 1\le q\le N^2 1 ≤ q ≤ N 2 , define
T q = min { m ≥ 1 : ∣ X m ∣ = q } . T_q=\min\{m\ge1:|X_m|=q\}. T q = min { m ≥ 1 : ∣ X m ∣ = q } . Then
E [ T q ] = N 2 ( H N 2 − H N 2 − q ) , \mathbb{E}[T_q]=N^2(H_{N^2}-H_{N^2-q}), E [ T q ] = N 2 ( H N 2 − H N 2 − q ) ,
where H 0 = 0 H_0=0 H 0 = 0 and H k = ∑ j = 1 k 1 j H_k=\sum_{j=1}^{k}\frac{1}{j} H k = ∑ j = 1 k j 1 . Moreover, X T q X_{T_q} X T q is uniformly distributed among the q q q -element subsets of Z N 2 \mathbb{Z}_N^2 Z N 2 .
For each x ∈ X T q x\in X_{T_q} x ∈ X T q , use the first sensor that lands in Q x Q_x Q x , and denote its location by Y x Y_x Y x . If g t ( x ) = f ( Y x ) g_t(x)=f(Y_x) g t ( x ) = f ( Y x ) and g ( x ) = f ( x N ) g(x)=f\left(\frac{x}{N}\right) g ( x ) = f ( N x ) , then
( 1 q ∑ x ∈ X T q ∣ g t ( x ) − g ( x ) ∣ 2 ) 1 2 ≤ 2 N ∥ f ∥ C 1 ( [ 0 , 1 ] 2 ) . \left(\frac{1}{q}\sum_{x\in X_{T_q}}|g_t(x)-g(x)|^2\right)^{\frac{1}{2}}\leq\frac{2}{N}\|f\|_{C^1([0,1]^2)}. q 1 x ∈ X T q ∑ ∣ g t ( x ) − g ( x ) ∣ 2 2 1 ≤ N 2 ∥ f ∥ C 1 ([ 0 , 1 ] 2 ) .
Proof. Every cell has area 1 N 2 \frac{1}{N^2} N 2 1 , and since the points Y j Y_j Y j are independent and uniformly distributed, the cell indices Z j Z_j Z j are independent and uniform on Z N 2 \mathbb{Z}_N^2 Z N 2 . Suppose that k k k distinct cells have already been hit. There are N 2 − k N^2-k N 2 − k unoccupied cells, so the probability that the next sensor lands in a new cell is p k = N 2 − k N 2 p_k=\frac{N^2-k}{N^2} p k = N 2 N 2 − k . Let W k W_k W k be the number of additional sensors needed to move from k k k occupied cells to k + 1 k+1 k + 1 . Conditional on the cells already encountered, W k W_k W k has the geometric distribution with success probability p k p_k p k , and therefore
E [ W k ] = 1 p k = N 2 N 2 − k . \mathbb{E}[W_k]=\frac{1}{p_k}=\frac{N^2}{N^2-k}. E [ W k ] = p k 1 = N 2 − k N 2 .
Since T q = ∑ k = 0 q − 1 W k T_q=\sum_{k=0}^{q-1}W_k T q = ∑ k = 0 q − 1 W k , linearity of expectation implies that
E [ T q ] = ∑ k = 0 q − 1 N 2 N 2 − k = N 2 ∑ j = N 2 − q + 1 N 2 1 j = N 2 ( H N 2 − H N 2 − q ) . \mathbb{E}[T_q]=\sum_{k=0}^{q-1}\frac{N^2}{N^2-k}=N^2\sum_{j=N^2-q+1}^{N^2}\frac{1}{j}=N^2(H_{N^2}-H_{N^2-q}). E [ T q ] = k = 0 ∑ q − 1 N 2 − k N 2 = N 2 j = N 2 − q + 1 ∑ N 2 j 1 = N 2 ( H N 2 − H N 2 − q ) .
We now turn to the uniformity assertion. Let π \pi π be any permutation of the N 2 N^2 N 2 cells. The sequence π ( Z 1 ) , π ( Z 2 ) , … \pi(Z_1),\pi(Z_2),\ldots π ( Z 1 ) , π ( Z 2 ) , … has the same distribution as the original sequence, and if A A A and B B B are two q q q -element subsets, one can choose π \pi π with π ( A ) = B \pi(A)=B π ( A ) = B . It follows that P ( X T q = A ) = P ( X T q = B ) \mathbb{P}(X_{T_q}=A)=\mathbb{P}(X_{T_q}=B) P ( X T q = A ) = P ( X T q = B ) , and since the probabilities over all ( N 2 q ) \binom{N^2}{q} ( q N 2 ) possible sets sum to one,
P ( X T q = A ) = 1 ( N 2 q ) . \mathbb{P}(X_{T_q}=A)=\frac{1}{\binom{N^2}{q}}. P ( X T q = A ) = ( q N 2 ) 1 .
Finally, since Y x ∈ Q x Y_x\in Q_x Y x ∈ Q x , there is a vector t x ∈ [ 0 , 1 ) 2 t_x\in[0,1)^2 t x ∈ [ 0 , 1 ) 2 such that Y x = x + t x N Y_x=\frac{x+t_x}{N} Y x = N x + t x , namely the one with coordinates t x , j = N Y x , j − x j t_{x,j}=NY_{x,j}-x_j t x , j = N Y x , j − x j , and the last estimate is therefore Theorem 5.1 with δ = 1 \delta=1 δ = 1 . □
Remark 5.4. Theorem 5.3 provides the uniform random subset required by many discrete recovery theorems, together with a deterministic bound for the perturbation of the measurements. A particular recovery theorem may be applied after checking its requirement on the sample size and matching its data fidelity norm to the error bound above. We emphasize that the coupon collector argument does not by itself assert any recovery probability.
Recovery on the periodic square
We now put together the Fourier ratio estimate on the square, the placement bound, and Proposition 2.2. The theorem below uses independent grid indices sampled with replacement, whereas Theorem 5.3 describes a different model, in which one retains the first sensor in each of a prescribed number of distinct cells.
Theorem 5.5. Let f ∈ C 1 ( [ 0 , 1 ] 2 ) f\in C^1([0,1]^2) f ∈ C 1 ([ 0 , 1 ] 2 ) be nonzero and 1 1 1 -periodic, let N ≥ 2 N\geq2 N ≥ 2 , and fix t ∈ [ 0 , 1 ) 2 t\in[0,1)^2 t ∈ [ 0 , 1 ) 2 . Define g t ( x ) = f ( x + t N ) g_t(x)=f\left(\frac{x+t}{N}\right) g t ( x ) = f ( N x + t ) for x ∈ Z N 2 x\in\mathbb{Z}_N^2 x ∈ Z N 2 , assume that this sampled vector is nonzero, and suppose that F R ( g t ) ≤ r FR(g_t)\leq r F R ( g t ) ≤ r . Fix 0 < ε < 1 2 0<\varepsilon<\frac{1}{2} 0 < ε < 2 1 and γ ≥ 1 \gamma\geq1 γ ≥ 1 , and set
s = min { N 2 , ⌈ r 2 ε 2 ⌉ } . s=\min\left\{N^2,\left\lceil\frac{r^2}{\varepsilon^2}\right\rceil\right\}. s = min { N 2 , ⌈ ε 2 r 2 ⌉ } .
Choose X 1 , … , X q X_1,\ldots,X_q X 1 , … , X q independently and uniformly from Z N 2 \mathbb{Z}_N^2 Z N 2 . For each i i i , choose a vector u i ∈ [ 0 , 1 ) 2 u_i \in[0,1)^2 u i ∈ [ 0 , 1 ) 2 and observe
y i = f ( X i + t + u i N ) , y_i=f\left(\frac{X_i+t+u_i}{N}\right), y i = f ( N X i + t + u i ) ,
where the periodic extension of f f f is used if a point crosses the boundary of the unit square. Let g ∗ : Z N 2 → C g^*:\mathbb{Z}_N^2\to\mathbb{C} g ∗ : Z N 2 → C minimize ∥ h ^ ∥ 1 \|\widehat{h}\|_1 ∥ h ∥ 1 among all functions h : Z N 2 → C h:\mathbb{Z}_N^2\to\mathbb{C} h : Z N 2 → C satisfying
( 1 q ∑ i = 1 q ∣ h ( X i ) − y i ∣ 2 ) 1 2 ≤ 2 N ∥ f ∥ C 1 ( [ 0 , 1 ] 2 ) . \left(\frac{1}{q}\sum_{i=1}^{q}|h(X_i)-y_i|^2\right)^{\frac{1}{2}}\leq\frac{2}{N}\|f\|_{C^1([0,1]^2)}. ( q 1 i = 1 ∑ q ∣ h ( X i ) − y i ∣ 2 ) 2 1 ≤ N 2 ∥ f ∥ C 1 ([ 0 , 1 ] 2 ) .
There is a constant C γ C_\gamma C γ such that, if
q ≥ C γ s log 2 ( 2 s ) log ( 2 N 2 ) , q\geq C_\gamma s\log^2(2s)\log(2N^2), q ≥ C γ s log 2 ( 2 s ) log ( 2 N 2 ) ,
then, with probability at least 1 − 1 N 2 γ 1-\frac{1}{N^{2\gamma}} 1 − N 2 γ 1 ,
1 N ∥ g ∗ − g t ∥ 2 ≤ 3 ε N ∥ g t ∥ 2 + 10 N ∥ f ∥ C 1 ( [ 0 , 1 ] 2 ) . \frac{1}{N}\|g^*-g_t\|_2\leq\frac{3\varepsilon}{N}\|g_t\|_2+\frac{10}{N}\|f\|_{C^1([0,1]^2)}. N 1 ∥ g ∗ − g t ∥ 2 ≤ N 3 ε ∥ g t ∥ 2 + N 10 ∥ f ∥ C 1 ([ 0 , 1 ] 2 ) .
The probability is taken over the choice of the grid indices X i X_i X i , and the conclusion holds simultaneously for every choice of the displacement vectors u i u_i u i , including choices that depend on the sampled indices.
Proof. Equip Z N 2 \mathbb{Z}_N^2 Z N 2 with normalized counting measure and consider the characters ϕ m ( x ) = e 2 π i x ⋅ m N \phi_m(x)=e^{\frac{2\pi i x\cdot m}{N}} ϕ m ( x ) = e N 2 π i x ⋅ m , m ∈ Z N 2 m\in\mathbb{Z}_N^2 m ∈ Z N 2 . These characters form an orthonormal basis and satisfy ∣ ϕ m ( x ) ∣ = 1 |\phi_m(x)|=1 ∣ ϕ m ( x ) ∣ = 1 , so Proposition 2.2 applies with D = N 2 D=N^2 D = N 2 and K = 1 K=1 K = 1 . The coefficient of g t g_t g t relative to normalized counting measure is
a ( m ) = 1 N 2 ∑ x ∈ Z N 2 e − 2 π i x ⋅ m N g t ( x ) = 1 N g t ^ ( m ) , a(m)=\frac{1}{N^2}\sum_{x\in\mathbb{Z}_N^2}e^{-\frac{2\pi i x\cdot m}{N}}g_t(x)=\frac{1}{N}\widehat{g_t}(m), a ( m ) = N 2 1 x ∈ Z N 2 ∑ e − N 2 π i x ⋅ m g t ( x ) = N 1 g t ( m ) ,
and consequently
∥ a ∥ 1 ∥ a ∥ 2 = F R ( g t ) ≤ r and ∥ a ∥ 2 = 1 N ∥ g t ∥ 2 . \frac{\|a\|_1}{\|a\|_2}=FR(g_t)\leq r\quad\text{and}\quad\|a\|_2=\frac{1}{N}\|g_t\|_2. ∥ a ∥ 2 ∥ a ∥ 1 = F R ( g t ) ≤ r and ∥ a ∥ 2 = N 1 ∥ g t ∥ 2 .
The displacement of the i i i th sensor from its reference point is u i N \frac{u_i}{N} N u i , and the argument with the fundamental theorem of calculus used in the proof of Theorem 5.1 shows that
∣ y i − g t ( X i ) ∣ ≤ 2 N ∥ f ∥ C 1 ( [ 0 , 1 ] 2 ) . |y_i-g_t(X_i)|\leq\frac{2}{N}\|f\|_{C^1([0,1]^2)}. ∣ y i − g t ( X i ) ∣ ≤ N 2 ∥ f ∥ C 1 ([ 0 , 1 ] 2 ) .
Define the sampling matrix A i , m = 1 q ϕ m ( X i ) A_{i,m}=\frac{1}{\sqrt{q}}\phi_m(X_i) A i , m = q 1 ϕ m ( X i ) and normalize the observations by setting y ~ i = 1 q y i \widetilde{y}_i=\frac{1}{\sqrt{q}}y_i y i = q 1 y i . Then y ~ = A a + e \widetilde{y}=Aa+e y = A a + e , where
∥ e ∥ 2 ≤ 2 N ∥ f ∥ C 1 ( [ 0 , 1 ] 2 ) . \|e\|_2\leq\frac{2}{N}\|f\|_{C^1([0,1]^2)}. ∥ e ∥ 2 ≤ N 2 ∥ f ∥ C 1 ([ 0 , 1 ] 2 ) .
If s < N 2 s<N^2 s < N 2 , then the definition of s s s implies that
σ s ( a ) 1 s ≤ ∥ a ∥ 1 s ≤ ε ∥ a ∥ 2 , \frac{\sigma_s(a)_1}{\sqrt{s}}\leq\frac{\|a\|_1}{\sqrt{s}}\leq\varepsilon\|a\|_2, s σ s ( a ) 1 ≤ s ∥ a ∥ 1 ≤ ε ∥ a ∥ 2 ,
and if s = N 2 s=N^2 s = N 2 , then σ s ( a ) 1 = 0 \sigma_s(a)_1=0 σ s ( a ) 1 = 0 , so the same conclusion holds. By Proposition 2.2,
∥ a ∗ − a ∥ 2 ≤ 3 ε ∥ a ∥ 2 + 10 N ∥ f ∥ C 1 ( [ 0 , 1 ] 2 ) . \|a^*-a\|_2\leq3\varepsilon\|a\|_2+\frac{10}{N}\|f\|_{C^1([0,1]^2)}. ∥ a ∗ − a ∥ 2 ≤ 3 ε ∥ a ∥ 2 + N 10 ∥ f ∥ C 1 ([ 0 , 1 ] 2 ) .
The coefficient vector of a candidate h h h is 1 N h ^ \frac{1}{N}\widehat{h} N 1 h , and multiplying the objective by 1 N \frac{1}{N} N 1 does not change its minimizer, so a ∗ a^* a ∗ is the coefficient vector of g ∗ g^* g ∗ . Since ∥ a ∗ − a ∥ 2 = 1 N ∥ g ∗ − g t ∥ 2 \|a^*-a\|_2=\frac{1}{N}\|g^*-g_t\|_2 ∥ a ∗ − a ∥ 2 = N 1 ∥ g ∗ − g t ∥ 2 by Parseval’s identity for normalized counting measure, the proof is complete. □
Corollary 5.6. Let f ∈ C 1 ( [ 0 , 1 ] 2 ) f \in C^1([0,1]^2) f ∈ C 1 ([ 0 , 1 ] 2 ) be nonzero and 1 1 1 -periodic. There is a translation t ∈ [ 0 , 1 ) 2 t \in[0,1)^2 t ∈ [ 0 , 1 ) 2 for which Theorem 5.5 applies with
r = 1 + 1 2 1 + log N ∥ ∇ f ∥ L 2 ( [ 0 , 1 ] 2 ) ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) . r = 1 + \frac{1}{\sqrt{2}}\sqrt{1+\log N}\frac{\|\nabla f\|_{L^2([0,1]^2)}}{\|f\|_{L^2([0,1]^2)}}. r = 1 + 2 1 1 + log N ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) ∥∇ f ∥ L 2 ([ 0 , 1 ] 2 ) .
If the u i u_i u i are chosen independently and uniformly from [ 0 , 1 ) 2 [0,1)^2 [ 0 , 1 ) 2 , independently of the grid indices, then the physical sensor locations x i + t + u i N \frac{x_i+t+u_i}{N} N x i + t + u i are independent and uniformly distributed on the two-dimensional torus.
Proof. Choose the translation provided by Theorem 3.8 . Its Fourier ratio is at most the value of r r r in the statement, so Theorem 5.5 applies. For the last assertion, the sensor locations are interpreted modulo Z 2 \mathbb{Z}^2 Z 2 . The cells x + t N + [ 0 , N − 1 ) 2 \frac{x+t}{N}+[0,N^{-1})^2 N x + t + [ 0 , N − 1 ) 2 , indexed by all x ∈ Z N 2 x\in\mathbb{Z}_N^2 x ∈ Z N 2 and interpreted periodically, partition the torus and have equal area, so choosing a cell uniformly and then choosing a point uniformly inside it produces normalized Lebesgue measure on the whole torus. □
Corollary 5.7 (Piecewise constant reconstruction). Under the hypotheses of Theorem 5.5 , let
Q x , t = x + t N + [ 0 , N − 1 ) 2 for x ∈ Z N 2 , Q_{x,t}=\frac{x+t}{N}+[0,N^{-1})^2\quad\text{for }x\in\mathbb{Z}_N^2, Q x , t = N x + t + [ 0 , N − 1 ) 2 for x ∈ Z N 2 ,
with addition understood periodically, and define F ∗ F^* F ∗ to equal g ∗ ( x ) g^*(x) g ∗ ( x ) on Q x , t Q_{x,t} Q x , t . On the recovery event in that theorem,
∥ F ∗ − f ∥ L 2 ( [ 0 , 1 ] 2 ) ≤ 3 ε ∥ f ∥ L 2 ( [ 0 , 1 ] 2 ) + 12 + 6 ε N ∥ f ∥ C 1 ( [ 0 , 1 ] 2 ) . \|F^*-f\|_{L^2([0,1]^2)}\leq3\varepsilon\|f\|_{L^2([0,1]^2)}+\frac{12+6\varepsilon}{N}\|f\|_{C^1([0,1]^2)}. ∥ F ∗ − f ∥ L 2 ([ 0 , 1 ] 2 ) ≤ 3 ε ∥ f ∥ L 2 ([ 0 , 1 ] 2 ) + N 12 + 6 ε ∥ f ∥ C 1 ([ 0 , 1 ] 2 ) .
Proof. Let G t G_t G t equal g t ( x ) g_t(x) g t ( x ) on Q x , t Q_{x,t} Q x , t . Each cell has area N − 2 N^{-2} N − 2 , so
∥ F ∗ − G t ∥ L 2 = 1 N ∥ g ∗ − g t ∥ 2 and ∥ G t ∥ L 2 = 1 N ∥ g t ∥ 2 , \|F^*-G_t\|_{L^2}=\frac{1}{N}\|g^*-g_t\|_2\quad\text{and}\quad\|G_t\|_{L^2}=\frac{1}{N}\|g_t\|_2, ∥ F ∗ − G t ∥ L 2 = N 1 ∥ g ∗ − g t ∥ 2 and ∥ G t ∥ L 2 = N 1 ∥ g t ∥ 2 ,
and the fundamental theorem of calculus inside each cell shows that ∥ G t − f ∥ L 2 ≤ 2 N ∥ f ∥ C 1 \|G_t-f\|_{L^2}\leq\frac{2}{N}\|f\|_{C^1} ∥ G t − f ∥ L 2 ≤ N 2 ∥ f ∥ C 1 . We now apply the triangle inequality and Theorem 5.5 . The approximation term satisfies
3 ε N ∥ g t ∥ 2 ≤ 3 ε ∥ f ∥ L 2 + 6 ε N ∥ f ∥ C 1 , \frac{3\varepsilon}{N}\|g_t\|_2\leq3\varepsilon\|f\|_{L^2}+\frac{6\varepsilon}{N}\|f\|_{C^1}, N 3 ε ∥ g t ∥ 2 ≤ 3 ε ∥ f ∥ L 2 + N 6 ε ∥ f ∥ C 1 ,
and the result follows. □
Sensor stability on compact manifolds
We now turn to compact manifolds. Write d g d_g d g for the geodesic distance on M M M , and for f ∈ C 1 ( M ) f\in C^1(M) f ∈ C 1 ( M ) let
∥ f ∥ C 1 ( M ) = max { ∥ f ∥ L ∞ ( M ) , ∥ ∇ g f ∥ L ∞ ( M ) } . \|f\|_{C^1(M)}=\max\{\|f\|_{L^\infty(M)},\|\nabla_g f\|_{L^\infty(M)}\}. ∥ f ∥ C 1 ( M ) = max { ∥ f ∥ L ∞ ( M ) , ∥ ∇ g f ∥ L ∞ ( M ) } .
The statements below apply to real or complex valued functions.
Proposition 5.8. Let ( M , g ) (M,g) ( M , g ) be a connected compact Riemannian manifold without boundary, and let f f f be a nonzero function in C 1 ( M ) C^1(M) C 1 ( M ) . Let q ≥ 1 q\geq1 q ≥ 1 , let x 1 , … , x q x_1,\ldots,x_q x 1 , … , x q be reference sensor locations and y 1 , … , y q y_1,\ldots,y_q y 1 , … , y q perturbed sensor locations satisfying d g ( x i , y i ) ≤ δ d_g(x_i,y_i)\leq\delta d g ( x i , y i ) ≤ δ for i = 1 , … , q i=1,\ldots,q i = 1 , … , q , and define g ( x i ) = f ( x i ) g(x_i)=f(x_i) g ( x i ) = f ( x i ) and g t ( x i ) = f ( y i ) g_t(x_i)=f(y_i) g t ( x i ) = f ( y i ) . Then
∣ g t ( x i ) − g ( x i ) ∣ ≤ δ ∥ f ∥ C 1 ( M ) |g_t(x_i)-g(x_i)|\leq\delta\|f\|_{C^1(M)} ∣ g t ( x i ) − g ( x i ) ∣ ≤ δ ∥ f ∥ C 1 ( M ) for every i i i , and
( ∣ M ∣ q ∑ i = 1 q ∣ g t ( x i ) − g ( x i ) ∣ 2 ) 1 2 ≤ ∣ M ∣ 1 2 δ ∥ f ∥ C 1 ( M ) . \left(\frac{|M|}{q}\sum_{i=1}^{q}|g_t(x_i)-g(x_i)|^2\right)^{\frac{1}{2}}\leq|M|^{\frac{1}{2}}\delta\|f\|_{C^1(M)}. ( q ∣ M ∣ i = 1 ∑ q ∣ g t ( x i ) − g ( x i ) ∣ 2 ) 2 1 ≤ ∣ M ∣ 2 1 δ ∥ f ∥ C 1 ( M ) .
Proof. Join x i x_i x i to y i y_i y i by a minimizing geodesic γ i : [ 0 , ℓ i ] → M \gamma_i:[0,\ell_i]\to M γ i : [ 0 , ℓ i ] → M parameterized by arclength. Since ℓ i = d g ( x i , y i ) ≤ δ \ell_i=d_g(x_i,y_i)\le\delta ℓ i = d g ( x i , y i ) ≤ δ , the fundamental theorem of calculus along γ i \gamma_i γ i shows that
f ( y i ) − f ( x i ) = ∫ 0 ℓ i ⟨ ∇ g f ( γ i ( s ) ) , γ i ′ ( s ) ⟩ g d s f(y_i)-f(x_i)=\int_{0}^{\ell_i}\langle\nabla_g f(\gamma_i(s)),\gamma_i'(s)\rangle_g\,ds f ( y i ) − f ( x i ) = ∫ 0 ℓ i ⟨ ∇ g f ( γ i ( s )) , γ i ′ ( s ) ⟩ g d s
and since ∣ γ i ′ ( s ) ∣ g = 1 |\gamma_i'(s)|_g=1 ∣ γ i ′ ( s ) ∣ g = 1 ,
∣ f ( y i ) − f ( x i ) ∣ ≤ ℓ i ∥ ∇ g f ∥ L ∞ ( M ) ≤ δ ∥ f ∥ C 1 ( M ) . |f(y_i)-f(x_i)|\le\ell_i\|\nabla_g f\|_{L^\infty(M)}\le\delta\|f\|_{C^1(M)}. ∣ f ( y i ) − f ( x i ) ∣ ≤ ℓ i ∥ ∇ g f ∥ L ∞ ( M ) ≤ δ ∥ f ∥ C 1 ( M ) .
The second assertion follows by squaring this estimate, summing over i i i , multiplying by ∣ M ∣ q \frac{|M|}{q} q ∣ M ∣ , and taking the square root. □ \square □
This estimate can be read as a tolerance condition on how far the actual sensors may move if the total measurement error is to be kept at a prescribed relative scale.
Corollary 5.9. Under the hypotheses of Proposition 5.8 , if
δ ≤ ε ∥ f ∥ L 2 ( M ) ∣ M ∣ 1 2 ∥ f ∥ C 1 ( M ) \delta\le\frac{\varepsilon\|f\|_{L^2(M)}}{|M|^{\frac{1}{2}}\|f\|_{C^1(M)}} δ ≤ ∣ M ∣ 2 1 ∥ f ∥ C 1 ( M ) ε ∥ f ∥ L 2 ( M ) then
( ∣ M ∣ q ∑ i = 1 q ∣ g t ( x i ) − g ( x i ) ∣ 2 ) 1 2 ≤ ε ∥ f ∥ L 2 ( M ) . \left(\frac{|M|}{q}\sum_{i=1}^{q}|g_t(x_i)-g(x_i)|^2\right)^{\frac{1}{2}}\le\varepsilon\|f\|_{L^2(M)}. ( q ∣ M ∣ i = 1 ∑ q ∣ g t ( x i ) − g ( x i ) ∣ 2 ) 2 1 ≤ ε ∥ f ∥ L 2 ( M ) . Proof. This follows by substituting the assumed upper bound for δ \delta δ into Proposition 5.8 . □ \square □
If a sensor is only known to lie in the same cell as its intended location, then the diameter of the cell can be used as the displacement parameter.
Corollary 5.10. Let ( M , g ) (M,g) ( M , g ) , f f f , x i x_i x i , y i y_i y i , g g g , and g t g_t g t be as in Proposition 5.8 . Suppose that x i , y i ∈ Q i ⊂ M x_i,y_i\in Q_i\subset M x i , y i ∈ Q i ⊂ M and diam g ( Q i ) ≤ h \operatorname{diam}_g(Q_i)\le h diam g ( Q i ) ≤ h for every i i i . Then d g ( x i , y i ) ≤ h d_g(x_i,y_i)\le h d g ( x i , y i ) ≤ h . Consequently, if
h ≤ ε ∥ f ∥ L 2 ( M ) ∣ M ∣ 1 2 ∥ f ∥ C 1 ( M ) , h\le\frac{\varepsilon\|f\|_{L^2(M)}}{|M|^{\frac{1}{2}}\|f\|_{C^1(M)}}, h ≤ ∣ M ∣ 2 1 ∥ f ∥ C 1 ( M ) ε ∥ f ∥ L 2 ( M ) , then
( ∣ M ∣ q ∑ i = 1 q ∣ g t ( x i ) − g ( x i ) ∣ 2 ) 1 2 ≤ ε ∥ f ∥ L 2 ( M ) . \left(\frac{|M|}{q}\sum_{i=1}^{q}|g_t(x_i)-g(x_i)|^2\right)^{\frac{1}{2}}\le\varepsilon\|f\|_{L^2(M)}. ( q ∣ M ∣ i = 1 ∑ q ∣ g t ( x i ) − g ( x i ) ∣ 2 ) 2 1 ≤ ε ∥ f ∥ L 2 ( M ) . Proof. Since x i , y i ∈ Q i x_i,y_i\in Q_i x i , y i ∈ Q i , we have d g ( x i , y i ) ≤ diam g ( Q i ) ≤ h d_g(x_i,y_i)\le\operatorname{diam}_g(Q_i)\le h d g ( x i , y i ) ≤ diam g ( Q i ) ≤ h , and the conclusion follows from Proposition 5.8 with δ = h \delta=h δ = h and the assumed upper bound for h h h . □ \square □
If the cells come from a partition into K K K pieces whose diameters decay at the natural rate K − 1 d K^{-\frac{1}{d}} K − d 1 , then the same condition can be stated as a lower bound on the number of cells.
Corollary 5.11. Assume the hypotheses of Corollary 5.10 . Suppose further that M M M has dimension d d d and that there exist A > 0 A>0 A > 0 and a positive integer K K K such that diam g ( Q i ) ≤ A K − 1 d \operatorname{diam}_g(Q_i)\le AK^{-\frac{1}{d}} diam g ( Q i ) ≤ A K − d 1 for every i i i . If
K ≥ ( A ∣ M ∣ 1 2 ∥ f ∥ C 1 ( M ) ε ∥ f ∥ L 2 ( M ) ) d , K\ge\left(\frac{A|M|^{\frac{1}{2}}\|f\|_{C^1(M)}}{\varepsilon\|f\|_{L^2(M)}}\right)^d, K ≥ ( ε ∥ f ∥ L 2 ( M ) A ∣ M ∣ 2 1 ∥ f ∥ C 1 ( M ) ) d , then
( ∣ M ∣ q ∑ i = 1 q ∣ g t ( x i ) − g ( x i ) ∣ 2 ) 1 2 ≤ ε ∥ f ∥ L 2 ( M ) . \left(\frac{|M|}{q}\sum_{i=1}^{q}|g_t(x_i)-g(x_i)|^2\right)^{\frac{1}{2}}\le\varepsilon\|f\|_{L^2(M)}. ( q ∣ M ∣ i = 1 ∑ q ∣ g t ( x i ) − g ( x i ) ∣ 2 ) 2 1 ≤ ε ∥ f ∥ L 2 ( M ) .
Proof. The assumed lower bound for K K K implies that
A K − 1 / d ≤ ε ∥ f ∥ L 2 ( M ) ∣ M ∣ 1 / 2 ∥ f ∥ C 1 ( M ) , AK^{-1/d} \le\frac{\varepsilon\|f\|_{L^2(M)}}{|M|^{1/2}\|f\|_{C^1(M)}}, A K − 1/ d ≤ ∣ M ∣ 1/2 ∥ f ∥ C 1 ( M ) ε ∥ f ∥ L 2 ( M ) ,
and the conclusion follows from Corollary 5.10 . □
Just as on the square, partitions into cells of equal volume allow us to pass from uniformly random physical sensors to uniformly random subsets of reference cells.
Theorem 5.12. Let ( M , g ) (M,g) ( M , g ) be a connected compact Riemannian manifold without boundary, and let Q 1 , … , Q K Q_1,\ldots,Q_K Q 1 , … , Q K be a measurable partition of M M M satisfying ∣ Q k ∣ = ∣ M ∣ K |Q_k|=\frac{|M|}{K} ∣ Q k ∣ = K ∣ M ∣ for every k k k . Choose a representative point x k ∈ Q k x_k\in Q_k x k ∈ Q k . Let Y 1 , Y 2 , … Y_1,Y_2,\ldots Y 1 , Y 2 , … be independent uniformly distributed random sensor locations on M M M with respect to normalized Riemannian volume, and let Z j Z_j Z j be the unique index such that Y j ∈ Q Z j Y_j\in Q_{Z_j} Y j ∈ Q Z j . For 1 ≤ q ≤ K 1\le q\le K 1 ≤ q ≤ K , define
X m = { Z 1 , … , Z m } and T q = min { m ≥ 1 : ∣ X m ∣ = q } . X_m=\{Z_1,\ldots,Z_m\}\quad\text{and}\quad T_q=\min\{m\ge1:|X_m|=q\}. X m = { Z 1 , … , Z m } and T q = min { m ≥ 1 : ∣ X m ∣ = q } . Then
E [ T q ] = K ( H K − H K − q ) , \mathbb{E}[T_q]=K(H_K-H_{K-q}), E [ T q ] = K ( H K − H K − q ) , where H 0 = 0 H_0=0 H 0 = 0 and H k = ∑ j = 1 k 1 j H_k=\sum_{j=1}^{k}\frac{1}{j} H k = ∑ j = 1 k j 1 , and X T q X_{T_q} X T q is uniformly distributed among the q q q -element subsets of { 1 , … , K } \{1,\ldots,K\} { 1 , … , K } .
Suppose further that diam g ( Q k ) ≤ h K \operatorname{diam}_g(Q_k)\le h_K diam g ( Q k ) ≤ h K for every k k k . Fix 1 ≤ q r e c ≤ K 1\le q_{\mathrm{rec}}\le K 1 ≤ q rec ≤ K , write T r e c = T q r e c T_{\mathrm{rec}}=T_{q_{\mathrm{rec}}} T rec = T q rec , and, for each k ∈ X T r e c k\in X_{T_{\mathrm{rec}}} k ∈ X T rec , let Y k ∗ Y_k^* Y k ∗ denote the first sensor to land in Q k Q_k Q k . If f ∈ C 1 ( M ) f\in C^1(M) f ∈ C 1 ( M ) , g ( k ) = f ( x k ) g(k)=f(x_k) g ( k ) = f ( x k ) , and g t ( k ) = f ( Y k ∗ ) g_t(k)=f(Y_k^*) g t ( k ) = f ( Y k ∗ ) , then
( ∣ M ∣ q r e c ∑ k ∈ X T r e c ∣ g t ( k ) − g ( k ) ∣ 2 ) 1 / 2 ≤ ∣ M ∣ 1 / 2 h K ∥ f ∥ C 1 ( M ) . \left(\frac{|M|}{q_{\mathrm{rec}}}\sum_{k\in X_{T_{\mathrm{rec}}}}|g_t(k)-g(k)|^2\right)^{1/2}\le|M|^{1/2}h_K\|f\|_{C^1(M)}. q rec ∣ M ∣ k ∈ X T rec ∑ ∣ g t ( k ) − g ( k ) ∣ 2 1/2 ≤ ∣ M ∣ 1/2 h K ∥ f ∥ C 1 ( M ) . In particular, the placement error is at most ε ∥ f ∥ L 2 ( M ) \varepsilon\|f\|_{L^2(M)} ε ∥ f ∥ L 2 ( M ) whenever
h K ≤ ε ∥ f ∥ L 2 ( M ) ∣ M ∣ 1 / 2 ∥ f ∥ C 1 ( M ) . h_K\le\frac{\varepsilon\|f\|_{L^2(M)}}{|M|^{1/2}\|f\|_{C^1(M)}}. h K ≤ ∣ M ∣ 1/2 ∥ f ∥ C 1 ( M ) ε ∥ f ∥ L 2 ( M ) . Proof. The hypothesis that the cells have equal volume implies that
P ( Z j = k ) = ∣ Q k ∣ ∣ M ∣ = 1 K , \mathbb{P}(Z_j=k)=\frac{|Q_k|}{|M|}=\frac{1}{K}, P ( Z j = k ) = ∣ M ∣ ∣ Q k ∣ = K 1 , so the cell indices are independent and uniformly distributed. The coupon collector calculation in the proof of Theorem 5.3 then shows that E [ T q ] = K ( H K − H K − q ) \mathbb{E}[T_q]=K(H_K-H_{K-q}) E [ T q ] = K ( H K − H K − q ) , and invariance under permutations of the cell labels shows that X T q X_{T_q} X T q is uniformly distributed among the q q q -element subsets. For k ∈ X T r e c k\in X_{T_{\mathrm{rec}}} k ∈ X T rec , both x k x_k x k and Y k ∗ Y_k^* Y k ∗ belong to Q k Q_k Q k , so d g ( x k , Y k ∗ ) ≤ diam g ( Q k ) ≤ h K d_g(x_k,Y_k^*)\le\operatorname{diam}_g(Q_k)\le h_K d g ( x k , Y k ∗ ) ≤ diam g ( Q k ) ≤ h K , and Proposition 5.8 implies that
∣ g t ( k ) − g ( k ) ∣ ≤ h K ∥ f ∥ C 1 ( M ) . |g_t(k)-g(k)|\le h_K\|f\|_{C^1(M)}. ∣ g t ( k ) − g ( k ) ∣ ≤ h K ∥ f ∥ C 1 ( M ) . The placement estimate follows by squaring, summing over the occupied cells, multiplying by ∣ M ∣ q r e c \frac{|M|}{q_{\mathrm{rec}}} q rec ∣ M ∣ , and taking the square root, and the final assertion follows from the condition on h K h_K h K . □
Sensors on the sphere
On the sphere the geodesic placement estimate takes a particularly simple form, and a partition into cells of equal area leads to the same coupon collector description of random physical sensors as on the square. We write d S 2 d_{S^2} d S 2 for the geodesic distance on S 2 S^2 S 2 .
Proposition 5.13. Let f ∈ C 1 ( S 2 ) f \in C^1(S^2) f ∈ C 1 ( S 2 ) and q ≥ 1 q \ge1 q ≥ 1 , and let ω 1 , … , ω q \omega_1,\ldots,\omega_q ω 1 , … , ω q and ω 1 , t , … , ω q , t \omega_{1,t},\ldots,\omega_{q,t} ω 1 , t , … , ω q , t be two collections of sensor locations satisfying d S 2 ( ω i , t , ω i ) ≤ δ d_{S^2}(\omega_{i,t},\omega_i) \le\delta d S 2 ( ω i , t , ω i ) ≤ δ for every i i i . Then
∣ f ( ω i , t ) − f ( ω i ) ∣ ≤ δ ∥ f ∥ C 1 ( S 2 ) |f(\omega_{i,t})-f(\omega_i)| \le\delta\|f\|_{C^1(S^2)} ∣ f ( ω i , t ) − f ( ω i ) ∣ ≤ δ ∥ f ∥ C 1 ( S 2 ) and
( 4 π q ∑ i = 1 q ∣ f ( ω i , t ) − f ( ω i ) ∣ 2 ) 1 2 ≤ 4 π δ ∥ f ∥ C 1 ( S 2 ) . \left(\frac{4\pi}{q}\sum_{i=1}^{q}|f(\omega_{i,t})-f(\omega_i)|^2\right)^{\frac{1}{2}} \le\sqrt{4\pi}\delta\|f\|_{C^1(S^2)}. ( q 4 π i = 1 ∑ q ∣ f ( ω i , t ) − f ( ω i ) ∣ 2 ) 2 1 ≤ 4 π δ ∥ f ∥ C 1 ( S 2 ) . Thus the relative placement error is bounded by
4 π ∥ f ∥ C 1 ( S 2 ) ∥ f ∥ L 2 ( S 2 ) . \sqrt{4\pi}\frac{\|f\|_{C^1(S^2)}}{\|f\|_{L^2(S^2)}}. 4 π ∥ f ∥ L 2 ( S 2 ) ∥ f ∥ C 1 ( S 2 ) .
Proof. This is Proposition 5.8 with M = S 2 M=S^2 M = S 2 and ∣ M ∣ = 4 π |M|=4\pi ∣ M ∣ = 4 π .
Corollary 5.14. Suppose Q 1 , … , Q q ⊂ S 2 Q_1,\ldots,Q_q \subset S^2 Q 1 , … , Q q ⊂ S 2 satisfy diam S 2 ( Q i ) ≤ A N \operatorname{diam}_{S^2}(Q_i) \le\frac{A}{N} diam S 2 ( Q i ) ≤ N A . If ω i , ω i , t ∈ Q i \omega_i,\omega_{i,t} \in Q_i ω i , ω i , t ∈ Q i , then d S 2 ( ω i , t , ω i ) ≤ A N d_{S^2}(\omega_{i,t},\omega_i) \le\frac{A}{N} d S 2 ( ω i , t , ω i ) ≤ N A . Consequently, the averaged placement error in Proposition 5.13 is at most ε ∥ f ∥ L 2 ( S 2 ) \varepsilon\|f\|_{L^2(S^2)} ε ∥ f ∥ L 2 ( S 2 ) whenever
N ≥ A 4 π ε ∥ f ∥ C 1 ( S 2 ) ∥ f ∥ L 2 ( S 2 ) . N \ge\frac{A\sqrt{4\pi}}{\varepsilon}\frac{\|f\|_{C^1(S^2)}}{\|f\|_{L^2(S^2)}}. N ≥ ε A 4 π ∥ f ∥ L 2 ( S 2 ) ∥ f ∥ C 1 ( S 2 ) .
Theorem 5.15. Let f ∈ C 1 ( S 2 ) f \in C^1(S^2) f ∈ C 1 ( S 2 ) , and let Q 1 , … , Q K Q_1,\ldots,Q_K Q 1 , … , Q K be a measurable partition of S 2 S^2 S 2 such that σ ( Q k ) = 4 π K \sigma(Q_k)=\frac{4\pi}{K} σ ( Q k ) = K 4 π for every k = 1 , … , K k=1,\ldots,K k = 1 , … , K , and choose a representative point ω k ∈ Q k \omega_k \in Q_k ω k ∈ Q k for each cell. Let Y 1 , Y 2 , … Y_1,Y_2,\ldots Y 1 , Y 2 , … be independent uniformly distributed random sensor locations on S 2 S^2 S 2 . For j ≥ 1 j \ge1 j ≥ 1 , let Z j ∈ { 1 , … , K } Z_j \in\{1,\ldots,K\} Z j ∈ { 1 , … , K } be the unique cell index such that Y j ∈ Q Z j Y_j \in Q_{Z_j} Y j ∈ Q Z j , and define X m = { Z 1 , … , Z m } X_m=\{Z_1,\ldots,Z_m\} X m = { Z 1 , … , Z m } . For 1 ≤ q ≤ K 1 \le q \le K 1 ≤ q ≤ K , set T q = min { m ≥ 1 : ∣ X m ∣ = q } T_q=\min\{m\ge1:|X_m|=q\} T q = min { m ≥ 1 : ∣ X m ∣ = q } . Then
E [ T q ] = K ( H K − H K − q ) , \mathbb{E}[T_q]=K(H_K-H_{K-q}), E [ T q ] = K ( H K − H K − q ) , where H 0 = 0 H_0=0 H 0 = 0 and H k = ∑ j = 1 k 1 j H_k=\sum_{j=1}^{k}\frac{1}{j} H k = ∑ j = 1 k j 1 . Moreover, X T q X_{T_q} X T q is uniformly distributed among the q q q -element subsets of { 1 , … , K } \{1,\ldots,K\} { 1 , … , K } .
Suppose further that diam S 2 ( Q k ) ≤ h K \operatorname{diam}_{S^2}(Q_k) \le h_K diam S 2 ( Q k ) ≤ h K for every k k k . Fix 1 ≤ q r e c ≤ K 1 \le q_{\mathrm{rec}} \le K 1 ≤ q rec ≤ K , write T r e c = T q r e c T_{\mathrm{rec}}=T_{q_{\mathrm{rec}}} T rec = T q rec , and, for each k ∈ X T r e c k \in X_{T_{\mathrm{rec}}} k ∈ X T rec , let Y k ∗ Y_k^* Y k ∗ denote the first sensor location to land in Q k Q_k Q k . If g ( k ) = f ( ω k ) g(k)=f(\omega_k) g ( k ) = f ( ω k ) and g t ( k ) = f ( Y k ∗ ) g_t(k)=f(Y_k^*) g t ( k ) = f ( Y k ∗ ) , then
( 4 π q r e c ∑ k ∈ X T r e c ∣ g t ( k ) − g ( k ) ∣ 2 ) 1 2 ≤ 4 π h K ∥ f ∥ C 1 ( S 2 ) . \left(\frac{4\pi}{q_{\mathrm{rec}}}\sum_{k\in X_{T_{\mathrm{rec}}}}|g_t(k)-g(k)|^2\right)^{\frac{1}{2}} \le\sqrt{4\pi}h_K\|f\|_{C^1(S^2)}. q rec 4 π k ∈ X T rec ∑ ∣ g t ( k ) − g ( k ) ∣ 2 2 1 ≤ 4 π h K ∥ f ∥ C 1 ( S 2 ) . In particular, this placement error is at most ε ∥ f ∥ L 2 ( S 2 ) \varepsilon\|f\|_{L^2(S^2)} ε ∥ f ∥ L 2 ( S 2 ) whenever
h K ≤ ε ∥ f ∥ L 2 ( S 2 ) 4 π ∥ f ∥ C 1 ( S 2 ) . h_K \le\frac{\varepsilon\|f\|_{L^2(S^2)}}{\sqrt{4\pi}\|f\|_{C^1(S^2)}}. h K ≤ 4 π ∥ f ∥ C 1 ( S 2 ) ε ∥ f ∥ L 2 ( S 2 ) .
Proof. This follows by applying Theorem 5.12 to the given partition of S 2 S^2 S 2 , since the normalized surface measure assigns probability 1 K \frac{1}{K} K 1 to each cell and ∣ S 2 ∣ = 4 π |S^2|=4\pi ∣ S 2 ∣ = 4 π .
Recovery in the Laplace–Beltrami eigenbasis
The results above control the sensor locations themselves. We now return to the Laplace–Beltrami eigenbasis and combine this control with the Fourier ratio bounds of § 4 and with Proposition 2.2 . For the spectral space V Λ V_\Lambda V Λ , let
K Λ = ∣ M ∣ 1 2 sup λ j ≤ Λ ∥ e j ∥ L ∞ ( M ) . K_\Lambda= |M|^{\frac{1}{2}} \sup_{\lambda_j \le\Lambda} \|e_j\|_{L^\infty(M)}. K Λ = ∣ M ∣ 2 1 λ j ≤ Λ sup ∥ e j ∥ L ∞ ( M ) .
The functions ϕ j = ∣ M ∣ 1 2 e j \phi_j = |M|^{\frac{1}{2}}e_j ϕ j = ∣ M ∣ 2 1 e j form an orthonormal system in L 2 ( M , 1 ∣ M ∣ d V g ) L^2(M,\frac{1}{|M|}dV_g) L 2 ( M , ∣ M ∣ 1 d V g ) , and K Λ K_\Lambda K Λ is the boundedness parameter of this normalized system.
Theorem 5.16. Let f ∈ V Λ f \in V_\Lambda f ∈ V Λ be nonzero and suppose that F R Λ ( f ) ≤ r FR_\Lambda(f) \le r F R Λ ( f ) ≤ r . Fix 0 < ε < 1 2 0 < \varepsilon< \frac{1}{2} 0 < ε < 2 1 and γ ≥ 1 \gamma\ge1 γ ≥ 1 , and set
s = min { D Λ , ⌈ r 2 ε 2 ⌉ } . s = \min\left\{D_\Lambda,\left\lceil\frac{r^2}{\varepsilon^2}\right\rceil\right\}. s = min { D Λ , ⌈ ε 2 r 2 ⌉ } . Let x 1 , … , x q x_1,\ldots,x_q x 1 , … , x q be independent random points chosen according to the normalized Riemannian measure. Suppose that the observations have the form y i = f ( x i ) + ξ i y_i=f(x_i)+\xi_i y i = f ( x i ) + ξ i and satisfy
( ∣ M ∣ q ∑ i = 1 q ∣ ξ i ∣ 2 ) 1 2 ≤ η . \left(\frac{|M|}{q}\sum_{i=1}^{q}|\xi_i|^2\right)^{\frac{1}{2}} \le\eta. ( q ∣ M ∣ i = 1 ∑ q ∣ ξ i ∣ 2 ) 2 1 ≤ η . Let f ∗ ∈ V Λ f^* \in V_\Lambda f ∗ ∈ V Λ minimize ∥ h ^ ∥ 1 \|\widehat{h}\|_1 ∥ h ∥ 1 among all h ∈ V Λ h \in V_\Lambda h ∈ V Λ satisfying
( ∣ M ∣ q ∑ i = 1 q ∣ h ( x i ) − y i ∣ 2 ) 1 2 ≤ η . \left(\frac{|M|}{q}\sum_{i=1}^{q}|h(x_i)-y_i|^2\right)^{\frac{1}{2}} \le\eta. ( q ∣ M ∣ i = 1 ∑ q ∣ h ( x i ) − y i ∣ 2 ) 2 1 ≤ η . There is a constant C γ C_\gamma C γ such that, if
q ≥ C γ K Λ 2 s log 2 ( 2 s K Λ 2 ) log ( 2 D Λ ) , q \ge C_\gamma K_\Lambda^2s\log^2(2sK_\Lambda^2)\log(2D_\Lambda), q ≥ C γ K Λ 2 s log 2 ( 2 s K Λ 2 ) log ( 2 D Λ ) , then, with probability at least 1 − 1 D Λ γ 1-\frac{1}{D_\Lambda^\gamma} 1 − D Λ γ 1 ,
∥ f ∗ − f ∥ L 2 ( M ) ≤ 3 ε ∥ f ∥ L 2 ( M ) + 5 η . \|f^*-f\|_{L^2(M)} \le3\varepsilon\|f\|_{L^2(M)}+5\eta. ∥ f ∗ − f ∥ L 2 ( M ) ≤ 3 ε ∥ f ∥ L 2 ( M ) + 5 η .
Proof. Write f = ∑ λ j ≤ Λ a j ϕ j f=\sum_{\lambda_j\le\Lambda}a_j\phi_j f = ∑ λ j ≤ Λ a j ϕ j . Since ϕ j = ∣ M ∣ 1 2 e j \phi_j=|M|^{\frac{1}{2}}e_j ϕ j = ∣ M ∣ 2 1 e j , comparison with the original eigenfunction expansion shows that a j = 1 ∣ M ∣ f ^ ( j ) a_j=\frac{1}{\sqrt{|M|}}\widehat{f}(j) a j = ∣ M ∣ 1 f ( j ) . The common factor cancels from the ratio of the coefficient norms, so the coefficient vector satisfies
∥ a ∥ 1 ∥ a ∥ 2 = F R Λ ( f ) ≤ r . \frac{\|a\|_1}{\|a\|_2}=FR_\Lambda(f)\le r. ∥ a ∥ 2 ∥ a ∥ 1 = F R Λ ( f ) ≤ r .
If s < D Λ s<D_\Lambda s < D Λ , the definition of s s s and the elementary bound σ s ( a ) 1 ≤ ∥ a ∥ 1 \sigma_s(a)_1\le\|a\|_1 σ s ( a ) 1 ≤ ∥ a ∥ 1 imply that
σ s ( a ) 1 s ≤ ∥ a ∥ 1 s ≤ ε ∥ a ∥ 2 , \frac{\sigma_s(a)_1}{\sqrt{s}}\le\frac{\|a\|_1}{\sqrt{s}}\le\varepsilon\|a\|_2, s σ s ( a ) 1 ≤ s ∥ a ∥ 1 ≤ ε ∥ a ∥ 2 ,
and if s = D Λ s=D_\Lambda s = D Λ , then σ s ( a ) 1 = 0 \sigma_s(a)_1=0 σ s ( a ) 1 = 0 , so the same conclusion holds. Consider the sampling matrix A i j = 1 q ϕ j ( x i ) A_{ij}=\frac{1}{\sqrt{q}}\phi_j(x_i) A ij = q 1 ϕ j ( x i ) , so that the vector A a Aa A a has entries 1 q f ( x i ) \frac{1}{\sqrt{q}}f(x_i) q 1 f ( x i ) . We normalize the observations and the noise by setting y ~ i = 1 q y i \widetilde{y}_i=\frac{1}{\sqrt{q}}y_i y i = q 1 y i and e i = 1 q ξ i e_i=\frac{1}{\sqrt{q}}\xi_i e i = q 1 ξ i . Then y ~ = A a + e \widetilde{y}=Aa+e y = A a + e , and the hypothesis on the noise in physical space implies that
∥ e ∥ 2 = ( 1 q ∑ i = 1 q ∣ ξ i ∣ 2 ) 1 2 ≤ 1 ∣ M ∣ η . \|e\|_2=\left(\frac{1}{q}\sum_{i=1}^{q}|\xi_i|^2\right)^{\frac{1}{2}}\le\frac{1}{\sqrt{|M|}}\eta. ∥ e ∥ 2 = ( q 1 i = 1 ∑ q ∣ ξ i ∣ 2 ) 2 1 ≤ ∣ M ∣ 1 η .
The data fidelity constraint in the theorem is therefore exactly the constraint in Proposition 2.2 , with noise tolerance 1 ∣ M ∣ η \frac{1}{\sqrt{|M|}}\eta ∣ M ∣ 1 η . Moreover, ∥ h ^ ∥ 1 = ∣ M ∣ 1 2 ∥ b ∥ 1 \|\widehat{h}\|_1=|M|^{\frac{1}{2}}\|b\|_1 ∥ h ∥ 1 = ∣ M ∣ 2 1 ∥ b ∥ 1 , where b b b is the coefficient vector of h h h in the ϕ j \phi_j ϕ j basis, and multiplication of the objective by the fixed positive number ∣ M ∣ 1 2 |M|^{\frac{1}{2}} ∣ M ∣ 2 1 does not change its minimizer. It follows from Proposition 2.2 that
∥ a ∗ − a ∥ 2 ≤ 3 σ s ( a ) 1 s + 5 ∣ M ∣ η , \lVert a^* - a\rVert_2 \le3\frac{\sigma_s(a)_1}{\sqrt{s}} + \frac{5}{\sqrt{|M|}}\eta, ∥ a ∗ − a ∥ 2 ≤ 3 s σ s ( a ) 1 + ∣ M ∣ 5 η ,
where a ∗ a^* a ∗ is the coefficient vector of f ∗ f^* f ∗ . Since the ϕ j \phi_j ϕ j are orthonormal for the normalized measure,
∥ a ∥ 2 = 1 ∣ M ∣ ∥ f ∥ L 2 ( M ) , \lVert a\rVert_2 = \frac{1}{\sqrt{|M|}}\lVert f\rVert_{L^2(M)}, ∥ a ∥ 2 = ∣ M ∣ 1 ∥ f ∥ L 2 ( M ) ,
and the same scaling relates ∥ a ∗ − a ∥ 2 \lVert a^* - a\rVert_2 ∥ a ∗ − a ∥ 2 to ∥ f ∗ − f ∥ L 2 ( M ) \lVert f^* - f\rVert_{L^2(M)} ∥ f ∗ − f ∥ L 2 ( M ) . The theorem follows by substituting the approximation estimate.
Corollary 5.17 (Explicit relative error). Let f ∈ V Λ f \in V_\Lambda f ∈ V Λ be nonzero and suppose FR Λ ( f ) ≤ r \operatorname{FR}_\Lambda(f) \le r FR Λ ( f ) ≤ r . Fix 0 < ε < 1 2 0 < \varepsilon< \frac{1}{2} 0 < ε < 2 1 and γ ≥ 1 \gamma\ge1 γ ≥ 1 , and set
s = min { D Λ , ⌈ r 2 ε 2 ⌉ } . s = \min\left\{D_\Lambda,\left\lceil\frac{r^2}{\varepsilon^2}\right\rceil\right\}. s = min { D Λ , ⌈ ε 2 r 2 ⌉ } . Choose x 1 , … , x q x_1,\ldots,x_q x 1 , … , x q independently according to normalized Riemannian measure, and let f ∗ ∈ V Λ f^* \in V_\Lambda f ∗ ∈ V Λ minimize ∥ h ^ ∥ 1 \lVert\widehat{h}\rVert_1 ∥ h ∥ 1 subject to
( ∣ M ∣ q ∑ i = 1 q ∣ h ( x i ) − f ( x i ) ∣ 2 ) 1 2 ≤ ε ∥ f ∥ L 2 ( M ) . \left(\frac{|M|}{q}\sum_{i=1}^{q}|h(x_i)-f(x_i)|^2\right)^{\frac{1}{2}} \le\varepsilon\lVert f\rVert_{L^2(M)}. ( q ∣ M ∣ i = 1 ∑ q ∣ h ( x i ) − f ( x i ) ∣ 2 ) 2 1 ≤ ε ∥ f ∥ L 2 ( M ) . There is a constant C γ C_\gamma C γ such that, if
q ≥ C γ K Λ 2 s log 2 ( 2 s K Λ 2 ) log ( 2 D Λ ) , q \ge C_\gamma K_\Lambda^2s\log^2(2sK_\Lambda^2)\log(2D_\Lambda), q ≥ C γ K Λ 2 s log 2 ( 2 s K Λ 2 ) log ( 2 D Λ ) , then, with probability at least 1 − 1 D Λ γ 1-\frac{1}{D_\Lambda^\gamma} 1 − D Λ γ 1 ,
∥ f ∗ − f ∥ L 2 ( M ) ≤ 8 ε ∥ f ∥ L 2 ( M ) . \lVert f^*-f\rVert_{L^2(M)} \le8\varepsilon\lVert f\rVert_{L^2(M)}. ∥ f ∗ − f ∥ L 2 ( M ) ≤ 8 ε ∥ f ∥ L 2 ( M ) .
Proof. We apply Theorem 5.16 with ξ i = 0 \xi_i=0 ξ i = 0 and η = ε ∥ f ∥ L 2 ( M ) \eta=\varepsilon\lVert f\rVert_{L^2(M)} η = ε ∥ f ∥ L 2 ( M ) . The zero noise satisfies this tolerance, the reconstruction constraint is the one in the statement, and the two error terms in the theorem are bounded by 3 ε ∥ f ∥ L 2 ( M ) 3\varepsilon\lVert f\rVert_{L^2(M)} 3 ε ∥ f ∥ L 2 ( M ) and 5 ε ∥ f ∥ L 2 ( M ) 5\varepsilon\lVert f\rVert_{L^2(M)} 5 ε ∥ f ∥ L 2 ( M ) , respectively.
Corollary 5.18. Assume the hypotheses of Theorem 5.16. After choosing the reference points x 1 , … , x q x_1,\ldots,x_q x 1 , … , x q , suppose the actual sensor locations x 1 , t , … , x q , t x_{1,t},\ldots,x_{q,t} x 1 , t , … , x q , t satisfy d g ( x i , t , x i ) ≤ δ d_g(x_{i,t},x_i)\le\delta d g ( x i , t , x i ) ≤ δ and that the observations are y i = f ( x i , t ) y_i=f(x_{i,t}) y i = f ( x i , t ) . Use the data fidelity tolerance
η = ∣ M ∣ δ ∥ ∇ g f ∥ L ∞ ( M ) . \eta=\sqrt{|M|}\delta\lVert\nabla_g f\rVert_{L^\infty(M)}. η = ∣ M ∣ δ ∥ ∇ g f ∥ L ∞ ( M ) . If
q ≥ C γ K Λ 2 s log 2 ( 2 s K Λ 2 ) log ( 2 D Λ ) , q \ge C_\gamma K_\Lambda^2s\log^2(2sK_\Lambda^2)\log(2D_\Lambda), q ≥ C γ K Λ 2 s log 2 ( 2 s K Λ 2 ) log ( 2 D Λ ) , then, with probability at least 1 − 1 D Λ γ 1-\frac{1}{D_\Lambda^\gamma} 1 − D Λ γ 1 ,
∥ f ∗ − f ∥ L 2 ( M ) ≤ 3 ε ∥ f ∥ L 2 ( M ) + 5 ∣ M ∣ δ ∥ ∇ g f ∥ L ∞ ( M ) . \lVert f^*-f\rVert_{L^2(M)} \le3\varepsilon\lVert f\rVert_{L^2(M)}+5\sqrt{|M|}\delta\lVert\nabla_g f\rVert_{L^\infty(M)}. ∥ f ∗ − f ∥ L 2 ( M ) ≤ 3 ε ∥ f ∥ L 2 ( M ) + 5 ∣ M ∣ δ ∥ ∇ g f ∥ L ∞ ( M ) . The conclusion holds simultaneously for every choice of the displaced points satisfying the stated distance bound.
Proof. Joining x i x_i x i to x i , t x_{i,t} x i , t by a minimizing geodesic and applying the fundamental theorem of calculus along that geodesic, we see that
∣ f ( x i , t ) − f ( x i ) ∣ ≤ δ ∥ ∇ g f ∥ L ∞ ( M ) , |f(x_{i,t})-f(x_i)|\le\delta\lVert\nabla_g f\rVert_{L^\infty(M)}, ∣ f ( x i , t ) − f ( x i ) ∣ ≤ δ ∥ ∇ g f ∥ L ∞ ( M ) ,
and consequently
( ∣ M ∣ q ∑ i = 1 q ∣ f ( x i , t ) − f ( x i ) ∣ 2 ) 1 2 ≤ ∣ M ∣ δ ∥ ∇ g f ∥ L ∞ ( M ) . \left(\frac{|M|}{q}\sum_{i=1}^{q}\left|f(x_{i,t})-f(x_i)\right|^2\right)^{\frac{1}{2}} \leq\sqrt{|M|}\delta\|\nabla_g f\|_{L^\infty(M)}. ( q ∣ M ∣ i = 1 ∑ q ∣ f ( x i , t ) − f ( x i ) ∣ 2 ) 2 1 ≤ ∣ M ∣ δ ∥ ∇ g f ∥ L ∞ ( M ) .
The conclusion is therefore exactly Theorem 5.16 with this value of η \eta η .
Corollary 5.19. Let f ∈ V Λ f\in V_\Lambda f ∈ V Λ be nonzero. For s 0 > 0 s_0>0 s 0 > 0 , define
r Λ , s 0 ( f ) = 1 ∣ M ∣ ∣ ∫ M f ( x ) d V g ( x ) ∣ ∥ f ∥ L 2 ( M ) + ( ∑ 0 < λ j ≤ Λ 1 λ j s 0 ) 1 2 ∥ ( − Δ g ) s 0 2 f ∥ L 2 ( M ) ∥ f ∥ L 2 ( M ) . r_{\Lambda,s_0}(f)=\frac{1}{\sqrt{|M|}}\frac{\left|\int_M f(x)\mathrm{d}V_g(x)\right|}{\|f\|_{L^2(M)}}+\left(\sum_{0<\lambda_j\leq\Lambda}\frac{1}{\lambda_j^{s_0}}\right)^{\frac{1}{2}}\frac{\|(-\Delta_g)^{\frac{s_0}{2}}f\|_{L^2(M)}}{\|f\|_{L^2(M)}}. r Λ , s 0 ( f ) = ∣ M ∣ 1 ∥ f ∥ L 2 ( M ) ∫ M f ( x ) d V g ( x ) + 0 < λ j ≤ Λ ∑ λ j s 0 1 2 1 ∥ f ∥ L 2 ( M ) ∥ ( − Δ g ) 2 s 0 f ∥ L 2 ( M ) .
Then F R Λ ( f ) ≤ r Λ , s 0 ( f ) FR_\Lambda(f)\leq r_{\Lambda,s_0}(f) F R Λ ( f ) ≤ r Λ , s 0 ( f ) . Consequently, Theorem 5.16 and Corollary 5.17 apply with r = r Λ , s 0 ( f ) r=r_{\Lambda,s_0}(f) r = r Λ , s 0 ( f ) .
Proof. The inequality F R Λ ( f ) ≤ r Λ , s 0 ( f ) FR_\Lambda(f)\leq r_{\Lambda,s_0}(f) F R Λ ( f ) ≤ r Λ , s 0 ( f ) is the first estimate of Proposition 4.1 with s = s 0 s=s_0 s = s 0 .
Remark 5.20. The factor K Λ 2 K_\Lambda^2 K Λ 2 measures the concentration of the selected eigenfunctions through their supremum norms, and on manifolds where eigenfunctions concentrate strongly the resulting sample bound may be large. For the standard spherical harmonic basis on S 2 S^2 S 2 one has K Λ 2 ≍ Λ 1 2 K_\Lambda^2\asymp\Lambda^{\frac{1}{2}} K Λ 2 ≍ Λ 2 1 as Λ → ∞ \Lambda\to\infty Λ → ∞ , or equivalently K L ( L + 1 ) 2 ≍ L K_{L(L+1)}^2\asymp L K L ( L + 1 ) 2 ≍ L for maximum degree L L L , where the lower bound comes from the zonal harmonics and the upper bound from the addition formula. Weighted sampling and preconditioning can improve this dependence on the sphere and on certain surfaces of revolution, as shown by Burq, Dyatlov, Ward, and Zworski [4 ] , whereas the theorem above uses uniform sampling and the chosen eigenbasis.
Concluding remarks
All the estimates in this paper come from the same energy calculation. On Z N d \mathbb{Z}_N^d Z N d , the dimension and the number of controlled differences determine whether the inverse frequency weights are summable, logarithmically divergent, or polynomially divergent. In dimension two, one derivative is critical and leaves a square-root logarithm, for Hölder exponents below one the differences chosen separately on each frequency annulus remove the logarithmic loss, and with two derivatives the bound is independent of the grid size.
A common translation allows us to compare the discrete difference energy with the continuous energy without imposing a lower bound on the grid size, and averaging the zero coefficient as well retains the continuous mean. The translation that we select may depend on the function, so the problem of finding a favorable grid from limited observations is a separate question. On a compact surface, the coefficients 1 λ j \frac{1}{\lambda_j} λ j 1 show that the critical square-root logarithm is necessary when the right-hand side is measured by the L 2 L^2 L 2 norm of the gradient, but additional regularity may improve the Fourier ratio, as the estimate with two derivatives on the square already shows.
Separate sensor displacements enter the reconstruction theorems as measurement noise. On the square we recover the sampled vector, and the piecewise constant extension controls the L 2 L^2 L 2 error on the torus, while on a manifold we reconstruct a function in a prescribed finite spectral space. In both cases the error bound consists of a contribution from spectral approximation and a contribution from placement accuracy. For uniform point sampling on a general manifold, the suprema of the chosen eigenfunctions remain in the sample count. Weighted sampling or a different eigenbasis may reduce this dependence, but any such change must also keep track of the Fourier ratio in the chosen basis.
Acknowledgments
The authors gratefully acknowledge support from Williams College and the National Science Foundation under Grant No. DMS-2241623 through the SMALL Undergraduate Research Program at Williams College.
References
Department of Mathematics, Virginia Tech, Blacksburg, VA 24061 Email address: nicoalbert@vt.edu
Department of Mathematics, Missouri State University, Springfield, MO 65897 Email address: christopherlancehousholder@gmail.com
Department of Mathematics, University of Rochester, Rochester, NY 14627 Email address: alex.iosevich@rochester.edu
Department of Mathematics, Williams College, Williamstown, MA 01267 Email address: sjm1@williams.edu
Department of Mathematics, Virginia Tech, Blacksburg, VA 24061 Email address: palsson@vt.edu