# Hermite distributed approximating functionals as almost-ideal low-pass filters.

AbstractThe two-parameter family of Hermite Distributed Approximating Functionals (HDAFs) is shown to possess all properties that are essential requirements in filter design. When properly scaled, HDAFs provide an arbitrarily sharp high-frequency cut-off while retaining their smoothness. More precisely, bounds on the Fourier transform of the HDAF integral kernel show that it converges almost-uniformly to the ideal window, and that the pass and transition bands can be tuned independently to any width while preserving Gaussian decay in both time and frequency domains. The effective length of the HDAF filter in both domains is controlled by an estimate of the Heisenberg uncertainty product. In addition, a new asymptotic relationship between the HDAF and a windowed sinc function is obtained. In all calculations, we have aimed at precise error estimates that may assist numerical implementations.

Key words and phrases : Filter design, ideal low-pass filter, Ganssian decay in time and frequency domains, uncertainty product.

1 Introduction

Optimizing the design of band-pass filters constitutes a major field of study in signal processing (see, e.g., the standard references by Strang and Nguyen [30], Mallat [17], Vaidyanathan [33], Oppenheim and Schafer [20], and Stenger [29]). The goals of filter design may vary from plain frequency selectivity to localization in the time domain or to other requirements depending on the specifics of an application, such as the numerical solution of linear and non-linear ordinary and partial differential equations in a sequence of works by Kouri, Hoffman and others (see [13], [14], [34], [35], [36], and [16]), data compression (as in the exposition by Sayood [26]), imaging (such as Andrew and Hunt [2] and Mallat [18]), or pattern recognition (see, e.g., Unser and Eden [32], Dunn, Higgins and Wakeley [5], or Gunaratne, Hoffman and Kouri [6]). Compared to filters in the analog domain, where causality imposes a severe restriction, there is more freedom in digital signal processing that can be exploited to attain these specific goals. Here, we restrict ourselves to discussing the context of the basic low-pass filter defined on the entire real line, because once this is constructed, a wide variety of related filters and computational tools can be obtained. In the Conclusion we will give an idea how such a basic low-pass filter can be used for purposes of digital signal processing.

The contemporary view of filter design emphasizes the role of the time-frequency domain (see, e.g., Strang and Nguyen [30] or Mallat [17]). From this perspective, it is intuitively clear what general conditions must be satisfied in order to produce a robust low-pass filter. These conditions are: 1) the filter must be able to approach the so-called "ideal window" in a practicable and efficient way; 2) the filter must show a strong type of decay in both the time and frequency domains or equivalently, a high degree of regularity including smoothness in both domains; and 3) the Heisenberg uncertainty product of the filter should grow slowly as the frequency selectivity increases. These conditions are at the moment rather vague, but we will make them more precise later on. For now, we mention that the first condition guarantees arbitrarily accurate separation of the desired and undesired frequency bands. Band-pass and band-stop filters are easily designed starting with the basic low-pass filter. The second condition prevents that the filter itself introduces uncontrolled aliasing and Gibbs' oscillations. This is important for the stability of numerical implementation of various operations. The third condition ensures that the effective length of the filter is small in both the time and frequency domains, in the spirit of filter design in the time-frequency domain. As far as we are aware, up to now, no filter has been shown to satisfy all three conditions in a mathematically rigorous fashion.

The purpose of this paper is to show that such a class of filters has, in fact, been created, by demonstrating that there is a precise sense in which all three conditions can be satisfied. This class of filters is called the Distributed Approximating Functionals (DAFs) discovered and developed by Hoffman, Kouri and others in a number of works (see [7], [8], [9], [19], and [10]), and the particular DAF which is shown to satisfy all the conditions is known as the Hermite DAF (HDAF). For the sake of space, we will simply posit the HDAF, but detailed derivations from a variety of viewpoints have been given elsewhere [7]. This paper is organized as follows: In Section 2, we introduce the notion of filters. We show how to understand convolution with the HDAF integral kernels as the implementation of low-pass filters that approximate the identity operator. In Section 3, we obtain an integral expression for the HDAF in time and frequency domains, which is needed to characterize its behavior. We analyze the detailed behavior of the HDAF in order to prove that, when properly scaled, it provides a smooth, arbitrarily close approximation to the ideal window. We also discuss the Gaussian decay of HDAFs in time and frequency domains and estimate the Heisenberg uncertainty product for the HDAFs. Finally, we summarize our results and point out further developments in Section 4.

2 Definitions and Notation

Definition 2.1. In this work, we understand a filter M as a bounded operator defined on the space [L.sup.2](R) of square-integrable functions on R such that M commutes with the family of unitary shift operators {[T.sub.a]}a[member of]R given by [T.sub.a]f(x) = f(x - a) for all f [member of] [L.sup.2](R). Consequently, M acts by multiplication with an essentially bounded function [??] in the frequency domain. When speaking about a filter M, we often identify it and its properties with those of the associated function [??]. For the Fourier transform, we adopt the convention

[??](k) := [[integral].sup.[infinity].sub.-[infinity]] f(x)[e.sup.-kx]dx (1)

