# Recovery of missing samples from multi-channel oversampling in shift-invariant spaces.

AbstractIt is well known that in the classical Shannon sampling theory on bandlimited signals, any finitely many missing samples can be recovered when the signal is oversampled at a rate higher than the minimum Nyquist rate. In this work, we consider the problem of recovering missing samples from multi-channel oversampling in a general shift-invariant space. We find conditions under which any finite or infinite number of missing samples can be recovered when they are from a single or two channels.

Key words and phrases : recovery of missing samples, shift-invariant space, oversampling, multi-channel sampling, frame

2000 AMS Mathematics Subject Classification--42C15, 94A20

1 Introduction

Any band-limited signal can be reconstructed using its equidistant sample values due to the classical Shannon sampling theorem [7]. When a band-limited signal is sampled at the minimum Nyquist rate, in general, perfect reconstruction fails even if a single sample value is missing. However, if it is sampled at a rate higher than the minimum Nyquist rate (oversampling), then the sample values thus obtained have some redundancy which enables perfect recovery even when finitely many samples are missing [3, 4, 111. Adapting these ideas to two-channel oversampling involving the signal and its derivative, Santos and Ferreira [13] showed that any finite missing samples can be recovered if they belong to a single channel (see also [1, 2]). Most works on this problem are for the band-limited signals or for Kramer's sampling expansion [3]. Only recently, has it been considered in [8] for multi-channel oversampling expansion of signals in a principal shift-invariant space with a Riesz generator with compact support when all the reconstruction functions also have compact support.

In this paper, as an extension of the results in [8], we consider the recovery of missing samples for the multi-channel oversampling expansion on a principal shift-invariant space without any compact supportedness of its generator or reconstruction functions. We find sufficient conditions for the recovery of a finite or infinite number of samples missing from a single channel or from two channels.

2 Preliminaries

On [L.sup.2] (R) [intersection] [L.sup.1] (R), we take the Fourier transform to be normalized as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

so that 1/[square root of 2[pi]] F [*] becomes a unitary operator from [L.sup.2](R) onto [L.sup.2](R). For any [phi](t) [member of] [L.sup.2](R), let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then [C.sub.[phi]](t) = [C.sub.[phi]](t + 1) [member of] [L.sup.1] [0, 1], [C.sub.[phi]]([xi]) = [C.sub.[phi]]([xi] + 2[pi]) [member of] [L.sup.1] [0, 2[pi]] and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We also let

[Z.sub.[phi]] (t, [xi]) := [summation over n [member of] Z] [phi](t + n)[e.sup.-in[xi]]

be the Zak transform of [phi](t) [L.sup.2](R). Then [Z.sub.[phi]] (t,[xi]) [member of] [L.sup.2]([0,1] x [0,2[pi]]). For any 2[pi]-periodic function [tau]([xi]), let [||[tau]([xi])||.sub.0] and [||[tau]([xi])||.sub.[infinity]] him be the essential infimum and the essential supremum of |[tau]([xi])| on [0, 2[xi]] respectively.

For any c = [{c(n)}.sub.n[member of]Z] in [l.sup.2] (Z), let

F[c]([xi]) = [??]([xi]) := [summation over n[member of]Z]c(n)[e.sup.-in[xi]]

be the discrete Fourier transform of c. Then [??]([xi]) = [??]([xi] = 2[pi]) [member of] [L.sup.2][0, 2[pi]] and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For any c = [{c(n)}.sub.n[member of]Z] and d = [{d(n)} .sub.n[member of]Z] in [l.sup.2] (Z), let

(c * d)(n) := [summation over k[member of]Z]] c(k)d(n- k)

be the discrete convolution product of c and d. Then c * d [member of] [l.sup.[infinity]] (Z) and [??]([xi]) = [??]([xi]) [??]([xi]) whenever [??]([xi]) [??]([xi]) [member of] [l.sup.2] [0, 2[pi]] or c * d [member of] l2(Z).

A Hilbert space H consisting of complex valued functions on a set E is called a reproducing kernel Hilbert space (RKHS) if there is a function q(s, t) on E x E, called the reproducing kernel of H, satisfying

* q(*,t) [member of] H for each t in E;

* (f(s),q(s,t)) = f(t), f [member of] H.

In an RKHS H, any norm converging sequence also converges uniformly on any subset of E, on which q(t, t) is bounded (Section 3.4 in [7]).

For any [phi] [member of] [L.sup.2](R), let V([phi]) := [bar.span]{[phi](t - n) : n [member of] Z} be the shift- invariant space generated by [phi]. We call [phi] a Riesz generator'-(resp, frame generator) when {[phi](t - n) : n [member of] Z} is a Riesz basis (resp. frame) of V([phi]).

3 Main Results

