Sampling formulas for spectral wavelet analysis on spaces of periodic sequences in base p>1 for computational applications of immune type[1]
by
N. Atreas and C. Karanikas
Department of Mathematics, Aristotle University of Thessaloniki, Thessaloniki 54006,Greece
Abstract We develop new discrete transforms, giving sufficient conditions for the existence of multiresolution analysis on the space of N-periodic sequences (N=pM, p,M =2,3,…). We also examine conditions such that the corresponding multiresolution analysis spaces have sampling sequence. We also present examples of sampling formulas and in particular sampling formulas of Shannon–type on spaces of sequences. Moreover we estimate the truncation error of sampling expansions, considering them as projections on the sampling subspaces. Finally we give conditions providing wavelet analysis on the spaces of periodic sequences; thus we get a mathematical background for immune type computational analysis and for local spectral analysis of data expressed in base p>1.
1. Introduction
Besides the Discrete Fourier Transform (DFT), one of the most widely used tools in science, engineering and computational mathematics is the Shannon Sampling Theorem. In this work we define new discrete transforms and Shannon-type Sampling Theorems on spaces of sequences.
Recall that Shannon’s Theorem, given by the formula:
(*)
holds for -band limited signals, i.e. continuous functions in L2(R) whose Fourier Transforms have support in , where L2(R) is the space of all square Lebesgue integrable functions defined on R. An important league between Fourier Transforms and Sampling Theory is in the theory of multiresolution analysis of L2(R) and in particular the wavelet theory.
Recall that a multiresolution analysis of L2(R) (MRA) is a nested sequence {VmVm+1, mZ} (Z is the set of all integers) of closed subspaces in L2(R) anda scaling function φ such that:
(i) for any mZ the set {2m/2 φ(2m.-n), nZ} is an orthonormal basis of Vm,
(ii) fV0 f(2m.)Vm, mZ,
(iii)=L2(R) and mVm ={0}.
It is remarkable that under some week conditions on φthere exists a sampling Riesz basis {S(2m.-n), nZ} of Vm (see [W] Proposition (9.1)), such that for any fVm we have:
,
where the convergence is in the L2(R) sense. The function S is called the sampling function of V0, i.e. S(n)=δ0,n, where δ0,n is the Kronecker’s delta (see [Z]).
In general the multiresolution analysis and the wavelet theory provide a great variety of sampling formulas for certain subspaces of L2(R) (see [W]). For example the sinc function produces a multiresolution analysis of L2(R) consisting of Paley-Wiener spaces, i.e. the spaces consist of all -bandlimited signals; in this case the sampling function is and the corresponding sampling formula is the Shannon’s sampling formula (*) for σ=π.
Since in most practical applications only sampled data are available, we are interested to examine sampling theory on spaces of sequences. Starting this project we had to deal with the following problems:
(i) How shall we define a multiresolution analysis on a space of sequences?
(ii) What is the notion of Paley Wiener subspaces on a space of sequences?
(iii) What is the corresponding Shannon Sampling Theorem?
To handle the problem of multiresolution analysis, we considered the space of all N-periodic sequences, where N=pMfor integers p,M>1. For p=2 Holschneider in [H] gives sufficient conditions for the existence of multiresolution analysis and wavelet decomposition on the space of N-periodic sequences.
The main reason for extending the multiresolution analysis for all p>1 is due to our interest on immunocomputing. It is well known that DNA and antibodies are usually expressed as words with finite length in a certain alphabet of p letters. Immunocomputing is a recent attempt (see [D]) to produce artificial intelligent methods imitating the immune systems, i.e. to construct the necessary mathematical background for problems as pattern recognition, data mining and many other operations. In a recent work [KP] we dealt with a p-adic multiresolution analysis and a relevant transform, so we have seen the necessity of new discrete transforms in base p>1.
The main target of this work is to create operations on the sampling spaces of sequences Vj(see bellow) for immune-type pattern recognition processes based on sampling operations. Notice that antigens in immune systems serve as a filter and as a lens: a filter that destroys molecular noise and a lens that focuses the attention of the lymphocyte receptors (see [D], p. 5). We believe that multiresolution analysis in base p is the suitable mathematical tool for immunocomputing applications.
In section 2 of this work we determine a dilation operations to describe a multiresolution analysis on the space of N-periodic sequences in base p. Moreover in Proposition 1 we determine some sufficient conditions to get “scaling” sequences.
In section 3 we introduce the notions of a sampling sequence of a space of periodic sequences. In Proposition 3 we give sufficient conditions on the scaling sequence of an MRA, such that the corresponding multiresolution subspaces have a sampling sequence. In Theorem 1 we have the sampling Theorem on spaces of sequences in base p.
In section 4 we give several examples of p-adic MRA. In particular, example 1 is the analog of Shannon’s sampling formula on spaces of sequences and example 4 is the analog of Haar’s sampling formula.
In section 5 we consider the sampling expansions as projections on the sampling subspaces and we estimate the truncation error of them. We also examine whether this process can be used for pattern recognition problems.
Finally, since under some weak conditions this work provides wavelet analysis on the spaces of periodic functions, in section 6 we give wavelet type local spectral analysis of data expressed in base p>1.
2. The p-adic multiresolution analysis
In this section we introduce the notion of p-adic multiresolution analysis on certain spaces of periodic sequences. We also give sufficient conditions for a sequence (called scaling) to generate a multiresolution analysis.
Let p,M>1 be positive integers and N=pM, we shall denote by the space of all complex N-periodic sequences.
We consider a nested sequence of subspaces of VM: V0V1…VM, such that V0 ={1,…,1} and Vjis spanned by the pM-j translations of an N-periodic sequence , j=0,…,M.
In order to find a relation between these bases of Vj , j=0,..,M we define the following:
Definition1 Let N=pM and is a given N-periodic sequence, we define the following operator
, n=0,…,N-1.
As in [H] (see Theorem 15.0.2) we define a collection of sequences such that
and . (1)
Notice that by straight calculation (1) can be written as
. (1a)
Proposition 1 Let N=pMand VM is the space of all complex periodic sequences. If
, (2)
then for any fixed j=1,…,M, the collection is an orthonormal basis for a nested sequence of subspaces Vj , where the sequences have been defined in (1).
We need the following Lemmas
Lemma 1 Let VM be as above and , then for any j=1,…,M a necessary and sufficient condition for the orthonormality of the set is
. (3)
Proof If is Kronecker’s delta, then using Parseval’s formula we have:
.
Lemma 2 Let VM be as above, , 1jM and the set is an orthonormal basis of Vj . Then
(4)
Proof For any we have
and by the uniqueness of the Discrete Fourier Transform the last implies the right hand side of (4).
Proof of Proposition 1 Since V0V1…VM-1it suffices to prove that:
(a) the Proposition is true for j=M-1 and
(b) if the Proposition is true for some subspace Vj (j fixed), then it is true for the space Vj-1 .
(a) From Lemma 1 we see that the p-translations of form an orthonormal basis for if and only if .
We apply (2) for j=M-1 to get:
,
thus Proposition 1 is valid for j=M-1.
(b) Now we suppose that the Proposition is true for the space Vj (we fix j) and we shall show that the translations of form an orthonormal basis for the space . By (3) in Lemma 1, it suffices to show that .
Using (1a) we have for 0rpj-1,
=
where the last follows as a combination of (2) and (3).
Proposition 2 If a sequence φ(n) is such that
,
then φ(n) is the scaling sequence of a p-adic MRA.
Proof For any r=0,1,…pM-1-1 we have
,
thus the collection is an orthonormal set and by (3) this is equiva-lent to say that
,
thus if we define , the relation (2) is satisfied and we produce an MRA.
3. The p-adic sampling sequence
In this section we introduce the notion of a sampling sequence for certain subspaces of VM which is generated by translations of a sequence φ. We give a sufficient condition on φ for the existence of a sampling sequence and we apply these results on p-adic MRA.
As in [Y] we define the notion of a reproducing kernel for a space V consisting of all N-periodic complex sequences:
Definition 2 We say that V has a reproducing kernel whenever
(1) the double indexed sequence {: 0n,mN-1} is N-periodic in n and m i.e. and are N-periodic sequences and
(2) any sequence α(n)V can be written: .
Definition 3 We say that an M-dimensional subspace W of V has a sampling basis if there exist M positive integers such thatfor any sequence α(n)W we have
In particular we say that W has a sampling sequences(n) (which is N-periodic), if there exist M positive integers such thatfor any sequence α(n)W we have
If the sequence which generates satisfies (2), then the subspaces Vjwhich have been defined by the pM-j translations of are reproducing kernel spaces and their reproducing kenel is given by the relation:
(5)
In fact, since the translations form an orthonormal basis of Vj, then any f in Vj can be written in terms of its Fourier series expansion:
.
Now we shall find the sampling sequence in Vj. First we prove the following:
Lemma 3 Let be as in (1), if
, (6)
where , then for any j=0, …M-1 we have
, . (6a)
Proof We observe that the Lemma is true for j=M-1 (see (6)). We suppose that (6a) is valid for some 0<j0<M-1 and it suffices to prove that (6a) is true for j0-1. In fact we use (1a) to get
,
because of (6) and the inductive hypothesis. Thus the Lemma is true for any j.
Proposition 3 Let be as in (1) and let satisfies conditions (2) and (6), then for any j the collection is a Riesz basis for the space Vj where has been defined in (5).
Proof First we show that is a frame for Vj. For any f(n)Vjwe have
, (7)
where the last equality was derived from the fact that and an application of Parseval’s Theorem. Since f(n)Vj and condition (2) is valid, we can writte
,
where the sequence (cjf)(r) is pj-periodic and where (cjf)(r) is the sequence of the Fourier coefficients of f(n) with respect to the orthonormal basis of Vj. Taking the Discrete Fourier Transforms in both sides of the above equality we get
, n=0,…pM-1 ,
where is pj-periodic. We apply in (7) to obtain
.
By (6) we see that it is a frame. In order to prove that the frame is a Riesz basis, we have to prove that if we remove an element of the frame the remaining elements do not constitute a frame. Using the definition of the frame (c.f. (7)) this is equivalent to say that we look for a sequence g(n)Vj such that g(pM-jm)=1 for some m and g(n)=0 for nm. Thus it suffices to find a sequence {cj(k)}, k=0,…pj-1 such that
,
or equivalently . We set n=k+pjr where k=0,…pj-1, r=0,…pM-j-1 and we sum over r to get
and since (6a) holds we can divide both sides of the above equality and we have
.
We take the Inverse Discrete Fourier Transform in both sides of the above equation and we have
,
where .Thus we have proved the Proposition.
Theorem 1 Let be as in (1) and let satisfies conditions (2) and (6), then any sequence f(n)Vj can be written as
, (8)
where
. (8a)
Obviously the sequence is the sampling sequence for Vj.
Proof Since the set is a Riesz basis for Vj then it possesses a unique biorthonormal sequence which is a sampling basis, see [Z], [W] and so
.
Since and the biorthonormal sequence also possesses this property, that is , there holds
,
or equivalently
.
Since (6) holds, we divide both terms of the above equality with and we have the Theorem.
4. Examples
In this section we present some examples of scaling sequences that produce p-adic MRA. For the first 3 Examples one can check condition (2) whether for Examples 4-6 we check the condition in Proposition 2. Notice that in example 1 we determine the analog of Shannon sampling theorem for sequences whether in example 4 we determine the analog of Haar’s sampling Theorem for sequences.
1. The p-adic Shannon MRA is defined by the scaling sequence
,
where 0θ<2π. It is clear that the scaling sequence is also sampling sequence. If we define
,
then φ(n)is a real-valued function.
2. Let
,
we define the following
.
Obviously satisfies (2) and defines a p-adic MRA.
3. Let
,
then is a scaling sampling sequence.
4. We define the Haar scaling sequence to be
,
where 0θ<2π. It is easy to see that , l=0,1…p-1, thus (2) is valid and we have the p-adic Haar MRA. In this case the denominator in (8a) is a constant , so the scaling sequence and the sampling sequence coincide. We may also define
.
In this case the Discrete Fourier Transform of φ(n) is a real-valued function.
5. Let
then the above sequence generates a p-adic MRA for which the sampling sequence and the scaling sequence do not coincide.
6. Let
,
then the above sequence generates a p-adic MRA for which the sampling sequence and the scaling sequence coincide.
5. Estimating the Truncation Error
In this section we consider the above sampling expansions as projections on the sampling subspaces and we estimate the truncation error of them. This process is used to the pattern recognition problem. Recall that
Definition 4 Let {sM-j, j=1,…,M-1} is a sampling basis of Vj which has been given in (8a), then the sequence
, n=0,…,pM-1 (9)
is called the Truncation error of f(n) with respect to the sampling series (8).
Proposition 2 Let f(n)VM, then for the Truncation error of f(n) we have
, (10)
where are the Fourier coefficients of the orthogonal projection of f onto the subspace Vjwith respect to the orthonormal system and where the sequence b(n) is the Discrete Fourier Transform of the sequence .
Proof Let fVM, we define
to be the projection of the sequence f(n) into the subspace Vj with respect to the the sampling sequence sM-j(n) whose pM-j translations form a Riesz basis of Vj (see Theorem 1).Then we have
,
where are the Fourier coefficients of sM-j(n) with respect to the orthonormal system . We observe that
= (see (8a))
=,
where . Let Pjf is the orthogonal projection of the sequence f(n) into the subspace Vj with respect to the orthonormal sequence , that is
,
then we have
,
thus using the orthonormality of the system we get
and since it is easy to see that we compute
.
Remark 1
Notice that implies that the sequence f(n) belongs in Vj ; thus in order to examine whether a sequence belongs to Vj or is “almost” in Vj it suffices to examine its truncation error . Thus certain thresholds for the truncation error provides pattern recognition processes .
Example 1 Let us consider the Haar scaling sequence in a 3-adic MRA with M=3 generations. In this case φ1(n)=(3-1/2,3-1/2,3-1/2,0,0,…) is an 27-periodic sequence. Let also f(n)=1 if n11 and f(n)=0 if n>11. It is easy to see that for j=M-1 we have cM-1,0=cM-1,1=cM-1,2=cM-1,3=31/2, cM-1,k=0 for k>3 and since we have , thus for p=3 we get
=12-12+0=0.
Example 2 Let us consider the Haar scaling sequence of example 1 and let f(n)=1 if n10 and f(n)=0 if n>10. In this case we have cM-1,0=cM-1,1=cM-1,2=31/2, cM-1,3=(2 31/2)/3, cM-1,k=0 for k>3 and
=11-(31/3)+(1/3)=1.
6. Spectral analysis on sampling spaces
Let us suppose that we have a p-adic MRA. We have seen that the multiresolution subspaces Vj j=0,…M-1 are pM-j dimensional spaces which are generated by the pM-j translations of an N-periodic sequence , j=0,…,M.
We believe that if the scaling sequence satisfies the condition in Proposition 2, then there exists a collection of p-1 N-periodic sequences , l=1,…p-1, which is generated by the scaling sequence in terms of the following relation
,
such that:
(a) and ,
(b)Vj+1 = Vj…,
where the subspaces l=1,…,p-1 are pj dimensional spaces which are generated by the pM-j translations of of an N-periodic sequence , j=0,…,M-1 which is defined in (a),
(c) any sequence f(n)VMcan be written as
(11)
We call each element of the collection , l=1,…p-1, wavelet sequence and (11) defines new type-discrete transforms. Obviously (11) is the decomposition algorithm or the spectral analysis of the sequence {f(n)}.
References
[D] D. Dasgupta (Editor), ”Artificial Immune Systems and Their Applications”, (1998).
[H] Holschneider M, “Wavelets an Analysis Tool”, Clarendon Press, Oxford (1995).
[KP] C. Karanikas and G. Proios, “A discrete transform based on the treestucture of a data for pattern recognition of immune type”, (submitted).
[Y] Young R. M., "An Introduction to non-Harmonic Fourier Series", Academic Press Inc., (1980).
[W] Walter G. G.,"Wavelets and other Orthogonal Systems with Applications", CRC Press, 1994.
[Z] Zayed A. I., "Advances in Shannon’s Sampling Theory", CRC Press Inc., 1993.
1
[1] Research supported by the EU Project IST-2000-26016 IMCOMP