when f [member of] [L.sup.1](R)[intersection]N[L.sup.2](R), and as usual extend f [??] [??] to a bounded map (unitary up to a normalization factor 1/2[pi]) on all of [L.sup.2] (R).

Example 2.2. The ideal low-pass filter X is associated with the characteristic function of an interval centered at k = 0, so [??](k) = [[chi].sub.[-[kappa]/2,[kappa]/2]].sup.(k)]. The length [kappa] > 0 of the interval is called the pass-bandwidth of X. A more general low-pass filter M is given by a complex-valued, bounded function [??] that has the limits [lim.sub.k[right arrow]0][??](k) = 1 and [lim.sub.k][right arrow][??][infinity]][??](k) = 0.

Definition 2.3. The family of Hermite Distributed Approximating Functional (HDAF) filters in one dimension is given by operators {[D.sub.n,[sigma]]} indexed by order and length-scale parameters n [member of] [N.sub.0] and [sigma] > 0. Each [D.sub.n,[sigma]] acts on f [member of] [L.sup.2] (R) by convolution with an integral kernel, [D.sub.n,[sigma]] f(x) = [[integral].sup.[infinity].sub.[-infinity]] [D.sub.n](x, x';[sigma])f(x')dx'. The

HDAF integral kernel is defined by Hoffman and other [7] as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

where x, x' [member of] R and the m-th Hermite polynomial is denoted as [H.sub.m](x) = [(-1).sup.m] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for any m [member of] No.

Remarks 2.4. The quantity [D.sub.n](x, x'; [sigma]) has the property that it approaches the Dirac distribution [delta](x - x') in either of the limits [sigma] [right arrow] 0 or n [right arrow] [infinity], see the following paragraph. In a joint limit where n, [sigma] [right arrow] [infinity] and n/[[sigma].sup.2] is kept constant, Shi [27] has suggested that convolving with HDAF kernels implements an ideal filter to arbitrary, controllable accuracy.

By [D.sub.n](x, x'; [sigma]) = [D.sub.n](x - x',0;[sigma]) = [D.sub.n](x'- x,0;[sigma]), one may verify that each HDAF filter [D.sub.n,[sigma]] is self-adjoint and indeed commutes with translations. Consequently,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

for all f [member of] [L.sup.2](R) [intersection] [L.sup.1](R) and k [member of] R with a real-valued function that is seen to be

[[??].sub.n](k;[sigma]) = exp (-[k.sup.2][[sigma].sup.2]/2)[e.sub.n]([k.sup.2][[sigma].sup.2]/2), (4)

containing the exponential, locally compensated by the truncated exponential series

[e.sub.n](y) := [n.summation over(j=0)][y.sup.j]/j!. (5)

For each fixed pair n [member of] [N.sub.0] and [sigma] > 0 the value [[??].sub.n](k; [sigma]) is non-negative, bounded above by [[??].sub.n](k; [sigma]) [less than or equal to] [[??].sub.n](0; [sigma]) = 1 and decays faster than any polynomial in k. Consequently, [D.sub.n],[sigma]] is a low-pass filter. As either n [right arrow] [infinity] or [sigma] [right arrow] 0, we have [[??].sub.n](k; [sigma]) [??] 1 monotonically and thus the operator [D.sub.n,[sigma]] approximates the identity on [L.sup.2](R) from below.

3 Bounds on HDAFs with Relevance for Filtering

In this section we investigate certain properties of HDAFs that demonstrate their usefulness for separating desired and undesired frequency bands in a signal, their regularity properties, and the behavior of their Heisenberg uncertainty products. In addition, we derive an asymptotic approximation formula for the HDAF integral kernel that shows its relation to a windowed sinc function, also referred to as Gaussian sinc-DAF by Hoffman and others (see [11] or [28]).

3.1 An Integral Representation for HDAFs

The following lemma provides integral representations for the Fourier transform [[??].sub.n](k;[sigma]) and for the HDAF integral kernel itself. In view of [D.sub.n](x,x'; [sigma]) = [D.sub.n](x - x', 0; [sigma]), we can assume x' = 0 and simplify notation. The integral representations will be instrumental in the derivation of various estimates that control the properties of HDAF filters.

Lemma 3.1. For any n [member of] [N.sub.0], k [member of] R and x [member of] R,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (7)

Proof. The representation for [[??].sub.n](k; [sigma]) is seen to be true by taking the derivative

