{'fraction_non_alphanumeric': 0.05781063914251687, 'fraction_numerical': 0.018558951965065504, 'mean_word_length': 3.784662867996201, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 16, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The approximation of almost time and band limited functions by their expansion in some orthogonal polynomials bases

The aim of this paper is to investigate the quality of approximation of almost time and almost band-limited functions by its expansion in three classical orthogonal polynomials bases: the Hermite, Legendre and Chebyshev bases. As a corollary, this allows us to obtain the quality of approximation in the L 2 --Sobolev space by these orthogonal polynomials bases. Also, we obtain the rate of the Legendre series expansion of the prolate spheroidal wave functions. Some numerical examples are given to illustrate the different results of this work.


Introduction
Time-limited functions and band-limited functions play a fundamental role in signal and image processing. The time-limiting assumption is natural as a signal can only be measured over a finite duration. The band-limiting assumption is natural as well due to channel capacity limitations. It is also essential to apply sampling theory. Unfortunately, the simplest form of the uncertainty principle tells us that a signal can not be simultaneously time and band limited. A natural assumption is thus that a signal is almost time-and almost band-limited in the following sense: Definition. Let T, Ω > 0 and ε T , ε Ω > 0. A function f ∈ L 2 (R) is said to be Here and throughout this paper the Fourier transform is normalized so that, for f ∈ L 1 (R), Of course, given f ∈ L 2 (R), for every ε T , ε Ω > 0 there exist T, Ω > 0 such that f is ε T -almost time limited to [−T, T ] and ε Ω -almost time limited to [−Ω, Ω]. The point here is that we consider T, Ω, ε T , ε Ω as fixed parameters. A typical example we have in mind is that f ∈ H s (R) and is time-limited to [−T, T ]. Such an hypothesis is common in tomography, see e.g. [14], where it is required in the proof of the convergence of the filtered back-projection algorithm for approximate inversion of the Radon transform. But, if f ∈ H s (R) with s > 0, that is if (1 + |Ω|) 2s .
An alternative to the back projection algorithms in tomography are the Algebraic Reconstruction Techniques (that is variants of Kaczmarz algorithm, see [14]). For those algorithms to work well it is crucial to have a good representing system (basis, frame...) of the functions that one wants to reconstruct.
Thanks to the seminal work of Landau, Pollak and Slepian, the optimal orthogonal system for representing almost time and band limited functions is known. The system in questions consists of the so called prolate spheroidal wave functions, ψ T k , and has many valuable properties (see [16,10,11,17,18]). Among the most striking properties they have is that, if a function is almost time limited to [−T, T ] and almost band limited to [−Ω, Ω] then it is well approximated by its projection on the first 4ΩT terms of the basis: For more details, see [10]. This is a remarkable fact as this is exactly the heuristics given by Shannon's sampling formula (note that to make this heuristics clearer, the functions are usually almost time-limited to [−T /2, T /2] and this result is then known as the 2ΩT -Theorem, see [10]). However, there is a major difficulty with prolate spheroidal wave functions that has attracted a lot of interest recently, namely the difficulty to compute them as there is no inductive nor closed form formula (see e.g. [2,3,4,13,21]). One approach is to explicitly compute the coefficients of the prolate spheroidal wave functions in terms of a basis of orthogonal polynomials like the Legendre polynomials or the Hermite functions basis. The question that then arises is that of directly approximating almost time and band limited functions by the (truncation of) their expansion in the Hermite, Legendre and Chebyshev bases. This is the question we address here.
An other motivation for this work comes from the work of the first author [8] on uncertainty principles for orthonormal bases. There, it is shown that an orthonormal basis (e k ) of L 2 (R) can not have uniform time-frequency localization. Several ways of measuring localization were considered, and for most of them, the Hermite functions provided the optimal behavior. However, in one case, the proof relied on (1.1): this shows that the set of functions that are ε T -time limited to [−T, T ] and ε Ω -band limited to [−Ω, Ω] is almost of dimension 4ΩT . In particular, this set can not contain more than a fixed number of elements of an orthonormal sequence. As this proof shows, the optimal basis here consists of prolate spheroidal wave functions. As the Hermite basis is optimal for many uncertainty principles, it is thus natural to ask how far it is from optimal in this case.
Let us now be more precise and describe the main results of the paper. In Section 2, we first give a brief description of the asymptotic approximation of the Hermite functions in terms of the sine and cosine functions. Then, we use the asymptotic behaviour of the Hermite function and give an error analysis of the uniform approximation of the Hermite function projection kernel k n (x, y) = n k=0 h k (x)h k (y) by an appropriate Sinc kernel. Here, h k denotes the k−th L 2 -normalized Hermite function. Then, based on the previous asymptotic approximation of the Hermite kernel, we give the quality of almost time-and band-limited functions by Hermite functions. In Section 3, we use the explicit formula for the finite Fourier transform of the Legendre polynomials in terms of the Bessel function and give the convergence rate of the Legendre series expansion of a c−band-limited function. Then, we extend this result to the case of almost time-and band-limited function. In Section 4, we show the results obtained for the Legendre polynomials to the case of Chebyshev polynomials. Section 5 is divided into two parts. In the first part, we first give an application of the results of Section 3 related to the convergence rate of the Legendre series expansion of the prolate spheroidal wave functions (PSWFs). Note that for a given bandwidth c > 0, and an integer n ≥ 0, the n−th PSWF, denoted by ψ n,c is a c−band-limited function, given as the n−th eigenfunction of a compact integral operator Q c , defined on L 2 ([−1, 1]) with the sinc kernel K c (x, y) = sin c(x − y) π(x − y) . In the second part of Section 5, we give various numerical examples that illustrate the different results of this work.

Approximation of almost band limited functions by Hermite functions basis.
In this section, we study the quality of approximation of band limited and almost band limited functions by the Hermite and scaled Hermite functions. For this purpose, we first need to review the asymptotic uniform approximation of the Hermite functions by the sine and cosine functions. This is the subject of the following paragraph.
2.1. Approximating Hermite functions with the WKB method. Let H n be the n-th Hermite polynomial, that is Define the Hermite functions as As is well known: (i) (h n ) n≥0 is an orthonormal basis of L 2 (R).
(ii) h n is even if n is even and odd if n is odd, in particular h 2p (0) = 0 and h 2p+1 (0) = 0. Further (iii) h n satisfies the differential equation h n (x) + (2n + 1 − x 2 )h n (x) = 0. We will now follow the WKB method to obtain an approximation of h n . In order to simplify notation, we will fix n and drop all supscripts during the computation. Let h = h n , λ = √ 2n + 1, and define for |x| < λ Note that ψ ± have been chosen to have Let us now define Integrating the previous differential equation between 0 and x, we obtain the system .
It remains to solve this system for h to obtain the principal term of h: Then, for |x| ≤ λ, Remark. One may explicitly compute ϕ: Also, ϕ n has a geometric interpretation: it this the area of the intersection of a disc of radius √ 2n + 1 centered at 0 with the strip [0, x] × R + . In particular, when x → √ 2n + 1, ϕ n (x) ∼ π 4 (2n + 1). The result is not entirely new (e.g. [5,6,9,12,15]), except for the Lipschitz bounds of E. Therefore we will only sketch the proof of this theorem in Appendix A.
Using standard asymptotic of h 2p (0) and of h 2p+1 (0) and the fact that √ λ 2 − x 2 λ when λ → ∞, one may further simplify this result to the following: Corollary 2.2. Let T ≥ 2 and let n ≥ 2T 2 . Then, for |x| ≤ T , we obtain that -if n is even, n = 2p where, for |x|, |y| ≤ T , To conclude, we will gather some facts about ϕ n that all follow from easy calculus.
2.2. The kernel of the projection onto the Hermite functions. As (h n ) n≥0 forms an orthonormal basis of L 2 (R), every f ∈ L 2 (R) can be written as where the limit is in the L 2 (R) sense. Further, for n an integer, let K n f be the orthogonal projection of f on the span of h 0 , . . . , h n . Then We will now use Corollary 2.2 to approximate this kernel: . Then, for |x|, |y| ≤ T , Remark. The same estimate holds for T = 1 provided n ≥ 6. Moreover, we should mention that in practice, the actual approximation error of the kernel is much smaller than the theoretical error R n . See example 1 in the numerical results section that illustrate this fact.
Again, the only improvement over known results [15,19] is in the estimate of R n . We will therefore only sketch the proof in Appendix B.

Approximating almost time and band limited functions by Hermite functions.
We can now prove the following theorem.
Assume that n ≥ max(2T 2 , 2Ω 2 ). Then, for T ≥ T 0 , Proof. We will introduce several projections. For T, Ω > 0, let The hypothesis on f is that for Ω ≥ Ω 0 . Let us also define the integral operator It is enough to prove (2.14) for T = T 0 . We may then reformulate Theorem 2.4 as following: . Note that N ≥ Ω 0 . By using (2.4), it is easy to see that Here we use the well known fact that the Hilbert-Schmidt norm of an integral operator is the L 2 norm of its kernel. Now, using the fact that projections are contractive and N ≥ Ω 0 , we have Therefore, Remark. The error estimate given by (2.14) is not practical due to the low decay rate of the bound of R T n given by By replacing this with a non explicit but a more realistic error estimate R T n HS , one gets the following error estimate which is more practical for numerical purposes,

2.4.
Approximating almost time and band limited functions by scaled Hermite functions. For α > 0 and f ∈ L 2 (R) we define the scaling operator Next, define the scaled Hermite basis h α k = δ α h k which is also an orthonormal basis of L 2 (R) and define the corresponding orthogonal projections: for f ∈ L 2 (R), Proposition 2.6. Let α > 0, T ≥ 2 and c ≥ 2/α. Assume that and Then, for n ≥ max(2(T /α) 2 , 2c 2 ), we have Remark. The scaling with α > 1 has as effect to decrease the dependence on T at the price of increasing the dependence on good frequency concentration, while taking α < 1 the gain and loss are reversed. In practice, the above dependence on T is very pessimistic and α > 1 is a better choice. The most natural choice is α = T and c = T Ω where Ω is such that f is ε Ω -almost band limited to [−Ω, Ω].
Proof. For f ∈ L 2 (R), since K α n is contractive, we have From this, one easily deduces that and, noting that It remains to apply Theorem 2.5 to complete the proof.

Approximation of almost band limited functions in the basis of Legendre polynomials
In agreement with standard practice, we will denote by P k the classical Legendre polynomials, defined by the three-term recursion with the initial conditions P 0 (x) = 1, P 1 (x) = x.
In the sequel, for c > 0, let B c denote the Paley-Wiener space of c-bandlimited functions, given by x . Note that j k has same parity as n and recall that, for where J α is the Bessel function of the first kind. In particular, we have the well known bound for x ∈ R From this we deduce that Now, since f ∈ B c , the Fourier inversion theorem implies that, for x ∈ R, we have Combining (3.20) and (3.23), one gets Using (3.22) together with Cauchy-Schwarz and a change of variable, one gets Finally, Parseval's identity implies (3.19).
Let us now introduce the following orthogonal projections on L 2 (R): Note that L N is the orthogonal projection onto the subspace of L 2 (R) consisting of functions of the P (x)1 (−1,1) with P a polynomial of degree ≤ N .
The proof of the L 2 -bound is essentially the same: From this (3.25) easily follows when N ≥ ec/2.
From this theorem, we simply get the following corollary: Let c > 0 and assume that f is ε T -concentrated to (−1, 1) and ε Ω -concentrated to (−c, c). Then, if N ≥ ec/2, It remains to notice that so that (3.27) follows.

Approximation of almost band limited functions in the basis of Chebyshev polynomials
In this paragraph, we show that the basis of the Chebyshev polynomials is also well adapted for the approximation of almost band limited functions. This is essentially done by showing that the weighted finite Fourier transform of the Chebyshev polynomial is given by a formula similar to (3.20). We first recall that the classical Chebyshev polynomials T k are defined by the three-term recursion It is interesting to also note that T k (x) are simply given by the formula T k (cos θ) = cos(kθ), k ∈ N, θ ∈ [0, π].
We will denote byT k the normalized Chebyshev polynomialT k = 2 c k π T k and theT k 's then form an orthonormal basis of L 2 ([−1, 1], dµ).
The following lemma gives us an explicit formula for the weighted Finite Fourier transform of T k , that we failed to find in the literature.
Lemma 4.1. For any k ∈ N, T k , the weighted finite Fourier transform of T k is given by Proof. This results follows directly from the formula Proof. Since f ∈ B c , then the Fourier inversion theorem implies that, for x ∈ R, we have Combining this with (3.20), one gets

Using (3.21) together with Cauchy-Schwarz inequality and a change of variable, one gets
To conclude, it suffices to use Parseval's identity.
From the orthonormality of theT k 's and this bound, we deduce that provided N ≥ ec/2.

Applications and numerical results
In the first part of this last section, we apply the quality of approximation of c−bandlimited functions by Legendre polynomials in the framework of prolate spheroidal wave functions (PSWFs). As a consequence, we give the convergence rate of the Flammer's scheme, see [7] for the computation of the PSWFs. 5.1. Approximation of prolate spheroidal wave functions. For a given real number c > 0, called bandwidth, the Prolate spheroidal wave functions (PSWFs) denoted by (ψ n,c (·)) n≥0 , are defined as the bounded eigenfunctions of the Sturm-Liouville differential operator L c , defined on C 2 ([−1, 1]), by They are also the eigenfunctions of the finite Fourier transform F c , as well as the ones of the operator They are normalized so that their L 2 ([−1, 1]) norm is equal to 1 and ψ n,c (1) > 0. We call (χ n (c)) n≥0 the corresponding eigenvalues of L c , µ n (c) the eigenvalues of F c and λ n (c) the ones of Q c . A well known property is then that ψ n,c L 2 (R) = 1 √ λn(c) .
The crucial commuting property of L c and Q c has been first observed by Slepian and co-authors [16], whose name is closely associated to all properties of PSWFs and their associated spectrum. Among their basic properties we cite their analytic extension to the whole real line and their unique properties to form an orthonormal basis of L 2 ([−1, 1]) and an orthonormal basis of B c . A well known estimate for χ n (c) is (5.33) n(n + 1) ≤ χ n (c) ≤ n(n + 1) + c 2 .
Recall that λ n (c) and µ n (c) are related by λ n (c) = c 2π |µ n (c)| 2 . A precise asymptotic of λ n (c) has been established by Widom [20]. Recently in [3], the authors have given an explicit approximation of the λ n (c), valid for n > 2c/π that gives rise to the exact super-exponential decay rate of the sequence of these eigenvalues. But, here we want a lower bound that is valid for all n. According to [11], while Bonami-Karoui established the following bound, see [2] (5.35) λ n (c) ≥ 2 5 2c π(n + 1)
In Appendix C we will prove the following slight improvement of this bound: Since ψ n,c ∈ L 2 ([−1, 1]), we may expand it in the Legendre basis Notation : Let us write β n k (c) = k + 1 2 ψ n,c , P k so that, on [−1, 1], Rokhlin, Xiao and Yarvin [21] have obtained induction formulas for the β n k (c)'s in order to compute the ψ n,c 's. Let us now obtain an estimate for them: Corollary 5.2. With the above notation, we have Proof. Since ψ n,c ∈ B c (R), from Lemma 3.1 we deduce that | ψ n,c , P k | ≤ 2 e πc To conclude, it suffices to use the lower bounds of λ n (c) given by (5.34) and the previous proposition.
From this, one can then easily obtain error estimates for the approximation of prolate spheroidal wave functions by the truncation of their expansion in the Legendre basis in the spirit of Theorem 3.3.

5.2.
Numerical results. In this paragraph, we give several examples that illustrate the different results of this work. Example 1. In this example, we check numerically that the actual error of the uniform approximation of the kernel k n (x, y) = n k=0 h k (x)h k (y) may be much smaller than the theoretical error given by Theorem 2.4. For this purpose, we have considered the value T = 1 and various values of the integer 10 ≤ n ≤ 100. For each value of n, we have used a uniform discretization Λ of the square [−1, 1] 2 with equidistant 6400 nodes. Then, we have computed over these grid points, a highly accurate approximation E n = sup of the exact uniform error . The obtained results are given by Table 1.   . Also, to illustrate the fact that the scaled Hermite approximation outperforms the usual Hermite approximation, we have repeated the previous numerical tests without the scaling factor (this corresponds to the special case of c = 1). Figure 3 shows the graphs of f and K n f . This clearly illustrates the out-performance of the scaled Hermite approximation, compared to the usual Hermite approximation.    and c n (f ) = f, T n L 2 (I,dµ) of f c , for the two values of c = 10 and c = 50. In Figure 4, we plot the graphs of the log(|l n (f )|), log(|c n (f )|), n ≥ ec 2 + 1 versus the logarithm of their respective error bounds given by (3.19) and (4.30).
Example 4. In this last example, we illustrate the quality of approximation by Legendre and Chebyshev polynomials in the Sobolev spaces H s (I). We have considered the two functions f, g given by f (x) = 1 [−1/2,1/2] (x) and g(x) = (1 − |x|)1 [−1,1] (x). It is clear that g ∈ H s (I), ∀s < 3/2. In Figure 5, we plot the graphs of the approximation error of f by its corresponding projections L N f and T N f over the subspaces spanned by the first N + 1 Legendre and Chebyshev polynomials, respectively, with N = 50. In Figure 6, we plot the graphs of g − L N g and g − T N g with N = 50.   We will again drop the index n and use the notation introduced before the statement of the theorem.
The bounds for e(x) are obtained by standard calculus, we will thus omit the proof. As for E(x), the computation shows Using Cauchy-Schwarz, we obtain x 0 25λ 4 16p(t) 9 dt 1/2 since h n 2 = 1. As |x| < λ, and p decreases, the estime |E(x)| ≤ 5λ 5/2 4p(x) 5 follows. When |x| ≤ λ/2, the change of variable y = λs and a numerical computation shows that |E(x)| ≤ 2 λ 3 . Note that this bound on E directly leads to a bound on h. For instance, if n ≥ 2 is even, then The Lipschitz bound on E is a bit more subtle so let us give more details. First, we introduce some further notation: We have proved that for |y| < λ/2, Φ(y, y) ≤ 2λ −3 . Simple calculus then implies that |E 1 | ≤ |x − y| λ 9/2 when |x|, |y| < λ/2.
Therefore, |E 2 | ≤ 3 λ 7/2 |x − y|. Finally, The integral is estimated in the same way as we estimated Φ(x, x), while for ϕ we use the mean value theorem and the fact that ϕ = p. We, thus, get |E 3 | ≤ 2 λ 5/2 |x − y|. The estimate for E follows.
Appendix B. Proof of Theorem 2.4 . For sake of simplicity, we will only prove the theorem in the case when n is even and write n = 2p. Let λ = √ 2n + 1, µ = √ 2n + 3, α = and are thus bounded with the help of the uniform and Lipschitz bounds of A and B by a factor of |x − y|.
It remains to group all estimates to get the result.
with the help of Turan's Lemma [Na2]. Therefore