Some Results on Quantization of Signals and Pair Frames

www.i-csrs.org

Available free online at http://www.geman.in

Some Results on Quantization of Signals and Pair Frames

M.M. Shamooshaki Department of Mathematics Comprehensive Imam Hossein University

Tehran, Iran

E-mail: [email protected] (Received: 15-6-13 / Accepted: 18-8-13)

Abstract

In this paper we consider quantized frame expansions and pair frames. Es- pecially one method of quantization called Σ∆ algorithm is studied, also we study pair frames and we obtain some properties of them. Moreover by using pair frames, duals and controlled frames, we get some upper bounds for the error obtained in Σ∆ algorithm.

Keywords: Quantization of signals, Pair frame, Approximation error.

1 Introduction

In 1946, Gabor [8] introduced a method for reconstructing functions (signals) using a family of elementary functions. Later in 1952, Duffin and Schaeffer [6] presented a similar tool in the context of nonharmonic Fourier series and this is the starting point of frame theory. After some decades, Daubechies, Grossmann and Meyer reintroduced frames in [5].

Let H be a separable Hilbert space and I be a finite or countable set.

A sequence F = {f_i}i∈I ⊆ H is a frame for H, if there exist two constants A, B >0, such that

Akfk² ≤X

i∈I

|hf, f_ii|² ≤Bkfk²,

for each f ∈ H. In this case we say that F is an (A, B)-frame. If only the right-hand side inequality holds, then F is called a Bessel sequence. If kfik = 1, for each i ∈I, then F is called a normalized frame. If F ={fi}i∈I

is a Bessel sequence, then the operator S : H −→ H, which is defined by S(f) = P

i∈Ihf, f_iif_i is bounded and called the frame operator of F. If F is an (A, B)-frame, then A.Id_H ≤S ≤B.Id_H. Now define ˜f_i =S⁻¹f_i. Then for eachf ∈H, we have

X

i∈I

hf,f˜_iif_i =f, f =X

i∈I

hf, f_iif˜_i.

The sequence Fe = {f˜i}i∈I is an (_B¹,_A¹)-frame for H and called the canonical dual frame ofF. We say that a Bessel sequence{g_i}i∈I is adual for the Bessel sequence{f_i}i∈I, if for each f ∈H, we have

f =X

i∈I

hf, f_iig_i,

or equivalently

f =X

i∈I

hf, g_iif_i.

In signal processing, one of the primary goals is to obtain a digital represen- tation of the signal which is suitable for storage, transmission and recovery.

As we stated above if {fi}i∈I is a frame for H, then every signal f ∈ H has an expansion like f = P

i∈Ic_if_i. This expansion is not digital, since the coefficient sequence {c_i}i∈I is real or complex valued, therefore it is needed to reduce this sequence to a discrete, and preferably finite set. This step is called quantization, for more information, see [2]. In this paper, we consider one method of quantization called Σ∆ algorithm, we obtain some upper error bounds especially by considering pair frames, duals and controlled frames.

2 Quantized Frame Expansions

We recall the definition of pair frames, for more study see [7]:

Definition 2.1. Let H be a Hilbert space, F = {f_i}i∈I, G = {g_i}i∈I ⊆ H and {mi}i∈I ⊆C.

(i) (m, G, F) is called an m-pair Bessel if the operator S_mGF :H −→H S_mGFf =X

i∈I

m_ihf, f_iig_i,

is bounded. If m_i = 1, for each i∈I, then(G, F)is called a pair Bessel.

(ii) Suppose that (m, G, F) is an m-pair Bessel. We say that (m, G, F) is an m-pair frame if S_mGF is invertible. If m_i = 1, for each i ∈ I, then (G, F) is called a pair frame.

(iii) Let (m, G, F) be an m-pair Bessel. We call it an m-pair dual if f =X

i∈I

m_ihf, f_iig_i,∀f ∈H.

(iv) Let (m, G, F) be an m-pair Bessel. Then it is called a near identity pair frame if there exists a nonzero elementa∈Csuch thatkIdH−aSmGFk<

1. In this case (m, G, F) is called an a-near identity pair frame.

Lemma 2.2. Let H be a Hilbert space. If {f_i}_i∈I is an (A, B) frame with the frame operator S, then A^α.Id_H ≤S^α ≤B^α.Id_H, for α ≥0 and B^α.Id_H ≤ S^α ≤A^α.Id_H, for α <0.

Proof. First suppose that α ≥ 0. If λ ∈ σ(S), since S is positive and S ≤ B.Id_H, then λ ∈ R⁺ and λ ≤ kSk ≤ B. For λ < A, we have S −λ.Id_H ≥ (A−λ)Id_H. Since A−λ >0, thenS−λ.Id_H is invertible, thereforeλ /∈σ(S).

