Blind sampling.

Abstract

In this note we use inverse spectral theory to generate a sampling theorem from a given sequence of irregularly spaced sampling points. We only require the sequence to verify a certain convergence condition in Marchenko's theorem. The recovered singular Sturm-Liouville operator over the half real line helps to construct universal sampling functions, which would allow for the recovery of functions in [PW.sup.e.sub.b] where the type b is either arbitrary or a priori unknown.

Key words and phrases: Irregular sampling, Interpolation, Inverse spectral theory

2000 AMS Mathematics Subject Classification--42A15, 34A55

1 Introduction

We are concerned with the theory of irregular sampling associated with singular boundary value problems. The connection between sampling and boundary value problems was already observed by Kramer (see [9]) who has shown that the eigenvalues of certain types of boundary value problems can be used as sampling points. The main drawbacks in Kramer's theorem is the fact that eigenvalues are dictated by the given boundary value problem, and thus are fixed and obviously cannot be changed as one wishes. Secondly, it applies to transforms only and not to general functions in Paley-Wiener spaces (see [3]). In practice, one would like to reconstruct an analytic function whose values are known at an arbitrary sequence of irregularly spaced points. Thus, in our setting, the sampling points are usually not prescribed. For example, when monitoring a random process, one would not know ahead of time what and when values are obtained. It may also happen that data can be lost, which modifies the original distribution of sampling points. Thus, in practice, since the sampling points are imposed by the experiment, Kramer's theorem is of little or no use. There is, therefore, the need for an algorithm that constructs sampling functions from a given sequence of sampling points. Another important issue is the assumption of the type of the exponential growth of the function. In all recovery problems by sampling one usually knows in advance the type of the function to be recovered in order to set the minimum sampling rate. This prompts our first questions:

Q1: How can we reconstruct a function, without the knowledge of its type?

Q2: Is there a "universal" sequence of sampling points and functions that can reconstruct a function of arbitrary type?

In other words, we are dealing with blind sampling, where the sampling points are not prescribed a priori and the type of the function is either unknown or arbitrary.

To solve the blind sampling problem, we need to extend the results in [1], which we now briefly recall. We first start with a given sequence of points and then use the Gelfand-Levitan algorithm [4, 6] to tailor an operator whose spectral data coincides with the given sampling points. Kramer's theorem then yields a sampling formula for the given sampling points. More precisely, it is shown that if [[lambda].sub.n] [approximately equal to] [pi]/b n, as n [right arrow] [infinity], and otherwise arbitrary, then we can construct a potential q [member of] L(0, b) such that the eigenfunctions of the regular Sturm-Liouville problem

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

help construct the sampling functions

[S.sub.n]([lambda] = 1/[[alpha].sup.2.sub.n][[integral].sup.b.sub.0] y (x, [[lambda].sub.n]) dx (2)

where [[alpha].sub.n] = [square root of [[integral].sup.b.sub.0][absolute value of y (x, [[[lambda].sub.n])].sup.2]] dx]. From the spectral theory of Sturm-Liouville (SL) operators, it follows that for any F [member of] [PW.sup.e.sub.b] the Paley-Wiener space of entire even functions, of order 1 and type b, a sampling formula holds:

