# Localization Operators and an Uncertainty Principle for the Discrete Short Time Fourier Transform

Authors: Carmen Fernández; Antonio Galbis; Josep Martínez
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

Localization operators in the discrete setting are used to obtain information on a signalf from the knowledge on the support of its short time Fourier transform. In particular, the extremal functions of the uncertainty principle for the discrete short time Fourier transform are characterized and their connection with functions that generate a time-frequency basis is studied.


---

## Body

## 1. Introduction

It is a well-known fact that a nontrivial function and its Fourier transform cannot be simultaneously well localized, and many variants of this vague statement are collected under the termuncertainty principle. We refer to [1] and the references therein for different versions. For functions defined on finite abelian groups, localization is generally expressed in terms of the cardinality of the support of the function. For instance, Donoho and Stark [2] proved the following: given a finite sequence (xi)i=1d-1 with discrete Fourier transform (x^i)i=1d-1 let Nt and Nw be the cardinals of their supports, then
(1)Nt·Nw≥d.
Meshulam [3] obtained a generalization for nonabelian groups. Moreover, those x for which one has the equality were characterized (see [2, 4, 5]). When d is a prime number the result was improved by Tao [6], who showed that the sum of the number of nonzero entries in a finite sequence and the number of nonzero entries in its Fourier transform are strictly larger than d. An extension to abelian groups of finite order is given in [7].Results of this type for joint time-frequency representations in the continuous case are obtained in [8–13] among others, and for functions defined on finite abelian groups in [14], where it is proved that the cardinality of the support of any short time Fourier transform of a nontrivial function defined on a finite abelian group is bounded below by the order of the group. Ghobber and Jaming obtained in [15] an uncertainty principle for the representation of a vector in two bases, which permitted in particular to get a quantitative version of the above-mentioned result by Krahmer et al. [14]. In Theorem 1 we present a different proof of the quantitative result in [15] improving the constant there obtained.Our aim is to obtain information on a signalf from the knowledge on the support of its short time Fourier transform. To this end we introduce the localization operators in the discrete setting, which provide a filtered version of the original signal f. The importance of localization operators in this context is due to the fact that, for a given subset Λ of ℤd×ℤd,f=(fi)i=0d-1 is a fixed point of the localization operator LΛ,g with window g=(gi)i=0d-1 whenever Vgf is supported in Λ. In Theorem 3 we characterize those finite sequences f and g such that the cardinal of the support of Vgf is minimum; that is, we characterize the extremal functions of the uncertainty principle for the discrete short time Fourier transform.Additional relevant information about the functions can be derived from the support of the short time Fourier transform. For instance, it is easy to see that whenf and g are periodic, the short time Fourier transform Vgf is supported in a certain subgroup. We will see in Proposition 4 that a sort of converse also holds. Here again localization operators are used in the proof. In a recent paper, Gilbert and Rzeszotnik [16] calculated the norm of the Fourier transform from the Lp space on a finite abelian group to the Lq space on the dual group and they studied the points at which the norm is attained. In connection with this problem they consider the functions on the group such that the set of all their translations coincides (up to some constants) with the set of all their modulations and produce an orthonormal basis. In the case of cyclic groups, these functions are easily characterized (up to constants) by the support of Vff (Proposition 6). In particular, for groups of prime order these are essentially the extremal functions of the uncertainty principle for the discrete short time Fourier transform.


## 2. The Results

