ANALYSIS OF DECIMATION ON FINITE FRAMES WITH
SIGMA-DELTA QUANTIZATION

arXiv:1803.02921v1 [] 8 Mar 2018

KUNG-CHING LIN
Abstract. In Analog-to-digital (A/D) conversion on oversampled bandlimited functions,
integration of samples in blocks before down-sampling, known as decimation, has been
proven to greatly improve the efficiency of data storage while maintaining high accuracy. In
particular, when coupled with the Σ∆ quantization scheme, the reconstruction error decays
exponentially with respect to the bit-rate. Here, a similar result is proved for finite unitarily
generated frames. Specifically, under certain constraints on the generator, decimation merely
increases the reconstruction error estimate by a factor of π/2, independent of the block size.
On the other hand, efficient encodings of samples are made possible from decimation, and
thus the error decays exponentially with respect to total bits used for data storage. Moreover,
the decimation on finite frames has the multiplicative structure that allows the process to
be broken down into successive iterations of decimation with smaller blocks, which opens
up the possibility for parallel computation and signal transmission through multiple nodes.

1. Introduction
Analog-to-digital (A/D) conversion is a process where bandlimited signals, e.g., audio
signals, are digitized for storage and transmission between computers, which is feasible due
to the well-known classical sampling theorem. In particular, the theorem indicates that
discrete sampling is sufficient to capture all features of a given bandlimited signal, provided
that the sampling rate is higher than the Nyquist rate.
However, the classical sampling theorem does not resolve all the difficulties for digital data
storages. In addition to its inability to store continuous information, perfect representation
of real numbers is also impossible for a computer. Simply put, approximation error occurs
at every sample due to limited storage space. The leveraging between efficient bit allocation
and high reconstruction accuracy is called quantization.
Quantization is an integral part of A/D conversion. On the other hand, most data that
are stored digitally also involve quantization problems. However, the data studied in those
fields are different from audio signals in nature: Instead of having finite bandwidth, the
objects of interest are more naturally represented in terms of finite frames. This prompts
the development of quantization theory for finite frames.
Fortunately, the similarities between bandlimited signals and finite frames enable the
translation of respective results for quantization, [1, 4]. On the other hand, as A/D conversion is closely tied to the properties of the Fourier transform, which is analogous to harmonic
frames, it can be viewed as a special case for finite frames. Moreover, whereas the classical sampling theorem asserts signal reconstruction with infinitely many samples, the data
2010 Mathematics Subject Classification. 42C15.
Key words and phrases. Decimation, Sigma-Delta Quantization, Unitarily Generated Frames.
The author gratefully acknowledges the support of ARO Grant W911NF-17-1-0014.
1

2

KUNG-CHING LIN

from finite frames are finite, creating boundary effects that make the adaptation of analysis
methods nontrivial in some cases.
In this paper, a specific signal processing method called decimation is applied to finite
frames. Candy [3] observed that decimation greatly improves the storage efficiency for A/D
conversion while retaining the same error decay rate by numerical experiments, but the
rigorous proof of this statement was not given until 2015, when Daubechies and Saab [8]
described effects of decimation explicitly, whose proof directly inspired this paper. As mentioned above, the adaptation introduces the boundary effect and requires extra attention
in the formulation More importantly though, it will be shown that such difficulties can be
circumvented, so decimation in A/D conversion is readily applicable to finite frames, and in
turn to a wide array of applications.
2. Background and Preliminaries
2.1. Classical Sampling Theorem and Sigma-Delta (Σ∆) Quantization. Given a
function f ∈ L1 (R), its Fourier transform fˆ is defined as:
Z ∞
ˆ
f (γ) =
f (t)e−2πıtγ dt.
−∞

The Fourier transform can also be uniquely extended to L2 (R) as a unitary transformation.
Definition 2.1. Given f ∈ L2 (R), f ∈ P W[−Ω,Ω] if its Fourier transform fˆ ∈ L2 (R) is
supported in [−Ω, Ω].
An important component of A/D conversion is the following theorem:
Theorem 2.2 (Classical Sampling Theorem). Given f ∈ P W[−1/2,1/2] , for any g ∈ L2 (R)
satisfying
• ĝ(ω) = 1 on [−1/2, 1/2]
• ĝ(ω) = 0 for |ω| ≥ 1/2 + ,
with  > 0 and T ∈ (0, 1 − 2), t ∈ R, one has
(1)

f (t) = T

X
n∈Z

f (nT )g(t − nT ),

where the convergence is both uniform on compact sets of R and in L2 .
In particular, for g(t) = sin(πt)/(πt) and T = 1, the following identity holds in L2 (R):
X
sin(π(t − n))
f (t) =
f (n)
.
π(t − n)
However, the discrete nature of digital data storage makes it impossible to store exactly the
samples {f (nT )}n∈Z . Instead, the quantized samples {qn }n∈Z chosen from a pre-determined
finite alphabet A are stored. This results in the following reconstructed signal
X
f˜(t) = T
qn g(t − nT ).
As for the choice of the quantized samples {qn }n , we shall discuss the following two schemes:

ANALYSIS OF DECIMATION ON FINITE FRAMES WITH SIGMA-DELTA QUANTIZATION

3

Samples {yn }
⌃

Quantization: y

q=

u
Quantized sample {qn } (un

Averaged samples {q̃n } (

un

un+⇢ un
⇢

Decimated Sub-samples q̃n⇢ (

1)

1

⇢

)

⇢
ũ⇢
n ũn
⇢

1

)

Figure 1. Illustration of Decimation Scheme: Taking averages of samples
nearby before down-sampling. The effect on the reconstruction (Replacing qn
with yn − qn ) is illustrated in parentheses
• Pulse Code Modulation (PCM):
Quantized samples are taken as the direct-roundoff of the current sample, i.e.,
(2)

qn = Q0 (f (nT )) := arg min |q − f (nT )|.
q∈A

• Σ∆ Quantization:
A sequence of auxiliary variables {un }n∈Z is introduced for this scheme. {qn }n∈Z
is defined recursively as
qn = Q0 (un−1 + f (nT )),
un = un−1 + f (nT ) − qn .
Σ∆ quantization was introduced in 1963, [13], and is still widely used, due to its advantages
in robustness against hardware imperfection and utilization on the oversampling over PCM,
[7]. For Σ∆ quantization, and more generally noise shaping schemes to be explained below,
the boundedness of {un }n∈Z turns out to be essential, as most analyses on quantization
problems rely on it for error estimates. Schemes with bounded auxiliary variables are said
to be stable.
2.2. Signal Decimation. The following procedure, known as decimation in the engineering
community [3], is applied after the quantized samples are determined: Given a fixed sampling
rate higher than the Nyquist rate, i.e., the lowest sampling rate such that reconstruction is
possible, the quantized samples are averaged within blocks of uniform size so that the process
effectively reduces the sampling rate to near-Nyquist.
Decimation greatly reduces the resources needed while preserving the differencing structure of the Σ∆ scheme. This means that decimation allows efficient storage of data while
retaining the error decay of Σ∆ quantization schemes. See Figure 1 for illustration.
2.3. Σ∆ Quantization on Finite Frames. Fix a Hilbert space H along with a set of
vectors {ej }j∈Z ⊂ H. The vectors {ej }j∈Z form a frame for H if there exist A, B > 0 such

.

4