F([lambda] = [summation over (n[greater than or equal to]0)] F [[lambda].sub.n] [S.sub.n]([lambda]). (3)

For blind sampling, we need a formula such as (3) applicable to [PW.sup.e.sub.b] where the type b is arbitrary. Obviously we need to take the largest possible b, i.e., b = [infinity] in (1). Since [PW.sup.e.sub.a] [subset] [PW.sup.e.sub.b] if a < b, we introduce the inductive limit

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and so F [member of] [PW.sup.e.sub.[infinity]] if there exists b < [infinity] such that F [member of] [PW.sup.e.sub.b].

In this paper we would like to revisit sampling expansions in [PW.sup.e.sub.[infinity]], see [2]. More precisely, we investigate the existence and the characterization of a universal sampling sequence of points [[lambda].sub.n], such that (3) is valid for all F [member of] [PW.sup.e.sub.[infinity]]. Since sampling in [PW.sup.e.sub.b] is generated by (1) over the finite interval [0, b] it similarly follows that sampling in [PW.sup.e.sub.[infinity]] must be generated by a singular Sturm-Liouville operator over the infinite interval [0, [[infinity]).

2 Notation 

In the spirit of Kramer's theorem we use the singular Sturm-Liouville operator defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

where q [member of] C[0, [infinity]) and h is a real constant. We assume that L is a self-adjoint operator acting in [L.sup.2] (0, [infinity]), in the limit-point at x = [infinity], so no boundary condition is needed at x = [infinity]. If we normalize the eigensolutions of (4) by

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

then for each [lambda] [member of] C, the initial value problem has then a unique solution y(x, [lambda]) [member of] [L.sup.l,loc][0, [infinity]). This defines a transform for f [member of] [L.sup.2](0, [infinity]) and supp(f) compact,

F([lambda]) = [[integral].sup.[infinity].sub.0] f(x)y(x, [lambda])dx

and its inverse transform

f(x) = [[integral].sup.[infinity].sub.-[infinity]] F([lambda])y(x, [lambda])d[rho]([lambda]).

Here [rho], which is called the spectral function, is right continuous, has jumps at the eigenvalues only, and increases over the continuous spectrum. The Parseval equality reads as

[[integral].sup.[infinity].sub.-[infinity]] [absolute value of F([lambda])].sup.2] d [rho]([lambda] = [[integral].sup.[infinity].sub.0] [absolute value of f(x)].sup.2] dx. (6)

For the purpose of sampling we need a discrete spectrum, eigenvalues only, and so [rho] is a step function. This would happen if, for example, q is an increasing function [8].

In all that follows, we assume we are given a sequence of real numbers [{[[lambda].sub.n]}.sub.n[greater than or equal to]0], such that [absolute value of [lambda].sub.n]] are distinct and increasing. For example, [[lambda].sub.n] = [[epsilon].sub.n] [square root of n + 1] where [[epsilon].sub.n] = [+ or -] 1 and n [greater than or equal to] 0.

Definition 1 Assume that L in (4) has a discrete spectrum, say [{[[lambda].sup.2.sub.n]}.sub.n[greater than or equal to]0]. We say that the set {[[lambda].sub.n], [[alpha].sub.n]}.sub.n[greater than or equal to] 0 is its spectral data if Ly (x, [[lambda].sub.n]) = [[lambda].sup.2.sub.n] y (x, [[lambda].sub.n]) and