d/dk [[??].sub.n](k; [sigma]) = k[[sigma].sup.2]/n![([k.sup.2][[sigma].sup.2]/2).sup.n] exp (- [k.sup.2][[sigma].sup.2]/2 (8)

of Eq. (4) and integrating it again, while adjusting the constant of integration to obtain the value [[??].sub.n](0; [sigma]) = 1 at k = 0. Eq. (8) follows from Eq. (4) by the telescoping derivatives [e'.sub.n](y) = [e.sub.n-1](y) for n [member of] N.

We recover the integral representation of the HDAF integral kernel by the inverse Fourier transform of (6),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

Writing this result as an integral over positive values of k and switching the order of integration, we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

where [I.sub.n](x;[sigma] is defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

Remarks 3.2. It is possible to bypass the Fourier transform in an alternative derivation of the integral representation for [D.sub.n](x, 0; [sigma]). The summation of Eq. (2) with the Christoffel-Darboux formula (see, e.g. Sansone [25, p. 307]) is the first step in this derivation, yielding

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (12)

for n [member of] [N.sub.0]. Inserting the known integral representation from Abramowitz and Stegun [1, Eq. 22.10.15] for Hermite polynomials,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (13)

valid for all m [member of] [N.sub.0], results in Eq. (10). The virtue of the approach via the frequency domain is that it painlessly generalizes to non-integral values of n [greater than or equal to] 0, whereas Eq. (12) requires an additional effort to interpolate [(-1).sup.n].

Using integration by parts the integrals [I.sub.n](x; [sigma]) of Eq. (11) are seen to obey a recursion relation that is equivalent to the standard one between even order Hermite polynomials. Specifically,

[I.sub.n] (x; [sigma]) = 1/4 [(8n - 2[x.sup.2]/[[sigma].sub.2] - 2) [I.sub.n - 1] (x; [sigma]) - (2n - 1)(2n - 2) [I.sub.n - 2](x; [sigma])], (14)

which simplifies the calculation of the HDAF kernel, since then one only needs [I.sub.n] (x; [sigma]) for n [member of] {0, 1} to obtain its value for any n [member of] [N.sub.0].

3.2 Bounds on the Width of the Transition Bands

While the ideal low-pass filter is characterized solely by its bandwidth, our HDAF approximation is controlled by two parameters n and [sigma]. Next to the width of the pass band, the second scale parameter implicit in our approximation is the width of the transition bands. In this subsection we illustrate how tuning n and a controls these bandwidths, enabling a high-frequency cut-off that is arbitrarily sharp and tuned to any given frequency.

Definition 3.3. The pass band associated with a low-pass filter M and an error [[epsilon].sub.1] > 0 is the set {k [member of] R : [absolutely value of [??](k) - 1] [less than or equal to] [[epsilon].sub.1]}. The stop or attenuation band associated with M and an error [[epsilon].sub.2] > 0 is the set {k [member of] R : [absolutely value of [??](k)] [less than or equal to] [[epsilon].sub.2]}. Given M and errors [[member of].sub.1,2], the so-called transition band is what is contained in neither pass nor stop band. Typically, these bands axe given by intervals or by finite unions thereof. If the transition band is given by two intervals, we speak of them separately as of two transition bands.

Now we investigate the properties implicit in the integral representation for the Fourier transform of the HDAF kernel. In Eq. (6), [[??].sub.n](k; [sigma]) is a manifestly even function, thus we can restrict ourselves to investigating the behavior of [[??].sub.n](k; [sigma]) for positive values of k. We begin with a heuristic consideration.

Remark 3.4. Intuitively, the region of rapid transition in k [greater than or equal to] 0 can be understood as the interval between the points, denoted as [k.sub.t.sup.[+ or -]], at which [d.sup.2]/[dk.sup.2] [[??].sub.n](k; [sigma] is an extremum. Taking further derivatives of Eq. (8), we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By setting [d.sup.3]/[dk.sup.3] [[??].sub.n](k; [sigma] to zero we find

[k.sub.t.sup.[+ or -]] = 1/[sigma][square root of (4n + 3) [+ or -]] [square root of 16n + 9]/2].

Moreover, setting Eq. (15) equal to zero, we find that the only inflection point in [R.sup.+], (in our case this is, in fact, the point where the slope d/dk [[??].sub.n](k; [sigma] has a global minimum) is given by

[k.sub.sl] = [square root of 2n + 1/[sigma]] (15)

Hence, this inflection point lies within the heuristically defined transition region. If we fix the position of the inflection point by scaling a with [square root of 2n + 1], then we expect that the width of the transition region decreases to leading order as [k.sub.t.sup.+] - [k.sub.t.sup.-] ~ [n.sup.-1/2][[sigma].sup.-1]. The qualitative characteristics of [[??].sub.n](k; [square root of 2n + 1[sigma]]) are such that for small values of k, it has a value close to one; and over a controllably short frequency range in the vicinity of k = 1/[sigma], it falls rapidly and monotonically to zero. This behavior makes it appropriate for a low-pass filter that approximates the ideal filter. In Fig. 1 we show [[??].sub.n](k; [square root of 2n + 1[sigma]]) as a function of k and n, to illustrate that we can obtain a function that is arbitrarily close to the ideal window.

The remaining part of this section is a rigorous verification of the above-described intuitive claims. As before, let k > 0. We begin by rewriting Eq. (6)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (16)

such that the maximum [e.sup.-(n + 1/2]) of the integrand occurs at t = 1, independently of n. By scaling a with [square root of 2n + 1] we also eliminate the dependence of the lower limit of integration on n. In the following, we want to compare the integrand with Gaussians to control the n [right arrow] [infinity] asymptotics.

[FIGURE 1 OMITTED]

Lemma 3.5. Given 0 < x [less than or equal to] 1 [less than or equal to] y [less than or equal to] [infinity], we claim the upper bound

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (17)

for all 0 [less than or equal to] t [less than or equal to] y and the lower bound

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (18)

for all t [greater than or equal to] x, with equality in either case only when t = 1. In addition, we have a complementary upper bound

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (19)

for t [greater than or equal to] y and correspondingly

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (20)

when 0 [less than or equal to] t [less than or equal to] x.

Proof. To show the various estimates, we define g(t) := (2n + 1) ln t - (n + 1/2)[t.sup.2] for all t > 0 and use that in an interval (x, y) with 0 < x [less than or equal to] 1 [less than or equal to] y [less than or equal to] [infinity], - (2n + 1)(1 + 1/[x.sup.2]) [less than or equal to] g"(t) [less than or equal to] -(2n + 1)(1 + 1/[y.sub.2]). Integrating this inequality twice starting from t = 1 and using the monotonicity of the exponential function yields the first pair of upper and lower bounds. In addition, integrating the inequality for g" twice starting at y [greater than or equal to] 1 gives the improved upper bound for t [greater than or equal to] y and similarly, starting at x [less than or equal to] 1, for 0 [less than or equal to] t [less than or equal to] x.

Once the integrand is bounded by suitable Gaussians, we use an estimate of the complementary error function

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (21)

valid whenever x [less than or equal to] 0 (see, e.g. Komatu [15] or Pollak [21]). The remaining ingredient in the derivation of upper and lower bounds is the Stirling-Robbins [24] estimate for the factorial,

[square root of 2[pi][n.sup.n + 1/2][e.sup.-n + 1/12n + 1]] < n! < [square root of 2[pi][n.sup.n + 1/2]][e.sup.-n + 1/12n]. (22)

Now we derive an upper bound on [??](k; [sigma]) in case [k.sup.2][[sigma].sup.2] [greater than or equal to] 1 and a lower bound in case [k.sup.2][[sigma].sup.2] [greater than or equal to] 1. For simplicity, we again consider only k > 0.

Lemma 3.6. Let n [member of [N.sub.0] and k, [sigma] > 0. If k[sigma] [greater than or equal to] 1 then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (23)

and if 0 < k[sigma] [less than or equal to] 1, then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (24)

Proof. We use first the upper bound Ineq. (19) for the integrand of Eq. (16) and

then Eqs. (21)-(22) to obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (25)

To obtain Ineq. (23), the simple inequality [(1 + y/n).sup.n] < [e.sup.y] for all y, n > 0 is applied and the marginal correction term [e.sup.-1/12n + 1] is dropped.

If 0 < k[sigma] [less than or equal to] 1, we use the normalization [??](0, [sigma]) = 1 and the upper bound Ineq. (20) for the integrand Eq. (16) in the interval [0, k[sigma]] and then extend the domain of integration to (-[infinity], k[sigma]], combined with the estimate Ineq. (21),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (26)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (27)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (28)

which simplifies to Ineq. (24) after applying Ineq. (22), the elementary estimate [(1 + y/n].sup.n] > [e.sup.y] for y, n > 0, and some cancellations in the exponent.

The upper and lower bounds on the Fourier transform of the HDAF integral kernel are illustrated in Fig. 2 and Fig. 3 for various values of n.

The properties of the locally compensated exponential series appearing in Eq. (4) have been discussed in Szego's work [31]. From these properties one can deduce the uniform convergence of [??]n(k; [square root of 2n + 1[sigma]]) to the ideal filter on compact sets in R that do not include the points k = [+ or -] 1/[sigma]. A result from Pritsker and Varga [22] extends this result to certain subsets of the complex plane. Here, we restrict ourselves to real arguments, but derive a uniform convergence result that allows to shrink the excluded neighborhoods of k = [+ or -] 1/[sigma] as n increases.

[FIGURE 2 OMITTED]

Theorem 3.7. In the limit n [right arrow] [infinity], the scaled HDAF low-pass filter approaches the ideal filter with band-width 2/[sigma]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (29)

The convergence is uniform at an asymptotic rate of [n.sup.-1/2] outside of two transition bands centered at k = [+ or -]1/[sigma] the widths of which decay asymptotically at least as 1/[sigma] [square root of ln n/n]. More precisely, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (30)

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (31)

[FIGURE 3 OMITTED]

Proof. From Ineq. (24) we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (32)

for any constant c > 0. Replacing this constant with any sequence [{[C.sub.n]}.sub. n [greater than or equal to] 0] that satisfies [c.sub.n] [right arrow] [infinity] gives a limit inferior of one. Together with the simple bound [[??].sub.n](k; [sigma]) [less than or equal to] 1 this establishes the limit

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (33)

The growth of {[c.sub.n]} can be arbitrarily slow, but of course it determines how quickly the limit is approached. Using l'Hopital's rule Ineq. (24) shows that to obtain the convergence rate of [n.sup.-1/2] as described in Eq. (30), it suffices to choose [c.sub.n] = [square root of 1/4 ln n].

Together with the non-negativity of [D.sub.n](k; [sigma]), the upper bound Ineq. (23) results analogously in

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (34)

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (35)

for any sequence {[c.sub.n]}, [c.sub.n] [right arrow] [infinity]. Inspecting Ineq. (23) and using l'Hopital's rule shows we can choose again [c.sub.n] = [square root 1/4 ln n] to ensure a convergence rate of [n.sup.-1/2] as in Eq. (31).

Finally, we verify the convergence [D.sub.n](1/[sigma]; [square root of 2 + 1[sigma]]) = 1/2 by the limit of the lower bound Ineq. (24) for k[sigma] = 1 as n [right arrow] [infinity] and a corresponding sharp upper bound. This is achieved via

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (36)

with any sequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] satisfying [c.sub.n] [right arrow] [infinity]. Using the previously established convergence of ([??].sub.n](1/[sigma] + 1/[sigma] [c.sub.n]/[square root of n + 1/2]; [square root of 2n + 1[sigma]]) [right arrow] 0 and the upper bound Ineq. (17)

for the integrand between the limits x = 1 and [y.sub.n] := 1 + [c.sub.n]/[square root of n + 1/2] results in

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (37)

Now dominated convergence applies and again with Ineq. (22)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (38)

follows, which finishes the proof. []

3.3 Gaussian decay of the HDAF kernel and of its Fourier transform

The upper bound Ineq. (23) on [[??].sub.n](k; [square root of 2n + 1[sigma]]) serves two purposes: The first one is in the separation of frequency bands as described above; the second one concerns regularity properties of the HDAF kernel. Ineq. (23) shows Gaussian decay of its Fourier transform. This has computational relevance because it implies that when a function is convolved with the HDAF kernel, the result is smooth, and we may then even apply a large class of pseudo-differential operators without spoiling this property.

Theorem 3.8. The scaled HDAF integral kernel of order n [member of] N is for any x [member of] R bounded by

[absolute value of [D.sub.n](x, 0; [square root of 2n + 1[sigma]])] [less than or equal to] [(1 + 1/2n).sup.1/2]/[pi][sigma]. (39)

For [absolute value of x] > (2n + 1)[sigma], it exhibits Gaussian decay,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (40)

Proof. For the bounds on [D.sub.n](x, 0; [square root of 2n + 1[sigma]]) we distinguish several cases, depending on the choice of n and x. In the simplest one, we have [absolute value of x] [less than or equal to] [sigma] and apply [absolute value of sin(s)] [less than or equal to] [absolute value of s] to the integrand of Eq. (11) resulting in

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (41)

Inserted in Eq. (10), this shows that D(x, 0; [square root of 2 + 1[sigma]]) is bounded by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (42)

with the gamma function F(re + 1) that extends the factorial re! to real arguments. The last estimate is again obtained from Ineq. (22) and only serves to illustrate the asymptotic behavior for large n.

The next case we consider is [sigma] < [absolute value of x] [less than or equal to] (2n + 1)[sigma]. This time, we estimate [absolute value of sin(s)] [less than or equal to] 1 in Eq. (11) and obtain algebraic decay,

[absolute value of [D.sub.n](x, 0; [square root of 2n + 1[sigma])] [less than or equal to] 1/[pi] [absolute value of x] .(43)

The last case is the main part and establishes Gaussian decay of the HDAF kernel. It is in the domain given by [absolute value of x] > (2n + 1)[sigma]. The estimate starts from the expression in Eqs. (10)-(11), written as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (44)

As a first step, we complete the square in the exponent. Since the integrand extends to a holomorphic function that exhibits Gaussian decay along the direction of the real axis, we can shift the line of integration from R to R - i x/(2n+1)[sigma] and obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (45)

This integral can be estimated by replacing the integrand with its absolute value and by splitting the domain of integration into lower and higher frequency parts,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (46)

The first integral in Eq. (46) is bounded by replacing the exponential in the integrand with a larger, algebraic expression,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (47)

To bound the second integral in Eq. (46), we use [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and again Ineq. (19), analogous to the derivation of Eq. (23). Together, the two integrals

are thus estimated by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (48)

Collecting all terms, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (49)

which simplifies to the claimed Ineq. (40).

Remark 3.9. We are grateful for Mark Arnold's suggestion to consider non-integral values of n. It is interesting to note that for such n, the Gaussian bounds in the frequency domain generalize painlessly, whereas in the time domain there is only algebraic decay. The reason is that [[??].sub.n](k; [sigma]) is for non-integral n only finitely often continuously differentiable, see Eq. (8).

3.4 Heisenberg Uncertainty Product for HDAFs

In this section we study the behavior of the Heisenberg uncertainty product for the HDAFs and show that it grows, up to logarithmic corrections, inverse proportionally to the square-root of the transition bandwidth.

Definition 3.10. The Heisenberg uncertainty product [DELTA]x[DELTA]k of a function f [member of] [L.sup.2](R) is a non-negative, possibly infinite quantity given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (50)

Theorem 3.11. The uncertainty product of the HDAF integral kernel [D.sub.n](x, 0; [sigma]) is independent of the choice of [sigma] > 0 and will be denoted by [([DELTA]x).sub.n][([DELTA]k).sub.n].

Asymptotically, its growth is bounded by [n.sup.1/4]. More explicitly, given any [epsilon] > 0, there is N [member of] [N.sub.0] such that [([DELTA]x).sub.n][([DELTA]k).sub.n] is for all n [greater than or equal to] N bounded by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (51)

Proof. In Eq. (51), we can omit the infimization over the shift parameters a and b in Eq. (50), because the HDAF kernel and its Fourier transform are even functions. Prom the functional form of the HDAF integral kernel given in Eq. (2) or Eq. (12) and its Fourier transform Eq. (4), we conclude that the uncertainty product is independent of the length parameter [sigma]. Therefore, we can set [sigma] = [square root of 2n + 1] and use that [[??].sub.n](k; [square root of 2n + 1]) is a sequence of uniformly bounded functions that converges almost uniformly to the ideal window with bandwidth 2. Consequently, by the unitarity of the Fourier transform and by dominated convergence using the bound given in Eq. (23), we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (52)

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII](53)

With the scaling of a used here, the only factor in the uncertainty product that contributes to its asymptotic growth with n is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (54)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (55)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (56)

As usual, we have used simple inequality [(1 + y/n).sup.n] < [e.sup.y]] for y > 1 and Eq. (22) in the last two steps. The last inequality, together with the convergence of Eq. (52) and Eq. (53) as well as that of the marginal correction term [e.sup.1/24n + 6] [right arrow] 1 prove Ineq. (51).

3.5 Large-Order Behavior of the Scaled HDAF Kernel

To estimate the scaled HDAF kernel [D.sub.n](x, 0; [square root of 2n + 1[sigma]]) for large n, we follow ideas of asymptotic analysis in the evaluation of the integral in Eq. (11).

Theorem 3.12. The n [right arrow] [infinity] asymptotics of the HDAF kernel are given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (57)

with an error term [F.sub.n] that is bounded such that for every [epsilon] > 0 there is an N [member of] [N.sub.0] satisfying

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (58)

for every n [greater than or equal to] N.

Proof. After a change of variables, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (59)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (60)

with an error term that is bounded by the sum of three contributions

[absolute value of [E.sub.n](x; [sigma])]] [less than or equal to] [(n + 1/2).sup.n+1] [[[DELTA].sub.1](x; [sigma]) + [DELTA].sub.2](x; [sigma]) + [[DELTA].sub.3](x; [sigma])] (61)

that arise by splitting the correction in integrals over three separate domains,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (62)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (63)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (64)

with an as yet unspecified split point at distance 0 < [tau] < 1 from the center of the Gaussian in the integrand. The first error term can be estimated directly with Ineq. (21) and gives

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (65)

The second one involves Ineq. (17) and Ineq. (18) with x = 1 - [tau] and y = 1 + [tau], followed by extending the domain of integration to the entire real line,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (66)

To bound the third error term, we use again Ineq. (19) and Ineq. (21), resulting in

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (67)

Collecting the terms,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (68)

Choosing [tau] = c/[square root of n + 1/2] [equivalent to] c/[r.sub.n] with some fixed c > 0 and the abbreviation [r.sub.n] :=

[square root of n + 1/2], we can further estimate

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (69)

The middle term comes from the inequality

[square root of 1 + y] - ]square root of 1 + x] [less than or equal to] y - x/2[square root of 1 + x] (70)

with y = [(1 - c/[r.sub.n]).sup.-2] and x = [(1 + c/[r.sub.n]).sup.-2] applied to the numerator and some elementary estimates in the denominator; the last term comes from

1 + [tau] - 1/1 + [tau] [greater than or equal to] [tau] (1 + 1/[(1 + [tau].sup.2]). (71)

To adjust the leading order of the three error contributions, we replace the constant c by the sequence [c.sub.n] = [square root of 1/2 ln (n[sigma]/[absolute value of x]) for [absolute value of x]/[sigma] < 1 and otherwise [c.sub.n] = [square root of (1/2 ln n)].

Inserting this in Ineq. (69) shows that independently of x and [sigma], the first and third term decay faster than the middle term. Consequently, for every [epsilon] > 0 there is an N > 0 such that for each n [greater than or equal to] N we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (72)

To obtain this bound from Ineq. (69), we have again estimated the middle term using 1/[(1 - [tau]).sup.2] - 1/[(1 - [tau]).sup.2] [less than or equal to] 4 [tau]/[(1 + [tau]).sup.3] and bounded the denominator by a constant for sufficiently large n.

Now we perform the Fourier integral in Eq. (60) and obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

with the final error bound

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (73)

that is valid for any given [epsilon] > 0 after a sufficiently large order n is reached.

Remark 3.13. The windowed sinc function appearing in Eq. (57) differs from the so-called Gaussian-sinc-DAF analyzed by Hoffman and others (see [11] or [28]) only by a constant factor that can be shown to be arbitrarily close to one using the Stirling-Robbins estimates Ineq. (22). In the limit n [right arrow], [F.sub.n] vanishes and Eq. (57) converges to the well known Fourier transform of the ideal low-pass filter

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (74)

with a cut-off frequency of 1/[sigma]. If error bounds are not desired, we can derive this limit by applying a slightly different scaling of a with [square root of 2n] to Eq. (12) in combination with the scaling limit of Hermite polynomials (see, e.g. Abramowitz and Stegun [1, Eq. 22.15.4]).

4 Conclusion

In this paper, we have analytically verified previous, numerical evidence that suggests the use of HDAFs as arbitrarily controllable band-pass filters. The properties we demonstrated were that 1) by proper scaling, HDAFs of order n approximate the so-called "ideal window", pointwise bounds show the convergence is uniform at a rate of [n.sup.-1/2], up to a transition region that asymptotically decays in width at least as 1/[sigma] [square root of ln n/n]; 2) HDAFs exhibit a high degree of regularity including Gaussian decay in both time and frequency domains; and 3) the growth of the Heisenberg uncertainty product for HDAFs is asymptotically bounded by a constant times [n.sup.1/4]. Although there was substantial computational evidence to support the conjecture that the HDAFs did, indeed, satisfy these conditions, Shi and others [27] did not provide an analytical demonstration. At the same time, we were lacking a simple prescription for choosing the parameters to control the behavior of HDAF band-pass filter. The strategy we followed in the present paper was to examine the HDAF in the frequency domain in order to obtain quantitative conditions governing the choice of the parameters n and [sigma].

