A generalized sampling theorem for frequency localized signals.

1 Introduction

In time-frequency analysis the concept of time-frequency localization is well-known [15, 8, 12]. It means the approximate concentration of a signal in both time and frequency allowing for tails of strong decay in either dimension. In many areas of communications the concept of (strict) bandlimitation is still prevailing. One reason might be the classical sampling theorem of Whittaker, Kotel'nikov, and Shannon [24, 18, 5, 28, 29] where bandlimited signals are the basic assumption. This leads to difficulties in practical applications [28] of the classical sampling theorem and researchers have been trying to overcome the entailed complications [3, 6, 9, 19, 25, 26, 28]. The goal of the present work is to contribute to these attempts by loosening the assumption of strict bandlimitation while retaining the model of sampling of the classical sampling theorem: An arbitrary finite-energy input signal is preprocessed by a prefilter, the filter output signal lying in a well-structured space similar to the space of bandlimited signals is ideally sampled at equidistant points of time, finally the complete filter output signal is to be reconstructed. A whole variety of prefilters has been described, some of which are presumably suitable for practical applications. The price to be paid will be, in general, imperfect reconstruction. Some effort is made to estimate the incurred reconstruction error and to find criteria for the size of the sampling interval to guarantee good reconstruction. This is well in the sense of A. J. Jerri's work on error analysis in sampling theory and applications [18, 19]. The chosen approach incorporates from the start some measure of generalized bandwidth for the used prefilter so that eventually the link between that generalized bandwidth (the so-called "soft bandwidth") and a critical sampling interval shall be found. That critical sampling interval would then correspond to the Nyquist interval in case of the classical sampling theorem [24, 29].

The paper is organized as follows. In Section 2 the frequency localization operator (prefilter) is defined and basic assumptions are compiled. In Section 3 the so-called localization space is described. In Section 4 a perfect reconstruction formula for elements of some subspace of localization space is derived. In Section 5 a general error estimate for the reconstruction error is given. As a conclusion, in Section 6 the sampling theorem is presented. In subsections at the end of Section 5 and 6 examples are discussed.

The following notation is used: [L.sup.2](R) is the space of square integrable functions (or finite-energy signals) f : K [right arrow] C with inner product <[f.sub.1]/[f.sub.2]) = [[integra].sup.[infinity].sub.-[infinity]][f.sub.1](x)[bar.[f.sub.2](x)]dx. For the Fourier transform we adopt the convention [??]([xi]) = [(2[pi]).sup.-1/2] [[integra].sup.[infinity].sub.-[infinity]] [e.sup.-ix[xi]] f(x) dx, where x denotes time and [xi] (angular) frequency. [R.sub.+] denotes the set of positive real numbers.

2 Frequency Localization Operator

For an arbitrary finite-energy signal f [member of] [L.sup.2](R) frequency localization is performed by an operator [P.sub.[phi]] : [L.sup.2](R) [right arrow] [L.sup.2](R) given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

We shall call [P.sub.[phi]] prefilter because in practice it would be an anti-aliasing prefilter or a related nonideal acquisition device [26]. Since ([P.sub.[phi]]f)(x) = <f, [phi](* - x)>, x [member of] R, the prefilter realizes a crosscorrelation of the input signal f with [psi] (rather than a convolution with [bar.[psi](-x)]). We make the following assumptions on the prefilter function [psi]:

1. [psi] [member of] [L.sup.2](R).

2. It holds the generalized moment condition

[M.sub.w]([psi]) = [[integral].sup.[infinity].sub.-[infinity]] w(|[xi]|)[|[??]([xi])|.sup.2]d[xi] < [infinity], (2)

where w = w([xi]) for [xi] > 0 is a positive and monotonically increasing weight function of sufficient growth,

W([xi]) [greater than or equal to] c[[xi].sup.1+[epsilon]] [for all][xi] [member of] [1, [infinity]) (C > 0, [epsilon] > 0). (3)

3. For any [lambda] [member of] [LAMBDA], where [LAMBDA] is some non-empty subset of [R.sub.+], the family of functions {[psi](* - n[lambda]); n [member of] Z} forms a Riesz basis in [L.sup.2](R).

We refer to [7, 28] concerning Riesz bases and their relevance to signal processing. The Riesz basis condition is equivalent to the existence of positive real numbers A, B (possibly depending on [lambda]) so that

0 < A [less than or equal to] [LAMBDA] [[infinity].summation over (n=-[infinity])] [|[??]([xi] + n[LAMBDA])|.sup.2] [less than or equal to] B < [infinity] a.e., (4)

where [LAMBDA] = 2[pi]/[lambda]. See [2] for a proof in case [lambda] = 1; the argument carries over to arbitrary [lambda] > 0 without changes. Actually, we shall use the Riesz basis condition mostly in the form of Ineq. (4).

Because of the upper bound in Ineq. (4), the Fourier transform [??] is bounded almost everywhere on R so that the range of [P.sub.[psi]] is a subset of [L.sup.2](R) as presumed. We note that because of condition (3) the prefilter function [psi] is in a Sobolev space [21] [H.sup.r](R) = {u [member of] [L.sup.2](R); [integral] [|[??]([xi])|.sup.2][(1 + [|[xi]|.sup.2]).sup.r] d[xi] < [infinity]) of order r > 1/2. Thus, by reason of the Sobolev embedding theorem, [psi] will necessarily be a continuous function.

In our paper monomial weights w([xi]) = [|[xi]|.sup.s], s > 1, and Gaussian weights w([xi]) = exp(s[[xi].sup.2]), s > 0, will be used. As prefilter functions [psi] the sinc-function, Gaussian functions and B-splines will be taken.