[[alpha].sub.n] = [square root of [[integral].sup.b.sub.0][[absolute value of y (x, [[lambda].sub.n]).sup.2]dx].

In the particular case when we have a discrete spectrum, the spectral function is a step function which leads to a variant of Theorem 2.3.1 from [7, p.169]:

Proposition 2 (Marchenko) Let [[alpha].sub.n] > [[lambda].sub.n] and An be two sequences of real numbers such that [absolute value of [[lambda].sub.n]] is strictly increasing; then there exists a unique continuous function q on [0, [infinity] and a real constant h such that the differential operator in (4) has spectral data [{[[alpha].sub.n], [[lambda].sub.n]}.sub.n[greater than or equal to] 0] if and only if the function [PHI](x) := [summation over (k [greater than or equal to] 0)] 1-cos(x [[lambda].sub.k)]/[[alpha].sup.2.sub.k] [[lambda].sup.2.sub.k] is thrice continuously differentiable and [PHI]'(0+) = 1.

The proof relies on Titchmarsh's result on the density of zeros of an entire functions in [PW.sub.b], which in our case happens to be the [[lambda].sub.n], and thus must satisfy the density condition

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where N(a) is the number of [[lambda].sub.n] in the interval (-a, a). The behavior of the spectral function plays a crucial role since it must satisfy [7, Theorem 2.4.2]

[rho] ([[lambda].sup.2]) = 2/[pi] [lambda] + c + 0(1) as [lambda] [right arrow] [infinity]. (7)

3 The norming constants [[lambda].sub.n]

Observe that a given irregularly spaced sampling sequence [[lambda].sub.n] is not sufficient to generate the operator (4). Namely we also need the sequence of norming constant [[alpha].sub.n] so we can use Marchenko's theorem. Because of the discreteness of the spectrum, the spectral function is a step function with jumps of size 1/[[alpha].sup.2.sub.n] at the points [[lambda].sub.n],

[rho] ([[lambda].sup.2.sub.n]) - [rho]([[lambda].sup.2.sub.n]) = 1/[[alpha].sup.2.sub.n].

Using the fact that [rho] is right continuous and constant between [[lambda].sub.n-1] and [[lambda].sub.n] to deduce that [rho] ([[lambda].sup.2.sub.n]) = [rho] ([[lambda].sup.2.sub.n-1] +)], (7) leads then to

2/[pi] [absolute value of [[lambda].sub.n]] - 2/[pi] [absolute value of [[lambda].sub.n-1]] + 0(1) = 1/[[alpha].sup.2.sub.n] as n [right arrow] [infinity] (8)

where the absolute value is due to the fact that (7) involves [square root of ([[lambda].sup.2.sub.n]) . Thus, we have the following proposition.

Proposition 3 If [{[[lambda].sub.n], [[alpha].sub.n]}.sub.n [greater than or equal to] 0] is spectral data, then [[alpha].sub.n] satisfy (8).

Therefore the [[alpha].sub.n]s depend on the sequence [[lambda].sub.n] which must satisfy the density condition [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [6]. Without loss of generality we can choose

1/[[alpha].sup.2.sub.n] = 2/[pi]([absolute value of [[lambda].sub.n]] - [absolute value of [[lambda].sub.n-1]]) for n [greater than or equal to] 0, (9)

which helps us recast Marchenko's theorem in terms of the given sampling sequence only.

Proposition 4 Let [{[[lambda].sub.n]}.sub.n [greater than or equal to] 0 be a sequence of real numbers such that [[absolute value of [lambda].sub.n]] is strictly increasing; the function

[PHI](x) := [[summation over (k [greater than or equal to]0)] ([absolute value of [[lambda].sub.k]] - [absolute value of [[lambda].sub.k-1]])/[[lambda].sup.2.sub.k] (1 - cos(x[[lambda].sub.k])) (10)

is thrice continuously differentiable and [PI]' (0+) = [pi]/2. Then there exists a continuous function q on [0, [infinity]) and a real constant h such that [{[[lambda].sup.2.sub.n]}.sub.n[greater than or equal to] 0] form the spectrum of the operator (4).

Here is an example of a sequence that satisfies the above proposition. If [[lambda].sub.n] = 1n (n + 1) for n = 1, 2, ..., then formally the continuity of

-[[PHI].sup.(3)] (x) = [summation over (k[greater than or equal to]1)]([[lambda].sub.k] - [[lambda].sub.k- 1])[[lambda].sub.k] sin (x [[lambda].sub.k]) = [summation over (k[greater than or equal to]1)] ln (1 + 1/k) ln (k + 1) sin (x ln (k + 1))

is equivalent to the continuity of [summation over (k[greater than or equal to]1)] ln (k + 1) sin(x ln (k + 1)). Indeed, for large k, ln (1 + 1/k) = 1/k + O (1/[k.sup.2]) and both series differ by [summation over (k[greater than or equal to]1)] 1/[k.sup.2] ln (k + 1) sin(x ln (k + 1)), which converges uniformly by Weierstrass M-test, since [absolute value of 1/[k.sup.2] ln(k + 1) sin(x ln(k+1))] [less than or equal to] 1/[k.sup.2] ln(k + 1) and [summation over (k[greater than or equal to]1] ln (k + 1) sin(x ln (k + 1)) < [infinity].

We now show that [summation over (k[greater than or equal to]1] ln (k + 1) sin(x ln (k + 1))sin(x ln (k + 1)) is absolutely continuous, and that is its derivative,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

is locally integrable in [0, [infinity]). To this end, since [summation over (k[greater than or equal to]1]1/[k.sup.2][(ln (k + 1))).sup.4] < [infinity], then by the Riesz-Fischer theorem [5, p193], the series

[summation over (k[greater than or equal to]1)] 1/k [(ln (k + 1)).sup.2][e.sup.ix ln(k+1)][member of] [B.sup.2].a.p.

where [B.sup.2].a.p is the Besicovitch space of almost periodic functions. The result follows from the fact that [B.sup.2].a.p [subset] [L.sup.2,loc] (-[infinity], [infinity]), [subset] [L.sup.1,loc] (-[infinity], [infinity]), i.e.,

[summation over (k[greater than or equal to]1)] 1/k [(ln (k + 1)).sup.2] cos (x ln (k + 1)) [member of ] [L.sup.1,loc] (-[infinity], [infinity])

[summation over (k[greater than or equal to]1)] 1/k ln (k + 1) sin(x ln (k + 1)) is absolutely continuous over [0, [infinity]). Thus, we have shown that [[PHI].sup.(3)](x) is continuous and we can use {ln (n + 1)} or any equivalent sequence as a sampling sequence. The above idea of using Riesz-Fischer and Besicovitch spaces to show [[PHI].sup.(4)] [member of] [B.sup.2].a.p, allows us to prove the following.

Proposition 5 A sufficient condition for [{[[lambda].sub.n]}.sub.n[greater than or equal to]0], where [absolute value of [[lambda].sub.n]] [up arrow] [infinity], to be a sampling sequence is the convergence of

[summation over (k[greater than or equal to]1)][([absolute value of [[lambda].sub.k]] - [absolute value of [[lambda].sub.k-1]]).sup.2][[lambda].sup.4.sub.k] < [infinity].

Assume now that for a given sequence of sampling point [[lambda].sub.n] the conditions of the Marchenko's theorem or equivalently proposition 4 hold. Thus, we can construct a continuous potential q and a constant h, and the solutions of the initial value problem defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

are entire in [lambda] and [[integral].sup.[infinity].sub.0] [[absolute value of y(x, [lambda])].sup.2] dx is finite if and only if [[lambda].sup.2] [member of] [sigma] = [[lambda].sup.2.sub.0], [[lambda].sup.2.sub.1], ..., [[lambda].sup.2.sub.n], ...}. Since the spectrum is simple and discrete, then Parseval equality (6) yields for any sequence of values F([[lambda].sub.n]) such that

[summation over n [greater than or equal to] 0][[absolute value of F([[lambda].sub.n])].sup.2]/[[alpha].sup.2].sub.n] < [infinity],

the existence of f [member of] [L.sup.2](0, [infinity]) such that

f(x) = [summation over (n[greater than or equal to]0] F([[lambda].sub.n])y(x, [[lambda].sub.n])1/[[alpha].sup.2.sub.n], (12)

where F([[lambda].sub.n]) = [[integral].sup.[infinity].sub.0] f(x)y (x, [[lambda].sub.n]) dx, and the series in (12) converges strongly in [L.sup.2](0, [infinity]).

To obtain a sampling expansion, we would need to formally multiply (12) by y(x, [lambda]) and integrate,

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

Since f [member of] [L.sup.2](0, [infinity]), the first integral in (13) may not produce an entire function unless f has a compact support. To this end we first assume that supp [subset] [0, b] where b < [infinity], which yields

F([lambda]) = [[integral].sup.b.sub.0] f(x)y(x, [lambda])dx [member of] [PW.sup.e.sub.b].

Here is our first sampling result.

Theorem 6 Let [[lambda].sub.n] be a sequence such that conditions of Proposition 4 hold; then for any F([lambda]) = [[integral].sup.b.sub.0]f(x)y (x, [lambda])dx we have

F([lambda]) = [summation over [n[greater than or equal to]0] F([[lambda].sub.n])[S.sub.n]([lambda], b)

where [S.sub.n]([lambda], b) = 1/[[alpha].sup.2.sub.n] [[integral].sup.b.sub.0] y(x, [lambda])y(x, [[lambda].sub.n])dx and [[alpha].sub.n] are defined by (9).

The proof reduces to the regular case since the integration in (13) is over a finite interval; see [1].

Note that the same sampling points [[lambda].sub.n] can be used for any finite positive b. To improve on the previous theorem, we need to replace the transform F([lambda]) = [[integral].sup.b.sub.0] f(x)y(x, [lambda])dx by an arbitrary function F [member of] [PW.sup.e.sub.b], where b is arbitrary. To this end we use transmutations or transformation operators, as done in [3, Proposition 4]. We recall that we can express the solutions of (11) as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (14)

where K (., .) and H (., .) are continuous functions; see [6].

Proposition 7 F [member of] [PW.sup.e.sub.b] if and only if there exists f [member of] [L.sup.2] (0, b) such that

F ([lambda]) = [[integral].sup.b.sub.0] f(x)y (x, [lambda]) dx.

Proof. If F [member of] [PW.sup.e.sub.b] then by the Paley-Wiener theorem there exists [phi] [member of] [L.sup.2] (0, b) such that

F([lambda]) = [[integral].sup.b.sub.0] [phi](x) cos (x[lambda]) dx.

Thus, from (14) we deduce that

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

Hence, we can define f by

f(x) = [(1 + g).sup.*] [phi](x) = [phi](x) + [[integral].sup.b.sub.x]H(t, x)[integral](t)dt

and clearly since H(t, x) is continuous, 1 + H and its adjoint are bounded operators acting in [L.sup.2](0, b), and so f [member of] [L.sup.2] (0, b), and by (15) we have

F([lambda]) = [[integral].sup.b.sub.0] f(x)y(x, [lambda])dx where f [member of] [L.sup.2] (0, b). (16)

Conversely, if (16) holds, then by (14),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where g(x) = [(1 + K).sup.*] f(x) is well defined, g [member of] [L.sup.2](0, b) and we deduce that F is a cosine transform:

F([lambda]) = [[integral].sup.b.sub.0] f(x)y(x, [lambda])dx [member of] [PW.sup.e.sub.b].

Remark: In [3] the operator 1 + K was acting in [L.sup.2](0, [infinity]).

4 Sampling in [PW.sup.e.sub.[infinity]]

In this section, we answer the blind sampling problem by showing that the same differential operator and its eigenvalues will help generate a sampling formula for any F [member of] [PW.sup.e.sub.[infinity]]. Recall that in this case there exists a finite type b > 0 such that F [member of] [PW.sup.e.sub.b] and by Proposition 6 there exists f [member of] [L.sup.2](0, b) such that

F([lambda]) = [[integral].sup.b.sub.0] f(x)y(x, [lambda])dx (17)

and

f(x) = [summation over (n[greater or equal to]0]F([[lambda].sub.n]) y(x, [[lambda].sub.n])1/[[alpha].sup.2.sub.n]

where the series converges in [L.sup.2](0, [infinity]) (see (12)) and so

F([lambda]) = [[integral].sup.b.sub.0][summation over (n[greater than or equal to]0)]F([[lambda].sub.n])y(x,[[lambda].sub.n])1/[[alpha].sup.2.sub.n]y (x,[lambda])dx (18)

holds for each [lambda] [member of] C. It is also clear that all integrals

[S.sub.n] ([lambda],b): = 1/[[alpha].sup.2.sub.n] [[integral].sup.b.sub.0]y(x,[[lambda].sub.n])y(x,[lambda])dx (19)

are well-defined entire functions of [lambda] and [S.sub.n](., b) [member of] [PW.sup.e.sub.b].

We now examine the convergence and the sampling formula in (18). As m [right arrow] [infinity] we have by (12)

[m.summation over (n=0)]F([[lambda].sub.n])y(x, [[lambda].sub.n])1/[[alpha].sup.2.sub.n][right arrow]f(x)

in [L.sup.2] (0, b), and since strong convergence implies weak convergence in [L.sup.2](0, b), we have

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

On the other hand, since 0 < b < [infinity], we have

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

Combining (20) and (21) we obtain pointwise convergence of the series

F([lambda]) = [[infinity].summation over (n=0)] F([lambda].sub.n])[S.sub.n]([lambda], b).

Proposition 8 Assume [[lambda].sub.n] are such that conditions of Proposition 4 hold; then for any F [member of] [PW.sup.e.sub.[infinity]] we have

F([lambda]) = [summation over (n[greater than or equal to]0] F([[lambda.sub.n])[S.sub.n]([lambda], b)

where the functions [S.sub.n]([lambda], b) are defined by (19).

Remark: The same sampling points [[lambda].sub.n] and solutions y(x,[lambda]) can be used for any function in [PW.sup.e.sub.[infinity]], but one needs a priori the knowledge of its type b to adjust the sampling function [S.sub.n] ([lambda], b).

Observe that if the type is unknown, then we can still use a variant of (19) to recover F.

Proposition 9 Assume [[lambda].sub.n] are such that conditions of Proposition 4 hold; then for any F [member of] [PW.sup.e.sub.[infinity]] we have

F([lambda]) = [[integral].sup.[infinity].sub.0] [summation over (n[greater than or equal to]0] F([[lambda].sub.n])y(x,[[lambda].sub.n])1/[[alpha].sup.2.sub.n]y (x,[lambda])dx. (22)

Proof. From the transforms associated with L (see (12)) we have for any f [member of] [L.sup.2] (0, [infinity]) the existence of

F([lambda]) = [[integral].sup.[infinity].sub.0] f(x)y(x,[lambda])dx

and

f(x) = [summation over(n[greater than or equal to]0] F([[lambda].sub.n])y(x,[[lambda].sub.n]1/[[alpha].sup.2.sub.n],

which yields (22). The key point here is that. we cannot interchange the summation signs because the integral defining the sampling functions [[integral].sup.[infinity].sub.0] y(x, [[lambda].sub.n])y(x,[lambda])dx diverges if [lambda] [not equal to] [[lambda].sub.n] and so a Shannon type sampling theorem is not possible for [PW.sup.e].sub.[infinity]] without the knowledge of the type b.

ACKNOWLEDGEMENT

The author sincerely thanks his colleague Professor Vu Kim Tuan for the many interesting discussions on sampling.

References

[1] A. Bournenir, Irregular sampling and the inverse spectral problem, Jour. Four. Anal. Appl., 5(3), 377-387, 1999.

[2] A. Bournenir, Irregular sampling and singular Sturm-Liouville problem, editor A. Zayed, Proceeding of SAMPTA2001, University of Central Florida, IEEE, 309-311, 2001.

[3] A. Bournenir and A. Zayed, The equivalence of Krarner and Shannon sampling theorems revisited. Sampl. Theory Signal Image Process., 4(3), 251-269, 2005.

[4] G. Freiling and V. Yurko, Inverse Sturm-Liouville problems and their applications, Nova Science Publishers, NY, 2001.

[5] R.S. Cuter, L.D. Kudryavtsev, and B.M. Levitan, Elements of the Theory of Functions, Inter. Series in Pure and applied mathematics, 90, Pergamon Press, 1966.

[6] B.M. Levitan, Inverse Sturm-Liouville Problems, VNU Science Press, The Netherlands, 1987.

[7] V.A. Marchenko, Sturm-Liouville operators and applications, OT22, Birkhauser, 1986.

[8] M.A. Nairnark, Linear Differential Operators, Part II, Ungar, New York, 1969.

[9] A. Zayed, Advances in Shannon's Sampling Theory, CRC Press, Boca Raton, 1993.

[10] A. Zygrnund, Trigonometric series, Cambridge University press, 1988.

Amin Boumenir

Department of Mathematics, University of West Georgia 

Carrollton, GA30118, USA

[e-mail]