In addition, we have obtained an asymptotic relation between the HDAF integral kernel and a windowed sinc function that has proved highly useful in numerical applications and is known as the Gaussian-sinc-DAF, a sinc function windowed by a Gaussian envelope. Such a relationship has long been suspected, and the present result explains how it comes about.

Finally, HDAFs can be used for converting a signal from analog to digital in a customary two-step process of filtering and sampling. Instead of applying a simple high-frequency cut-off to an analog signal, we convolve it with an HDAF integral kernel and thus effectively truncate it in the frequency domain. While there remains an unwanted, higher frequency component, we can suppress its contribution to achieve any desired level of attenuation. The benefit of this procedure is the numerical robustness guaranteed by the Gaussian decay of HDAFs in both domains. For such HDAF-filtered signals, the results obtained here can be combined with an approximate sampling theorem as in Qian's fairly recent article [23], or as in the discussion by Bodmann and others [3], which is anticipated to have a wide range of applications, in particular in the numerical solution of linear and non-linear ordinary and partial differential equations.

ACKNOWLEDGMENT

The authors are very grateful for helpful suggestions by Mark Arnold. This research was partially supported by University of Houston TLCC funds, National Science Foundation Grant DMS-0406748, R. A. Welch Foundation Grant E-0608, and a subcontract of the "T5"-grant held by the University of Texas Health Science Center at Houston.