Thus σ(S) ⊆ [A, B]. Now define f(z) = B^α −z^α. Since the spectrum of S does not contain zero and negative numbers, thenf is analytic onσ(S), hence

σ(B^α.Id_H −S^α) =σ(f(S)) =f(σ(S)) [ by Theorem 4.10 in [4]].

Sinceσ(S)⊆[A, B] andα ≥0, thenf(σ(S))⊆R⁺. Hence

(B^α.Id_H−S^α) is a positive operator. It means thatS^α ≤B^α.Id_H. Now define g(z) = z^α−A^α. We have

σ(S^α−A^α.Id_H) =σ(g(S)) =g(σ(S)).

Since σ(S) ⊆ [A, B] and α ≥ 0, then g(σ(S)) ⊆ R⁺. Thus S^α −A^α.Id_H is positive. For α <0, put η = −α. By the first case, we have A^η.Id_H ≤ S^η ≤ B^η.Id_H. Now by Theorem 2.2.5 in [9],B^α.Id_H ≤S^α ≤A^α.Id_H.

Proposition 2.3. Let {f_i}_i∈I be an (A, B)frame, α ∈R andm ={m_i}_i∈I with m_i = 1, for each i∈I. Then

(i) If α ≥ 0 and _A2^B(A^2α+2α+1)² < 1, then (m,{(Id_H +S^α)⁻¹S⁻¹f_i}i∈I,{f_i}i∈I) is an 1-near identity pair frame.

(ii) If α <0 and ^B_(B^2Aα+1)^2α−22 <1, then (m,{(Id_H +S^α)⁻¹S⁻¹f_i}i∈I,{f_i}i∈I) is an 1-near identity pair frame.

Proof. (i) Let g_i = (Id_H +S^α)⁻¹S⁻¹f_i and h_i = f_i +S^αf_i. It is clear that G= {g_i}_i∈I and Z = {h_i}_i∈I are frames. Since the frame operator of {h_i}_i∈I is (Id_H +S^α)S(Id_H +S^α), then

{(Id_H +S^α)⁻¹S⁻¹(Id_H +S^α)⁻¹(Id_H +S^α)f_i}i∈I ={g_i}i∈I,

is the canonical dual frame of {h_i}i∈I. Now for each f ∈H, we have X

i∈I

|hf, fi −hii|² =X

i∈I

|hS^αf, fii|² ≤BkS^αk²kfk² ≤B^2α+1kfk²,

the last inequality follows from the above lemma and Theorem 2.2.5 in [9].

Also we have X

i∈I

|hf, gii|² ≤ BkS⁻¹k²k(IdH +S^α)⁻¹k²kfk²

≤ B

A²(A^α+ 1)²kfk².

Note that the inequality k(Id_H + S^α)⁻¹k < _Aα¹+1, follows from the above lemma. Now we have

k(Id_H −S_mGF)xk=k(S_mGZ−S_mGF)xk = sup

kyk=1

|h(S_mGZ −S_mGF)x, yi|

≤ h

B^2α+1( B

A²(A^α+ 1)²)i¹₂ kxk,

and since B^2α+1(_A2(A^Bα+1)²)<1, then the result follows.

The proof of (ii) is similar to (i).

Now we recall some definitions from [2]:

LetK ∈N and δ >0. Given the midrise quantization alphabet A^δ_K ={(−K +1

2)δ,(−K+3

2)δ, . . . ,(−1 2)δ,(1

2)δ, . . . ,(K −1 2)δ},

consisting of 2K elements, the 2K-level midrise uniform scalar quantizer with stepsizeδ is defined by

Q(u) = argmin_q∈A^δ

k|u−q|.

Thus,Q(u) is the element of the alphabet which is closest tou. If two elements ofA^δ_K are equally close tou, then letQ(u) be the larger of these two elements, i.e., the one larger than u.

Definition 2.4. Let N ∈ N, δ > 0, {c_i}^N_i=1 ⊆ R and p be a permutation of {1,2, . . . , N}. The associated first order Σ∆ quantizer is defined by the iteration

u_i =ui−1+c_p(i)−q_i, q_i =Q(ui−1+c_p(i)),

where u₀ is a specified constant. The first order Σ∆ quantizer produces the quantized sequence{q_i}^N_i=1, and an auxiliary sequence{u_i}^N_i=0of state variables.

So if f ∈R^d has an expansion by using the sequence {c_p(i)}^N_i=1, then after quantization, it will be changed to a signalfewhich it’s expansion uses{q_i}^N_i=1. Definition 2.5. Let F = {f_i}^N_i=1 be a finite frame for R^d, and let p be a permutation of {1, . . . , N}. The variation of the frame F with respect to p is defined by