In this work, we always assume that [phi](t) [member of] [L.sup.2](R) [intersection] C(R) is a continuous Riesz generator satisfying [sup.sub.R] [C.sub.[phi]] (t) < [infinity]. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is a reproducing kernel Hilbert space and for any c [member of] [l.sup.2] (Z), (c * [phi])(t) = [[SIGMA].sub.n[member of]Z] [c.sub.n] [phi](t - n) converges both in [L.sup.2](R) and absolutely and uniformly on R to a bounded continuous function. Moreover, the reproducing kernel of V([phi]) is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [{[phi](t - n)}.sub.n[member of]Z] is the dual Riesz basis of [{[phi](t - n)}.sub.n[member of]Z]. Since [sup.sub.R] [C.sub.[phi]] (t) < [inifinity], the function q(t, t) is bounded on R.

Let L[*] be an LTI (linear time-invariant system with impulse response l(t), that is,

L[f](t) := (l * f) = [[integrall].sub.R] l (t-s)f(s)ds.

Here we assume that l(t) is one of the following three types:

(i) l(t) = [delta] (t + a), a [member of] R;

(ii) l(t) [member of] [L.sup.2](R);

(iii) l(t) [member of] [L.sup.1] (R).

Lemma 3.1. Let L[*] be an LTI system with impulse response l(t) as above and [psi](t) :: L[[phi]](t) = (l* [phi])(t). Then

(a) [psi](t) [member of] C(R) and [sup.sub.R] [C.sub.[psi]] (t) < [infinity].

(b) For any f(t) : (c * [phi])(t) [member of] V([phi]) with c [member of] [l.sup.2] (Z), L[f](t) : (c * [psi])(t) converges absolutely and uniformly on R. Hence L[f](t) [member of] C(R).

Proof. For types (i) and (ii), see the proof of Lemma 3.1 in [5] or Lemma 3.1 in [9].

Assume that l(t) LI(]R). Then for any t and [t.sub.0] in R, |[psi](t) - [psi]([t.sub.0])| [less than or equal to] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as t [right arrow] [t.sub.0.] Hence [psi](t) [member of] C(]R). Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

so that [sup.sub.R] [C.sub.[psi]] (t) < [infinity]. By Young's inequality, L[*] : [L.sup.2](]R) [right arrow] [L.sup.2](]R) is a bounded linear operator so that, for any f(t) = (c * [phi])(t) [member of] V([phi]), L[f](t) = [[SIGMA].sub.n[member of]Z] c(n)L[[phi](t - n)] = [[SIGMA].sub.n[member of]Z] c(n) [psi](t - n) = (c * [psi])(t) converges in [L.sup.2](]R). Then (a) implies that (c * [psi])(t) also converges absolutely and uniformly on R to L[f](t)[member of] C(R).

For later use, we note that L[*] is a bounded linear operator from [L.sup.2](R) into [L.sup.2](R) for types (i) and (iii) and a bounded linear operator from [L.sup.2](R) into [L.sup.[infinity]] (R) for type (ii).

Let {[L.sub.j] [*] : 1 [less than or equal to] j [less than or equal to] N} be N LTI systems with impulse responses {[l.sub.j] (t) : 1 [less than or equal to] j [less than or equal to] N} where each [l.sub.j] (t) is one of the above three types. We are interested in the recovery of missing samples for the multi-channel oversampling expansion:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [[sigma].sub.j] [member of] R for 1 [less than or equal to] j [less than or equal to] N, r is a positive integer, and {[S.sub.j] (t - nr) : 1 [less than or equal to] j [less than or equal to] N, n [member of] Z} is a frame of V([PHI]). Before we discuss our main problem, we first need to recall conditions under which such a multi-channel oversampling expansion is possible on V([PHI]).

Let D be the unitary operator from [L.sup.2] [0, 2[pi]] onto [L.sup.2][[0, 2[pi]/r].sup.r] defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