References

[1] M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions, NBS Applied Math. Series, 55, U.S. Gov't. Printing Office, Washington, DC 20402, 1964.

[2] H. C. Andrew and B. R. Hunt, Digital Image Restoration, Prentice-Hall, Englewood Cliffs, NJ, 1977.

[3] B. G. Bodmann, A. Melas, M. Papadakis, Th. Stavropoulos, Analog to digital, revisited: Controlling the accuracy of reconstruction, Samp. Theory Signal Image Process., 5, 321-340, 2006.

[4] C. Chandler and A. G. Gibson, Uniform approximation of functions with discrete approximation functionals, J. Approx. Theory, 100, 233-250, 1999.

[5] D. Dunn, W. E. Higgins, and J. Wakeley, Texture segmentation using 2-D Gabor elementary functions, IEEE Transactions on Pattern Analysis and Machine Intelligence, 16, 130-149, 1994.

[6] G. H. Gunaratne, D. K. Hoffman, and D. J. Kouri, Characterizations of natural patterns, Phys. Rev. E, 57, 5146-5149, 1998.

[7] D. K. Hoffman, N. Nayar, O. A. Sharafeddin, and D. J. Kouri, Analytic banded approximation for the discretized free propagator; J. Phys. Chem., 95, 8299-8305, 1991.