Letℤd denote the cyclic group ℤd∶=ℤ/dℤ in which addition is performed modulo d. If f:ℤd→ℂ is any complex-valued function on ℤd, we define the Fourier transform f^:ℤd→ℂ by the formula
(2)f^(k)=1d∑ℓ=0d-1‍f(ℓ)e-2πiℓk/d.
From now on, we identify ℂℤd with ℂd and we endow it with the Euclidean norm. The translation operator Tj,j∈ℤd, is the unitary operator on ℂd given by (Tjf)(ℓ)∶=f(ℓ-j). Similarly, the modulation operator Mk,k∈ℤd, is the unitary operator defined by
(3)(Mkf)(ℓ)∶=e2πikℓ/df(ℓ).
We have Mkf^=Tkf^. The short-time Fourier transform of f∈ℂd with respect to the window g∈ℂd is given by ([17–19])
(4)(Vgf)(j,k)=1d∑ℓ=0d-1‍f(ℓ)g(ℓ-j)¯e-2πiℓk/d,j,k∈ℤd.That is,(5)(Vgf)(j,k)=(f·Tjg¯)^(k)=1d〈f,MkTjg〉.
It is well-known that
(6)∑(j,k)∈ℤd2|(Vgf)(j,k)|2=∥f∥2∥g∥2.‍
This identity means that {MkTjg:(j,k)∈ℤd2} is a tight frame for ℂd whenever g∈ℂd∖{0}.IfA is a set we denote by |A| its cardinal. For f∈ℂA we represent by ∥f∥0 the cardinal of the set supp⁡f={a∈A:f(a)≠0}. Clearly, ∥·∥0 is not a norm.The first result we present was given in [15] as a quantitative version of a result of Krahmer et al. [14] which states that ∥Vgf∥0≥d for every f,g∈ℂd∖{0}. Its proof was an adaptation of a method that was originally developed in [11, 12] in the continuous setting. We give a different proof improving the estimate.Theorem 1 (Ghobber and Jaming [15]).
LetS⊂{0,1,…,d-1}2 be a subset with cardinal |S|<d. Then
(7)∥f∥∥g∥≤1(1-(|S|/d))(∑(j,k)∉S|(Vgf)(j,k)|2‍)1/2.Proof.
From the definition we get(8)|(Vgf)(j,k)|≤1d∥f∥∥g∥.
Hence
(9)∥f∥2∥g∥2=∑(j,k)∉S‍|(Vgf)(j,k)|2+∑(j,k)∈S|(Vgf)(j,k)|2‍≤∑(j,k)∉S|(Vgf)(j,k)|2‍+1d∥f∥2∥g∥2|S|,
from where the conclusion follows.Our next aim is to investigate under which conditions the support ofVgf has the smallest possible cardinal. The proof of the result that follows is based on an analysis of the discrete localization operators. These operators where introduced by Daubechies [20] in the continuous case in order to localize a signal both in time and frequency.It is well known thatf can be recovered from Vgf as
(10)f(ℓ)=∥g∥-21d∑(j,k)∈ℤd2(Vgf)(j,k)g(ℓ-j)e2πikℓ/d‍.Definition 2.
Letg∈ℂd and Λ⊂ℤd2 be given such that ∥g∥=1. Then, the localization operator LΛ,g:ℂd→ℂd is defined by
(11)(LΛ,gf)(ℓ)=1d∑(j,k)∈Λ(Vgf)(j,k)g(ℓ-j)e2πikℓ/d.‍LΛ,gf is a filtered version of f, as only those values of Vgf corresponding to entries in Λ are considered. Clearly LΛ,gf=f whenever Vgf is supported in Λ. Let us denote by ℓd1 the vector space ℂd endowed with the ℓ1-norm and by {en}n=1d the canonical basis.The main difficulty in the proof of the following theorem is that, a priori,f and g are arbitrary finite sequences of complex numbers. That is, we cannot assume that, after normalizing, f(ℓ)=e2πi(u(ℓ)/d) and g(ℓ)=e2πi(v(ℓ)/d) for some ℤd-valued u and v.Theorem 3.
Let one assume that∥f∥0+∥g∥0>d. Then ∥Vgf∥0=d if, and only if, f(0)≠0 and there are a,λ,c such that ad=(-1)d-1, λd=cd=1, and
(12)f(ℓ)=aℓcℓ(ℓ-1)/2f(0),g(ℓ)=(λa)ℓcℓ(ℓ-1)/2g(0).Proof.
For everyj∈ℤd the function f·Tjg¯ is different from zero; hence there is k∈ℤd such that (Vgf)(j,k)≠0. Consequently, the hypothesis ∥Vgf∥0=d means that the support of Vgf is a set
(13)Λ={(j,kj):j∈ℤd}.
Without loss of generality we can assume that ∥g∥2=1. We now consider the discrete localization operator LΛ,g:ℓd1→ℓd1,
(14)(LΛ,gh)(ℓ)=1d∑(j,k)∈Λ(Vgh)(j,k)g(ℓ-j)e2πikℓ/d‍.
It is well known that
(15)∥LΛ,g:ℓd1⟶ℓd1∥=max⁡n⁡∑ℓ=0d-1|(LΛ,gen)(ℓ)|=1dmax⁡n⁡∑ℓ=0d-1|∑j=0d-1g(n-j)¯g(ℓ-j)e-2πi(kj(n-ℓ)/d)|‍≤1.
Since LΛ,gf=f then ∥LΛ,g:ℓd1→ℓd1∥≥1 and we finally obtain
(16)max⁡n1d∑ℓ=0d-1‍|〈gℓ,gn〉|=1,
where
(17)gℓ(j)=g(ℓ-j)e2πikjℓ/d.
This implies that there is ℓ0∈ℤd such that
(18)|〈gℓ,gℓ0〉|=1∀ℓ∈ℤd.
According to Cauchy-Schwarz inequality, for every ℓ∈ℤd there is μ(ℓ)∈ℂ such that |μ(ℓ)|=1 and gℓ=μ(ℓ)·gℓ0. That is,
(19)g(ℓ-j)g(ℓ0-j)=μ(ℓ)·e-2πikj(ℓ-ℓ0)/d,ℓ∈ℤd,
which implies
(20)g(ℓ-j)g(n-j)=μ(ℓ)μ(n)·e-2πikj(ℓ-n)/d∀ℓ,n,j.
We now check that μ¯·f is constant. In fact, for every n∈ℤd,
(21)(Vgf)(j,k)=1d∑ℓ=0d-1f(ℓ)g(ℓ-j)¯e-2πikℓ/d‍=g(n-j)¯μ(n)¯e-2πikjn/d1d×∑ℓ=0d-1f(ℓ)μ(ℓ)¯e2πiℓ(kj-k)/d‍=g(n-j)¯μ(n)¯e-2πikjn/dμ¯·f^(k-kj).
Since the support of Vgf coincides with Λ we conclude that the Fourier transform of μ¯·f vanishes at any coordinate k∈ℤd∖{0}. Hence μ¯·f is constant and we conclude
(22)g(ℓ-j)g(n-j)=f(n)¯f(ℓ)¯·e-2πikj(ℓ-n)/d∀ℓ,n,j.
After replacing ℓ,n, and j by ℓ+1,n+1, and j+1 in the previous identity we obtain
(23)e-2πikj+1(ℓ-n)/df(n+1)¯f(ℓ+1)¯=e-2πikj(ℓ-n)/df(n)¯f(ℓ)¯.
We take ℓ=n+1 and conclude that
(24)e2πi(kj+1-kj)/d
does not depend on j. That is, kj+1-kj is constant (modulo d) and there is p∈ℤ such that
(25)kj+1=k0+pj(modulod).
We put λ∶=e-2πik0/d and take n=j=0 in (22) to obtain
(26)g(ℓ)·f(ℓ)¯=λℓf(0)¯g(0).
In order to simplify we normalize the function f so that
(27)f(0)¯g(0)=1.
We take n=j in (22) to obtain
(28)g(ℓ-j)=e-2πi(k0+pj)(ℓ-j)/df(j)¯f(ℓ)¯g(0),
that is,
(29)λℓ-jf(ℓ-j)¯=λℓ-je-2πipj(ℓ-j)/df(j)¯f(ℓ)¯g(0),f(ℓ)=f(ℓ-j)f(j)e2πipj(ℓ-j)/dg(0)¯.
Then j=1 gives
(30)f(ℓ)=f(ℓ-1)f(1)e2πip(ℓ-1)/dg(0)¯.
Finally, we consider
(31)a∶=f(1)g(0)¯,b∶=λa¯,c∶=e2πip/d.
Then
(32)f(ℓ)=acℓ-1f(ℓ-1)∀ℓ∈ℤd,
which implies
(33)f(ℓ)=aℓcℓ(ℓ-1)/2f(0)∀ℓ∈ℤd.
Since f(ℓ)=f(ℓ+d) we conclude
(34)adcd(d-1)/2=1.
That is, ad=(-1)d-1. Now, using that |a|=|c|=1,
(35)g(ℓ)=λℓf(ℓ)¯=(λa¯)ℓcℓ(ℓ-1)/21f(0)¯=(λa)ℓcℓ(ℓ-1)/2g(0).
The necessary condition is proved. In order to show the sufficiency, let us consider a,λ,c with λd=cd=1,ad=(-1)d-1 and
(36)f(ℓ)=aℓcℓ(ℓ-1)/2,g(ℓ)=(λa)ℓcℓ(ℓ-1)/2.
Then
(37)(Vgf)(j,k)=(λa)jd∑ℓ=0d-1(λ¯)ℓc(2ℓj-j2-j)/2e-2πikℓ/d‍=(λa)jdc(-j2-j)/2∑ℓ=0d-1rj,kℓ,
where
(38)rj,k=λ¯cje2πik/d.
Consequently,
(39)(Vgf)(j,k)≠0⟺rj,k=1.
That is, using that λ¯=e2πim/d, we have that
(40)(Vgf)(j,k)≠0⟺k=m+jp(modulod).According to the previous result, the support ofVgf is highly regular for instance when g does not vanish and ∥Vgf∥0=d.Next we prove that the periodicity off and g is related to the fact that the short time Fourier transform Vgf is supported in a certain subgroup.Proposition 4.
Letd=pq and f,g∈ℂd∖{0} be given. Then, the following conditions are equivalent.(1)
There isλ∈ℂsuch thatλp=1and(41)f(ℓ+q)=λf(ℓ),g(ℓ+q)=λg(ℓ),ℓ∈ℤd.(2)
The support ofVgfis contained inℤd×pℤd.Proof.
(1) implies (2) is obvious and we only prove (2) implies (1). Without loss of generality, we can assume that∥g∥2=1. We take Λ=ℤd×pℤd and consider the localization operator LΛ,g:ℓd1→ℓd1 defined by
(42)(LΛ,gh)(ℓ)=1d∑(j,k)∈Λ(Vgh)(j,k)g(ℓ-j)e2πikℓ/d.‍
Condition (2) implies LΛ,gf=f; hence
(43)∥LΛ,g:ℓd1⟶ℓd1∥≥1.
That is,
(44)max⁡n⁡∑ℓ=0d-1|(LΛ,gen)(ℓ)|≥1.‍
On the other hand, (Vgen)(j,k)=1dg(n-j)¯e-2πi(nk/d) and
(45)(LΛ,gen)(ℓ)=1d(∑j=0d-1g(n-j)¯g(ℓ-j))×(∑k=0q-1e-2πi((n-ℓ)k/q)).
Consequently,
(46)(LΛ,gen)(ℓ)=0whenevern≠ℓmoduloq,(LΛ,gen)(ℓ)=1p∑j=0d-1g(n-j)¯g(ℓ-j)whenevern=ℓmoduloq.
From (44), Cauchy-Schwarz inequality, and condition ∥g∥2=1 we finally conclude that, for some n∈ℤd,
(47)∑m=0p-11p|∑j=0d-1g(n-j)¯g(n+mq-j)|=1.‍
Hence
(48)|∑j=0d-1g(n-j)¯g(n+mq-j)|=1for everym=0,1,…,p-1.
In particular, by Cauchy-Schwarz inequality, there is λ∈ℂ with |λ|=1 such that
(49)g(n+q-j)=λg(n-j),j=0,1,…,d-1.
That is, g(ℓ+q)=λg(ℓ) for every ℓ=0,1,…,d-1. From g(ℓ)=g(ℓ+d)=λpg(ℓ) we obtain λp=1. Since |Vgf(j,k)|=|Vfg(-j,-k)| we can proceed as before and obtain f(ℓ+q)=μf(ℓ) for some μ∈ℂ with μp=1. Finally, from the fact that
(50)(Vgf)(j,k)=1d(∑ℓ=0q-1f(ℓ)g(ℓ-j)¯e-2πi(ℓk/q)‍)×(∑m=0p-1(λ¯μ)me-2πi(mk/p)‍)
is different from zero for some k∈pℤd we conclude λ¯μ=1. That is, λ=μ and the proposition is proved.In connection with the norm attaining points of the Fourier transform the following definition was given in [16].Definition 5.
We say thatf=(fi)i=0d-1∈ℂd gives rise to a time-frequency basis if the translations of (1/d)f form an orthonormal basis and this basis is equal to {ck(1/d)Mkf:k∈ℤd} for some constants ck∈𝕋.Iff generates a time-frequency basis it must be biunimodular; that is, |fi|=|f^i|=1, but the opposite does not hold. Biunimodular vectors and vectors generating time-frequency basis are easily characterized in terms of the support of Vff.Proposition 6.
Letf∈ℂd∖{0} be given. Then (1)
fis biunimodular if and only ifVff(0,k)=Vff(k,0)=δk,0,(2)
a multiple offgenerates a time-frequency basis if and only if(51)supp⁡Vff={(j,π(j)):j=0,…,d-1},where π:{0,…,d-1}→{0,…,d-1} is a permutation.Proof.
(1) Follows fromVff(0,k)=|f|2^(k) and Vf^f^(j,k)=Vff(k,j).
(2) Let us first assume thatf∈ℂd generates a time-frequency basis. Accordingly, |fi|=1 and there is a permutation π:{0,…,d-1}→{0,…,d-1} such that π(0)=0 and
(52)f(ℓ-j)=λje-2πiπ(j)ℓ/df(ℓ),|λj|=1.
Then
(53)(Vff)(j,k)=λj¯d∑ℓ=0d-1e-2πi(k-π(j))/d,
which is nonzero only for k=π(j) (mod d).
To show the converse implication we first note that(Vff)(0,0)=(1/d)∥f∥2>0 implies π(0)=0. As Vff(j,k)=fTjf¯^(k) one has
(54)fTjf¯^=λjeπ(j)
for some λj∈ℂ, from where
(55)f(ℓ)f(ℓ-j)¯=μje2πiℓπ(j)/d
for some μj∈ℂ. Since π(0)=0 then |f(ℓ)|2=μ0. Therefore |f(ℓ)| is constant. We now deduce
(56)|μj|=|f(ℓ)f(ℓ-j)|=μ0
for every j. In particular, we can write
(57)μ1=μ0e-2πir1
and we obtain
(58)f(ℓ)f(ℓ-1)¯=μ0e-2πir1e2πiℓπ(1)/d,ℓ∈ℤd.
Proceeding by recurrence we finally obtain
(59)f(ℓ)=f(0)e-2πi(r1ℓ+k1(ℓ+1)ℓ)/2d,
and then it is easy to see that for some constants cj∈𝕋,Tjf=cjMjk1f. Finally, as Vff(j,0)=0 for j≠0 we get that {Tjf:j=1,…,d-1} is an orthogonal basis, and this basis coincides up to constants with the set of all modulations.As an application we recover [16, Theorem 4.5].Corollary 7.
Letf∈ℂd∖{0} be given. Then a multiple of f generates a time-frequency basis if and only if there exist a and c such that ad=(-1)d-1,c is a primitive d-root of unity, and
(60)f(ℓ)=aℓcℓ(ℓ-1)/2f(0),ℓ∈ℤd.Proof.
Let us assume thatf generates a time-frequency basis and f(0)=1. According to Theorem 3, there exist a and c such that ad=(-1)d-1,cd=1, and
(61)f(ℓ)=aℓcℓ(ℓ-1)/2f(0),ℓ∈ℤd.
We put c=e-2πip/d. From the proof of the same result we have (Vff)(j,k)≠0 if and only if k=pj (modulo d). Hence, Proposition 6 gives that the map ℤd→ℤd,j↦pj, is injective, or equivalently, p and d have no common prime divisors. That is, c is a primitive d-root of unity.Corollary 8.
Letd be a prime number. Then ∥Vff∥0=d if and only if f satisfies one of the following conditions:(1)
∥f∥0=1.(2)
∥f^∥0=1.(3)
(A multiple of)f generates a time-frequency basis.Proof.
We assumed>2. If 2∥f∥0>d we can apply Theorem 2.5 to conclude that f(ℓ)=f(0)aℓcℓ(ℓ-1)/2 with ad=cd=1. If c≠1 it is a primitive d-root of the unity and therefore f generates a time-frequency basis. In case c=1,∥f^∥0=1.
If2∥f∥0≤d then, by [6], we have 2∥f^∥0>d; hence as before either f^ generates a time-frequency basis or the support of f^ is a singleton.



---

*Source: 131459-2014-02-13.xml*