be an N x r matrix where [g.sub.j] ([xi]):= 1/2[pi] [Z.sub.[psi]j] ([[sigma].sub.j,] [xi]) and [[psi].sub.j] (t) := [L.sub.j] [[PHI]](t). Let [[alpha].sub.G] := [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [[lambda].sub.min](G([xi])*G([xi])) and [[lambda].sub.max](G([xi])*G([xi])) are the smallest and the largest eigenvalues of the positive semi-definite r x r matrix (G([xi])*G([xi])), respectively.

Proposition 3.2 (see Theorem 2 and Corollary 1 in [6] or Theorem 3.3 and Theorem 3.4 in [9]). Assume [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Then the following are equivalent.

(a) There is aflame {[S.sub.j](t-nr) : 1 [less than or equal to] j [less than or equal to] N,n [member of] Z} of V([PHI]) such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

(b) [[alpha].sub.G] > O.

Moreover we have in this case:

* series (1) converges both in [L.sup.2] (N) and absolutely and uniformly on R;

* r[less than or equal to]N;

* r = N if and only if{[S.sub.j] (t-nr) : 1 [less than or equal to] j [less than or equal to] N,n [member of] Z} is a Riesz basis of V([PHI]);

* {[L.sub.j][f]([[sigma].sub.j] + nr)}n[member of]Z [member of] [l.sup.2] (Z) for 1 [less than or equal to] j [less than or equal to] N.

Note that if r = N and 0 < [[alpha].sub.G] [less than or equal to] [[beta].sub.G] < [infinity] so that {[S.sub.j] (t- nr) : 1 [less than or equal to] j [less than or equal to] N, n [member of] Z} is a Riesz basis of V([phi]) for which (1) holds, then it is impossible to recover any set of missing samples from (1) due to the uniqueness of basis expansion.

Hence in the following, we assume r < N and 0 < [[alpha].sub.G] [less than or equal to] [[beta].sub.G] < [infinity] so that the sampling expansion (1) holds for an overcomplete frame {[S.sub.j] (t-nr) : 1 [less than or equal to] j [less than or equal to] N, n [member of] Z} of V([PHI]). Notice that {[S.sub.j] (t-n) : 1 [less than or equal to] j [less than or equal to] N, n [member of] Z} is also a frame of V([PHI])so that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (see Theorem

2.2.14 in [12]). Also [sup.sub.R] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where B is an upper frame bound of {[S.sub.j] (t-n) : 1 [less than or equal to] j [less than or equal to] N, n [member of] Z}.

Let L[*] be any one of the prescribed LTI systems [L.sub.j] [*], 1 [less than or equal to] j [less than or equal to] N. Then applying L[*] to (1) gives

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

which converges either in [L.sup.2](N) or [L.sup.[infinity]] (R) by the continuity of L[*]. We claim that (2) also converges absolutely and uniformly on R to L[f](t) [member of] C(R). If : [less than or equal to] L[*] is of type (i), then the claim is trivial. For type (ii), using the Poisson summation formula (cf. Lemma 5.1 in [10]) we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For type (iii), observe that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence [[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for both types (ii) and (iii). Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the right hand side of (2) then converges absolutely and uniformly to a continuous function L[f](t) on R.

We are now ready to consider the problem of recovering (finite or infinite) missing sample values among {Lj[f]([[sigma].sub.j] + nr) : 1 [less than or equal to] j [less than or equal to] N,n [member of] Z}. In the following, let [B.sub.j] and [B.sup.k] be the j-th row and the k-th column of a matrix [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with infinite rows and finite columns. We view [B.sup.k] both as a column vector and as a sequence [{[b.sub.j,k]}.sub.j[member of]Z]. For any sequence c = [{c(n)}.sub.n[member of]Z] and k [member of] Z, let [T.sub.k] c = [{c(n - k)}.sub.n[member of]Z] be the shifting of c by k,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then [alpha]([[tau].sub.k]c) = [alpha](c) + k and [beta] ([[tau].sub.k]c) = [beta](c) + k for any k [member of] X. If c [not equal to] 0, then -[infinity] [less than or equal to] [alpha](c) [less than or equal to][beta](c) [less than or equal to] [infinity], whereas [alpha](0) = [infinity] and [beta](0) = -[infinity]. We say that e is upper (resp. lower) supported if [alpha](c) (resp. [beta](c)) is finite. If e is either upper or lower supported, then we say that e is one-side supported. Let [[delta].sub.0] := [{[[delta].sub.0],n}.sub.n[member of]Z].

Case 1: finitely many missing samples from a single channel Assume that finitely many samples are missing from a single channel, say, from the first channel. That is, we assume that M = {[L.sub.1][f]([[sigma].sub.1] + nr) : n [member of] I} is missing where I = {[n.sub.1] < ... < [n.sub.m]}, m [greater than ] 1. Then we have from (2) with L = [L.sub.1] and t = [[sigma].sub.1] + lr,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For any fixed [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and h = [{h(n)}.sub.n[member of]Z] where s(n) = [L.sub.1] [f]([[sigma].sub.1] + nr) and u(n) = [L.sub.1] [[S.sub.1]]([[sigma].sub.1] + nr). Then (3) becomes

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

where finitely many entries M = {s(n) : n [member of] I} = {s([n.sub.1]), ... ,S([n.sub.m])} are missing from s.

Theorem 3.3. Assume that u is one-side supported. Then any finitely many missing entries {s(n) : n [member of] I} can be recovered from (4) if and only if u [not equal to] [[delta].sub.0].

Proof. For l [member of] I, (4) becomes

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

so that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

For l [member of] I, (4) becomes

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

Let x = [[s([n.sub.k])].sup.m.sub.k=1] and g = [[g(l)].sub.l[member of]Z be column vectors. Then we can express (5) and (6) in matrix form as

Bx = g (7)

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that the k-th column of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [u.sup.(0)] := [[sigma].sub.0] - u, i.e. [B.sup.k] is a shift of [u.sup.(0)] by units [n.sub.k].

Assume u = [[sigma].sub.0], i.e. [u.sup.(0)] = 0. Then (4) becomes the trivial equation: s(l) = s(l), l [member of] Z, or equivalently B = 0 so no missing entry from s can be recovered from (4).

Now assume u [not equal to] [[sigma].sub.0], i.e. [u.sup.(0)] [not equal to] 0. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

First assume u is upper supported, i.e., [alpha](u) is finite. Then p := [alpha]([u.sup.(0))] is also finite so that [u.sub.(0)] (n) = 0 for n < p and [u.sub.(0)(p)] [not equal to] 0. Since [alpha]([B.sup.k]) = [alpha]([u.sup.(0)])+[n.sub.k]= p + [n.sub.k], 1 [less than or equal to] k [less than or equal to] m,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Then BR is a non-singular mxm lower triangular matrLx with det [B.sub.R] = [u.sup.(0)] ([p).sup.m] [not equal to] 0 and

[B.sub.R] x = [g.sub.R] := [g(P + [[n.sub.k])].sup.m.sub.k=1] (8)

from which we can recover x as x = [B.sup.-1.sub.R] [g.sub.R].

Now assume u is lower supported, i.e., [beta] u) is finite. Then q := [beta]([u.sup.(0))] is also finite. Then [u.sup.(0)] (n) = 0 for n > q and [u.sup.(0)] (q) [not equal to] 0. Since [beta]([B.sup.k]) = [beta]([u.sup.(0)]) + [n.sub.k]= q + [n.sub.k] , 1 [less than or equal to] k [less than or equal to] m,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

so that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a non-singular rn x m upper triangularm matrix with det [B.sub.R] = [u.sup.(0)] (q) [not equal to] 0 satisfying (8), where [g.sub.R] := [g(q + [[n.sub.k])].sup.m.sub.k=2]. Hence again we can recover x as x = [B.sup.-1.sub.R] [g.sub.R].

It is worth to note that if r = N so that {[S.sub.j](t - nr) : 1 [less than or equal to] j [less than or equal to] N,n [member of] Z} in (1) is a Priesz basis of V([phi]), then [L.sub.j][[S.sub.j]] ([[sigma].sub.j] + nr) = [[delta].sub.0](n) for any 1 [less than or equal to] j [less than or equal to] N which implies u = [[delta].sub.0]. in Theorem 3.3.

Remark 3.4. In most previous works [2, 3, 4, 8, 11] on recovery of missing samples, one considers only the equation (5), which can be rewritten in a matrix form as

(I - R)x = y

where x = [[s([n.sub.k])].sup.m.sub.k=1], y = [[g([n.sub.k])].sup.m.sub.k=1] and R = [[u([n.sub.j] - [u.sub.k]).sup.m.sub.j,k=1], and tries to show that 1 is not an eigenvalue of the interpolation matrix R.

Case 2: finitely many missing samples from two channels We may assume that finitely many samples are missing from the first and second channels, say, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are missing, where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Case 1, we have from (2)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

For each n Z, set s[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then (9) and (10) can be written as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)

Equation (11) for l [member of] [I.sub.1] and l [not member of] [I.sub.1] become

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (13)

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (14)

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Equation (12) for l [member of] [I.sub.2] and l [not member of] [I.sub.2] become

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (16)

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be column vectors. Then we may express (13)-(16) in matrix form as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (17)

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Theorem 3.5. Assume [u.sub.j] := [[delta].sub.0] - [u.sub.jj] [not equal to] 0 for j = 1, 2. Let [p.sub.j] := [alpha]([u.sub.j]), [q.sub.j] := [beta]([u.sub.j]) and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], Then any finitely many missing entries M = {[s.sub.1] (n) : n [member of] [I.sub.1]} [union] {[s.sub.2](n) : n [member of] [I.sub.2]} can be recovered from (11) and (12) if any one of the following holds:

(i) [u.sub.1] is upper supported, u2 is one-side supported, and there exists an integer 0 [less than or equal to] d < [[DELTA].sub.1] such that [u.sub.1] ([p.sub.1] +d) [not equal to] 0 and [p.sub.1] + d + [n.sup.1.sub.k] - [n.sup.2.sub.l] [not member of] supp [u.sub.12] for 1 [less than or equal to] k [less than or equal to] [m.sub.1], 1 [less than or equal to] l [less than or equal to] [m.sub.2];

(ii) [u.sub.1] is lower supported, [u.sub.2] is one-side supported, and there exists an integer 0 [less than or equal to] d < [[DELTA].sub.1] such that [u.sub.1] ([q.sub.1] - d) [not equal to] 0 and [q.sub.1] - d + [n.sup.1.sub.k] - [n.sup.2.sub.l] [not member of] supp [u.sub.12] for 1 [less than or equal to] k [less than or equal to] [m.sub.1], 1 [less than or equal to] l [less than or equal to] [m.sub.2];

(iii) [U.sub.1] is one-side supported, [u.sub.2] is upper supported, and there exists an integer 0 [less than or equal to] d < [[DELTA].sub.2] such that [u.sub.2] ([p.sub.2] + d) [not equal to] 0 and [P.sub.2] + d + [n.sup.2.sub.l] - [n.sup.1.sub.k] [not member of] supp [u.sub.21] for 1 [less than or equal to] k [less than or equal to] [m.sub.1], 1 [less than or equal to] l [less than or equal to] [m.sub.2];

(iv) [u.sub.1] is one-side supported, [u.sub.2] is lower supported, and there exists an integer 0 [less than or equal to] d < [[DELTA].sub.2] such that [u.sub.2]([q.sub.2] - d) [not equal to] and [q.sub.2] - d + [n.sup.2.sub.l] - [n.sup.1.sub.k] [not member of] supp [u.sub.21] for 1 [less than or equal to] k [less than or equal to] [m.sub.1], 1 [less than or equal to] l [less than or equal to] [m.sub.2];

(v) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(vi) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(vii) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(viii) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof. (i) Assume that [u.sub.1] and [u.sub.2] are upper supported (i.e., [P.sub.1] and [P.sub.2] are finite) and there exists an integer 0 [less than or equal to] d < [[DELTA].sub.1] such that [u.sub.1]([p.sub.1] + d) [not equal to] 0 and [p.sub.1] + d + [n.sup.1.sub.k] - [n.sup.2.sub.l] [not member of] supp [u.sub.12] for 1 [less than or equal to] k [less than or equal to] [m.sub.1], 1 [less than or equal to] l [less than or equal to] [m.sub.2]. Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for each 1 [less than or equal to] k [less than or equal to] [m.sub.1] - 1, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then as in the proof of Theorem 3.3, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are non-singular lower triangular matrices with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. On the other hand, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We then have from (17)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (18)

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [A.sub.R] is a block triangular matrix so that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Hence we can recover x from (18) as x = [A.sup.-1.sub.R] [g.sub.R]. When [u.sub.1] is upper supported and [u.sub.2] is lower supported, the proof is essentially the same as above. The cases (ii), (iii) and (iv) can be also proved similarly as in ([??]).

(v) Assume [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are non-singular triangular matrices with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] We then have from (17)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (19)

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since [C.sup.1.sub.R] = 0, [A.sub.R] is a block triangular matrix with det [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Hence we can recover x from (19) as x = [A.sup.-1.sub.R][g.sub.R]. The cases (vi), (vii) and (viii) can be proved similarly as in (v).

In Theorem 3.5 (i)-(iv), if d = 0, then [u.sub.1]([P.sub.1]) [not equal to] 0 in (i), [u.sub.1]([q.sub.1]) [not equal to] 0 in (ii), [u.sub.2]([p.sub.2]) [not equal to] 0 in (iii), and [u.sub.2]([q.sub.2]) [not equal to] 0 in (iv) by the definitions of [p.sub.j] and [q.sub.j]. Hence we have:

Corollary 3.6. Let [u.sub.j], [p.sub.j] and [q.sub.j] be the same as in Theorem 3.5. Then any finitely many missing entries M = {[s.sub.1] (n) : n [member of] [I.sub.i]} [union] {[s.sub.2](n) : n [member of] [I.sub.2]} can be recovered if any one of the following holds:

(i) [u.sub.1] is upper supported, [u.sub.2] is one-side supported, and [p.sub.1] + [n.sup.1.sub.k] - [n.sup.2.sub.l] [not member of] supp [u.sub.12] for l [less than or equal to] k [less than or equal to] [m.sub.1], 1 [less than or equal to] l [less than or equal to] [m.sub.2];

(ii) [u.sub.1] is lower supported, [u.sub.2] is one-side supported, and [q.sub.1] + [n.sup.1.sub.k] - [n.sup.2.sub.l] [not member of] supp [u.sub.12] for 1 [less than or equal to] k [less than or equal to] [m.sub.1], 1 [less than or equal to] l [less than or equal to] [m.sub.2];

(iii) [u.sub.1] is one-side supported, [u.sub.2] is upper supported, and [p.sub.2] + [n.sup.2.sub.l] - [n.sup.1.sub.k] [not member of] supp [u.sub.21] for 1 [less than or equal to] k [less than or equal to] [m.sub.1], 1 [less than or equal to] l [less than or equal to] [m.sub.2];

(iv) [u.sub.1] is one-side supported, [u.sub.2] is lower supported, and [q.sub.2] + [n.sup.2.sub.l] - [n.sup.1.sub.k] [not member of] supp [u.sub.21] for 1 [less than or equal to] k [less than or equal to] [m.sub.1], 1 [less than or equal to] l [less than or equal to] [m.sub.2];

In [8], the same problem of recovering finitely many missing samples from (1) is also considered when the generator [phi](t) and the reconstruction functions [{[S.sub.j](t)}.sup.N.sub.j=1]] are compactly supported (see Theorem 3.4 and Theorem 3.5 in [8]).

In [8], [L.sub.j][[S.sub.k]](t), 1 [less than or equal to] j, k [less than or equal to] N, are also compactly supported so that the sequences corresponding to u in Theorem 3.3, [u.sub.11], [u.sub.12], [u.sub.21], and [u.sub.22] in Theorem 3.5 are finitely supported. It is clear that Theorem 3.3 above improves Theorem 3.4 in [8]. Also Theorem 3.5 in [8] follows as a consequence of Corollary 3.7 below.

Corollary 3.7. Assume that [u.sub.11], [u.sub.12], [u.sub.21], and [u.sub.22] are finitely supported. For each j = 1, 2, let [p.sub.j], [q.sub.j] and [[DELTA].sub.j] be the same as in Theorem 3.5 and [I.sup.(j)] = [[a.sup.(j)], [b.sup.(j)]] be the smallest closed interval containing supp [u.sub.jj] where [a.sup.(j)] and [b.sup.(j)] are integers. Then any finitely many missing entries M = {[s.sub.1](n) : n [member of] [I.sub.1]} [union] {[s.sub.2](n) : n [member of] [I.sub.2]} can be recovered if any one of the following holds:

(i) [u.sub.11] (0) [not equal to] 1, [u.sub.22] [not equal to] [[delta].sub.0], [n.sup.1.sub.k] - [n.sup.2.sub.l] [not member of] supp [u.sub.12] for 1 [less than or equal to] k [less than or equal to] [m.sub.1], 1 [less than or equal to] l [less than or equal to] [m.sub.2], and either 0 [not member of][I.sup.(1)] or 2[[DELTA].sub.1] > [b.sup.(1)] - [a.sup.(1)];

(ii) [u.sub.22] (0) [not equal to] 1, [u.sub.11] [not equal to] [[delta].sub.0], [n.sup.2.sub.l] - [n.sup.1.sub.k] [not member of] supp [u.sub.21] for 1 [less than or equal to] k [less than or equal to] [m.sub.1], 1 [less than or equal to] l [less than or equal to] [m.sub.2], and either 0 [not member of][I.sup.(2)] or 2[[DELTA].sub.2] > [b.sup.(2)] - [a.sup.(2)].

Proof. Assume that (i) holds. Then [u.sub.11](0) [not equal to] 1 implies that -[infinity] < [P.sub.1] = min{0, [a.sup.(1)]} [less than or equal to] 0 [less than or equal to] [q.sub.1] = max{0, [b.sup.(1)]} < [infinity]. If 0 [not member of] [I.sup.(1)], then either [P.sub.1] = 0 or [q.sub.1] = 0 so that (i) or (ii) of Theorem 3.5 holds respectively with d = 0. On the other hand, if 0 [not member of] [I.sup.(1)] and 2[[DELTA].sub.1] > [b.sup.(1)] - [a.sup.(1)]), then [P.sub.1] = [a.sup.(1)] and [q.sub.1] = [b.sup.(1)] so that 2[[DELTA].sub.1] > [q.sub.1] + (-[P.sub.1]), which implies either [[DELTA].sub.1] > - [p.sub.1] or [[DELTA].sub.1] > [q.sub.1]. If [[DELTA].sub.1] > -[P.sub.1], then (i) of Theorem 3.5 holds with d = -[P.sub.1]. If [[DELTA].sub.1] > [q.sub.1], then (ii) of Theorem 3.5 holds with d = [q.sub.1]. Hence the claim follows by Theorem 3.5.

Now assume that (ii) holds. Then by similar arguments as above, either (iii) or (iv) of Theorem 3.5 holds so that the claim follows by Theorem 3.5.

We now investigate the case of infinitely many missing samples.

Case 3: infinitely many missing samples from a single channel Assume that infinitely many samples are missing from a single channel, say the first channel i = 1: M = {[L.sub.i][f]([[sigma].sub.1] + n[micro]r) : n [member of] Z} are missing, where [micro] [greater than or equal to] 1 is an integer. Then with the same notations as in the Case 1, we also have (4) where M = {s([mu]n) :n [member of] Z} are missing.

For l = [mu]j, j [member of] Z, (4) becomes

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

so that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (20)

where g([mu]j) = [[SIGMA].sub.n[not member of [mu]Z] s(n)u([mu]j - n) + h([mu]j).

For l [not member of] [micro]Z, (4) becomes

-[summation over (k[member of]Z] s([mu]k)u(l - [mu]k) = g(l) (21)

where g(l) = [[SIGMA].sub.n[not member of [mu]Z] s(n)u(l - n) + h(l) - s(l).

Let x = [[s([mu]k)].sub.k[member of]Z] and g = [[g(k)].sub.k[member of]Z] be column vectors. Then we can express (20) and (21) in matrix form as

Ax = g (22)

where A =[[a.sub.j,k)].sub.j,k[member of]Z] and [a.sub.j,k]= [[delta].sub.j,[mu]k] - u(j -[mu]k).. Decompose the system (22) into [mu] subsystems by grouping rows of A mod [micro]: For 0 [less than or equal to] [alpha] [less than or equal to] [alpha] [less than or equal to] [micro] - 1, let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then (22) becomes

[A.sup.([alpha])] x = [g.sup.([alpha])], 0 [less than or equal to] [alpha] [less than or equal to] [micro] - 1. (23)

Note that [A.sup.([alpha])] = [[a.sup.([alpha].sub.j,k]].sub.j,k[member of]Z] where [a.sup.([alpha].sub.j,k] =[a.sub.[mu]k+[alpha],k] = [a.sup.([alpha])](j-k), [a.sup.([alpha])] (n) = [[delta].sub.[mu]n+[alpha],0] -u([mu]n + [alpha]). Hence (23) becomes

[a.sup.([alpha])] * x = [g.sup.([alpha])], 0 [is less than or equal to] [alpha] [less than or equal to] [micro]-1. (24)

Here we note that [a.sup.([alpha])] (0 [less than or equal to] [alpha] [less than or equal to] [micro] - 1) and x are in [l.sup.2](Z) since {[L.sub.j][f]([[sigma].sub.j] +nr) : 1 [less than or equal to] j [less than or equal to] N, n [member of] Z} [member of] [l.sup.2] [(z).sup.N] for any f [member of] V([phi]).

Theorem 3.8. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some [alpha] = 0,1, ..., [mu] - 1, then M = {[L.sub.1][f] ([[sigma].sub.1] + n[mu]r) : n [member of] Z} can be recovered as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (25)

Proof. Assume 0 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then the convolution operator [a.sup.([alpha])] * . : [l.sup.2] (Z) [right arrow] [l.sup.2] (Z) is an isomorphism with inverse [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Hence (24) implies [g.sup.([alpha])] [member of] [l.sup.2] (Z) and [??]([zeta]) = [[??].sup.([alpha])] [([zeta]).sup.-1] [[??].sup.([alpha])] ([zeta]) from which (25) follows.

If [L.sub.j] [[S.sub.k]](t), 1 [less than or equal to] j, k [less than or equal to] N, are compactly supported, then [a.sup.([alpha])], 0 [less than or equal to] [alpha] [less than or equal to] [micro] - 1, are finitely supported so that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. In this case, which happens under the setting of [8], we only require [[parallel][[??].sup.([alpha])] ([zeta])[parallel].sub.0] > 0 for some [alpha] = 0, 1, ..., [micro] - 1 in Theorem 3.8.

As pointed out in [8] and [9], we may allow rational sampling period as well as asymmetric sampling periods in the sampling formula (1). If r = p / q < 1 where p and q are coprime positive integers, then for each j = 1, ..., N,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence the case of rational sampling period can be reduced to the case of integer sampling period p by extending the number of LTI systems involved.

Case 4: infinitely many missing samples from two channels Assume that infinitely many samples are missing from two channels, say the channels [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are missing, where [micro] [greater than or equal to] 1 is an integer. Then with the same notations as in Case 2, we also have (11) and (12) where M = {[s.sub.1]([micro]n) : n [member of] Z} [union] {[s.sub.2]([micro]n) : n [member of] Z} are missing.

Equation (11) for l [member of] [micro]Z and l [not member of] [micro]Z become

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Let [x.sub.1] = [[[s.sub.1]([mu]n)].sub.n[member of]Z]] and [x.sub.2] = [[[s.sub.2]([mu]n)].sub.n[member of]Z]]. By an argument similar to Case 3, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (26)

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for J [member of] Z, and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for l [not member of] [mu]Z. Then we obtain similarly from (12)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (27)

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We can express (26) and (27) as

[H.sup.([alpha])] ([zeta]) [??] ([zeta]) = [[??].sup.([alpha])]([zeta]) (28)

Where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Theorem 3.9. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some [alpha] = 0,1, ... [mu] - 1, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be recovered as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (29)

Here, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for [a.sub.j]([xi]) [member of] [L.sup.2] [0, 2[pi]], j =1,2.

Proof. Assume [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then the operator [H.sup.([alpha])] : [L.sup.2] [[0,2[pi]].sup.2] [right arrow] [L.sup.2] [[0,2[pi]].sup.2] is bounded invertible a.e. on [0, 2[pi]]. Hence it follows from (28) that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] which implies (29).

Example 3.10. (Band-limited signals) If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the Paley- Wiener space of signals band-limited in [-[pi], [pi]]. In this case, WSK (Whittaker-Shannon-Kotel'nikov) sampling theorem [7] says that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For any sampling rate [omega] > 1, we also have the oversampling expansion

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (30)

which converges in [L.sup.2] (R) and absolutely and uniformly on R. Since {sinc (t - n/w): n [member of] Z} is an overcomplete frame of PW[pi], the redundancy among the samples {f(n/[omega]) : n [member of] Z} leads to the recovery of finitely many missing samples from (30) [3,4,11].

We now consider the oversampling expansion (30) with a rational sampling rate [omega] = q/p > 1, where p and q are coprime positive integers. Then (30) can be written as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (31)

where [S.sub.j](t) = p/q sinc (t - p/q (j - 1)), which can be viewed as a multi-channel over-sampling (1) with r = p, N = q, [l.sub.j] (t) = [delta](t), and [[sigma].sub.j] = p/q(j - 1). Note that (31) converges absolutely and uniformly on R and {f(n p/q) : n [member of] Z} [member of] [l.sup.2] (Z) for any f [member of] [PW.sub.[pi]] by the Plancherel-Pdlya inequality (Theorem 6.10 in [7]).

Assume now that infinitely many samples M = {f(np) : n [member of] Z} are missing from (31). Then we have the equation (22) or equivalently the equation (24)

with [mu] = 1, where a(:=[a.sup.0] = (1-p/q]) [[delta].sub.0], x = [[f(np)].sub.n[member of]Z] and g = [[g(n)].sub.n[member of]Z]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since [??]([xi]) = 1 - p/q [not equal to] 0, M can be recovered as (cf. (25))

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

ACKNOWLEDGEMENT

K.H. Kwon and D.G. Lee are partially supported by the National Research Foundation of Korea (NRF) (2012RIA1A2038650). S. Kang is partially supported by EM-BEAM program funded by European Commission.

References

[1] P. Brianzi and V. Del Prete, Stability of the recovery of missing samples in derivative oversampling, Sampl. Theory Signal Image Process., 10, 191-210, 2011.

[2] V. Del Prete, Recovery of missing samples in oversampling formulas for band limited functions, Sampl. Theory Signal Image Process., 8, 161-180, 2009.

[3] P.J.S.G. Ferreira, Incomplete sampling series and the recovery of missing samples from oversampled band-limited signals, IEEE Trans. Signal Process., 40, 225-227, 1992.

[4] P.J.S.G. Ferreira, The stability of a procedure for the recovery of lost samples in band-limited signals, Signal Process., 40, 195-205, 1994.

[5] A.G. Garcia, J.M. Kim, K.H. Kwon, and G.J. Yoon, Multi-channel sampling on shift-invariant spaces with frame generators, Int. J. Wavelets Multiresolut. Inf. Process., 10, DOI: 10.1142/S0219691311004456, 2012.

[6] A.G. Garcia, G. Perez-Villardn, Dual frames in [L.sup.2](0, 1) connected with generalized sampling in shift-invariant spaces, Appl. Comput. Harmon. Anal., 20, 422-433, 2006.

[7] J.R. Higgins, Sampling Theory in Fourier and Signal Analysis : Foundations, Oxford Univ. Press, Oxford, 1996.

[8] S. Kang and K.H. Kwon, Recovery of missing samples for oversampling in shift invariant spaces, Y. Math. Anal. Appl., 391, 139-146, 2012.

[9] S. Kang, J.M. Kim, and K.H. Kwon, Asymmetric multi-channel sampling in shift invariant spaces, Y. Math. Anal. Appl., 367, 20-28, 2010.

[10] J.M. Kim and K.H. Kwon, Sampling expansion in shift invariant spaces, Int. Y. Wavelets Multiresolut. Inf. Process., 6, 223-248, 2008.

[11] R.J. Marks II, Introduction to Shannon Sampling and Interpolation Theory, Springer-Verlag, New York, 1991.

[12] A. Ron and Z. Shen, Frames and stable bases for shift-invariant subspaces of [L.sup.2]([R.sup.d]), Canad. Y. Math., 47, 1051-1094, 1995.

[13] D.M.S. Santos and P.J.S.G. Ferreira, Reconstruction from missing function and derivative samples and oversampled filter banks, Proc. of the IEEE Int. Conf. on Acoustics, Speech, and Signal Process. ICASSP 2004, 3, 941-944, 2004.

Sinuk Kang

Laboratory of Mathematics Applied to Systems, Eeole Centrale Paris

Grande voie de vignes, 92290 Chatenay Malabry, France

sinuk.kang@ecp.fr

Kil Hyun Kwon

Department of Mathematical Sciences, KAIST

Daejeon, 305-701, Republic of Korea

khkwon@kaist.edu

Dae Gwan Lee

Department of Mathematical Sciences, KAIST

Daejeon, 305-701, Republic of Korea

daegwan@kaist.ac.kr

Printer friendly Cite/link Email Feedback | |

Author: | Kang, Sinuk; Kwon, Kil Hyun; Lee, Dae Gwan |
---|---|

Publication: | Sampling Theory in Signal and Image Processing |

Article Type: | Report |

Geographic Code: | 9SOUT |

Date: | Jan 1, 2012 |

Words: | 7184 |

Previous Article: | Optimal design of optical filter for white light interferometry based on sampling theory. |

Next Article: | Saturation results for the truncated max-product sampling operators based on sinc and Fejer-type kernels. |

Topics: |