[8] D. K. Hoffman and D. J. Kouri, Distributed approximating function theory--a general, fully quantal approach to wave-propagation, J. Phys. Chem. 96, 1179-1184, 1992.

[9] D. K. Hoffman, M. Arnold, and D. J. Kouri, Properties of the optimum distributed approximating function class propagator for discretized and continuous wave packet propagations, J. Phys. Chem., 96, 6539-6545, 1992.

[10] D. K. Hoffman, T. L. Marchioro II, M. Arnold, Y. Huang, W. Zhu, and D. J. Kouri, Variational derivation and extensions of distributed approximating functionals, J. Math. Chem., 20, 117-140, 1996.

[11] D. K. Hoffman, G. W. Wei, and D. J. Kouri, A variational approach to the Dirichlet-Gabor wavelet-distributed approximating functional, J. Math. Chem., 25, 235, 1999.

[12] D. K. Hoffman, G. H. Gunaratne, D. S. Zhang, and D. J. Kouri, A method to Fourier filter textured images, CHAOS, 10, 240-247, 2000.

[13] Y. Huang, D.J. Kouri, M. Arnold, T. L. Marchioro II, and D. K. Hoffman, Distributed approximating function approach to time-dependent wavepacket propagation in more than one-dimension: Inelastic, collinear atom-diatom collisions, J. Chem. Phys., 99, 1028-1030, 1993.