σ(F, p) :=

N−1

X

i=1

kf_p(i)−f_p(i+1)k.

It was shown in [2] that variation is an important tool to find a good approximation error. Note that if f ∈ R^d and feis quantized of f, then it is desirable that kf −fek gets small. In the rest of this paper, we obtain some upper bounds for kf−fek by using different concepts related to frame theory such as controlled frames which are considered in [1]:

Definition 2.6. Let R be a bounded and invertible operator on H.

A sequenceF ={f_i}i∈I ⊆H is called a frame controlled by T or T−controlled frame if there exist two positive numbers A and B such that

Akfk² ≤X

i∈I

hf, f_iihRf_i, fi ≤Bkfk²,

for each f ∈ H. It was proved in [1] that in this case F is a frame and the operator S_R :H −→H which is defined by

S_R(f) =X

i∈I

hf, f_iiRf_i,

is bounded, positive and invertible.

Suppose that H =R^d, {f_i}^N_i=1 and {g_i}^N_i=1 are two frames for H and T is an invertible operator such that

f =

N

X

i=1

c_p(i)T⁻¹g_p(i), c_p(i) =hf, f_p(i)i,

wherepis a permutation of {1, . . . , N}. Now suppose thatfeis quantized off obtained by Σ∆ algorithm, so fe=PN

i=1q_iT⁻¹g_p(i).

Theorem 2.7. Let F = {f_i}^N_i=1 and G = {g_i}^N_i=1 be two frames for R^d, f ∈R^d and for each 1≤i≤N −1, |u_i| ≤ ^δ₂. Then

(i) kf −fk ≤ kTe ⁻¹k

σ(G, p)^δ₂ +|u_N|kg_p(N)k+|u₀|kg_p(1)k .

(ii) If F and G are duals, then kf −fk ≤e σ(G, p)δ

2+|u_N|kg_p(N)k+|u₀|kg_p(1)k.

(iii) If F is an R-controlled frame, then kf −fk ≤ kSe _R⁻¹Rk

σ(F, p)δ

2 +|u_N|kf_p(N)k+|u₀|kf_p(1)k .

(iv) If (m, G, F) is an m-pair frame and m={m_i}^N_i=1, then kf−fk ≤ kSe _mGF⁻¹ k

σ(m.G, p)δ

2+|u_N|km_p(N).g_p(N)k+|u₀|km_p(1).g_p(1)k , where m.G={m_ig_i}^N_i=1.

(v) If (m, G, F) is an m-pair dual andm ={m_i}^N_i=1, then kf −fek ≤σ(m.G, p)δ

2+|u_N|km_p(N).g_p(N)k+|u₀|km_p(1).g_p(1)k, where m.G={m_ig_i}^N_i=1.

(vi) If (m, G, F) is ana-near identity pair frame, then kf−fk ≤ kSe _mGF⁻¹ k

σ(m.G, p)δ

2+|u_N|km_p(N).g_p(N)k+|u₀|km_p(1).g_p(1)k . Proof. (i) We have

f−fe =

N

X

i=1

(c_p(i)−qi)T⁻¹g_p(i)

=

N

X

i=1

(ui−ui−1)T⁻¹gp(i)

=

N−1

X

i=1

u_iT⁻¹(g_p(i)−g_p(i+1)) + u_NT⁻¹g_p(N)−u₀T⁻¹g_p(1), consequently

kf−fek ≤

N−1

X

i=1

δ

2kT⁻¹kkg_p(i)−g_p(i+1)k

+ |u_N|kT⁻¹kkg_p(N)k+|u₀|kT⁻¹kkg_p(1)k

= kT⁻¹kδ

2σ(G, p) +|u_N|kg_p(N)k+|u₀|kg_p(1)k .

(ii) IfF and G are duals, then T =Id_H and the result follows from part (i).

(iii) IfF is an R-controlled frame, then

f =

N

X

i=1

c_p(i)S_R⁻¹Rf_p(i), c_p(i) =hf, f_p(i)i,

so{S_R⁻¹Rf_i}^N_i=1 is a dual for F and by part (ii), we have kf −fk ≤e σ({S_R⁻¹Rf_i}^N_i=1, p)δ

2 +|u_N|kS_R⁻¹Rf_p(N)k + |u₀|kS_R⁻¹Rf_p(1)k

≤ kS_R⁻¹Rk

σ(F, p)δ

2+|u_N|kf_p(N)k+|u₀|kf_p(1)k .