3 Localization Space

The localization space [P.sub.[psi]] of the prefilter [P.sub.[psi]] corresponds to the space of bandlimited signals in case of an ideal low-pass filter and is defined as the range of [P.sub.[psi]],

[P.sub.[psi]] = {g = [P.sub.[psi]]f; f [member of] [L.sup.2](R)}.

[P.sub.[psi]] is a linear, not necessarily closed subspace of [L.sup.2](R); it even may be dense in [L.sup.2](R). Moreover, the localization space is invariant with respect to arbitrary translations g [??] g(* - t), t [member of] R. The function [PHI] [member of] [P.sub.[psi]] defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

will be of importance. Since [PHI](x) = <[psi],[psi](* - x)>, x [member of] R, it is the autocorrelation function of [psi]. On [P.sub.[psi]] we define the inner product

[<[g.sub.1][g.sub.2]>.sub.[psi]] = 1/2[pi] [[integra].sub.supp[??]] [[??].sub.1]([xi])[bar.[[??].sub.2]([xi])][|[??]([xi])|.sup.-2]d[xi] (5)

with corresponding norm [||g||.sub.[psi]] = [square root of [<g,g>.sub.[psi]]]

The reproducing kernel Hilbert space (RKHS) property of localization space [P.sub.[psi]] will be described in the next theorem. The shorthand notation [L.sup.2](R| supp [??]) for the closed subspace {f [member of] [L.sup.2](R); supp [??] [subset or equal to] supp [??]} of [L.sup.2](R) will be used. We remark that [L.sup.2](R| supp [??]) = [L.sup.2](R) in case of a Gaussian function or a B-spline [psi] (see Section 6.1}.

Proposition 1 The linear space [P.sub.[psi]] endowed with the inner product (5) is an RKHS. The reproducing kernel is K(x, y) = [PHI](y - x). [P.sub.[psi]] maps [L.sup.2](R| supp [??]) isometrically onto [P.sub.[psi]], i.e., if [g.sub.i] = [P.sub.[psi]][f.sub.i] with [f.sub.i] [member of] [L.sup.2](R| supp [??]), i = 1, 2, then

[<[g.sub.1],[g.sub.2]>.sub.[psi]] = <[f.sub.1],[f.sub.2]>. (6)

Proof. Since the Fourier transform of [g.sub.i] = [P.sub.[psi]][f.sub.i] is [[??].sub.i]([xi]) = [square root of 2[pi]][bar.[??]([xi])][[??].sub.i]([xi]), [xi] [member of] R, we have by Parseval's formula that [<[g.sub.1],[g.sub.2]>.sub.[psi]] = <[[??].sub.1],[[??].sub.2]> = <[f.sub.1],[f.sub.2]>. If g = [P.sub.[psi]] f with f [member of] [L.sup.2](R), then the function [f.sub.0] defined by [[??].sub.0] ([xi]) = [??]([xi])/([square root of 2[pi]][bar.[??]([xi])]) in case [xi] [member of] supp [??] and [[??].sub.0]([xi]) = 0 else is in [L.sup.2](R| supp [??]) and g = [P.sub.[psi]] [f.sub.0]. Thus, [P.sub.[psi]][L.sup.2](R| supp [??]) = [P.sub.[psi]]. Because of the isometry relation (6), [P.sub.[psi]] endowed with the inner product [<*,*>.sub.[psi]] becomes a Hilbert space as is [L.sup.2](R| supp [??]) with respect to the inner product <*,*> of [L.sup.2](R).

For any x [member of] R we define the function [[psi].sub.x] [member of] [L.sup.2](R| supp [??]) by [[psi].sub.x](Y) = [psi](Y - x), y [member of] R. Since ([P.sub.[psi]][[psi].sub.x])(Y) = [PHI](y - x) = K(x, y), we have K(x, *) [member of] [P.sub.[psi]]. For any function g = [P.sub.[psi]][f.sub.o] with [f.sub.0] [member of] [L.sup.2](R| supp [??]) and any x [member of] R we now infer by means of (6) that

[<g,K(x,*)>.sub.[psi]] = [<[P.sub.[psi]][f.sub.0], [P.sub.[psi]][[psi].sub.x]>.sub.[psi]] = <[f.sub.0],[[psi].sub.x]> = [[integral].sup.[infinity].sub.-[infinity]] [f.sub.0](y)[bar.[psi](y - x)]dy = ([P.sub.[psi]][f.sub.0])(x) = g(x).

Thus, K(x, y) is the reproducing kernel in the Hilbert space [P.sub.[psi]]. This concludes the proof of Proposition 1.

We remark that Eq. (6) should not be taken as a definition of the inner product [<[g.sub.1],[g.sub.2]>.sub.[psi]], because it implies inversion of operator [P.sub.[psi]] which, in general, is an ill-posed problem. We shall need the following subspaces of domain [L.sup.2](R) and range [P.sub.[psi]] of operator [P.sub.[psi]].

Definition 1 The shift-invariant subspace [V.sub.[lambda]]([psi]) [subset or equal to] [L.sup.2](R) is the closed linear span of {[[psi].sub.n] = [psi](* - n[lambda]); n [member of] Z} in [L.sup.2](R).

Definition 2 The subspace [R.sub.[lambda]]([psi]) [subset or equal to] [P.sub.[psi]] ("reconstruction subspace") is the closed linear span of {[[PHI].sub.n] = [PHI](* - n[lambda]); n [member of] Z} in

[P.sub.[psi]].

Remark 1 The shift-invariant spaces [V.sub.T]([psi]), T > 0, of Unser [28] are generated by translated and dilated versions [psi] (x/T - n), n [member of] Z, of a generating function [psi].