[14] Y. Huang, D. J. Kouri, M. Arnold, T. L. Marchioro II, and D. K. Hoffman, Distributed approximating function approach to time-dependent wavepacket propagation in 3-dimensions: Atom-surface scattering, Computer Phys. Commun., 80, 1-16, 1994.

[15] Y. Komatu, Elementary inequalities for Mills' ratio, Rep. Statist. Appl. Res. Un. Jap. Sci. Engrs., 4, 69-70, 1955.

[16] D. J. Kouri, D. S. Zhang, G. W. Wei, T. Konshak, and D. K. Hoffman, Numerical solutions of nonlinear wave equations, Phys. Rev. E, 59, 12741277, 1999.

[17] S. Mallat, Wavelet Signal Processing, Academic Press, New York, 1996.

[18] S. Mallat, A Wavelet Tour of Signal Processing, Academic Press, New York, 1998.

[19] T. L. Marchioro II, M. Arnold, D. K. Hoffman, W. Zhu, Y. Huang, and D. J. Kouri, Extensions to the distributed approximating functional--the harmonic propagator, Phys. Rev. E, 50, 2320-2330, 1994.

[20] A.V. Oppenheim and R.W. Schafer, Discrete-Time Signal Processing, Prentice Hall, Englewood Cliffs, NJ, 1989.