(iv) Let (m, G, F) be an m-pair frame and m = {mi}^N_i=1. Then it is easy to see thatm.G is a Bessel sequence and

f =

N

X

i=1

c_p(i)S_mGF⁻¹ m_p(i)g_p(i), c_p(i) =hf, f_p(i)i,

and the result follows from part (i).

(v) If (m, G, F) is an m-pair dual, then S_mGF = Id_H and the result follows from part (iv).

(vi) SincekId_H −aS_mGFk<1, then aS_mGF is invertible, soS_mGF is invertible and the result follows from part (i).

The following corollary considers normalized frames which are very impor- tant in frame theory:

Corollary 2.8. Suppose that f ∈R^d, F and G are two frames in R^d such thatG is normalized and for each 1≤i≤N −1, |u_i| ≤ ₂^δ. Then

(i) kf −fk ≤ kTe ⁻¹k

σ(G, p)^δ₂ +|u_N|+|u₀| .

(ii) If F and G are duals, then

kf −fk ≤e σ(G, p)δ

2 +|u_N|+|u₀|.

(iii) If F is an R-controlled frame and F is normalized, then kf−fek ≤ kS_R⁻¹Rk

σ(F, p)δ

2+|u_N|+|u₀| .

(iv) If (m,G,F) is an m-pair frame and m={m_i}^N_i=1, then kf −fk ≤ kSe _mGF⁻¹ k

σ(m.G, p)δ

2 +|uN||m_p(N)|+|u0||m_p(1)| , where m.G={m_ig_i}^N_i=1.

(v) If (m, G, F) is an m-pair dual andm ={m_i}^N_i=1, then kf −fk ≤e σ(m.G, p)δ

2+|u_N||m_p(N)|+|u₀||m_p(1)|, where m.G={m_ig_i}^N_i=1.

(vi) If (m, G, F) is ana-near identity pair frame, then kf −fk ≤ kSe _mGF⁻¹ k

σ(m.G, p)δ

2 +|u_N||m_p(N)|+|u₀||m_p(1)| .

Corollary 2.9. Suppose that f ∈R^d, F and G are two frames in R^d such thatG is normalized and for each 0≤i≤N, |u_i| ≤ ^δ₂. Then

(i) kf −fk ≤ kTe ⁻¹k^δ₂

σ(G, p) + 2 .

(ii) If F and G are duals, then

kf−fek ≤ δ 2

σ(G, p) + 2 .

(iii) If F is an R-controlled frame and F is normalized, then kf−fek ≤ kS_R⁻¹Rkδ

2

σ(F, p) + 2 .

(iv) If (m,G,F) is an m-pair frame and m={mi}^N_i=1, then kf−fek ≤ kS_mGF⁻¹ kδ

2

σ(m.G, p) +|m_p(N)|+|m_p(1)| , where m.G={m_ig_i}^N_i=1.

(v) If (m, G, F) is an m-pair dual andm ={m_i}^N_i=1, then kf−fek ≤ δ

2

σ(m.G, p) +|m_p(N)|+|m_p(1)| , where m.G={m_ig_i}^N_i=1.

(vi) If (m, G, F) is ana-near identity pair frame, then kf−fek ≤ kS_mGF⁻¹ kδ

2

σ(m.G, p) +|m_p(N)|+|m_p(1)| .

Note that parts (i) of the above results generalize Theorem 3.4 and Corol- lary 3.6 in [2].

Acknowledgements: The author would like to thank the referee for valu- able comments and suggestions which improved the manuscript.

References

[1] P. Balaz, J. Antoine and A. Grybos, Weighted and controlled frames, Int.

J. Waveletes, Multiresolution Inf. Process, 8(1) (2010), 109-132.

[2] J. Benedeto, A. Powell and O. Yilmaz, Sigma-Delta quantization and finite frames, IEEE Trans. Inform. Th, 52(2006), 1990-2005.

[3] O. Christensen, Frames and Bases: An Introductory Course, Birkh¨auser, Boston, (2008).

[4] J.B. Conway, A Course in Functional Analysis, Springer-Verlag, New York, (1985).

[5] I. Daubechies, A. Grossmann and Y. Meyer, Painless nonorthogonal ex- pansions, J. Math. Phys., 27(1986), 1271-1283.

[6] R.J. Duffin and A.C. Schaeffer, A class of nonharmonic Fourier series, Trans. Amer. Math. Soc., 72(1952), 341-366.

[7] A. Fereydooni and A. Safapour, Pair frames, (To Appear).

[8] D. Gabor, Theory of communication,J. Inst. Elec. Engrg., 93(1946), 429- 457.

[9] G.J. Murphy, C^∗-Algebra and Operator Theory, Academic Press, San Diego, (1990).