SOBOLEV DUALS IN FRAME THEORY AND SIGMA-DELTA QUANTIZATION JAMESBLUM,MARKLAMMERS,ALEXANDERM.POWELL,ANDO¨ZGU¨RYILMAZ Abstract. Anewclassofalternativedualframesisintroducedinthesetting offiniteframesforRd. Thesedualframes,calledSobolevduals,provideahigh precision linear reconstruction procedure for Sigma-Delta (Σ∆) quantization offiniteframes. Themainresultissummarizedasfollows: reconstructionwith SobolevdualsenablesstablerthorderSigma-Deltaschemestoachievedeter- ministicapproximationerroroforderO(N−r)forawideclassoffiniteframes of size N. This asymptotic order is generally not achievable with canonical dual frames. Moreover, Sobolev dual reconstruction leads to minimal mean squarederrorundertheclassicalwhitenoiseassumption. 1. Introduction Insignalprocessing, anessentialproblemistoencodeasignal,typicallyanana- log object, with finitely many bits in an efficient and robust manner. Efficiency of an encoding is reflected by the associated approximation error: given a bit-budget, one seeks the error to be as small as possible in an appropriate norm. Noting that the encoding process typically involves an analog-to-digital (A/D) conversion step, it is also essential that the required digital representation be robust, for example, with respect to errors in arithmetic operations during the encoding process, and partial loss of information. This robustness requirement is frequently satisfied by redundantly representing signals before the A/D conversion or quantization stage. For example, one oversamples if the signals to be encoded are bandlimited func- tions,oroneusesovercompleteframeexpansionsifthesignalsofinterestarevectors in a finite dimensional Hilbert space. Redundantly representing a signal provides robustness, but it also makes A/D conversion more complex since coefficients in the representation are correlated. In particular,componentwisescalarquantization,alsoknownaspulsecodemodulation (PCM), is generally suboptimal for redundant expansions. Σ∆ quantization was devised as an alternative to PCM for quantizing bandlimited sampling expansions, [19]. Since then, the practice has matured and Σ∆ quantizers have established themselves as a preferred method for quantizing oversampled bandlimited signals, e.g., see [23]. The mathematical theory of Σ∆ quantization on the other hand is quite recent. After work by Gray, e.g., [14, 16], Daubechies and DeVore [10] established an approximation theoretical framework and provided rigorous results ontherelationshipbetweenrobustnessofΣ∆schemes,redundancyoftheassociated representations, and the approximation error. The work in [10] gives an explicit construction of stable 1-bit Σ∆ schemes of general order r. Moreover, [10] shows M.LammerswassupportedinpartbyaCahillGrantfromUNCW. A.M.PowellwassupportedinpartbyNSFGrantDMS-0811086. O¨.YılmazwassupportedinpartbyNSERCofCanada. 1 2 J.BLUM,M.LAMMERS,A.M.POWELL,ANDO¨.YILMAZ thatinthebandlimitedsettingtheL∞approximationerrorassociatedwithastable rth order Σ∆ scheme behaves like 1/λr where λ is the oversampling ratio. InspiredbytheworkofDaubechiesandDeVore,inparticularthatΣ∆quantiza- tion exploits redundancy more efficiently than PCM for bandlimited functions, [2] investigatedtheuseofΣ∆quantizationforredundantfiniteframeexpansions. The performance of PCM for quantizing finite frames is well investigated, e.g., [13, 12]. It was shown in [2] that even a first order Σ∆ scheme outperforms PCM (with linear reconstruction) in terms of approximation error, at least for certain families of frames with sufficiently high redundancy. A main focus of the subsequent work in [1, 7, 4, 5, 21] is to achieve better approximation rates (as the redundancy of the frame increases) for higher order Σ∆ schemes. In particular, one desires an approximation error of order O(N−r) with an rth order Σ∆ scheme, where N is the number of frame vectors. It was proved in [21] that for Σ∆ schemes of order 3 or higher one cannot obtain these sought-for approximation rates, at least in the case of harmonic frames, if one uses canonicaldualframesinthereconstruction. Asaremedy,twomainapproacheshave been developed. One approach concentrates on choosing special Parseval frames and uses the same frame in both analysis and reconstruction after quantization, e.g., [5]. This approach is less computationally intensive as there is no need to compute a dual frame, but it only works for rather specific analysis frames. A different approach used in [21], and in this paper, allows a more flexible choice of analysis frame and chooses a non-canonical dual frame that is specially designed for the particular quantization scheme. Overview. The work in [21] identifies general conditions under which alternative dual frames can be used in rth order Σ∆ quantization to achieve pointwise recon- structionerroroforderO(N−r), whereN istheframesize. However, [21]doesnot indicate how to construct such alternative dual frames. Indeed, concrete examples are only given for harmonic frames and the methods are decidedly ad hoc. The main result of this paper, Theorem 5.4, provides a general constructive method for finding alternative dual frames that are suitable for reconstruction in higher order Σ∆ quantization of finite frames. Specifically, we define a new class of alternative dual frames, the Sobolev duals, and prove that the associated recon- struction error for rth order Σ∆ quantization satisfies ||x−x||=O(N−r). (cid:101) The paper is organized as follows. Section 2 recalls basic frame theory. Section 3 briefly reviews Σ∆ quantization for finite frames. In Section 4 we define Sobolev dual frames. Our main result, Theorem 5.4, on pointwise Σ∆ error bounds with Sobolev duals is proven in Section 5. Section 6 addresses mean squared error with Sobolev duals. Section 7 contains numerical results. 2. Finite frames Definition 2.1. A finite collection of vectors {e }N ⊆Rd is a frame for Rd with n n=1 frames bounds 0<A≤B <∞ if N (cid:88) (2.1) ∀x∈Rd, A(cid:107)x(cid:107)2 ≤ |(cid:104)x,e (cid:105)|2 ≤B(cid:107)x(cid:107)2, n n=1 SOBOLEV DUALS IN FRAME THEORY AND SIGMA-DELTA QUANTIZATION 3 where (cid:107)·(cid:107)=(cid:107)·(cid:107) denotes the Euclidean norm. If A=B then the frame is said to 2 be tight, and it is unit-norm if (cid:107)e (cid:107) = 1 for each n. The frame bounds are taken n to be the respective largest and smallest values of A and B such that (2.1) holds. If {e }N ⊆ Rd is a frame then there exists a dual frame {f }N ⊆ Rd such n n=1 n n=1 that N N (cid:88) (cid:88) (2.2) ∀x∈Rd, x= (cid:104)x,e (cid:105)f = (cid:104)x,f (cid:105)e . n n n n n=1 n=1 IfN >dthentheframe{e }N ⊂Rd isanovercompletecollectionandthechoice n n=1 of dual frame {f }N in (2.2) is not unique. We will work with the left expansion n n=1 in(2.2),andhencereferto{e }N astheanalysisorencodingframe,andthedual n n=1 frame {f }N as the synthesis or decoding frame. Tight frames have the property n n=1 that the dual frame can be chosen as f = A−1e , where A is the frame bound. n n For more background on frames see [8, 9]. For finite frames in Rd, the basic definitions can be conveniently reformulated in terms of matrices. Given a frame {e }N ⊂Rd we define the associated frame n n=1 matrix E to be the d×N matrix with e as its jth column. In particular, the j columns of a d×N matrix E form a frame for Rd if and only if E has rank d. In viewofthisequivalence, weshallidentifyaframe{e }N withitsframematrixE n n=1 and simply refer to both as frames for Rd. Let {e }N ⊂ Rd be a frame for Rd with dual frame {f }N ⊂ Rd, and let E n n=1 n n=1 andF bethecorrespondingd×N framematrices. Theframeexpansions(2.2)can be equivalently expressed in terms of E and F as FE∗ =EF∗ =I , d where I is the d×d identity matrix and S∗ denotes the adjoint of a matrix S. d Namely,F isadualframeforEifandonlyifF isaleftinversetoE∗. Thisnaturally leads one to define the canonical dual frame associated to E by F = (EE∗)−1E. The canonical dual frame is a minimal norm dual frame with respect to various matrix norms described below. Given a d×N matrix E with the vectors {e }N as its columns n n=1 (cid:32) N (cid:33)1/2 (cid:112) (cid:88) (cid:107)E(cid:107) = tr(EE∗)= (cid:107)e ||2 and (cid:107)E(cid:107) = sup (cid:107)Ex(cid:107) F n op n=1 ||x||=1 will respectively denote the Frobenius norm and operator norm of E. Here tr(·) denotes the trace of a square matrix. We will also use the following norm N (cid:88) t(E)=sup{(cid:107) u e (cid:107):u ∈{−1,1}} n n n n=1 =sup{(cid:107)Eu(cid:107):u=(u ,··· ,u ) and u ∈{−1,1}}. 1 N n ThisissimplytheoperatornormofE asamappingfrom(RN,(cid:107)·(cid:107) )to(Rd,(cid:107)·(cid:107) ). ∞ 2 Thenotationt(·)isusedinviewoftheworkin[4]ontotalvariationofframepaths. The next lemma is standard. The proof follows easily from Theorem 3.6 in [22]. Lemma 2.2. Let E be a d×N frame matrix and let F be an arbitrary dual frame to E. The three quantities (cid:107)F(cid:107) ,(cid:107)F(cid:107) and t(F) are minimized when F is taken op F to be the canonical dual frame of E, namely F =(EE∗)−1E. 4 J.BLUM,M.LAMMERS,A.M.POWELL,ANDO¨.YILMAZ The following standard lemma relates the lower frame bound of a frame to the operatornormofitscanonicaldual. Weincludeaproofforthesakeofcompleteness. Lemma 2.3. Let E be an d×N frame matrix. If F is the canonical dual frame matrix of E then (cid:107)F(cid:107) =A−1/2 where A is the lower frame bound for E. op Proof. Note that the frame inequality (2.1) can be rewritten as ∀x∈Rd, A(cid:107)x(cid:107)2 ≤(cid:107)EE∗x(cid:107)2 ≤B(cid:107)x(cid:107)2. Also, the canonical dual frame is given by F =(EE∗)−1E so that FF∗EE∗ =(EE∗)−1EE∗(EE∗)−1EE∗ =I. SinceFF∗andEE∗arepositiveandareinversesofeachothertheresultfollows. (cid:3) 3. Sigma-Delta quantization of finite frame expansions Quantization is the process of digitally encoding frame coefficients (cid:104)x,e (cid:105) by n replacing them with elements of a finite set of numbers A known as a quantization alphabet. Given a finite set A⊂R, the associated scalar quantizer is defined by (3.1) Q(u)=arg min |u−q|. q∈A If Q(u) has two possible values for a specific u then arbitrarily specify one. Sigma-Delta(Σ∆)schemesareaclassofrecursivealgorithmsthatdirectlymake use of dependencies among frame vectors in the quantization process. We give a brief description of Σ∆ schemes, but refer the reader to [10, 23] for more detailed background. Suppose that {e }N ⊂ Rd is a frame for Rd and that x ∈ Rd has n n=1 frame coefficients x =(cid:104)x,e (cid:105). An rth order Σ∆ scheme with alphabet A runs the n n following iteration (3.2) q =Q(ρ(u1 ,u2 ,··· ,ur ,x )), ∆rur =x −q with n n−1 n−1 n−1 n n n n uj =∆uj+1, j =1,...,r−1, n n where u1 = u2 = ··· ,ur = 0, and where the iteration runs for n = 1,··· ,N. 0 0 0 Here ρ : Rr+1 → R is a fixed function, called the quantization rule, and ∆r is the rth order backwards difference operator defined by ∆w = w −w and n n n−1 ∆r =∆r−1∆. The uj are internal state variables in the algorithm and the q ∈A n n arethedesiredoutputcoefficients. Onecanlinearlyreconstructasignalxfromthe (cid:101) q with a dual frame {f }N by n n n=1 N (cid:88) (3.3) x= q f . (cid:101) n n n=1 The main issue of this paper concerns how to construct a suitable dual frame {f }N so that the reconstruction error (cid:107)x−x(cid:107) is small. n n=1 (cid:101) For a Σ∆ scheme to be useful in practice it should be stable. The scheme (3.2) is stable if there exist constants C ,C > 0, such that for any N > 0 and any 1 2 {x }N ⊂R, n n=1 (3.4) ∀ 1≤n≤N, |x |≤C =⇒ ∀ 1≤n≤N,∀j =1,··· ,r, |uj|<C . n 1 n 2 The stability constants C , C depend on the quantization alphabet A and the 1 2 quantization rule ρ. If the frame vectors e are uniformly bounded above in norm n by a constant M then the frame coefficients satisfy |x | = |(cid:104)x,e (cid:105)| ≤ M(cid:107)x(cid:107). This n n allows one to consider stability in terms of the norm of the input signal x ∈ Rd SOBOLEV DUALS IN FRAME THEORY AND SIGMA-DELTA QUANTIZATION 5 since (cid:107)x(cid:107)≤C /M =η implies |x |≤C . Since we will be working with uniformly 1 n 1 norm-boundedfamiliesofframes, weshallrefertostabilityintermsof(cid:107)x(cid:107)andsay that the Σ∆ scheme is stable for inputs (cid:107)x(cid:107)≤η. Constructing a stable Σ∆ scheme requires carefully choosing the quantization ruleρin(3.2). StabilityanalysisofΣ∆schemescanbequitecomplicated,especially for1-bithigherorderschemes,[10]. Thefollowingexampleshowsabasicfirstorder Σ∆ quantizer. For examples of stable higher order Σ∆ schemes, see [10, 18, 25]. Example 3.1. Let Q be the scalar quantizer associated to the alphabet Aδ = K {±(k− 1)δ : |k|≤K, k ∈Z}. The following first order Σ∆ scheme is stable: 2 q =Q(u +x ), u =u +x −q , n n−1 n n n−1 n n where u = 0 and n = 1,··· ,N. In particular, if the input sequence satisfies 0 |x |≤(K−1/2)δ then the state variables satisfy |u |≤δ/2, e.g., see [2]. n n The following notation will help simplify the error analysis of Σ∆ schemes. Let D be the first-order difference matrix given by   1 −1 0 ··· 0 0 1 −1 ··· 0    (3.5) D = ... ...    0 ··· 0 1 −1 0 ··· 0 0 1 N×N and define the discrete Laplacian ∇=D∗D. Note that D and ∇ are invertible. If one linearly reconstructs from the Σ∆ quantized coefficients q , obtained via (3.2), n as in (3.3) using a dual frame {f }N , then the reconstruction error equals n n=1 N N (cid:88) (cid:88) (3.6) (cid:107)x−x(cid:107)=(cid:107) (x −q )f (cid:107)=(cid:107) (∆rur) f (cid:107)=(cid:107)FDr∗(u)(cid:107), (cid:101) n n n n n n=1 n=1 where u=[ur,ur,··· ,ur ]∗ and F is the frame matrix associated to {f }N . 1 2 N n n=1 4. Sobolev dual frames In this section we introduce the class of Sobolev dual frames. Definition 4.1. Let F be a d×N matrix. Define the Sobolev-type matrix norms (cid:107)F(cid:107) =(cid:107)DrF∗(cid:107) =(cid:107)FDr∗(cid:107) , r,op op op (cid:107)F(cid:107) =(cid:107)DrF∗(cid:107) =(cid:107)FDr∗(cid:107) , r,F F F and the norm, e.g., [4, 5], given by T (F)=t(FDr∗). r Definition 4.2. (Sobolev dual) Fix a positive integer r. Let {e }N ⊂ Rd be a n n=1 frameforRd andletE betheassociatedd×N framematrix. TherthorderSobolev dual {f }N ⊂Rd of E is defined so that f is the jth column of the matrix n n=1 j F =(ED−r(D∗)−rE∗)−1ED−r(D∗)−r, where D is the invertible matrix defined by (3.5). The next theorem is motivated by the work on alternative dual frames in [11]. Theorem 4.3. Let E be an d×N frame matrix. The rth order Sobolev dual F is the dual frame of E for which (cid:107)F(cid:107) ,(cid:107)F(cid:107) and T (F) are minimal. r,op r,F r 6 J.BLUM,M.LAMMERS,A.M.POWELL,ANDO¨.YILMAZ Proof. Note that FE∗ = (ED−r(D∗)−rE∗)−1ED−r(D∗)−rE∗ = I, since D is in- vertible and E has full rank. Thus F is a dual frame for E. Since D is invertible, U is a dual frame to E if and only if UD∗r(D∗)−rE∗ = UE∗ =I ifandonlyifUD∗r isadualframetoED−r. IfF istherthorderSobolev dual of E then (4.1) FD∗r =(ED−r(D∗)−rE∗)−1ED−r is the canonical dual frame of ED−r. By Lemma 2.2, FD∗r is the dual frame of ED−r with minimal operator norm, Frobenius norm, and norm t(·). So, the SobolevdualF isthedualframeofE minimizing(cid:107)·(cid:107) and(cid:107)·(cid:107) andT (·). (cid:3) r,op r,F r 5. Signal reconstruction in Σ∆ quantization with Sobolev duals In this section we prove that Sobolev dual frames provide an effective recon- struction method for Σ∆ quantization of finite frame expansions, and enable rth order Σ∆ schemes to achieve pointwise error of order 1/Nr, where N is the frame size. We focus on the class of frames associated with piecewise smooth paths in Rd and adopt the terminology of [5]. Frames with this property arise naturally in quantization problems, e.g., [2, 1, 4, 5]. We say that a function f : [0,1] → R is piecewise-C1 if it is C1 except at finitely many points in [0,1], and the left and right limits of f and f(cid:48) exist at all of these points. Definition 5.1. A vector valued function E : [0,1] → Rd given by E(t) = [e (t), e (t),···e (t)]∗ is a piecewise-C1 uniformly-sampled frame path if the fol- 1 2 d lowing three conditions hold: (i) For 1≤n≤N, e :[0,1]→R is piecewise-C1 on [0,1]. n (ii) The functions {e }d are linearly independent. n n=1 (iii) There exists N such that for each N ≥N the collection {E(n/N)}N is 0 0 n=1 a frame for Rd. Frame vectors generated by such a frame path are uniformly bounded in norm. Namely, there exists M such that (cid:107)E(n/N)(cid:107)≤M holds for all n and N. Example 5.2. Roots-of-unity frame path. Considertheframepathdefinedby E(t) = [cos(2πt),sin(2πt)]∗. It is well known, e.g., [13], that for each N ≥ 3, the collection U ={E(n/N)}N ⊂R2 given by N n=1 (5.1) E(n/N)=[cos(2πn/N),sin(2πn/N)]∗, 1≤n≤N, isaunit-normtightframeforR2. Figure1showscoordinatecomponentsof(a)the canonical dual of U for R2, and (b) the associated 2nd order Sobolev dual. 200 Example 5.3. Repetition frame path. Consider the frame path E(t)=[χ (t),χ (t),···χ (t)]∗, [0,1] (1,2] (d−1,1] d d d d where χ denotes the characteristic function of S. Note that R ={E(n/N)}N S N n=1 is a frame for Rd for all N ≥ d. When N ∈ dN, then R is obtained by N-fold N repetitionofthestandardbasisforRd,hencethenamerepetitionframe. Ford=32 and N =192, Figure 2 shows (a) the components h , h , and h of the canonical 1 8 15 dual of the repetition frame R in R32, and (b) the components f , f , and f 192 1 8 15 of the associated 2nd order Sobolev dual. For s∈R, we say that f(N)=O(Ns) if limsup N−s|f(N)|<∞. N→∞ SOBOLEV DUALS IN FRAME THEORY AND SIGMA-DELTA QUANTIZATION 7 0.01 0.02 0.005 0.01 0 h1−0.005 f1 0 −0.01 −0.01 −0.0150 20 40 60 80 100 120 140 160 180 200 −0.020 20 40 60 80 100 120 140 160 180 200 0.01 0.03 0.005 0.025 0.02 h2 0 f20.015 0.01 −0.005 0.005 −0.010 20 40 60 80 100 120 140 160 180 200 00 20 40 60 80 100 120 140 160 180 200 n n (a) (b) Figure 1. Componentsof(a)thecanonicaldual,and(b)the2nd order Sobolev dual for the roots-of-unity frame, see Example 5.2. 0.2 0.5 h10.1 f1 0 00 20 40 60 80 100 120 140 160 180 200 −0.50 20 40 60 80 100 120 140 160 180 200 0.2 0.2 h80.1 f8 0 00 20 40 60 80 100 120 140 160 180 200 −0.20 20 40 60 80 100 120 140 160 180 200 0.2 0.2 h150.1 f15 0 00 20 40 60 80 1n00 120 140 160 180 200 −0.20 20 40 60 80 1n00 120 140 160 180 200 (a) (b) Figure 2. Componentsof(a)thecanonicaldual,and(b)the2nd order Sobolev dual for the repetition frame, see Example 5.3. Theorem 5.4. Let r be a positive integer, and suppose that one is given an rth order Σ∆ scheme, with quantization alphabet A, that is stable for all inputs x∈Rd with (cid:107)x(cid:107)≤η for some η >0. Let E(t) be a piecewise-C1 uniformly-sampled frame path for Rd, and suppose that N is such that E ={E(n/N)}N is a frame for Rd for all N ≥N . Given 0 N n=1 0 x ∈ Rd, (cid:107)x(cid:107) ≤ η, with frame coefficients {(cid:104)x,E(n/N)(cid:105)}N , let {qN}N ⊂ A n=1 n n=1 be the sequence of quantized frame coefficients that are generated by the rth order Σ∆ scheme. If one uses the rth order Sobolev dual frame F of E to linearly N N reconstruct an approximation x to x from the quantized frame coefficients via (cid:101) x=F q (cid:101) N where q =[qN,qN,··· ,qN]∗, then 1 2 N (5.2) (cid:107)x−x(cid:107)=O(N−r). (cid:101) The implicit constant may be taken independent of x. Proof. Since the Σ∆ scheme is stable there exists C > 0 such that the Σ∆ state variables satisfy |uj| ≤ C for 1 ≤ n ≤ N . Letting u = [ur,ur,··· ,ur ]∗ gives √ n 1 2 N (cid:107)u(cid:107) ≤C N, whereby it follows from (3.6) that 2 √ (cid:107)x−x(cid:107) =(cid:107)FDr∗u(cid:107) ≤(cid:107)FDr∗(cid:107) (cid:107)u(cid:107) ≤C N(cid:107)FDr∗(cid:107) . (cid:101) 2 2 op 2 op 8 J.BLUM,M.LAMMERS,A.M.POWELL,ANDO¨.YILMAZ It therefore suffices to prove that (cid:107)FDr∗(cid:107) =O(N−r−1/2). op WithaslightabuseofnotationletE =E betheframematrixassociatedwith N {E(n/N)}N . Since F is the rth order Sobolev dual of E, we have that FDr∗ is n=1 thecanonicaldualframeofED−r,see(4.1). ByLemma2.3itisthereforesufficient to prove that the lower frame bound A=A of ED−r satisfies N (5.3) A=A ≥αN2r+1+O(N2r), N for some constant α>0. To estimate the frame bound A associated with ED−r first note that D−1 is N the N ×N upper triangular matrix with 1 in all entries on and above the main diagonal and 0 elsewhere. Thus in the case when r = 1 we have that the frame elements associated with ED−1 are given by {(cid:80)i E(j/N)}N . Similarly, for j=1 i=1 general r we have that the frame elements associated with ED−r are given by (cid:26) (cid:88)ir (cid:88)i2 (cid:88)i1 (cid:27)N ··· E(i /N) . 0 ir−1=1 i1=1i0=1 ir=1 Let v = [v ,v ,···v ]T be on the unit sphere of Rd, i.e., (cid:107)v(cid:107) = 1, and let r be 1 2 d an arbitrary positive integer. We estimate the lower frame bound A of ED−r as N follows. Note that (cid:88)N |(cid:104)v, (cid:88)ir ···(cid:88)i2 (cid:88)i1 E(i0)(cid:105)|2 N ir=1 ir−1=1 i1=1i0=1 = (cid:88)N | (cid:88)ir ···(cid:88)i2 (cid:88)i1 (cid:104)v,E(i0)(cid:105) 1 |2 1 N2r+1 N Nr N ir=1 ir−1=1 i1=1i0=1 (cid:90) 1 (cid:90) tr (cid:90) t2(cid:90) t1 (5.4) =N2r+1 | ··· (cid:104)v,E(t )(cid:105)dt dt ···dt |2dt +O(N2r). 0 0 2 r−1 r 0 0 0 0 Lemma 7.2 in the Appendix provides complete details for the Riemann sum argu- ment used to obtain (5.4). We next show that if v ∈Rd,(cid:107)v(cid:107)=1, then there exists a subset S ⊆[0,1] with v positive measure 0<|S | such that v (cid:90) tr (cid:90) t2(cid:90) t1 t ∈S =⇒ γ(−r)(t )= ··· (cid:104)v,E(t )(cid:105)dt dt ···dt (cid:54)=0. r v v r 0 0 1 r−1 0 0 0 Suppose to the contrary that there exists (cid:107)v(cid:107) = 1 such that γ(−r)(t) = 0 for v a.e. t ∈ [0,1]. Noting that γ(−r) is continuous (in fact it is at least r−1 times v continuouslydifferentiable)wethenhavethatγ(−r)(t)=0forallt∈[0,1]. Takingr v derivativesofγ(−r) impliesthat(cid:104)v,E(t )(cid:105)=0forallt ∈[0,1]. Howeverthisleads v 0 0 to (cid:80)d v e (t ) = 0 for all t ∈ [0,1] which contradicts the linear independence n=1 n n 0 0 of the component functions {e (t)}d of the frame path E(t). n n=1 Therefore, for every (cid:107)v(cid:107)=1 we have that the continuous function (cid:90) 1 (cid:90) tr (cid:90) t2(cid:90) t1 B(v ,v ,···v )= | ··· (cid:104)v,E(t )(cid:105)dt dt ···dt |2dt >0, 1 2 d 0 0 1 r−1 r 0 0 0 0 is nonzero for all (cid:107)v(cid:107) = 1, and therefore attains a positive minimum over the compact set {v ∈ Rd : (cid:107)v(cid:107) = 1}. Thus there exists a constant α > 0 such that for SOBOLEV DUALS IN FRAME THEORY AND SIGMA-DELTA QUANTIZATION 9 all v ∈Rd,(cid:107)v(cid:107)=1, (cid:88)N |(cid:104)v, (cid:88)ir ···(cid:88)i2 (cid:88)i1 E(i0)(cid:105)|2 ≥αN2r+1+O(N2r). N ir=1 ir−1=1 i1=1i0=1 It follows that (5.3) holds. This completes the proof. (cid:3) Sobolevdualsarehierarchicalinthefollowingsense: ifquantizationisperformed with an rth order Σ∆ scheme, and if the decoding party uses a Sobolev dual of order s < r, then the approximation error will be of order O(N−s). This follows by using norm properties of the rth order Sobolev dual (see the proof of Theorem 5.4) and (cid:107)D(cid:107) ≤2 to obtain op (cid:107)FDr∗(cid:107) ≤(cid:107)FDs∗(cid:107) (cid:107)D(r−s)∗(cid:107) ≤O(N−s−1/2) 2(r−s) =O(N−s−1/2), op op op which implies that the approximation error satisfies (cid:107)x − x(cid:107) = O(N−s). Thus, (cid:101) depending on the required precision, one can use a lower order Sobolev dual, and thereby reduce the computational resources required to construct the dual. 6. Mean Squared Error for Σ∆ quantization with Sobolev duals This section shows that linear reconstruction with Sobolev duals achieves mini- malmeansquarederror(MSE)undertheΣ∆ white noise assumption(Σ∆-WNA). Statisticalnoisemodelshavealonghistoryintheanalysisanddesignofquantiza- tionalgorithms,withthegeneralgoalbeingtoreplaceorapproximatedeterministic analysiswithreasonablestatisticalmodels. Bennett’sclassicalwork[3]modeledin- dividualcoefficientquantizationerrorsinsimplescalarquantizationasindependent uniform random variables. While Bennett’s noise model has mathematical short- comings, it is known to be empirically accurate in many settings, especially when the quantizer step size is small, e.g., see [3, 20, 15]. Similar noise models have been applied to the analysis of Σ∆ algorithms, e.g., [15, 23, 24, 6, 2]. We shall consider the following Σ∆ noise model that treats the Σ∆ state variables u in (3.6) as n independent identically distributed (i.i.d.) random variables. Design Criterion 6.1 (Σ∆-WNA). Suppose that x, the vector to be quantized, ischosenrandomlyaccordingtosomeprobabilitymeasuresupportedonacompact set in Rd, and quantized with an rth-order Σ∆ scheme. Model the corresponding Σ∆statevariables{u }N in(3.6)asindependent,identicallydistributedrandom n n=1 variables with mean zero and variance σ2. We previously saw that the state variables for the first order Σ∆ scheme in Example 3.1 satisfy |u | ≤ δ/2. In view of this, it is common to model the state n variables u as uniform random variables on [−δ/2,δ/2]. Ergodic properties of the n statevariables,e.g.,see[17,18],arealsocloselyrelatedtotheuniformdistribution. WeemphasizethattheΣ∆-WNAisnotmathematicallyrigorousbutisnonetheless empirically reasonable in many settings. For this reason, we simply view the noise model as a useful design criterion, and refer to [24, 14, 16, 15] for discussion of its mathematical validity. Theorem 6.2. Let {e }N ⊂Rd be a frame for Rd with frame matrix E. Suppose n n=1 thatxisrandomlydrawnfromacompactsetB inRd accordingtoaBorelprobability measurep, supportedonB, andsupposethattheframecoefficients{(cid:104)x,e (cid:105)}N are n n=1 10 J.BLUM,M.LAMMERS,A.M.POWELL,ANDO¨.YILMAZ 100 Altdual 100 Altdual Candual Candual 10−1 C/N 10−1 C/N m) c/N3 m) c/N3 m error (2−nor1100−−32 m error (2−nor1100−−32 maximu10−4 maximu10−4 10−5 10−5 102 102 N (number of elements in the frame) N (number of elements in the frame) Third order scheme (repetition frame) Third order scheme (roots−of−unity frame) (a) (b) Figure 3. Comparison of worst case error in Σ∆ reconstruction with canonical duals and Sobolev duals, see Example 7.1. Errors for (a) repetition frame path, and (b) roots-of-unity frame path. quantized using an rth order Σ∆ scheme that is stable on B. UndertheΣ∆-WNA, among all dual frames F of E, the rth-order Sobolev dual minimizes the MSE MSE =E(cid:107)x−x(cid:107)2, (cid:101) where x = x is as in (3.3), and E denotes the expectation with respect to the (cid:101) (cid:101)F probability measure p. Proof. Let E be a frame and let F be any dual frame. It follows from (3.6) that the MSE is given by MSE =E(cid:107)x−x(cid:107)2 =E[(cid:104)FDr∗u,FDr∗u(cid:105)]=σ2(cid:107)FDr∗(cid:107)2. (cid:101) F ByTheorem4.3theMSEisminimalwhenF istherthorderSobolevdualofE. (cid:3) 7. Numerical example The following experiment numerically compares the performance of Sobolev du- als and canonical dual frames for reconstructing Σ∆ quantized frame coefficients. Example 7.1. 30 points in R2 are randomly chosen according to the uniform distributionontheunit-square. For eachofthe30points, thecorrespondingframe coefficients with respect to the repetition frame R are quantized using the 3rd N order Σ∆ scheme from [10]. Linear reconstruction is then performed with each of the30setsofquantizedcoefficientsusingboththecanonicaldualframeandthe3rd order Sobolev dual of R . Candual(N) and Altdual(N) will denote the largest of N the30errorsobtainedusingthecanonicaldualframeandSobolevdualrespectively. Part (a) in Figure 3 shows a log-log plot of Altdual(N) and Candual(N) against the frame size N. For comparison, log-log plots of 1/N3 and 1/N are also given. Part(b)inFigure3repeatstheaboveexperimentusingtheroots-of-unityframe insteadoftherepetitionframe. Inthiscase,notethesplitbehaviorinthecanonical reconstructionwhichwasdiscussedin[21]. Inbothparts(a)and(b)Sobolevduals yield smaller reconstruction error than canonical dual frames.