Proposition 2 [P.sub.[psi]] is an isometry from [V.sub.[lambda]]([psi]) onto [R.sub.[lambda]]([psi]). If {[[PHI].sub.n];n [member of] Z} forms a Riesz basis in [L.sup.2](R), then [R.sub.[lambda]]([psi]) may be identified with the shift-invariant subspace [V.sub.[lambda]]([PHI]) [subset or equal to] [L.sup.2](R) defined as the closed linear span of {[[PHI].sub.n];n [member of] Z} in [L.sup.2](R).

Proof. Since [P.sub.[psi]][[psi].sub.n] = [[PHI].sub.n] [for all]n [member of] Z and, by Proposition 1, [P.sub.[psi]] is an isometry from [V.sub.[lambda]]([psi]) [subset or equal to] [L.sup.2](R| supp [??]) into [P.sub.[psi]], it follows that [P.sub.[psi]] [V.sub.[lambda]]([psi]) = [R.sub.[lambda]]([psi]).

An element v(x) = [[SIGMA].sup.finite.sub.n[member of]Z] [c.sub.n][[PHI].sub.n] of the linear span of {[[PHI].sub.n]; n [member of] Z} has norms in [P.sub.[psi]] and [L.sup.2](R), resp.,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [LAMBDA] = 2[pi]/[lambda], C([xi]) = [[SIGMA].sup.finite.sub.n[member of]Z] [c.sub.n][e.sup.-2[pi]in[xi]], [A.sub.[psi]]([xi]) is the central term in (4), and [A.sub.[PHI]]([xi]) = [LAMBDA] [[SIGMA].sub.k[member of]Z] [|[??]([xi] + k[LMABDA])|.sup.2]. Because of inequality (4) we have norm equivalence [||v||.sub.[psi]] [??] [[[[integral].sup.1.sub.0][|C([xi])|.sup.2] d[xi]].sup.1/2]. If {[[PHI].sub.n]; n [member of] Z} also forms a Riesz basis, a similar inequality will hold for [A.sub.[PHI]]([xi]), so that ||v|| [??] [[[[integral].sup.1.sub.0][|C([xi])|.sup.2] d[xi]].sup.1/2]. Then, [||v||.sub.[psi]] [??]. ||v|| and consequently [R.sub.[lambda]]([psi]) = [V.sub.[lambda]]([PHI]), which concludes the proof of Proposition 2.

In the case of a Gaussian function [psi], {[PHI].sub.n]; n [member of] Z} indeed forms a Riesz basis in [L.sup.2](R) [17]. But examples can be given where, although [psi] satisfies all the assumptions made in Section 2, we have

0 < [A.sub.[PHI]]([xi]) [less than or equal to] 1/k a.e. [xi] [member of] [S.sub.k]

for some [lambda] [member of] [LAMBDA] and a sequence of subsets [S.sub.k] [subset or equal to] R, k = 1,2,..., of positive measure. As a consequence, {[[PHI].sub.n] = [PHI](* - n[lambda]); n [member of] Z} neither can form a Riesz basis nor a frame in [L.sup.2](R), cf. [7, Theorem 7.2.3].

Proposition 3 Localization space [P.sub.[psi]] has the orthogonal decomposition

[P.sub.[psi]] = [R.sub.[lambda]]([psi]) [direct sum] [N.sub.[lambda]]([psi]), (7)

where subspace [N.sub.[lambda]]([psi]) consists of all functions h [member of] [P.sub.[psi]] with the property that h(n[lambda]) = 0 [for all]n [member of] Z. Every function g [member of] [R.sub.[lambda]]([psi]) is completely determined by the sample values g(n[lambda]), n [member of] Z.

Proof. The space [L.sup.2](R) has the orthogonal decomposition

[L.sup.2](R) = [V.sub.[lambda]]([psi]) [direct sum] [V.sub.[lambda]][([psi]).sup.[perpendicular to]]. (8)

Application of [P.sub.[psi]] yields [P.sub.[psi]] = [P.sub.[psi][V.sub.[lambda]]([psi]) + [P.sub.[psi]]([V.sub.[lambda]][([psi]).sup.[perpendicular to]]). By Proposition 2, [P.sub.[psi]][V.sub.[lambda]]([psi]) = [R.sub.[lambda]]([psi]). We now show that [P.sub.[psi]]([V.sub.[lambda]][([psi]).sup.[perpendicular to]]) = [N.sub.[lambda]]([psi]). If f [member of] [V.sub.[lambda]][([psi]).sup.[perpendicular to]], then h = [P.sub.[psi]]f satisfies

h(n[lambda]) = ([P.sub.[psi]]f)(n[lambda]) = <f, [psi](* - n[lambda])) = 0 [for all]n [member of] Z. (9)

So, h [member of] [N.sub.[lambda]]([psi]). Conversely, if h [member of] [N.sub.[lambda]]([psi]), then h = [P.sub.[psi]] f for some f [member of] [L.sup.2](R). Reading (9) from the left to the right shows that f is orthogonal on the dense subset {[[psi].sub.n];n [member of] Z} of [V.sub.[lambda]]([psi]). So, f [member of] [V.sub.[lambda]][([psi]).sup.[perpendicular to]].