[21] H. O. Pollak, A remark on "Elementary inequalities for Mills' ratio" by Yusaku Komatu, Rep. Statist. Appl. Res. Un. Jap. Sci. Engrs., 4, 110, 1956.

[22] I. E. Pritsker and R. S. Varga, The Szego curve, zero distribution and weighted approximation, Trans. Amer. Math. Soc., 349, 4085-4105, 1997.

[23] L. Qian, On the regularized Whittaker-Kotel'nikov-Shannon sampling formula, Proc. Amer. Math. Soc., 131, 1169-1176, 2002.

[24] H. Robbins, A remark on Stirling's formula, Amer. Math. Monthly, 62, 26-29, 1955.

[25] G. Sansone, Orthogonal Polynomials, Interscience, New York, 1959.

[26] K. Sayood, Introduction to Data Compression, Morgan Kaufmann Pub., Inc., San Francisco, 1996.

[27] Z. Shi, G. W. Wei, D. J. Kouri, and D. K. Hoffman, Perceptual normalized subband image restoration, Proceedings of the IEEE Symposium on Time-frequency and Time-scale Analysis, no. 144, 469-472, 1998.

[28] Z. Shi, D. J. Kouri, G. W. Wei, and D. K. Hoffman, Generalized symmetric interpolating wavelets, Computer Phys. Commun., 119, 194, 1999.

[29] F. Stenger, Numerical Methods Based on Sinc and Analytic Functions, Springer, New York, 1993.

[30] G. Strang and T. Nguyen, Wavelets and Filter Banks, Wellesley-Cambridge Press, Wellesley, MA, 1997.

[31] G. Szego, Uber eine Eigenschaft der Exponentialreihe, Sitzungsber. Berl. Math. Ges., 23, 50-64, 1924.

[32] M. Unser and M. Eden, Multiresolution feature extraction and selection for texture segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 11, 717-728, 1989.

[33] P. P. Vaidyanathan, Multirate Systems and Filter Banks, Prentice Hall, Engelwood Cliffs, NJ, 1993.

[34] G. W. Wei, D. S. Zhang, D. J. Kouri and D. K. Hoffman, Distributed approximating functional approach to the Fokker-Planck equation: Time propagation, J. Chem. Phys., 107, 3239-3246, 1997.

[35] G. W. Wei, D. S. Zhang, S. C. Althorpe, D. J. Kouri, and D. K. Hoffman, Wavelet-distributed approximating functional method for solving the Navier-Stokes equation, Computer Phys. Commun., 115, 18-24, 1998.

[36] G. W. Wei, S. C. Althorpe, D. J. Kouri, and D. K. Hoffman, An application of distributed approximating functional-wavelets to reactive scattering, J. Chem. Phys., 108, 7065-7069, 1998.

Bernhard G. Bodmann

Department of Applied Mathematics, University of Waterloo

Waterloo, Ontario N2L 3G1, Canada

bgb@uwaterloo.ca

David K. Hoffman

Department of Chemistry and Ames Laboratory, Iowa State University

Ames, IA 50011

hoffman@ameslab.gov

Donald J. Kouri

Department of Chemistry and Department of Physics

University of Houston, Houston, TX 77204-5641

kouri@uh.edu

Manos Papadakis

Department of Mathematics, University of Houston

Houston, TX 77204-3008

mpapadak@math.uh.edu

Printer friendly Cite/link Email Feedback | |

Author: | Bodmann, Bernhard G.; Hoffman, David K.; Kouri, Donald J.; Papadakis, Manos |
---|---|

Publication: | Sampling Theory in Signal and Image Processing |

Article Type: | Technical report |

Geographic Code: | 1USA |

Date: | Jan 1, 2008 |

Words: | 7207 |

Previous Article: | Tight frame completions with prescribed norms. |

Next Article: | Matrix representation of operators using frames. |

Topics: |

The Volterra and Wiener theories of nonlinear systems. |

Extrema of nonlocal functionals and boundary value problems for functional differential equations. |