KUNG-CHING LIN

that for any v ∈ H, the following inequality holds:
X
Akvk2H ≤
|<v, ej >|2 ≤ Bkvk2H .
j∈Z

The notion of frames is a generalization of orthonormal bases in a vector space. Different from
bases, frames are usually over-complete: The vectors form a linearly dependent spanning set.
It is particularly useful in signal processing in that such over-completeness can be utilized
for noise reduction and is more robust against data corruption than orthonormal bases.
Given a frame {ej }j∈Z , the linear operator T : H → `2 (Z) satisfying T (v) = {<v, ej >}j∈Z
∗
2
∗
is
Pcalled the analysis operator, and its adjoint operator T : ` (Z) → H with T ({c∗ j }j∈Z ) =
j∈Z cj ej is called the synthesis operator. Defining the Hermitian operator S = T T : H →
H, we have the following reconstruction formulas: For any v ∈ H,
X
 X
v = S −1 Sv = S −1
<v, ej >ej =
<v, ej >S −1 ej
j∈Z

= SS −1 v =

X

j∈Z

<S −1 v, ej >ej =

j∈Z

X
j∈Z

<v, S −1 ej >ej .

Suppose now the Hilbert space is finite dimensional and the number of vectors is also finite.
Then this Hilbert space is isomorphic to a finite-dimensional Euclidean space, and the corresponding analysis operator T : H → `2 (Z) is also finite-dimensional. Thus, we are able to
consider T as a matrix E ∈ Cm×k , where the rows of E are {e∗j }j , the conjugate transpose
of {ej }j . The synthesis operator is then E ∗ and S = E ∗ E.
Under this framework, one considers the quantization q of y = Ex before reconstructing
x̃ = S −1 E ∗ q. The frame-theoretic greedy Σ∆ quantization is defined as follows: Given a
finite alphabet A ⊂ C, we introduce again the auxiliary variable {un }m
n=1 , where we shall
set u0 = 0. For n = 1, . . . , m, we calculate {qn }n and {un }n as follows:
(3)

qn = Q0 (un−1 + yn )
un = un−1 + yn − qn ,

where Q0 is defined in (2). In the matrix form, we have
(4)

y − q = ∆u,

where ∆ ∈ Zm×m is the backward difference matrix.
In practice, the alphabet A is often chosen to be A0 which is uniformly spaced and
symmetric around the origin: Given δ > 0, we define
A0 = {−(2K + 1)δ/2, −(2K − 1)δ/2, . . . , (2K − 1)δ/2, (2K + 1)δ/2}.

For complex Euclidean spaces, we define A = A0 +ıA0 . In both cases, A is called a mid-rise
uniform quantizer. Throughout this paper we shall always deal with such A .
2.4. Unitarily Generated Frames. The frame elements of unitarily generated frames are
generated by a cyclic group: Given a base vector φ0 ∈ Ck and a Hermitian matrix Ω ∈ Ck×k ,
the frame elements are defined as follows:
(5)

Ut := e2πıΩt ,

(m)

φj

= Uj/m φ0 .

ANALYSIS OF DECIMATION ON FINITE FRAMES WITH SIGMA-DELTA QUANTIZATION

5

As symmetry occurs naturally in many applications, it is not surprising that unitarily generated frames receive serious attention, and their applications in signal processing abound,
[11, 10].
It should be noted that unitarily generated frames are group frames with the generator
G = U1/m provided U1 = Ik , while harmonic frames are special cases of unitarily generated
frames with√ generator Ω as a diagonal matrix with integer values and base vector φ0 =
(1, . . . , 1)t / k.
2.5. Noise Shaping Scheme and the Choice of Dual Frames. In [5], it is pointed out
that the reconstruction error of Σ∆ quantization for bandlimited functions is concentrated
in high frequency. Since audio signals have finite bandwidth, it is now possible to separate
the signal from the error. This discovery led to the introduction of noise shaping schemes,
aiming to design the scheme so that the quantization error has desirable structures for noise
reduction.
In terms of finite frames, noise shaping schemes differ from the Σ∆ scheme in the following
way:
y − q = Hu,

(6)

where H is lower-triangular so that q can be determined recursively.
Now, given a frame E, a noise shaping scheme H, and a dual frame F of E, i.e. , F E = Ik ,
the reconstruction error of this problem is
kx − F qk2 = kF (y − q)k2 = kF Huk2 ≤ kF Hk∞→2 kuk∞ ,
where k · k∞→2 is the operator norm between `∞ and `2 , i.e.,
kT k∞→2 :=

sup
x:kxk∞ =1

kT xk2 .

It gives us an idea that the choice of the dual frame F can play a role in the reconstruction
error. For instance, [2] proved that the choice of F = (H −1 E)† H −1 gives minimum 2-norm
for F H, where given any matrix A, A† is defined as the canonical dual (A∗ A)−1 A∗ . More
generally, one can consider a V -dual, namely (V E)† V , provided that V E is still a frame.
With this terminology, decimation can be viewed as a special case of V -dual, and conversely
each V -dual can be associated with some manipulation on the quantized sample q.
2.6. Prior Works.
2.6.1. Bandlimited Functions. Despite its simple form and robustness, Σ∆ quantization only
results in linear error decay with respect to the sampling period T as T → 0. It was later
proven in [6] that a generalization of Σ∆ quantization, namely the r-th order Σ∆ quantization, exists for any arbitrary r ∈ N, and for such schemes the error decay is of polynomial
order r. Leveraging the different constants for this family of quantization schemes, subexponential decay can also be achieved. A different family of quantization schemes was
shown [12] to have exponential error decay with small exponent (c ≈ 0.07.) In [9], the
exponent was improved to c ≈ 0.102.

6

KUNG-CHING LIN

2.6.2. Finite Frames. Σ∆ quantization is also applied on finite frames. It is proven [1]
that for any family of frames with bounded frame variation, the reconstruction error decays
linearly with respect to the oversampling rate m/k, where the frame is an m × k matrix.
With different choices of dual frames, [2] proposed that the so-called Sobolev dual achieves
minimum induced matrix 2-norm for reconstructions. By carefully matching between the
dual frame and the quantization scheme, [5] proved that using β-dual for random frames, it
will result in exponential decay with near-optimal exponent and high probability.
2.6.3. Decimation. In [3], using the assumption that the noise in Σ∆ quantization is random
along with numerical experiments, it was asserted that decimation greatly reduces the number of bits needed while maintaining the reconstruction accuracy. In [8], a rigorous proof
was given to show that such an assertion is indeed valid, and the reduction of bits used turns
the linear decay into exponential decay with respect to the bit-rate.
2.7. Notation. The following notation is used in this paper:
• x ∈ Ck : The signal of interest.
• E ∈ Cm×k : A fixed frame.
• y = Ex ∈ Cm : The sample.
• ρ ∈ N: The block size of the decimation, satisfying ρk ≤ m.
• p = bm/ρc ∈ N: The greatest integer smaller than the ratio m/ρ.
• A = A0 + ıA0 ⊂ C: The quantization alphabet. A is said to have length 2L if
A0 = {(2j + 1)δ/2 : −L ≤ j ≤ L − 1} for some δ > 0.
• q ∈ Cm : The quantized sample obtained from the greedy Σ∆ quantization defined in
(3).
• u ∈ Cm : The auxiliary variable.
• F̃ ∈ Ck×m : A dual frame to the frame E, i.e. F̃ E = Ik .
• E : The reconstruction error E = kx − F̃ qk2 .
• R: Total bits used to record the quantized sample.
• Ω ∈ Ck×k : A Hermitian matrix with eigenvalues {λj }kj=1 and corresponding orthonormal eigenvectors {vj }kj=1 .
• φ0 ∈ Ck : A base vector in Ck .
• Φ∗ ∈ Cm×k : The unitarily generated frame (UGF) with the generator Ω and the base
vector φ0 .
3. Alternative Decimation Operator D̄ρ S̄ρ
We have mentioned that decimation consists of two steps: Integration and down-sampling.
Since both are linear transformations, it is natural to consider the following operators:
Pρ
1
• Sρ ∈ Rm×m is the integration operator defined by (Sρ u)i = 2ρ+1
j=−ρ ui+j where we
adopt the convention that u−n := um−n , n ∈ N.
• Dρ ∈ Rp×m is the sub-sampling matrix which has value 1 on entries (i, 1 + (2ρ + 1)(i −
1)), 1 ≤ i ≤ p, and zero otherwise. Note that p = bm/(2ρ + 1)c is chosen so that
p ≥ k. This means (2ρ + 1) ≤ m/k.
This formulation seems like a harmless translation from bandlimited functions to finite
frames. However, one distinction between the two frameworks is that A/D conversion inherently works on an infinite-dimensional space and in turn an infinite number of samples,
while finite frames only deal with finite-dimensional vectors.

ANALYSIS OF DECIMATION ON FINITE FRAMES WITH SIGMA-DELTA QUANTIZATION

7

As such, when we consider Sρ ∆, instead of complete cancellations as in the bandlimited
function case, the last column will carry ρ non-zero entries, thereby creating unnecessary
terms. Thus, during the down-sampling step of decimation, extra care needs to be taken
for the residual terms. To avoid such an issue, we introduce a similar procedure which is
intuitively clearer and ultimately yields the same result. Instead of taking averages for each
entry, a similar alternative method will be employed, which we call alternative decimation.
Definition 3.1 (Alternative Decimation). Given fixed m, ρ ∈ N, the alternative decimation
operator is defined to be D̄ρ S̄ρ , where
• S̄ρ = Sρ+ − Sρ− ∈ Rm×m is the integration operator satisfying
 1
if l ≥ ρ, l − ρ − 1 ≤ j ≤ l
+
ρ
(Sρ )l,j =
0 otherwise,
 1
if l ≤ ρ − 1, l + 1 ≤ j ≤ m − ρ + l
ρ
(Sρ− )l,j =
0 otherwise, and
• D̄ρ ∈ Np×m is the sub-sampling operator satisfying

1 if j = ρ · l
(D̄ρ )l,j =
0 otherwise,
where p = bm/ρc.
Remark 3.2. Visually, both Sρ+ and Sρ− contain a parallelogram. The one in Sρ+ has height
m − ρ + 1 and width ρ while the one for Sρ− has height ρ − 1 and width m − ρ:


0 −1 . . . . . . −1 0
.. ..
..

. 
.
.



−1 . . . . . . −1 0



1 . . . . . . 1

1
.
.
.
(7)
Sρ = 
.
.

.
.
ρ




..
..
.
.




.
.

..
.. 
1

... ... 1

Remark 3.3. Symmetric integrations are employed in A/D conversion, but it is not necessary in finite frames. We are thus able to go from summing over an odd number of entries
to any number, and this proves to be beneficial as the estimate is better for the case ρ|m.
Despite its seemingly unintuitive construction, the alternative decimation operator is the
natural one to choose in the sense that it is compatible with Σ∆ quantization, preserving
its differencing structure.
¯ ρ where
Lemma 3.4. S̄ρ = Sρ+ − Sρ− satisfies S¯ρ ∆ = ρ1 ∆


δ(j − l) − δ (ρ + j − l) mod m if j =
6 m,
¯
(8)
(∆ρ )l,j =
δ(j − l)
if j = m,
and δ is the Kronecker delta.

8

KUNG-CHING LIN

Proof. Note that
−1

(9)



(∆ )l,j =

1 if l ≥ j,
0 otherwise,

and
1¯
1 ¯ −1
¯
S¯ρ ∆ = ∆
ρ ⇐⇒ Sρ = ∆ρ ∆ .
ρ
ρ

(10)
Now, compute
¯ ρ ∆−1 )l,j =
ρ · (∆
(11)
=

X
j≤t≤m−1

X
j≤t≤m


(δ(t − l) − δ (ρ + t − l) mod m ) + δ(j − m)

δ(t − l) −

X

(δ(ρ + t − l) + δ(ρ + t − l − m)).

j≤t≤m−1

By definition,
 P
= 1 if j ≤ l
 Pj≤t≤m δ(t − l)
δ(ρ + t − l)
= 1 if l ≥ ρ + 1, j ≤ l − ρ
(12)
 Pj≤t≤m−1
j≤t≤m−1 δ(ρ + t − l − m) = 1 if l ≤ ρ − 1, j ≤ m − ρ + l.

Thus, splitting into l ≤ ρ − 1, l = ρ, and l ≥ ρ + 1, we see that
1 ¯ −1
(13)
∆ρ ∆ = Sρ+ − Sρ− ,
ρ
as claimed.



Remark 3.5. If S̃ρ is the circulant matrix extended from the lower part of S̄ρ , then D̄ρ S̃ρ =
D̄ρ S̄ρ . Thus, alternative decimation is essentially the same as the natural decimation.
As a frame-theoretic problem, there are two questions that should be answered in the
following order:
(1) Given a signal x ∈ Ck and a frame E ∈ Cm×k , can we reconstruct the signal x from
its down-sampled data D̄ρ S̄ρ Ex? That is, is D̄ρ S̄ρ E a frame?
(2) If D̄ρ S̄ρ E is indeed a frame, let F be the canonical dual of D̄ρ S̄ρ E. What is the
reconstruction error kx − F (D̄ρ S̄ρ q)k2 ?
4. Main Results
It will be shown that, for unitarily generated frames Φ∗ ∈ Cm×k satisfying conditions
specified in Theorem 4.4, Σ∆ quantization coupled with alternative decimation still has
linear error decay with respect to the ratio m/k, while the constant only increases by a
factor of π/2. On the other hand, decimation allows for efficient storage of data, making the
error decay exponentially with respect to the bits used. For the rest of the paper, we shall
also assume that our Σ∆ quantization scheme is stable, i.e. kuk∞ remains bounded as the
dimension m → ∞. We shall start with results on harmonic frames.
Definition 4.1 (Frame variation). Given F = (F1 , . . . , Fp ) ∈ Cs×p , the frame variation σ(F )
is defined to be
p−1
X
σ(F ) =
kFt − Ft+1 k2 .
t=1

ANALYSIS OF DECIMATION ON FINITE FRAMES WITH SIGMA-DELTA QUANTIZATION

9

Theorem 4.2 (Special case: Decimation for harmonic frames). Given the frame E = Em,k ∈
Cm×k with entries El,j = √1k exp(−2πı(nj l)/m) and suppose {nl }kl=1 are distinct integers in
[−k/2, k/2], then the following statements are true:
(a) Signal reconstruction: The matrix D̄ρ S̄ρ E is a frame.
(b) Error estimate: The choice of the dual frame F̃ = (D̄ρ S̄ρ E)† D̄ρ S̄ρ to E gives reconstruction error
kx − F̃ qk2 ≤

(14)

π
(σ(F̄ ) + kF̄p k2 )kuk∞ ,
2ρ

where F̄ = (F̄1 , . . . , F̄p ) is the canonical dual of the down-sampled matrix
( √1k e−2πıρlnj /m )l,j .
Moreover, if ρ | m, then
(
(15) E := kx − F̃ qk2 ≤

π 2 (k+1)
k
√
kuk∞ m
3
k
π 2π(k+1)
( √3 + 1)kuk∞ m
2

if m, k are even and nj ’s are nonzero,
otherwise.

In particular, the error decays linearly with respect to the oversampling rate m/k.
(c) Efficient data storage: Suppose the length of the quantization alphabet A is 2L,
then the decimated samples D̄ρ S̄ρ q can be encoded by a total of R = 2bm/ρc log(2Lρ) =
2p log(2Lρ) bits. Furthermore, suppose m/ρ = p is fixed as m → ∞, then as a function of total bits, the reconstruction error is
(16)

E (R) ≤ CF,L,p kuk∞ 2− 2p R ,
1

(2)

where CF,L ≤ πL(σ(F (2) ) + kFp k).
For ρ | m, we have a better estimate
(17)

E (R) ≤ Ck,L,p kuk∞ 2− 2p R ,
1

√
+ 1), independent of m. The optimal exponent
where Ck,L ≤ πkL
( 2π(k+1)
p
3
achieved in the case ρ = m/k ∈ N.

1
2k

will be

Remark 4.3. For the usual Σ∆ quantization without decimation, i.e. , ρ = 1, the reconk
√
struction error satisfies E ≤ ( 2π(k+1)
+ 1)kuk∞ m
. Comparing it with (15), we see that indeed
3
the error estimate only grows by a factor of π/2.
The more general result is as follows:
Theorem 4.4 (Decimation for Unitarily Generated Frames (UGF)). Given Ω, φ0 , {λj }j ,
{vj }j , and Φ∗ = Φ∗m,k as the generator, base vector, eigenvalues, eigenvectors, and the corresponding UGF, respectively, suppose
• {λj }kj=1 are concentrated between [−m/(2ρ), m/(2ρ)],
• {λj − λl }j6=l are nonzero integers,
• Cφ0 = mins |<φ0 .vs >|2 > 0, and
• ρ | m,
then the following statements are true:
(a) Signal reconstruction: D̄ρ S̄ρ Φ∗m,k is a frame.

10

KUNG-CHING LIN

(b) Error estimate: For the dual frame F̃ = (D̄ρ S̄ρ Φ∗m,k )† D̄ρ S̄ρ , the reconstruction error
Em,ρ satisfies
π
(2π max |λj | + 1)kuk∞ .
(18)
Em,ρ ≤
1≤j≤k
2mCφ0
(c) Efficient data storage: Suppose the length of the quantization alphabet is 2L, then
the total bits used to record the quantized samples are R = 2p log(2Lρ) bits. Furthermore, suppose m/ρ = p is fixed as m → ∞, then as a function of bits used at each
entry, Em,ρ satisfies
E (R) ≤ Ck,φ0 ,L,p kuk∞ 2− 2p R ,
1

(19)
where Ck,φ0 ,L,p =

πL
(2π
pCφ0

max1≤j≤k |λj | + 1), independent of m.

Remark 4.5. For both Theorem 4.2 and 4.4, if both the signal and the frame are real, then
the total bits used will be R = p log(2Lρ) bits, half the amount needed for the complex case.
Remark 4.6. Harmonic frames are unitarily generated frames with the generator
Ω being
√
the diagonal matrix with entries {nj } and the base vector φ0 = (1, . . . , 1)t / k, so Theorem
4.2 is truly a special case of Theorem 4.4. In this case, Cφ0 = 1/k
√ and max |λj | ≤ k.
The estimate (18) is worse than the one given in (15) by a factor of 3 due to the lack of
knowledge on the actual distribution of {|<φ0 , vj >|}, which is the difference between Lemma
5.8 and Proposition 6.2.
One additional property of decimation is its multiplicative structure.
Definition 4.7. Given m0 , ρ0 ∈ N such that kρ0 ≤ m0 , the decimation operator of order ρ0
is defined to be D̄ρ0 ,m0 S̄ρ0 ,m0 where
D̄ρ0 ,m0 ∈ Nbm0 /ρ0 c×m0 ,

S̄ρ0 ,m0 ∈ Rm0 ×m0 .

Theorem 4.8 (The Multiplicative Structure of Decimation Schemes). Suppose ρ | m and
ρ = ρ1 ρ2 , then the decimation of order ρ is equal to the successive iterations of decimation
of order ρ1 coupled by the one of order ρ2 in the sense that the corresponding canonical dual
frames and reconstruction errors are the same.
To provide motivations, Theorem 4.2 will be proven separately in Section 5 even though
it is essentially a special case of Theorem 4.4. The proof of Theorem 4.4 will be given in
Section 6, and Theorem 4.8 will be proven in Section 7.
5. Decimation for Finite Harmonic Frames
5.1. The Scaling Effect of Decimation. Let E = (el,j )l,j = ( √1k exp(−2πı(nj l)/m))l,j =
Em,k be a harmonic frame. For any ρ ≤ m, we have the following lemma:
Lemma 5.1. S̄ρ and E satisfy

S̄ρ E = E C̄
if nj 6= 0 ∀j
(20)
S̄ρ E = E C̄ − K if nj0 = 0 for some j0 ,
where C̄ ∈ Ck×k is a diagonal matrix with entries
(
sin(ρn π/m)
eπı(ρ−1)nj /m ρ sin(njj π/m) if nj =
6 0
(21)
C̄j,j =
1
if nj = 0,

ANALYSIS OF DECIMATION ON FINITE FRAMES WITH SIGMA-DELTA QUANTIZATION

11

and K is zero except for the j0 -th column, having


Kl,j0 =

√
m/(ρ k) if 1 ≤ l ≤ ρ − 1
0
otherwise.

In either case D̄ρ S̄ρ E = D̄ρ E C̄ as D̄ρ K = 0.
Remark 5.2. In (7), one observes that Sρ looks like a circulant matrix, with the exception
on the first ρ − 1 rows. On the other hand, Sρ differs from an actual circulant matrix by a
matrix L with 1/ρ on every
P entry of the first ρ − 1 rows and zero otherwise. Given a column
ej of Em,k , if it satisfies m
s=1 es,j = 0, then Lej = 0. It is true for all columns of Em,k except
possibly when nj = 0.
Proof. We start with the computation on ρ ≤ l ≤ m. First, suppose nj 6= 0. Then

(Sρ+ E)ρ,j

ρ
1 X
= √
exp(−2πınj s/m)
ρ k s=1

eπı(ρ−1)nj /m (1 − e−2πıρnj /m) )
1
= √ e−πı(ρ+1)nj /m
1 − exp(−2πınj /m)
ρ k
1
sin(ρnj π/m)
.
= √ e−πı(ρ+1)nj /m
ρ sin(nj π/m)
k

For ρ ≤ l ≤ m,
(S¯ρ E)l,j = (Sρ+ E)l,j = (Sρ+ E)ρ,j exp(−2πı(l − ρ)nj /m)
(22)

1
sin(ρnj π/m)
= √ eπı(ρ−1)nj /m
exp(−2πılnj /m)
sin(nj π/m)
ρ k
sin(ρnj π/m)
= eπı(ρ−1)nj /m
El,j .
ρ sin(nj π/m)

If nj = 0, then (Sρ+ E)l,j = √1k = El,j .
For l ≤ ρ, we make the following observation:

(23)

(S̄ρ )l,j +

1
= (S̄ρ )l+ρ,j+ρ ,
ρ

12

KUNG-CHING LIN

with the modulo convention on indices. Then for l ≤ ρ − 1, noting that exp(−2πınj (s +
m)/m) = exp(−2πınj s/m),
(S̄ρ E)l,j =

m
X

(S̄ρ )l,s Es,j

s=1

=
(24)

=

m
X

m

(S̄ρ )l+ρ,s+ρ Es,j

s=1
m
X

1X
−
Es,j
ρ s=1

m
(S̄ρ )l+ρ,s+ρ Es+ρ,j exp(2πıρnj /m) − √ δ(nj )
ρ k
s=1

sin(ρnj π/m)
m
El+ρ,j e2πıρnj /m − √ δ(nj )
ρ sin(nj π/m)
ρ k
m
sin(ρnj π/m)
= eπı(ρ−1)nj /m
El,j − √ δ(nj ).
ρ sin(nj π/m)
ρ k
= eπı(ρ−1)nj /m


Now we can give the condition for D̄ρ S̄ρ E to be a frame.
Proposition 5.3. The following statements are equivalent:
• D̄ρ S̄ρ E is a frame.
• {ρnj }kj=1 are distinct residues modulo m, and ρnj = 0 modulo m implies nj = 0.
Proof. By Lemma 5.1, we see that
 

Eρ
E1
E2ρ 
 E2 
 

D̄ρ S̄ρ E = D̄ρ E C̄ = D 
 ...  C̄ =  ...  C̄.
Epρ
Em


(25)

D̄ρ E is a sub-matrix of a Vandermonde matrix with parameters {exp(−2πıρnj /m)}kj=1 . Thus
this matrix has full-rank if and only if {ρnj }kj=1 are distinct modulo m. On the other hand,
C̄ is an invertible diagonal matrix if and only if C̄j,j 6= 0. It is true when ρnj 6= 0 for all j
except if nj = 0 to begin with.

Remark 5.4. |{−bp/2c, . . . , bp/2c}| ≥ p, and if {nj }kj=1 ⊂ {−bp/2c, . . . , bp/2c} are distinct
residues modulo m, then {ρnj }j are distinct since elements of {−bp/2c, . . . , bp/2c} are in
different cosets of (Z/mZ)/ker(σ) where σ : Z/mZ → Z/mZ satisfies σ(x) = ρx.
To this point, we have found the constraints for D̄ρ S̄ρ E to be a frame, and when ρ | m,
we have an explicit form for its dual frame. If ρ - m, then the situation is murkier since D̄ρ E
will no longer be a group frame:
• kρ = p · ρ = m:
Suppose that D̄ρ S̄ρ E is a frame, then D̄ρ Em,k = Ek,k is, up to permutation of
columns, a multiple of discrete Fourier transform (DFT) matrix. In this case, its
∗
canonical dual frame is simply Ek,k
.

ANALYSIS OF DECIMATION ON FINITE FRAMES WITH SIGMA-DELTA QUANTIZATION

13

m
:
ρ

• ρ | m, i.e. p =
With the same assumption, we see that D̄ρ Em,k = Em/ρ,k is a harmonic frame.
Then its canonical dual is kρ
since
E∗
m m/ρ,k
m
∗
(26)
Em/ρ,k
Em/ρ,k =
Ik .
kρ
• (ρ, m) = 1:
In this case, any distinct {nj }j will make D̄ρ S̄ρ E a frame.
• (ρ, m) = s > 1:
In this case, simply let ρ̃ = ρ/s, m̃ = m/s, then (ρ̃, m̃) = 1 again.
5.2. Estimation on kC̄ −1 k2 . By Lemma 5.1, D̄ρ S̄ρ E = D̄ρ E C̄. Thus for any dual F of
such matrix, F = C̄ −1 F̄ where F̄ is a dual frame of D̄ρ E. This section gives an estimate on
kC̄ −1 k2 .
Proposition 5.5. If {nj }kj=1 are concentrated in [−m/(2ρ), m/(2ρ)] in Z/mZ, then
π
kC̄ −1 k2 ≤ .
2
We need a lemma for this proposition:
Lemma 5.6. Given any number α ≥ 1, the function
sin(αx)
h(x) = hα (x) =
α sin(x)
π
is even and strictly decreasing in (0, π/(2α)). Moreover, hα ( 2α
) ≥ π2 .

Proof. Given any α ≥ 1, note that limx→0 h(x) = 1. Taking the derivative of h, we have
(27)



cos(αx) cos(x)
α cos(αx) sin(x) − sin(αx) cos(x)
=
α tan(x) − tan(αx) .
h (x) =
α2 sin2 (x)
α2 sin2 (x)
0

The first fractal is even and positive in (0, π/(2α)), while the second term α tan(x) − tan(αx)
is found to be odd and decreasing in (0, π/(2α)) by taking yet another derivative. Thus, the
derivative of h is odd and negative in (0, π/(2α)]. That is, on Iα = [−π/(2α), π/(2α)], h
achieves global maximum at x = 0 and minimum at x = π/(2α). At the minimum point,
 
π
1
2
hα
=
≥
2α
α sin(π/(2α))
π
by noting that sin(z) ≤ z for any z ∈ R.



Proof. of Proposition 5.5:
By (21), we see that
1 sin(ρnl π/m)
ρ sin(nl π/m)
with the convention that sin(ρ · 0)/(ρ sin(0)) = 1. Thus,

−1

sin(ρnl π/m)
−1
−1
kC̄ k2 = max |C̄(l)|
= min {
}
.
1≤l≤k
1≤l≤k ρ sin(nl π/m)
|C̄l,l | =

Using the result from Lemma 5.6 with α = ρ ≥ 1, we see that kC̄ −1 k2 ≤ π2 .



14

KUNG-CHING LIN

By Remark 5.4, such the choice of {nj }kj=1 will guarantee that D̄ρ Sρ E is a frame.
Remark 5.7. With a similar estimate, we actually see that for {nj } concentrated between
[−c, c] where c < m/ρ, we have kC̄ −1 k2 ≤ π/(2 sin(cρπ/m)).
5.3. Proof of Theorem 4.2. Before proving Theorem 4.2, we still need two more lemmas:
∗
Lemma 5.8. For any n ≥ k, En,k
, suppose {nj }j are concentrated between [−k/2, k/2], then
2π(k+1)
it has frame variation σ(E) ≤ √3 .

Proof.
∗
σ(En,k
)

n−1 k
1 X X −2πılnj /n
(
|e
− e−2πı(l+1)nj /n |2 )1/2
=√
k l=1 j=1
n−1 k
1 XX
=√
(
|1 − e2πınj /n |)1/2
k l=1 j=1
n−1 k
1 XX
( (2πnj /n)2 )1/2
≤√
k l=1 j=1
k/2
1
n − 1 X 2 1/2
(
nj )
≤ √ 2π
n
k
j=−k/2
r
1
k/2(k/2 + 1)(k + 1)
≤ √ 2π 2 ·
3
k
2π(k + 1)
√
≤
.
3


Lemma 5.9 ([1], Theorem III.7). Given a stable Σ∆ quantization scheme with the choice of
mid-rise uniform quantizer of gap δ, if the frame F = {ej }m
j=1 satisfies the zero sum condition
m
X

ej = 0,

j=1

then the auxiliary variable um has

|um | =

0,
if m even,
δ/2, if m odd.

Now we are ready to give the proof of Theorem 4.2.
Proof. of Theorem 4.2:
Adopting the notations above, we see that the reconstruction error is
(28)

kx − F (D̄ρ S̄ρ q)k2 = kF (D̄ρ S̄ρ )(y − q)k2

= kF D̄ρ S̄ρ ∆uk2
¯ ρ uk2 ≤ kC̄ −1 k2 kF̄ D̄ρ ∆
¯ ρ uk2 ,
= kF D̄ρ ∆

ANALYSIS OF DECIMATION ON FINITE FRAMES WITH SIGMA-DELTA QUANTIZATION

15

where the second equality comes from (4) and that F̃ = C̄ −1 F̄ with F̄ being the canonical
dual frame to D̄ρ Em,k . For clarity, we denote ∆(j) as the j-by-j backward difference matrix.
Observe that
1
(29)
D̄ρ S̄ρ ∆(m) u = ∆(p) u(p) ,
ρ
where u(p) = (uρ , . . . , upρ )t . Suppose F̄ = (F̄1 , · · · , F̄p ), then
(30)

p−1

1
1 X
(p) (p)
¯
F̄ D̄ρ ∆ρ u = F̄ ∆ u =
(F̄s − F̄s+1 )usρ + F̄p upρ .
ρ
ρ s=1

By Proposition 5.5 and (30),
¯ ρ uk2 ≤ π (σ(F̄ ) + kF̄p k)kuk∞ .
kC̄ −1 k2 kF̄ D̄ρ ∆
2ρ
For the case ρ | m, we have, by Lemma 5.8 and (26),

(31)

k 2π(k + 1)
( √
+ 1).
m/ρ
3
Thus, we have obtained the following error bound
k π 2π(k + 1)
π 2π(k + 1)
k
( √
(32) Eρ = kx − F (D̄ρ S̄ρ q)k2 ≤
+ 1)kuk∞ = ( √
+ 1)kuk∞ .
m/ρ 2ρ
2
m
3
3
Furthermore, by Lemma 5.9, if m, k are even, nj ’s are all nonzero, and ρ | m, then upρ =
um = 0. With that there is a better estimate
k π 2π(k + 1)
π 2 (k + 1) k
√
√
(33)
Eρ = kx − F (D̄ρ S̄ρ q)k2 ≤
kuk∞ .
kuk∞ =
m/ρ 2ρ
m
3
3
σ(F̄ ) + kF̄m/ρ k ≤

Letting F̃ = F D̄ρ S̄ρ , the first statement of Theorem 4.2 is now proven.
For the second assertion of the theorem, note that for mid-rise uniform quantizers A =
A0 + ıA0 with length 2L, each entry qj of q is a number of the form
δ
qj = (2sj + 1) + ı(2tj + 1) , −L ≤ sj , tj ≤ L − 1.
2
Then, each entry in D̄ρ S̄ρ q is the average of ρ entries in q, which has the form
δ
(D̄ρ S̄ρ q)j = (2s̃j + ρ) + ı(2t̃j + ρ)
, −Lρ ≤ s̃j , t̃j ≤ (L − 1)ρ.
2ρ
There are at most ((2L − 1)ρ + 1)2 ≤ (2Lρ)2 choices per entry and p = bm/ρc entries in
total. so the vector D̄ρ S̄ρ q can be encoded by R = 2p log(2Lρ) bits. Noting that m1 ≤ p1 · ρ1
and
1
1
e− 2p R =
,
2Lρ
then for any estimate we have
1
11
2L 1
E ≤C ≤C
= C e− 2p R ,
m
pρ
p
for some C > 0. Substituting the suitable constant for each case, we have
(34)

E (R) ≤ CF,L kuk∞ 2− 2p R ,
1

16

KUNG-CHING LIN

where CF,L ≤ πL(σ(F̄ ) + kF̄p k). If ρ | m, then by (32), (33),
E (R) ≤ Ck,L kuk∞ 2− 2p R ,
1

(35)
where Ck,L ≤

πkL 2π(k+1)
( √3
p

+ 1), independent of m.



6. Generalization: Decimation on Unitarily Generated Frames
There are two features of decimation on harmonic frames that result in exponential decay
for the reconstruction error:
• Commutativity: D̄ρ S̄ρ Em,k = Em/ρ,k C̄m,ρ .
• Scalability: D̄ρ S̄ρ ∆(m) u = ρ1 ∆(p) u(p) .
Fixing the Σ∆ quantization scheme for now, for any family of frames satisfying the commutativity condition, the decimation will give similar results, which is exponential decay with
optimal exponents. One immediate example is the unitarily generated frames.
Given a Hermitian matrix Ω ∈ Ck×k and a base vector φ0 ∈ Ck , we consider the operator
path and its generated frame elements
(m)

Ut := e2πıΩt ,

φj

(m)

= Uj/m φ0 .

(m)

(m)

The collection of such elements Φm,k = (φ1 | φ2 | . . . |φm ) ∈ Cm×k is the frame of interest.
Lemma 6.1. For the same D̄ρ and S̄ρ along with Φ generated by (Ω, {λj }kj=1 , φ0 ),
(m) 
(φρ )∗
(φ(m) )∗ 


=  2ρ.  C̄m,ρ ,
 .. 



D̄ρ S̄ρ Φ∗m,k

(36)

(m)

(φpρ )∗
where p = bm/ρc and C̄m,ρ =

the convention that

sin(ρ·0π/m)
ρ sin(0π/m)

sin(ρλ π/m)

Pρ

s=1

j
∗
U(s−ρ)/m
has eigenvalues {eπı(ρ−1)λj /m ρ sin(λπ/m)
}j with

= 1. In particular, if ρ | m, then
D̄ρ S̄ρ Φ∗m,k = Φ∗m/ρ,k C̄m,ρ .

Proof. First, consider the ρ-th row of S̄ρ Φ∗m,k :
(S̄ρ Φ∗m,k )ρ
(37)

 X
∗
ρ
1
=
Us/m φ0
ρ s=1
 X
∗
ρ
1
U(s−ρ)/m φρ
=
ρ s=1
ρ

= φ∗ρ

ρ


1X ∗
1X ∗
U(s−ρ)/m = (Φ∗m,k )ρ ·
U
.
ρ s=1
ρ s=1 (s−ρ)/m

ANALYSIS OF DECIMATION ON FINITE FRAMES WITH SIGMA-DELTA QUANTIZATION

17

As for the t · ρ-th row, 1 ≤ t ≤ p,

(S̄ρ Φ∗m,k )tρ


=

1
ρ

tρ
X

∗
Us/m φ0

s=(t−1)ρ+1
ρ

1X ∗
= (U(t−1)ρ/m φρ ) ·
U
ρ s=1 (s−ρ)/m
∗

(38)

ρ

=

(Φ∗m,k )tρ

1X ∗
·
U
.
ρ s=1 (s−ρ)/m

Since, by construction, D̄ρ only takes the t · ρ-th rows of S̄ρ Φ∗ , (36) is satisfied.
Note that we can diagonalize Ut = BTt B ∗ where B is a unitary
and Tt is a
Pρ matrix
1
∗
2πıλj t k
∗
diagonal matrix with entries {e
}j=1 . Then, B C̄m,ρ B = ρ s=1 (B U(s−ρ)/m B)∗ is a
diagonal matrix, with entries

ρ

∗

(B C̄m,ρ B )j,j
(39)

1X
s−ρ
exp(−2πı
λj )
=
ρ s=1
m
λj (ρ−1) e−2πıρλj /m − 1
1
πı(ρ−1)λj /m sin ρλj π/m
= e2πı m
=
e
.
ρ
ρ sin(λj π/m)
e−2πıλj /m − 1



Now, we can find the conditions under which D̄ρ S̄ρ Φ∗m,k is a frame:
Proposition 6.2. Let {vs }ks=1 be a set of orthonormal eigenvectors of Ω with eigenvalues
{λs }ks=1 . Suppose
• ρ | m,
• {ρ(λs − λt )}ts=1 are nonzero
integers modulo m, and
P
• the base vector φ0 = s cs vs satisfies cs 6= 0 for all s,
then Φ∗m,(m/ρ) is a frame with frame bounds






m/ρ
X
m
m
2
2
(m)
2
2
min |cs | kxk2 ≤
|<x, φsρ >| ≤
max |cs | kxk22 .
s
ρ s
ρ
s=1

18

KUNG-CHING LIN

Proof. Suppose the assumptions above are true, then given an arbitrary x ∈ Ck ,
m/ρ
X
s=1

2
|<x, φ(m)
sρ >|

m/ρ
k
X
X
2
|
<x, vt ><vt , φ(m)
=
sρ >|
s=1

t=1

m/ρ

k
X X
=
|
<x, vt ><U−sρ/m vt , φ0 >|2
s=1

t=1

m/ρ
k
X
X
=
|
e−2πısρλt /m <x, vt ><vs , φ0 >|2
s=1

=

k
X

t=1

<x, vj ><x, vl ><vj , ρ><vl , φ0 >

=

m
ρ

j=1

e−2πısρ(λj −λl )/m

s=1

j,l=1
k
X

m/ρ
X

|<x, vj >|2 |<vj , φ0 >|2 ,

where the second equality follows from the fact that Ut is unitary, the fourth by expanding
the sums, and the last one from the following equality
 m
m/ρ
X
if j 6= l
ρ
exp(−2πısρ(λj − λl )/m) =
0 if j = l.
s=1

Finally, we have




k
m
m
mX
2
2
2
2
2
min |cs | kxk2 ≤
|<x, vj >| |<vj , φ0 >| ≤
max |cs | kxk22 .
ρ s
ρ j=1
ρ s

−1
Moreover, with the same proof in Proposition 5.5, we have the estimate on kC̄m,ρ
k2 :

Proposition 6.3. If the eigenvalues {λj }kj=1 of the generator Ω are concentrated between
[−m/(2ρ), m/(2ρ)], then
(
)
−1
π
sin(ρλj π/m)
−1
−1
≤ .
kC̄m,ρ
k2 = kB ∗ C̄m,ρ
Bk2 = max
1≤j≤k
ρ sin(λj π/m)
2
Now we are ready to prove Theorem 4.4.
Proof. of Theorem 4.4.
First of all, that D̄ρ S̄ρ Φ∗m,k = Φ∗m/ρ,k is a frame follows from Proposition 6.2 and 6.3. For
notational clarity, we shall denote Φ∗m/ρ,k = Φ∗m/ρ .
−1
Let Φm/ρ Φ∗m/ρ = Sm/ρ be the corresponding frame operator, then kSm/ρ
k2 ≤ ρ/(mCφ0 )
2
where Cφ0 := mins |cs | . Also, note that
1 −1
−1
Sm/ρ
Φm/ρ (D̄ρ S̄ρ )∆(m) u = Sm/ρ
(Φm/ρ ∆(m/ρ) )u(m/ρ) ,
ρ

ANALYSIS OF DECIMATION ON FINITE FRAMES WITH SIGMA-DELTA QUANTIZATION

with the same notation as in (29). Then, the reconstruction error
is

19

−1 −1
kx−C̄m,ρ
Sm/ρ Φm/ρ (D̄ρ S̄ρ )qk2

−1 −1
−1 −1
kx − C̄m,ρ
Sm/ρ Φm/ρ (D̄ρ S̄ρ )qk2 = kC̄m,ρ
Sm/ρ Φm/ρ (D̄ρ S̄ρ )∆(m) uk2

1 −1
−1
≤ kC̄m,ρ
k2 kSm/ρ
k2 (σ(Φm/ρ ) + kφm k2 )ku(m/ρ) k∞
ρ
π 1
(σ(Φm/ρ ) + kφ(m)
≤
m k2 )kuk∞ ,
2 mCφ0

(40)

−1
k2 ≤ π/2 by Proposition 6.3.
where kC̄m,ρ
Now, to compute σ(Φm/ρ ), we see
m/ρ
X
s=1

kφ(m/ρ)
s

−

(m/ρ)
φs+1 k2

=

m/ρ
X
s=1

kUsρ/m (I − Uρ/m )φ0 k2

m/ρ−1

=

X
s=1

k(I − Uρ/m )φ0 k2

m/ρ−1

=

X
s=1

k

k
X
j=1

cj (1 − e2πıλj ρ/m )vj k2

m/ρ−1

k
X X
=
(
|cj |2 |e2πıλj ρ/m − 1|2 )1/2

(41)

s=1

j=1

m/ρ−1 

≤

X

k
X

s=1

ρ 2
|cj | · 2π|λj |
m
j=1
2

m/ρ−1

≤

X
s=1

max 2π|λj |

1≤j≤k

1/2

ρ
· kφ0 k2
m

≤ 2π max |λj | · kφ0 k2 .
1≤j≤k

(m)

Combining (40), (41), and the fact that kφm k2 = kU1 φ0 k2 = kφ0 k2 , the reconstruction
error Em,ρ can be bounded by
(42)

Em,ρ ≤

π 1
π kφ0 k2
(σ(Φm/ρ ) + kφ(m)
(2π · max |λj | + 1)kuk∞ .
m k2 )kuk∞ ≤
1≤j≤k
2 mCφ0
2 mCφ0

The second assertion of Theorem 4.4 follows verbatim from the proof in Theorem 4.2.
7. The Multiplicative Structure of Decimation Schemes
Proof. of Theorem 4.8:
Given m, ρ, ρ1 , ρ2 ∈ N fixed with ρ = ρ1 ρ2 and ρ | m, consider the following operators:
D̄ρ ∈ N(m/ρ)×m ,
S̄ρ ∈ Rm×m ,
(m/ρ1 )×m
D̄ρ1 ∈ N
,
S̄ρ1 ∈ Rm×m ,
D̄ρ2 ∈ N(m/ρ)×(m/ρ1 ) , S̄ρ2 ∈ R(m/ρ1 )×(m/ρ1 ) .



20

KUNG-CHING LIN

The decimation operator of order ρ is D̄ρ S̄ρ while the successive iterations of decimation of
order ρ1 and ρ2 combine to be D̄ρ2 S̄ρ2 D̄ρ1 S̄ρ1 . In order to prove Theorem 4.8, we need to
show that given a unitarily generated frame Φ∗m,k satisfying the conditions stated in Theorem
4.4, we have
• Same frame: D̄ρ S̄ρ Φ∗m,k = D̄ρ2 S̄ρ2 D̄ρ1 S̄ρ1 Φ∗m,k , and
• Same reconstruction error: Given the same dual frame F ∈ Ck×(m/ρ) ,
kx − F D̄ρ S̄ρ qk2 = kx − F D̄ρ2 S̄ρ2 D̄ρ1 S̄ρ1 qk2 .

For the first assertion, we see in Lemma 6.1 that if ρ | m, then for any ρ = ρ1 ρ2 , D̄ρ1 Φ∗m,k =
Φ∗m/ρ1 ,k is still a unitarily generated frame. Moreover,
(43)

D̄ρ2 S̄ρ2 D̄ρ1 S̄ρ1 Φ∗m,k = D̄ρ2 S̄ρ2 Φ∗m/ρ1 ,k C̄m,ρ1 = Φ∗m/ρ,k C̄m/ρ1 ,ρ2 C̄m,ρ1 ,

where C̄m/ρ1 ,m/ρ and C̄m,ρ1 are simultaneously diagonalizable by B with eigenvalues
sin(ρ1 nj /m) πı(ρ2 −1)nj /(m/ρ1 ) sin(ρ2 ρ1 nj /m)
e
ρ1 sin(nj /m)
ρ2 sin(ρ1 nj /m)
sin(ρnj /m)
nj πı
=
exp(
(ρ2 ρ1 − ρ1 + ρ1 − 1))
ρ sin(nj /m)
m
= (B C̄m,ρ B ∗ )j,j .

(B C̄m/ρ1 ,ρ2 C̄m,ρ1 B ∗ )j,j = eπı(ρ1 −1)nj /m
(44)

Thus, combining (43) and (44), we see that the multiplicative structure is also preserved
when ρ | m:
(45)

D̄ρ S̄ρ Φ∗m,k = Φ∗m/ρ,k C̄m,ρ = D̄ρ2 S̄ρ2 D̄ρ1 S̄ρ1 Φ∗m,k .

As for the second one, recall the observation in (29). Essentially it shows that the decimation
operator of order ρ transforms ∆(m) u into ρ1 ∆(m/ρ) u(m/ρ) . Splitting it into two iterations, we
see that
1
D̄ρ S̄ρ ∆(m) u = ∆(m/ρ) u(m/ρ)
ρ
(46)
1
= D̄ρ2 S̄ρ2 ∆(m/ρ1 ) u(m/ρ1 ) = D̄ρ2 S̄ρ2 D̄ρ1 S̄ρ1 ∆(m) u.
ρ1
Thus,
kx − F D̄ρ S̄ρ qk2 = kF D̄ρ S̄ρ ∆(m) uk2

= kF D̄ρ2 S̄ρ2 D̄ρ1 S̄ρ1 ∆(m) uk2 = kx − F D̄ρ2 S̄ρ2 D̄ρ1 S̄ρ1 qk2 .



Remark 7.1. Note that if ρ - m has ρ = ρ2 ρ1 where ρ1 | m, ρ2 - (m/ρ1 ), then (45) and
(46) still holds. For harmonic frames, it means that similar results extend to the case when
ρ - m. On the other hand, it is not clear whether D̄ρ S̄ρ Φ∗m,k is still a frame for ρ - m.
Such property implies the possibility to conduct decimation with multiple steps, gradually
down-sizing the dimension m to lower numbers without any penalty. It can be particularly
useful for parallel computation and transmission of data through multiple devices with scarce
storage resources. In particular, for each stage, it suffices to choose ρj to be a small number
dividing m. It reduces the waiting time between each transmission, and the amplification of
quantized sample q will not be large after each stage.

ANALYSIS OF DECIMATION ON FINITE FRAMES WITH SIGMA-DELTA QUANTIZATION

21

Moreover, although the case where ρ - m does not produce this structure for frames, it is
now possible to first reduce m to a number closer to k. Only at the last stage do we choose
ρ that does not divide m. This yields the same result as direct division m/k by the remark
above while possibly gaining sharper estimate on the error.
8. Acknowledgement
The author would like to thank the support from ARO Grant W911NF-17-1-0014 and J.
Benedetto for all the thoughtful advice and insights.
References
1. John J Benedetto, Alexander M Powell, and Ozgur Yilmaz, Sigma-delta quantization and finite frames,
IEEE Transactions on Information Theory 52 (2006), no. 5, 1990–2005.
2. James Blum, Mark Lammers, Alexander M Powell, and Özgür Yılmaz, Sobolev duals in frame theory
and sigma-delta quantization, Journal of Fourier Analysis and Applications 16 (2010), no. 3, 365–381.
3. James Candy, Decimation for sigma delta modulation, vol. 34, IEEE transactions on communications,
1986.
4. Evan Chou and C. Sinan Güntürk, Distributed noise-shaping quantization: Ii. classical frames, Excursions in Harmonic Analysis, Volume 5: The February Fourier Talks at the Norbert Wiener Center (2017),
no. 179-198.
5. Evan Chou and C.Sinan Güntürk, Distributed noise-shaping quantization: I. beta duals of finite frames
and near-optimal quantization of random measurements., Constructive Approximation 44 (2016), no. 1,
1–22.
6. Ingrid Daubechies and Ron DeVore, Approximating a bandlimited function using very coarsely quantized
data: A family of stable sigma-delta modulators of arbitrary order, Annals of mathematics 158 (2003),
no. 2, 679–710.
7. Ingrid Daubechies, Ronald A DeVore, C Sinan Gunturk, and Vinay A Vaishampayan, A/d conversion
with imperfect quantizers, IEEE Transactions on Information Theory 52 (2006), no. 3, 874–885.
8. Ingrid Daubechies and Rayan Saab, A deterministic analysis of decimation for sigma-delta quantization
of bandlimited functions, IEEE Signal Processing Letters 22 (2015), no. 11, 2093–2096.
9. Percy Deift, Felix Krahmer, and C Sınan Güntürk, An optimal family of exponentially accurate onebit sigma-delta quantization schemes, Communications on Pure and Applied Mathematics 64 (2011),
883–919.
10. Yonina C Eldar and Helmut Bolcskei, Geometrically uniform frames, IEEE Transactions on Information
Theory 49 (2003), no. 4, 993–1006.
11. G David Forney, Geometrically uniform codes, IEEE Transactions on Information Theory 37 (1991),
no. 5, 1241–1260.
12. C Sinan Güntürk, One-bit sigma-delta quantization with exponential accuracy, Communications on Pure
and Applied Mathematics 56 (2003), no. 11, 1608–1630.
13. Hiroshi Inose and Yasuhiko Yasuda, A unity bit coding method by negative feedback, Proceedings of the
IEEE 51 (1963), 1524–1535.
Norbert Wiener Center, Department of Mathematics, University of Maryland, College
Park, MD 20742, USA,, Tel. +1 301-405-5058; Fax. +1 301-314-0827
E-mail address: kclin@math.umd.edu