The orthogonality [r.sub.[lambda]]([psi]) [perpendicular to] [N.sub.[lambda]]([psi]) in [P.sub.[psi] (implying [R.sub.[lambda]]([psi])[intersection] [N.sub.[lambda]]([psi]) = {0}) is seen as follows. If g [member of] [R.sub.[lambda]]([psi]), h [member of] [N.sub.[lambda]]([psi]), then g = [P.sub.[psi]][f.sub.1] for some [f.sub.1] [member of] [V.sub.[lambda]]([psi]) [subset or equal to] [L.sup.2](R| supp [??]) and h = [P.sub.[psi]][f.sub.2] for some [f.sub.2] [membet of] [V.sub.[lambda]][([psi]).sup.[perpendicular to]]. Define [f.sub.0] [member of] [L.sup.2](R| supp [??]) by [[??].sub.0] = [X.sub.supp [??]] x [[??].sub.2]. Then [P.sub.[psi]][f.sub.2] = [P.sub.[psi]][f.sub.0]. So, by Proposition 1 we have [<g, h>.sub.[psi]] = [<[P.sub.[psi]][f.sub.1], [P.sub.[psi]][f.sub.0]>.sub.[psi]] = <[f.sub.1], [f.sub.0]> = <[[??].sub.1], [[??].sub.0]> = <[[??].sub.1], [[??].sub.2]> = <[f.sub.1], [f.sub.2]> = 0. Thus, g [perpendicular to] h in [P.sub.[psi]].

Finally, if [g.sub.1], [g.sub.2] [member of] [R.sub.[lambda]]([psi]) with [g.sub.1](n[lambda]) = [g.sub.2](n[lambda])[for all]n [member of] Z, then [g.sub.1] - [g.sub.2] [member of] [R.sub.[lambda]]([psi]) [intersection] [N.sub.[lambda]]([psi]) = {0}. Hence, [g.sub.1] = [g.sub.2], which concludes the proof of Proposition 3.

We refer to [9, 10, 11] where orthogonal decompositons of Hilbert spaces have been used for the purpose of sampling and reconstruction in a more general and abstract setting.

4 Perfect Reconstruction in a Subspace

Since {[[PHI].sub.n]; n [member of] Z} does not always form a Riesz basis, the proof of the next theorem is based on frame theory. Concerning frame theory we refer to [7, 15, 31]. Because {[[PHI].sub.n]; n [member of] Z} also not always forms a frame for its closed linear span in [L.sup.2](R) we cannot resort to, e.g., [25, Theorem 2.1]. The RKHS property of [P.sub.[psi]] will now prove helpful; see [20, 22, 30], with regard to application of reproducing kernel Hilbert spaces in sampling theory.

Theorem 1 Let the prefilter function [psi] and the set [LAMBDA] [subset or equal to] [R.sub.+] be as assumed in Section 2 and let [lambda] [member of] [LAMBDA]. Then any function g [member of] [R.sub.[lambda]]([psi]) can be perfectly reconstructed from its sample values g(n[lambda]), n [member of] Z, by the series

g(x) = [[infinity].summation over (n=-[infinity])] g(n[lambda])[[PHI].sub.int](x - n[lambda]), x [member of] R, (10)

where the interpolating function [[PHI].sub.int] [member of] [R.sub.[lambda]]([psi]) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

The series in (10) converges in the norm of [P.sub.[psi]] and uniformly on N.

Proof. Since {[[psi].sub.n]; n [member of] Z} is a Riesz basis of [V.sub.[lambda]]([psi]) it also forms a frame for that space. Hence, there exist positive constants A, B (actually the' same as in (4)) so that for all f [member of] [V.sub.[lambda]]([psi]) we have

A [||f||.sup.2] [less than or equal to] [summation over (n[member of]Z)] [|<f,[[psi].sub.n]>|.sup.2] [less than or equal to] B[||F||.sup.2].

Because [[PHI].sub.n] = [P.sub.[psi]][[psi].sub.n] and [P.sub.[psi]] : [V.sub.[lambda]]([psi]) [right arrow] [R.sub.[lambda]]([psi]) is an isometry, we conclude that for all g [member of] [R.sub.[lambda]]([psi]) it holds that

A[||g||.sup.2.sub.[psi]] [less than or equal to] [summation over (n[member of]Z)] [|[<g,[[PHI].sub.n]>.sub.[psi]]|.sup.2] [less than or equal to] B[||g||.sup.2.sub.[psi]].

Thus, {[[PHI].sub.n];n [member of] Z} is a frame for the Hilbert space [R.sub.[lambda]]([psi]) [subset or equal to] [P.sub.[psi]]. The corresponding frame operator S : [R.sub.[lambda]]([psi]) has the representation Sg = [[SIGMA].sub.n[member of]Z][<g,[[PHI].sub.n]>.sub.[psi]] [[PHI].sub.n]. By frame theory it has a continuous inverse [S.sup.-1] : [R.sub.[lambda]]([psi]) [right arrow] [R.sub.[lambda]]([psi]) yielding the reconstruction formula

g = [summation over (n[member of]Z)] [<g,[[PHI].sub.n]>.sub.[psi]][S.sup.-1] [[PHI].sub.n]. (12)

Because of the RKHS property of the localization space [P.sub.[psi]], we already know that [<g,[[PHI].sub.n]>.sub.[psi]] = [<g,[PHI](* - n[lambda])>.sub.[psi]] = g(n[lambda]). The uniquely determined solution [psi]dual [member of] [V.sub.[lambda]]([psi]) of the system of equations

<[[psi].sub.dual], [psi](*, - n[lambda])> = [[delta].sub.n], n [member of] Z,

exists by virtue of the positive lower bound in Ineq. (4) and has Fourier transform

[[??].sub.dual]([xi] = [??]([xi)/[LAMBDA][[SIGMA].sub.k[member of]Z][|[??]([xi] + k[LAMBDA])|.sup.2] (13)

(The argument in [17] in the case of a Gaussian function [psi] carries over to the general case without changes.) Defining [[PHI].sub.int] = [P.sub.[psi]] [[psi].sub.dual] we infer, again by isometry, that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus, [S.sup.-1][[PHI].sub.m] = [[PHI].sub.int](* - m[lambda]) and (12) turns into (10). By means of the Fourier domain representation of [P.sub.[psi]] we readily obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which proves (11).

Frame theory ensures convergence of the series in (12) in the norm [parallel]*[[parallel].sub.[psi]]. Let [g.sub.N] be the Nth partial sum. Since (g - [g.sub.N])(x) = [<g - [g.sub.N], [PHI](x - X)>.sub.[psi]], application of the Cauchy-Schwarz inequality results for any x E [9 in the estimate

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which proves uniform convergence [g.sub.N] [right arrow] g on R and concludes the proof of Theorem 1. [1].

We note that because of [[PHI].sub.int] (n[lambda]) = <[[psi].sub.dual], [psi](* - n[lambda])> the interpolating function [[PHI].sub.int] has the interpolation property

[[PHI].sub.int](n[lambda]) = [[delta].sub.n], n e Z. (14)

Remark 2 A similar result holds for the space [V.sub.[lambda]]([psi]): Every f [member of] [V.sub.[lambda]]([psi]) can be perfectly reconstructed from its sample values f(n[lambda]), n E Z, by the series

f(x) = [[infinity].summation over (n=-[infinity])] f(n[lambda])[[psi].sub.int](x - n[lambda]),

where the interpolating function [[psi].sub.int] [member of] [V.sub.[lambda]]([psi]) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

provided that the denominator in (15) does not vanish (and some additional regularity assumptions on [psi]). This result is due to Walter [30] who proved it for orthonormal bases {[psi](* - n); n [member of] Z}. The argument is essentially the same for Riesz bases; see [17] for the case of a Gaussian function [psi]. We shall return to this topic at the end of Section 6.

5 Error Estimate

If g is in [P.sub.[psi]] \ [R.sub.[lambda]](psi), then the series in Theorem 1 still may be computed but will result in an orthogonal projection [??] of g onto [R.sub.[lambda]]([psi]) rather than in g itself. The purpose of this section is to estimate the error [absolute value of g(x) - [??](x)] for any x [member of] R.

Let g = [P.sub.[psi]]f with f [member of] [L.sup.2](R) and define [??] = [P.sub.[lambda]]f where [P.sub.[lambda]] is the orthogonal projection from [L.sup.2](R) onto [V.sub.[lambda]]([psi]). Then [??] = [P.sub.[psi]][??] = [P.sub.[psi]][P.sub.[lambda]]. So, we need to estimate [absolute value of ([P.sub.[psi]])(x) - ([P.sub.[psi]][P.sub.[lambda]]f)(x)] for arbitrary f [member of] [L.sup.2](R) and x [member of] R.

Proposition 4 Let [lambda] [member of] [LAMBDA]. The orthogonal projection [P.sub.[lambda]] : [L.sup.2](R) [right arrow] [V.sub.[lambda]]([psi]) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (16)

where [LAMBDA] = 2[pi]/[lambda] and [[??].sub.dual] is as in (13).

Proof. In the special case [lambda] = 1 representation (16) is readily obtained from [4, Theorem 2.9]. The general case [lambda] [member of] [LAMBDA] can then be deduced from the previous one by rescaling. This concludes the proof of Proposition 4. []

Proposition 5 Let [lambda] [member of] [LAMBDA]. The operator [Q.sub.[lambda]] = [P.sub.[psi]][P.sub.[lambda]] : [L.sup.2](R) [right arrow] [R.sub.[lambda]]([psi]) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (17)

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof. Let f [member of] S(R) where S(R) is the Schwartz space of [C.sup.[infinity]] functions on R rapidly decaying at infinity. By (1), (13), and (16) we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since [P.sub.[lambda]], and [P.sub.[psi]] are continuous operators from [L.sup.2](R) into itself, so is [Q.sub.[lambda]]. Consequently, the representation (17) extends to all of [L.sup.2](R) by continuity. This completes the proof of Proposition 5. []

Lemma 1 (Generalized Chebyshev Inequality) Let [phi] be a probability density function on R, i.e., [phi](x) [greater than or equal to] 0, [[integral].sub.R][phi](x)dx exists and is equal to 1. Assume that M = [[integral].sub.R] w([absolute value of x])[phi](x) dx < [infinity], where w(x) for x > 0 is positive and monotonically increasing. Then

[[integral].sub.[absolute value of x][greater than or equal]t] [phi](x) dx [less than or equal to] M/qt [for all]t > 0. (18)

Proof. Let t > 0. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which proves Lemma 1. We found the preceding theorem as an exercise in the textbook [13]. Note that the normalization condition [[integral].sub.R] [phi](x) dx = 1 is unnecessary. []

Theorem 2 Let f [member of] [L.sup.2](R), g = [P.sub.[psi]]f and [??] = [Q.sub.[lambda]]f, where [lambda] [member of] [LAMBDA]. Then for all x [member of] R it holds that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (19)

Proof. By (1) and (17) we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since [absolute value of [e.sup.ix[xi]] - [Q.sub.[lambda]]),(x, [xi])] [less than or equal to] 2[E.sub.[lambda]]([xi]), where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

we obtain by means of the Cauchy-Schwarz inequality that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Because

0 [less than or equal to] [E.sub.[lambda]] ([xi]) [less than or equal to] 1 (20)

we get for the first integral factor [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Writing

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where we have used the notation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

we need to estimate the two constituent integrals. This will be done by means of inequalities (18) and (20).

Integral I([pi]/[lambda], [infinity]):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (21)

Integral I(0, [pi]/[lambda]):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (22)

Because of growth condition (3) imposed on the weight function w, the infinite series converges. By (21), (22) it follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Consequently,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By Proposition 1 we may assume that f [member of] [L.sup.2](R|supp [??]). Then [parallel]f[parallel] = [parallel]g[[parallel].sub.[psi]], which concludes the proof of Theorem 2. []

5.1 Example: Monomial Weight w([xi]) = [[absolute value of [xi]].sup.s], s > 1

We define

[[mu].sub.s]([psi]) = [[[M.sub.w]([psi])/[parallel][psi][[parallel].sup.2].sup.1/s].

It is not difficult to prove the identity [[summation].sup.[infinity]].sub.n=1][(2n - 1).sup.-s] = (1 - 2-s) [zeta](s) for the Riemann zeta function [zeta](s) = [[summation].sup.[infinity]].sub.n=1] [n.sup.-s], R(s) > 1. Then, Ineq. (19) turns into

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (23)

The right-hand side of (23) shows sth-order decays as

0 [left arrow] [lambda] [[lambda].sub.0] = [pi] / [[mu].sub.s]([phi]). (24)

Here, of course, inf [LAMBDA] = 0 is supposed. Note that the upper bound in (24) becomes more and more tight as s [right arrow] [infinity]. In the special case s = 2 we obtain by means of the celebrated identity [zeta](2) = [[pi].sup.2]/6 of Euler (1) the remarkably simple inequality

[|g(x) - [??](x)|.sup.2] [less than or equal to] [([[mu].sub.2]([phi])[lambda]).sup.2][[parallel][phi][parallel].sup.2] [[parallel]g[parallel].sup.2.sub.[phi]]. (25)

6 Sampling Theorem

The following theorem is a consequence of Theorem 1, Theorem 2, and the interpolation property (14).

Theorem 3 (Generalized Sampling Theorem) Let the prefilter [P.sub.[phi]] and the set [LAMBDA] of admissable sampling intervals be as assumed in Section 2. For arbitrary [lambda] [member of] [LAMBDA] the interpolating function [[PHI].sub.int] [member of] [R.sub.[lambda]]([phi]) [[subset].bar] [P.sub.[phi]] is defined by (11). Then for any signal g in the localization space [P.sub.[phi]] of [[P.sub.[phi]] the series

[??]g(x) = [[infinity].summation of (n=-[infinity])] g(n[lambda])[[PHI.sub.int](x - n[lambda]) (26)

converges in the norm of [P.sub.[phi]] and uniformly on R to a function [??] [member of] [R.sub.[lambda]]([phi]) with the property that [??](n[lambda]) = g(n[lambda) [for all]n [member of] Z. For all other x [membr of] R the relative approximation error [[member of].sub.lambda](x) = |g(x) - [??](x)\[[parallel]g[parallel].sub.[phi]] satisfies the estimate

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (27)

Theorem 3 may serve as a pattern for the proof of specific sampling theorems. Examples are given in the following subsection.

The upper bound in Ineq. (27) deserves special attention. As seen in Section 5.1, it may allow for the identification of a critical sampling interval [[lambda].sub.0] with the property that the error [[member of].sub.[lambda]](x) diminishes substantially as soon as the sampling interval [lambda] falls under [[lambda].sub.0]. Similar to the Nyquist interval in the classical sampling theorem [24, 29], we may also get a link between [[lambda].sub.0] and some measure of bandwidth for the prefilter function [phi] (or the prefilter [P.sub.[phi]]). Indeed, inequality (25) suggests the critical sampling interval [[lambda].sub.0] = 1/[sigma]([phi]), where [sigma]([phi]) = [mu]2([phi]) is defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (28)

[sigma]([phi]) may be viewed as the standard deviation of the probability density function [[parallel[??][parallel].sup.2][absolute value of [??].sup.2] in the frequency domain. Following Gabor [14] where a centered version of [sigma]([phi]) called "effective frequency width" has been defined, we might take [sigma]([phi]) as a measure of "soft bandwidth" for [phi] (or [P.sub.[phi]]). Inequality (25) then tells us that, under the assumption [sigma]([phi] < [infinity], the sampling interval should be chosen smaller than the reciprocal "soft bandwidth" [sigma]([phi]).

A definition of "soft bandwidth" could, of course, also be based on other weights w leading to, e.g., the moment-like quantities [[mu].sub.s] ([phi]) of Section 5.1.

6.1 Instances of the Generalized Sampling Theorem

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (29)

where sinc x = (sin x)/x, defines the ideal low-pass filter of (two-sided) bandwidth 2[pi][beta]. For an arbitrary weight function [w.sub.s]([xi]) = s[([pi][beta]).sup.1-1][[absolute value of [xi].sup.s-1] with s > 2 we compute that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The Riesz basis condition (4) is fulfilled for [member of] A = [1/[beta], [infinity]). Localization space [P.sub.[phi]] coincides with the space of finite-energy signals bandlimited to [-[pi][beta], [pi][beta]]. With the special choice [lambda] = 1/[beta] (Nyquist interval) we now obtain by means of Theorem 3 for fixed g [member of] [P.sub.[phi]], and an arbitrary weight function [W.sub.s]([xi]), s > 2, observing that [[parallel]g[parallel].sub.[phi]] = [beta][parallel]g[parallel], the inequality

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since the upper bound tends to 0 as s [right arrow] [infinity], it follows that [??](x) = g(x) [for all]x [member of] R. Furthermore, by (11) we immediately see that [[PHI].sub.int](X) = sine ([pi][beta]x). As a result, we have proved the classical sampling theorem [24] showing that it is within the scope of our generalized approach.

2) For the prefilter function

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (30)

a Gaussian probability density function of standard deviation l/[beta], [beta] > 0, the weight function

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and [LAMBDA] = [R.sub.+] may be used. Since [M.sub.w]([phi]) = [beta]/[square root of 2[pi]] < [infinity] and for [lambda] > 0 small enough (condition (32), see below, is sufficient)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

we obtain by Theorem 3 the estimate

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (31)

Because of the "three-sigma rule" for the Gaussian function in the interpretation given in [16], the right-hand side of Ineq. (31) becomes small as soon as [pi]/[lambda] > [pi][beta] or, equivalently,

0 < [lambda] < [[lambda].sub.0] = 1/[beta], (32)

then decaying super-exponentially to 0 as [lambda] [right arrow] 0. (By means of a specific inequality for the tails of the Gaussian function it is shown in [16] that the error becomes very small when [lambda] = [[lambda].sub.0] = 1/[beta].) We note that A0 is related to the "soft bandwidth" [sigma]([phi]) of the Gaussian function (30) by the equation [[lambda].sub.0] = 1/([square root of 2[sigm]([phi])). The corresponding interpolating function [[PHI].sub.int] has been calculated in [16, 17].

3) The centered B-spline of order m [27], m = 2, 3, ...,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (33)

may also be used as prefilter function [phi]. Any weight function

w([xi]) = [|[xi]|.sup.s], 1 > s > 2m - 1,

may be taken. Since the central term in (4) has zeros when [lambda] = 1/2, 1/3, 1/4, ..., we choose [LAMBDA] = [R.sub.+}\ {1/2, 1/3, 1/4, ...} as the set of admissable sampling intervals. Then Theorem 3 applies and Ineq. (23) becomes

[|g(x) = [??](x)|.sup.2] [less than or equal to] C [[lambda].sup.s] [for all]x [member of] R, (34)

where C is some finite constant not depending on [lamda] [member of [LAMBDA]. Now, let [LAMBDA] [??] [lambda] [right arrow] [[lambda].sub.l] = 1/l for l [member of] {2, 3, ...} held constant. Since zeros arising in (11) in the denominator are cancelled by corresponding zeros of the numerator [??]([xi] = [[??].sup.2m-1]([xi]) we observe convergence [[PHI].sub.int] [right arrow] [[PHI].sub.l,int] in [L.sup.2](R) where [[PHI].sub.l,int] is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with [[??].sub.l]([xi]) = (1/l)[??]([xi]/l). In Figure 1(a)-(d) this bevaviour is depicted for prefilter function [phi](x) = [[beta].sup.2](x) in case l = 4.

[FIGURE 1 OMITTED]

As a consequence, [??] as given by (26) tends to [??].sub.l] in [L.sup.2](R) as [lambda] [right arrow] [[lambda].sub.l], where

[[??].sub.l](x) = [summation over of (n[member of) g(n/l)[[PHI].sub.l,int](x - n/l).

Since inequality (34) continues to hold as [lambda] [right arrow] [[lambda].sub.l], [??] [right arrow] [[??].sub.l], it follows that

|g(x) - [[??].sub.l](x)|.sup.2] [less than or equal to] C [l.sup.-s] a.e. (35)

for any l [member of] N held constant. Because g, [??] are continuous functions, inequality (35) holds everywhere in R. By inspection of the Fourier transform of [[??].sub.l] it can be seen that always [[??].sub.l] [member of] [P.sub.[phi]] (whereas [[PHI].sub.l,int] [??] [P.sub.[phi]] l = 2,3, ...!). As a result, the functions [[??].sub.l] form an approximation to g in [P.sub.[phi]] with sth-order decay of squared error [|g(x) - [[??].sub.l](x)|.sup.2] as l [right arrow] [infinity], uniformly in x [member of] R.

Since [[PHI].sub.l,int] is the interpolating function (11) for the dilated prefilter function [phi].sub.l](x) = [l.sup.1/2][[beta].sub.m-l](lx) and [lambda] = l/l, it can be computed by the theorem of residues as indicated in [1].

There is no reason to refrain from using non-centered B-spline functions [N.sub.m](x) [23] of any order m = 2, 3, 4, ... defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (36)

Indeed, the prefilter function [phi](x) = [N.sub.m](x) will result in the same localization space [[P.sub.[phi]] as when using [phi](x) = [[beta].supm-1](x). The interpolating functions [[PHI].sub.int] will also coincide. Therefore, when [phi](x) = [N.sub.m](x) we always have a sampling theorem in the space [R.sub.[lambda]]([phi]) = [P.sub.[phi]][V.sub.[lambda]]([phi]) (at least when 0 < [lambda] [not equal to] 1/2, 1/3, 1/4, ...). On the other hand, there is no sampling theorem in the shift-invariant subspace [V.sub.[lamda]]([phi]) [[subset].bar] [L.sup.2](R) in case [lambda] = 1 and rn = 3,5,7, ... as shown by the following counterexample (a simple generalization of the one given by Walter [30]): The interpolating function (see Remark 2) [[phi].sub.int] [member of] [V.sub.1] ([N.sub.m]), m [greater than or equal to] 3 odd, defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

has a pole in [xi] = [pi] because in the numerator we obtain [[??].sub.m] ([pi]) [not equal to] 0, whereas the denominator becomes

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

As a conclusion, in Figure 2 the Fourier transforms of related interpolating functions [[PHI].sub.int] or [[PHI].sub.l,int] are depicted: for ideal low-pass ([beta] = 4), Gaussian ([beta] = 2) and B-spline (m = 3) prefilter function [phi] and [lambda] = 0.25 or l = 4.

[FIGURE 2 OMITTED]

ACKNOWLEDGEMENT

The present work originates in a talk given in the Time-Frequency Seminar of EUCETIFA during a stay at the University of Vienna, May 15-17, 2006. We are grateful to K. Grochenig and H. G. Feichtinger for hospitality and advice.

References

[1] A. Aldroubi, M. Unser, and M. Eden, Cardinal spline filters: Stability and convergence to the ideal sinc interpolator, Signal Process., 28, 127-138, 1992.

[2] A. Aldroubi and M. Unser, Sampling procedures in function spaces and asymptotic equivalence with Shannon's sampling theory, Numer. Funct. Anal. and Optimiz, 15, 1-21, 1994.

[3] T. Blu and M. Unser, Approximation error for quasi-interpolators and (multi-)wavelet expansions, Appl. Comput. Harmon. Anal., 6, 219-251, 1999.

[4] C. de Boor, R.A. DeVore, and A. Ron, Approximation from shift-invariant subspaces of [L.sub.2]([R.sup.d]), Trans. Amer. Math. Soc., 341, 787-806, 1994.

[5] P.L. Butzer, W. Splettstosser, and R.L. Stens, The sampling theorem and linear prediction in signal analysis, Jber. d. Dt. Math.-Verein., 90, 1-70, 1988.

[6] P.L. Butzer and R.L. Stens, Sampling theory for not necessarily band-limited functions: A historical overview, SIAM Review, 34, 40-53, 1992.

[7] O. Christensen, An Introduction to Frames and Riesz Bases, Birkhauser, Boston, 2003.

[8] I. Daubechies, The wavelet transform, time-frequency localization and signal analysis, IEEE Trans. Inform. Theory, 36, 961-1005, 1990.

[9] Y.C. Eldar, Sampling with arbitrary sampling and reconstruction spaces and oblique dual frame vectors, J. Fourier Anal. Appl., 9, 77-96, 2003.

[10] Y.C. Eldar and T. Werther, General framework for consistent sampling in Hilbert spaces, Int. J. of Wavelets, Multiresolution and Inform. Process., 3, 497-509, 2005.

[11] Y.C. Eldar and T.G. Dvorkind, A minimum squared-error framework for generalized sampling, IEEE Trans. Signal Process., 54, 2155-2167, 2006.

[12] H.G. Feichtinger and T. Strohmer (ed.), Advances in Gabor Analysis, Birkhauser, Boston, 2003.

[13] W. Feller, An Introduction to Probability Theory and Its Applications, vol. I, 3rd ed., John Wiley & Sons, New York, 1967 (revised printing 1970).

[14] D. Gabor, Theory of communication, J. Inst. Elect. Eng. (London), 93 (III), 429-457, 1946.

[15] K. Grochenig, Foundations of Time-Frequency Analysis, Birkhauser, Boston, 2001.

[16] E. Hammerich, A sampling theorem for time-frequency localized signals, Sampl. Theory Signal Image Process., 3, 45-81, 2004.

[17] E. Hammerich, Sampling in shift-invariant spaces with Gaussian generator, Sampl. Theory Signal Image Process., 6, 71-86, 2007.

[18] A.J. Jerri, The Shannon sampling theorem--Its various extensions and applications: A tutorial review, Proc. IEEE, 65, 1565-1596, 1977.

[19] A.J. Jerri, Error analysis in application of generalizations of the sampling theorem, in: R.J. Marks II (ed.), Advanced topics in Shannon sampling and interpolation theory, Springer, New York, 219-298, 1993.

[20] H.P. Kramer, A generalized sampling theorem, J. Math. and Phys., 38, 68-72, 1959.

[21] V.G. Maz'ja, Sobolev Spaces, Springer, Berlin, 1985.

[22] M.Z. Nashed and G.G. Walter, General sampling theorems for functions in reproducing kernel Hilbert spaces, Math. Control, Signals, Syst., 4, 363-390, 1991.

[23] I.J. Schoenberg, Contribution to the problem of approximation of equidistant data by analytic functions, Quart. Appl. Math., 4, 45-99, 112-141, 1946.

[24] C.E. Shannon, Communication in the presence of noise, Proc. IRE, 37, 10-21, 1949.

[25] W. Sun, Sampling theorems for multivariate shift invariant subspaces, Sampl. Theory Signal Image Process., 4, 73-98, 2005.

[26] M. Unser and A. Aldroubi, A general sampling theory for nonideal acquisition devices, IEEE Trans. Signal Process., 42, 2915-2925, 1994.

[27] M. Unser, Splines: A perfect fit for signal and image processing, IEEE Signal Process. Mag., 16, 22-38, 1999.

[28] M. Unser, Sampling--50 years after Shannon, Proc. IEEE, 88, 569-587, 2000.

[29] P.P. Vaidyanathan, Generalizations of the sampling theorem: Seven decades after Nyquist, IEEE Trans. Circuit Syst. I, 48, 1094-1109, 2001.

[30] G.G. Walter, A sampling theorem for wavelet subspaces, IEEE Trans. Inform. Theory, 38, 881-884, 1992.

[31] R.M. Young, An Introduction to Nonharmonic Fourier Series (Revised First Edition), Academic Press, London, 2001.

Dedicated to Professor Abdul J. Jerri on the occasion of his 75th birthday

* Presented in part on the International Workshop on Sampling Theory and Applications (SampTA07), Thessaloniki, Greece, June 1-5, 2007.

(1) See M. du Sautoy, The Music of Primes. Why an Unsolved Problem in Mathematics Matters, Fourth Estate, London, 2003, for a historical account

Edwin Hammerich

Ministry of Defence

Kulmbacher Str. 58-60, D-95030 Hof, Germany

e-mail: [e-mail]