THE PALEY-WIENER-LEVINSON THEOREM REVISITED

THE PALEY-WIENER-LEVINSON THEOREM REVISITED

A.G.GARC(A

Departamento

de Matemticas Escuela Polit6cnicaSuperior UniversidadCarlos

III

de Madrid

c/Butarque,

15,28911

Legan6s,

Madrid, Spain

(Received August 4, 1995 and in revised form October 12, 1995)

ABSTRACT. In

this paper a newproof of the Paley-Wiener-Levinson theorem is presented.

This proofisbasedupon the isometrybetween the Paley-Wienerspaceand that of the square- integrablefunctions in

[-r, r],

^{on one}

hand,

and aTitchmarsh’stheorem which allowsrecovering

bandlimited,

entirefunctionsfromtheirzeros, onthe other hand.

KEY WORDS AND PHRASES.

Nonuniformsampling,

Lagrange

type interpolation series, Rieszbasis,entirefunctionsofexponentialtype.

1991

AMS SUBJECT CLASSIFICATION CODES. 30D10, 30D20,

41A05, 42A65, 94A12

1 Introduction

Theaimof this paper istwofold:

first,

itprovidesanew somehow simpler-

proof

of thePaley- Wiener-Levinson

(PWL) theorem,

and

second,

itmakes clear the relationshipbetweenrecovering finite-energy, bandlimited functions froman infinite set ofsamples ^or from its real zeros

(zero

crossings,intechnical

jargon),

twowell-known toolsinsignal processing

[1,

2,

3].

If

B

^{denotes the spaceof}

[-r, r]-bandlimited L2-functions,

the classic Whittaker-Shannon- Kotel’nikov

(WSK)

^theoremstatesthatany

f B

^{canbe writtenas}

f(z) f(n)Sinr(z ⁿ⁾

r(z-n) z, (1.1)

which canalso bewritten

f(z) f(n) C(z)

G’(n)(z n) ^(1.2)

if

G(z)

^sin

rz/r.

The latter expression exhibits the

Lagrange

type interpolatory character of the

WSK

result. Equation

(1.1)

expresses thepossibilty of recoveringacertainkind ofsignalfrom asequence ofregularly spaced samples.

From

apracticalpoint of viewit isinterestingtohaveasimilarresult, but for asequence of samplestaken witha

nonuniform

distribution alongthe real line

(a

straightforward application of this result would be the recovering ofsignals fromsamples affected by time-jittererror, i.e..

takenat pointst, n

+

^{$,, with}

,

^somemeasurementuncertainty).

An

appropriate questionto getsucharesult would be how close should thesamplepoints be to the

regular

samplepointsso thatasimilar equationto

(1.2)

stillholds.

A

first answertothis questionwasgiven by Paleyand Wiener

[4],

^whoproved that if the sequence ofsamplepoints,

{t}eZ,

^satifies

D

sup

I,- ,I < , (1.3)

where

" ^1/r2,

^and the sequenceissymmetric,i.e., t_

t (n > 1),

^{then a.ny}

J"

E /3 can be expressed^as

wherenow

f(z) f(t) a()

G,(t,)(z t,) (1.4)

a(z) (z to) 1"1 ^(-)

Later

on, Levinson

[5]

^extendedcondition

(1.3)

tor

1/4

and nonsymmetric sequences. This resultis relatedwiththe "maximum" perturbationofthe Hilbert basis

{e }eZ

of the square- integrablefunction space

LZ[-Tr, r],

^{in sucha}way that theperturbed sequence

{c

^{-’t’’’}

}eZ

^isa

Riesz basisof thesamespa.ce. Ka.dec proved that Levinson’sresllt,

- ^1/4,

^{is1.1" l,sl, iossiile,}

in thesensethat if

D 1/4

counterexamplescan be found.

See [6]

for details.

The problemofsignal recovering has alsobeen consideredfromadifferent point of view.

It

is well-knownfromthe classic Paley-Wienertheorem that

[-zr, r]-bandlimitcd L2-function

space coincides withthat of theentirefunctionsof exponential type at most 7rwhose restriction to

IR belongs

to

L(IR). Although

^entire functionsare not

completely

deter:ninedby the location of their zeros, ascan be seenfromthe Hadamardfactorization theorem

[6],

bandlimited functions are,as canbededuced fromaTitchmarsh’stheorem

[7, 8]

towhich willreferlateron.

A [a,

bandlimited functionisuniquelydeterminedbyits zerosup toanexponentialfactordependingon thespectralinterval. Ifthespectralintervalisof the form

[-a, a],

^thisexponentialfactor reduces toaconstant.

A good

survey of alltheseresultscan be foundinRef.

[9].

As

explainedin thebeginning, the^aimofthis paper is to combinetheideasof perturbingthe Hilbert basis

{e }eZ

^{to get aRieszbasis with thoseofrecoveringa}bandlimited signalfrom itszerocrossings,intoanewproof of the

PWL

interpolation theorem.

2 Recovering bandlimited L2-functions

Let

usconsider the spaceof

[-Tr, 7r]-bandlimited L2-functions

B,, f

E

L(IR) /[If[[ If(x)[ dx <

^candsupp

f

^C_

[-Tr, ’]

{f

^entireof exponential typeat most7r,with

fllR L(IR)}

where the last equalityis the statement of the classic Paley-Wiener theorem. Provided with the innerproduct

(f, ^g)s =/(C) ^f.,

^{the space}

^B

^isaseparableHilbert space, isometricallyisomorphic to

L2[-Tr, 7r].

^Theisomorphismis preciselythe Fouriertransform

B, [-5’r] f(z)

j_

f(t)

^dt.

(2.1)

f f

The followingpropertiescanbe established:

(a)

The energy of

f B

^{iscontainedin itssamples}

{f(n))=eZ:

--[Ifllt ....

^1-

^If(n)

Ilfl[ ^{If(x)] =dx} If(t)[ 2dt

since

{f(n)},eZ

^arethe Fourier coefficients ofthe 27r-periodic^{extension of}

f

in the expo- nentialtrigonometricbasis.

(b)

^Since

{e )eZ

^isanorthonormal basis of

L[-r,r],

^sois

.T

^-1

({e }eZ) {sinr(z- (- ) n)} .z ^{{Tsinc z},Z,}

where

T,f(z) f(z-a)is

the translationoperator.

Therefore,

any

f

^E

^B,

^{canbeexpanded}

as thecardinal series

sin

7r(z n)

f(z) c

^c,

(f,

T,sinc

>B,,.

(c) Convergence

inthenormof

B

implies uniform convergence in horizontal stripsil

,

^because

If(z)! _< ,:l’lllJ’ll.,

^{z z}

+

^,y.

Thisfollows,in astraightforwardway, from theisometry and Cauchy-Schwarz inequality:

(d)

^Thesincfunctionisthe reproducing kernelof

B:

^for

f

^E

B

^{and x}E

IR,

/_"

^e

’’

j(z) J"(,) df (f,-’’>z,=[ ....

^]=

fir ^{f(t)sinc (t x)}

^dt

(f sinc)(x).

By

taking z n

e ’

ⁱⁿ

^(b)

^andusing

^(c),

^itfollows that

c f(n).

This isa proofof the classic

WSK

theorem:

THEOREM

2.1

(WKS theorem) Every f ^e L2(IR)

bandhmzted to

[-Tr, Tr]

^can be recon- structed

from

^{ztssamples at} the integers

{f(n)}ne z

^{via the}

formula

f(z) f(n)SinTr(z-- ⁿ⁾

.(z--)

where the convergence ^is

umform

ⁱⁿhorizontal strips

of

^(.

(in ^partzcular

ⁱⁿ

IR).

By

meansof this theoremwehaveatoolforrecoveringbandlimitedsignalsfromasequence of samples; but, ^as commented in the Introduction, these signals can also be recovered from theirzeros

(zero

^crossingsin the real

case).

The followingTitchmarsh’s theorem

[7]

^providesthe

mathematical foundation for this:

THEOREM

2.2

(Titchmarsh theorem) Let F e L[a, b]

^and

define

^{the entire}

functzon f

to be

f(z) F(w)

^edw.

Then

f

has infinitely many zeros,

{z,},e,

^with nondecreasmg absolute values, such that

f(z) f(O)

^e

z II

^i-

where the

infinite

^productzs conditionally

convergent.

In

the above

theorem,

it is assumedthat a and bare the effective lower and upper limits of theintegral, in thesensethat therearenonumbersa

>

^a

and/9 <

bsuch that

F(aa)

⁰

(a.e.)

ⁱⁿ

[, ]

^or

[Z, ].

If

f

^isbandlimited to

I-a, el,

^then

provided

f(0) #

^0,or

f(z)=f(O) H

^i----

r=l Zn

f(z) Az 1-I

^1-

ifz 0 isazeroof

f

^{of orderm.}

Noticethat the zeros in Titchmarshtheorem may be complex. This poses a difficulty from a technical viewpoint, a.s complex zerosarc harder todetect 1.l,a, real zeros;

arereal,^thistheorem providesauseful tool for signalrecovering, usually referred ^{to as} real-zero mlerpolatwn

[2, 10].

3 The PWL interpolation theorem

In

what follows

{t}eZ

^C

^IR

^willdenoteasequence of real numbers such that

Let

us define

D

sup

]t,- n[ <

,’,eZ 4

O(z) (z-t0) ri

^{1- 1-}

anentire, well-defined function

(whose

^{set ofzeros is}

{t,}eZ

^asit will be madeclear

along

the proofof the

following

theorem.

THEOREM

3.1

(PWL theorem) Any f

^E

^B,

^can be recovered

from

^its sample values

{f(t)}ez

^bymeans

of

^the

^Lagrange

type interpolationseries

f(z) f(t.) a(z) G,(t.)(z

which ^is uniformly convergentznhomzontalstrops

of

^f.

(in

partzcularⁱⁿ

PROOF: By

Kadec’s

-theorem ^(p.

^{42of Ref.}

^[6]), {e-’t"}Z

^isaRiesz basis of

L[-=, ].

Consequently

it will admit a unique biorthogonal basis

{h()}e _z ^(p.

^{2S of aef.}

[6]),

i.e., for everym,n 6

,

(h, e-’t=)L ....

¹⁼

⁶ (Kronecker’s symbol).

Thus,every

] L2[-r, r]

canbeexpressed

f) (Lh.)L=[ ....

^]e-’’"e

<Le-""e>L=[ .... ^lh()

By

using the isometry

-,

^{wehave in}

B

f(z)= (,> .... -’ (,-,’.)(z)=

By

setting g

’-l(h)

and taking into acount that

(f,h)L[ .... ^(f,g)s.

^{and that, by}

property

(d)

ofsection2,

(f,e-’t>L ....

^]=

(f, Tt.sinc)B, f(t,),

^{we canrewrite}

Now,

f(z)= [ (f,g)s.(Tt.sinc)(z)= , f(t,)g,(z).

a.(z) :-’(h.)(z) h.()

isanentirefunction,bandlimitedto

[-Tr, 7r]

^{whosezerosare}

{t, },#,

^and

therefore,

byTitchmarsh theorem,

g(z) A ^G(z)

(Notice

^thatbysettingn 0,forinstance, the above formulashowsthat

G(z)

^isa.nentirefunction, stated at the beginingof this

section.)

^Since

g(t)

1,then

A ^1/G’(t);

^thus

C(z)

which isconvergentin thenormof

B,, and,

by property

(c)

^ofsection2,uniformly in horizontal strips of

.

Although^notimportant for theproof,^wehaveobtained,sabyproduct,theinterestingresult that

{(Tt, sinc)(z)}ez

^and

{g(z)}e

^arebiorthogonalRieszbasesin

The irregular sampling problem h also been considered within more

general

bandlimited L-functions

[11],

^forinstance, where thereisasimilartheoremwhichhas been

proved

withcomplex variablestechniques.

One

ofthe most strikingdifferences is that the samplingis somewhatmoresensitive tonoise, inthe sensethat

{t}eZ

^{mustsatisfythestronger}restriction

D < 1/2p

for 2 p

< .

Acknowledgments

Thiswork is supported bythegrant no. PB-93-0228-C02-01 from theComisihn Interministeral de Ciencia yTecnologia

(CICyT)

ofSpain.

References

[1] SHANNON, C.E.,

"Communicationinthe presence ofnoise",

Proc. IRE

i37

(1949),

^10-21.

[2] MARVASTI, F., A Unified

^Approachto

^Zero

^Crossingsand

Nonuniform

^{Samphn#and Mul-}

tidzmensional Signals and

Systems,

1st

ed.,

Oak

Park, IL,

1987.

[3] REQUICHA, A.G.,

"The zerosofentirefunctions: Theory and Engineering Applications",

Proc. IEEE

68

(1980),

308-328.

[4] PALEY, R.,

and

WIENER, N.,

Fourier

Transforms

^{zn the Complex}

^Domazn,

^{Amer Math.}

Soc.

Colloq. Pub. Series, Vol.19,

Amer.

Math.

Soc.,

Providence,

RI,

^1934.

[5] LEVINSON, N., Gap

and Density

Theorems, Amer.

Math.

Soc.

Colloq. Pub. Series,Vol.26,

Amer.

Math.

Soc., New

York,

NY,

1940.

[6] YOUNG, R.M., An

Introduction to Nonharmonic

Fourzer

Series,Academic Press,New York, 1980.

[7] TITCHMARSH, E.C.,

^"Thezerosofcertainintegral functions",

Proc.

LondonMath.

Soc.

o.5

(1926),

^283-302.

[8] ZAYED, A.I.,

"Sampling forfunctionsbandlimited toadisc", Complex Varzables 26

(1994),

245-254.

[9] ZAYED, A.I.,

Advances znShannon’s

Samplzng

Theory,

CRC Press, Boca Raton, FL,

1993.

[10] BOND, F.E.,

and

CHAN, C.R., "On

samplingthe zerosof bandwidth limitedsignals",

IRE Trans. Inform.

Theory,

IT 4 (1958),

^110-113.

[11] ^HINSEN, G.,

"Irregular sampling of bandlimited LP-functions

’’, J. of ^Approx.

^{Theory 72}

(1993),

346-364.