# Effective Approach to Calculate Analysis Window in Infinite Discrete Gabor Transform

Authors: Rui Li; Yong Huang; Jia-Bao Liu
Journal: Complexity
 (2018)

---

## Abstract

The long-periodic/infinite discrete Gabor transform (DGT) is more effective than the periodic/finite one in many applications. In this paper, a fast and effective approach is presented to efficiently compute the Gabor analysis window for arbitrary given synthesis window in DGT of long-periodic/infinite sequences, in which the new orthogonality constraint between analysis window and synthesis window in DGT for long-periodic/infinite sequences is derived and proved to be equivalent to the completeness condition of the long-periodic/infinite DGT. By using the property of delta function, the original orthogonality can be expressed as a certain number of linear equation sets in both the critical sampling case and the oversampling case, which can be fast and efficiently calculated by fast discrete Fourier transform (FFT). The computational complexity of the proposed approach is analyzed and compared with that of the existing canonical algorithms. The numerical results indicate that the proposed approach is efficient and fast for computing Gabor analysis window in both the critical sampling case and the oversampling case in comparison to existing algorithms.


---

## Body

## 1. Introduction

The discrete Gabor transform (DGT) [1], extended from the short-time Fourier transform (STFT), is an important time-frequency analysis tool for processing and analyzing the nonstationary signal [2–4], which multiplied a signal by a time-shifted and frequency-modulated window function with the aim of representing analyzed signals in a time-frequency localized manner. As a general case of STFT, DGT, sampled version of the STFT, is an efficient tool for analyzing the energy distribution of analyzed signals in the time-frequency domain/plane and more valuable than Fourier transform (FT) in many applications which require to extract temporal frequency information and localize simultaneously. According to the type of time-frequency atom, the DGT can be classified into two categories: the complex-valued discrete Gabor transform (CDGT) and the real-valued Discrete Gabor transform (RDGT) [5–8]. The former method for computing the DGT and its inverse transform all involves complex operators while the latter one can utilize discrete Hartley’s cas transform (DHT) kernel, discrete cosine transform (DCT) kernel, or discrete sine transform (DST) kernel as the Gabor basis function which only involves real operators. More specifically, in some real-time applications, the CDGT is more difficult to be implemented in hardware or software and the RDGT for sampled speech and image has an advantage of the computationally efficient implementation.Over the past decades, the DGT has become a very valuable and widely used mathematic tool in diverse applications [12–19] such as audio processing, speech processing, image processing, sonar and radar signal processing, seismic signal processing, and transient signal processing. The analyzed signal, analysis window, and synthesis window in the periodic DGT usually have the same periodic length, which may confront difficulties in applying to some real-time applications of long-periodic signal sequences. To bridge these gaps, the long-periodic DGT [9, 10, 19] of complex-valued kernel and real-valued kernel has been presented to utilize the short window to analyze and process the long-periodic (or infinite) signal sequences in practical applications. Because existing canonical algorithms [11, 20–27] are mainly used in periodic/finite DGT and derived from Gabor frame theory, in this paper, a fast and effective algorithm, based on the orthogonal analysis approach and FFT algorithm, is proposed to obtain the analysis window for the long-periodic/infinite DGT in both the critical sampling case and the oversampling case.The rest of the paper is organized as follows. In Section2, the long-periodic/infinite DGT will be reviewed. In Section 3, a fast approach, which uses the new orthogonal constraint relationship of the analysis window and the synthesis window to deduce a series of independent linear equation sets, is introduced to calculate analysis window in the long-periodic/infinite DGT under both the critical sampling case and the oversampling case. In Section 4, the detailed comparison of computational complexity of related algorithms and numerical experiments have been given to show that the proposed method can overcome the existing algorithms in computing analysis window of the long-periodic/infinite DGT. Finally, the paper is concluded with Section 5.


## 2. DGT for Long-Period and Infinite Sequences

Letf
[
k
] represent a periodic and discrete-time signal with length L
s and the length of analysis window g
[
k
] and synthesis window h
[
k
]. In order to use g
[
k
] and h
[
k
] to analyze and process the signal f
[
k
], the three periodic sequences f
^
[
k
], g
^
[
k
], and g
^
[
k
] of length L
0
=
L
+
L
s should be constructed as follows:(1)
f
^
k
=
f
^
k
+
i
L
0
=
f
k
0
≤
k
<
L
s
0
L
s
≤
k
<
L
0
,
(2)
g
^
k
=
g
^
k
+
i
L
0
=
g
k
0
≤
k
<
L
0
L
s
≤
k
<
L
0
,
(3)
h
^
k
=
h
^
k
+
i
L
0
=
h
k
0
≤
k
<
L
s
0
L
s
≤
k
<
L
0
,where i
=
0
,
±
1
,
±
2
,
±
3
,
…
. The DGT for long-periodic/infinite sequences [4, 19] is defined by the following:(4)
f
^
k
=
∑
m
=
0
M
-
1
∑
n
=
0
N
-
1
c
m
,
n
h
^
k
-
m
a
exp
⁡
j
2
π
n
k
N
,and the Gabor coefficients c
[
m
,
n
] can be calculated by(5)
c
m
,
n
=
∑
k
=
0
L
0
-
1
f
^
k
g
^
k
-
m
a
exp
⁡
-
j
2
π
n
k
N
=
∑
k
=
0
L
s
-
1
f
^
k
g
^
k
-
m
a
exp
⁡
-
j
2
π
n
k
N
,where j
=
-
1 is the imaginary unit. The DGT for long-periodic/infinite sequences can be obtained by (5) corresponding to its expansion in (4). In (4) and (5), L
0
=
M
a
=
N
ω, let the positive integers M, N are the sampling points in time and frequency, and let ω and a denote a modulation step in frequency and a translation interval in time. For a numerically stable reconstruction, the constrained condition by L
0
≤
M
N (or L
0
≥
ω
a) has to be satisfied. By choosing proper parameters a and N, the Gabor oversampling rate β
=
N
/
a
=
M
/
ω is a positive integer. The biorthogonal relationship [4, 19] of g
^
[
k
] and h
^
[
k
], which are derived from the completeness condition between (4) and (5), can be rewritten as(6)
a
N
δ
m
δ
n
=
∑
k
=
0
L
0
-
1
h
^
k
+
m
N
exp
⁡
-
j
2
π
n
k
a
g
^
k
=
∑
k
=
0
L
-
1
h
^
k
+
m
N
exp
⁡
-
j
2
π
n
k
a
g
k
,where δ
[
k
] denotes the discrete form of delta function, 0
≤
m
≤
ω, and 0
≤
n
≤
a.


## 3. FFT-Based Method for Solving the Analysis Sequences

To derive a new type biorthogonality relationship from the completeness between (4) and (5), substituting (5) into (4) yields(7)
f
^
k
=
∑
m
=
0
M
-
1
∑
n
=
0
N
-
1
∑
k
¯
=
0
L
0
-
1
f
^
k
¯
g
^
k
¯
-
m
a
exp
⁡
-
j
2
π
n
k
¯
N
·
h
^
k
-
m
a
exp
⁡
j
2
π
n
k
N
=
∑
k
¯
=
0
L
0
-
1
f
^
k
¯
∑
m
=
0
M
-
1
∑
n
=
0
N
-
1
h
^
k
-
m
a
g
^
k
¯
-
m
a
·
exp
⁡
j
2
π
n
k
N
exp
⁡
-
j
2
π
n
k
¯
N
=
∑
k
¯
=
0
L
0
-
1
f
^
k
¯
∑
m
=
0
M
-
1
h
^
k
-
m
a
g
^
k
¯
-
m
a
·
∑
n
=
0
N
-
1
exp
⁡
j
2
π
n
k
N
exp
⁡
-
j
2
π
n
k
¯
N
,recalling(8)
∑
n
=
0
N
-
1
exp
⁡
j
2
π
n
k
N
·
exp
⁡
-
j
2
π
n
k
¯
N
=
∑
n
=
0
N
-
1
exp
⁡
j
2
π
n
k
-
k
¯
N
=
N
∑
m
¯
=
0
ω
-
1
δ
k
-
k
¯
-
m
¯
N
,and putting (8) into (7) leads to(9)
f
^
k
=
N
·
∑
k
¯
=
0
L
0
-
1
f
^
k
¯
∑
m
=
0
M
-
1
h
^
k
-
m
a
g
^
k
¯
-
m
a
·
∑
m
¯
=
0
ω
-
1
δ
k
-
k
¯
-
m
¯
N
=
N
·
∑
k
¯
=
0
L
0
-
1
∑
u
=
0
M
-
1
h
^
k
+
u
a
g
^
k
¯
+
u
a
∑
m
¯
=
0
ω
-
1
δ
k
-
k
¯
-
m
¯
N
f
^
k
¯
.According to the completeness of the transform, the following constraint relationship has to be satisfied:(10)
δ
k
-
k
¯
=
N
·
∑
u
=
0
M
-
1
h
^
k
+
u
a
g
^
k
¯
+
u
a
·
∑
m
¯
=
0
ω
-
1
δ
k
-
k
¯
-
m
¯
N
,so(11)
N
·
∑
u
=
0
M
-
1
h
^
k
+
u
a
g
^
k
¯
+
u
a
=
1
,
k
=
k
¯
0
,
k
≠
k
¯
,
k
-
k
¯
mod
⁡
N
=
0
.Equation (11) can be expressed as a equivalent form in the following:(12)
δ
m
¯
=
N
·
∑
u
=
0
M
-
1
h
^
k
¯
+
m
¯
N
+
u
a
g
^
k
¯
+
u
a
,where 0
≤
m
¯
<
ω and 0
≤
k
¯
<
L
0. Let k
¯
=
q
+
p
a, 0
≤
p
≤
M
-
1, and 0
≤
q
≤
a
-
1; then (12) can be written as(13)
δ
m
¯
=
N
∑
u
=
0
M
-
1
h
^
q
+
p
a
+
m
¯
N
+
u
a
g
^
q
+
p
a
+
u
a
=
N
∑
u
¯
=
p
M
+
p
-
1
h
^
q
+
m
¯
N
+
u
¯
a
g
^
q
+
u
¯
a
=
N
∑
u
¯
=
p
M
-
1
h
^
q
+
m
¯
N
+
u
¯
a
g
^
q
+
u
¯
a
+
∑
u
¯
=
M
M
+
p
-
1
h
^
q
+
m
¯
N
+
u
¯
a
g
^
q
+
u
¯
a
=
N
∑
u
¯
=
p
M
-
1
h
^
q
+
m
¯
N
+
u
¯
a
g
^
q
+
u
¯
a
+
∑
u
¯
=
0
p
-
1
h
^
q
+
m
¯
N
+
u
¯
a
g
^
q
+
u
¯
a
=
N
∑
u
¯
=
0
M
-
1
h
^
q
+
m
¯
N
+
u
¯
a
g
^
q
+
u
¯
a
.Obviously, (13) can be rewritten in matrix form as follows:(14)
N
H
^
0
0
⋯
0
0
H
^
0
⋯
0
⋮
⋮
⋱
⋮
0
0
⋯
H
^
a
-
1
g
^
0
g
^
1
⋮
g
^
a
-
1
=
e
^
e
^
⋮
e
^
,where e
^
=
1,0
,
…
,
0
T is an ω-long unit vector with first element being one and others being zeros; g
^
(
q
) is a M-long vector composed by(15)
g
^
q
=
g
^
q
,
g
^
q
+
a
,
…
,
g
^
q
+
M
-
1
a
T
,and H
^
(
q
) is a ω
×
M matrix constructed by(16)
H
^
q
=
h
^
0,0
q
h
^
0,1
q
⋯
h
^
0
,
M
-
1
q
h
^
1,0
q
h
^
1,1
q
⋯
h
^
1
,
M
-
1
q
⋮
⋮
⋱
⋮
h
^
ω
-
1,0
q
h
^
ω
-
1,1
q
⋯
h
^
ω
-
1
,
M
-
1
q
,where h
^
u
,
v
(
q
)
=
h
^
[
q
+
u
N
+
v
a
], 0
≤
u
<
ω, and 0
≤
v
<
M. Equation (14) can be split into a unrelated linear equation sets:(17)
N
·
H
^
q
g
^
q
=
e
^
0
≤
q
≤
a
-
1
.Due to the fact that most of elements in h
^
[
k
] and g
^
[
k
] were zeros according to (2) and (3), let Δ
ω, Δ
M be the positive integer constrained by L
=
Δ
ω
N
=
Δ
M
a: (15) and (16) are rewritten as follows:(18)
g
^
q
=
g
q
g
q
+
a
⋮
g
q
+
Δ
M
-
1
a
0
⋮
0
=
g
q
0
,
H
^
q
=
h
0,0
q
⋯
h
0
,
Δ
M
-
1
q
0
⋯
0
h
1,0
q
⋯
h
1
,
Δ
M
-
1
q
0
⋯
0
⋮
⋱
⋮
⋮
⋮
⋮
h
Δ
ω
-
1,0
q
⋯
h
Δ
ω
-
1
,
Δ
M
-
1
q
0
⋯
0
0
⋯
0
0
⋯
0
⋮
⋯
⋮
⋮
⋯
⋮
0
⋯
0
0
⋯
0
=
H
q
0
0
0
,where(19)
g
q
=
g
q
g
q
+
a
⋮
g
q
+
Δ
M
-
1
a
,
H
q
=
h
0,0
q
h
0,1
q
⋯
h
0
,
Δ
M
-
1
q
h
1,0
q
h
1,1
q
⋯
h
1
,
Δ
M
-
1
q
⋮
⋮
⋱
⋮
h
Δ
ω
-
1,0
q
h
Δ
ω
-
1,1
q
⋯
h
Δ
ω
-
1
,
Δ
M
-
1
q
,
h
u
,
v
(
q
)
=
h
[
q
+
u
N
+
v
a
], 0
≤
u
<
Δ
ω
-
1, and 0
≤
v
<
Δ
M
-
1. Equation (17) can then be rewritten in the following form:(20)
N
·
H
q
0
0
0
g
q
0
=
e
^
=
e
0
,where e
=
[
1,0
,
…
,
0
]
T is a unit vector of length Δ
ω
-
1. Obviously, the following formula can be easily obtained by (20):(21)
N
·
H
q
g
q
=
e
,where 0
≤
q
≤
a
-
1.


### 3.1. Fast Approach for Computing Analysis Window in the Critical Sampling Case

In the critical sampling case, the oversampling rateβ
=
M
/
ω
=
N
/
a
=
Δ
M
/
Δ
ω
=
1; (21) can be rewritten in following form:(22)
H
¯
q
g
q
=
1
N
·
h
q
,
(23)
H
¯
q
=
H
q
T
H
q
,
(24)
h
q
=
h
q
h
q
+
a
⋮
h
q
+
Δ
M
-
1
a
=
h
q
h
q
+
a
⋮
h
q
+
Δ
ω
-
1
a
.Because H
¯
(
q
) is a right circulant matrix by Δ
M
×
Δ
M (or Δ
ω
×
Δ
ω), so (22) can be written as a circular convolution in following form:(25)
h
¯
q
∗
g
q
=
1
N
·
h
q
,where h
¯
(
q
) is the first column of H
¯
(
q
) as the following form: (26)
h
¯
q
=
h
q
∗
h
^
q
,
(27)
h
^
q
=
h
q
h
q
+
Δ
ω
-
1
a
⋮
h
q
+
Δ
ω
-
Δ
ω
-
1
a
=
h
q
h
q
+
Δ
ω
-
1
a
⋮
h
q
+
a
.By utilizing the circular convolution theorem [28], the FFT algorithm can then be used to transform (25) into component-wise multiplication by recalling (26) as follows: (28)
F
Δ
ω
h
¯
q
∗
g
q
=
F
Δ
ω
h
q
·
F
Δ
ω
h
^
q
·
F
Δ
ω
g
q
=
1
N
·
F
Δ
ω
h
q
,where F
Δ
ω is the Δ
ω-point DFT. Thus, h
(
q
) can be fast computed by(29)
g
q
=
1
N
·
F
Δ
ω
-
1
1
F
Δ
ω
h
^
q
.The computation of (29) is obviously much faster than that using the standard Gaussian elimination method to solve the linear equation set.Remark 1.
More similar result to (29), the author in [11] provides a method, based on Gabor frame theory [20] and discrete Zak transform [29], to obtain dual Gabor window in periodic/finite DGT under the critical sampling. However, in present paper, the proposed method uses the orthogonal analysis approach and FFT algorithm to solve the analysis window for long-periodic/infinite signal sequences.


### 3.2. Fast Approach for Computing Analysis Window in the Oversampling Case

In the oversampling case, the oversampling rateβ
=
M
/
ω
=
N
/
a
=
Δ
M
/
Δ
ω
≥
2 can be a positive integer by setting Δ
M and Δ
ω properly. Because the rank of H
(
q
) is less than the number of rows, (21) is an underdetermined linear equation which could have no solution or have an infinite number of solutions. Equation (21) could be rewritten in the following form in order to use convolution theory and FFT algorithm as that in the critical sampling case.(30)
N
·
H
0
q
,
H
1
q
,
…
,
H
β
-
1
q
g
0
q
g
1
q
⋮
g
β
-
1
q
=
e
,where 0
≤
i
≤
β
-
1 and H
i
(
q
) is a Δ
ω
×
Δ
ω left circulant matrix composed by(31)
H
i
q
=
h
0,0
q
,
i
h
0,1
q
,
i
⋯
h
0
,
Δ
ω
-
1
q
,
i
h
1,0
q
,
i
h
1,1
q
,
i
⋯
h
1
,
Δ
ω
-
1
q
,
i
⋮
⋮
⋱
⋮
h
Δ
ω
-
1,0
q
,
i
h
Δ
ω
-
1,1
q
,
i
⋯
h
Δ
ω
-
1
,
Δ
ω
-
1
q
,
i
,where h
u
,
v
q
,
i
=
h
q
+
u
N
+
v
N
+
i
a and g
i
(
q
) is a vector with length Δ
ω constructed by(32)
g
i
q
=
g
q
+
i
a
g
q
+
N
+
i
a
⋮
g
q
+
Δ
ω
-
1
N
+
i
a
.Then we rewrite (30) as(33)
H
¯
i
q
g
¯
i
q
=
1
N
·
h
i
q
,where(34)
H
¯
i
q
=
H
i
q
T
H
i
q
.Let(35)
g
i
q
=
λ
i
g
¯
i
q
s.t.
∑
i
=
0
β
-
1
λ
i
=
1
,
h
i
q
=
h
q
+
i
a
h
q
+
N
+
i
a
⋮
h
q
+
Δ
ω
-
1
N
+
i
a
.Then, (33) also can be rewritten as a circular convolution:(36)
h
¯
i
q
∗
g
¯
i
q
=
h
i
q
∗
h
^
i
q
∗
g
¯
i
q
=
1
N
·
h
i
q
,where h
¯
i
(
q
) is the first column of H
¯
i
(
q
) as follows:(37)
h
¯
i
q
=
h
i
q
∗
h
^
i
q
,
h
^
i
q
=
g
q
+
i
a
g
q
+
Δ
ω
-
1
N
+
i
a
⋮
g
q
+
Δ
ω
-
Δ
ω
-
1
N
+
i
a
=
g
q
+
i
a
g
q
+
Δ
ω
-
1
N
+
i
a
⋮
g
q
+
N
+
i
a
.By using the circular convolution theorem and the FFT operator, (36) can be expressed in the following form:(38)
F
Δ
ω
h
¯
i
q
∗
g
¯
i
q
=
F
Δ
ω
h
i
q
·
F
Δ
ω
h
^
i
q
·
F
Δ
ω
g
¯
i
q
=
1
N
·
F
Δ
ω
h
i
q
,so g
¯
i
(
q
) can be solved by(39)
g
¯
i
q
=
1
N
·
F
Δ
ω
-
1
1
F
Δ
ω
h
^
i
q
.Due to the fact that g
[
k
] should be close to h
[
k
] in the sense of the least square error (LSE) as shown in [30],(40)
min
N
H
q
g
q
=
e
⁡
g
q
g
q
-
h
q
2
2
.
g
(
q
)
[
k
] has to satisfy the least of l
2 norm which make g
(
q
)
[
k
] a Gaussian-type function of the localization property:(41)
m
i
n
g
q
2
2
=
min
⁡
∑
i
=
0
β
-
1
g
i
q
2
2
=
m
i
n
∑
i
=
0
β
-
1
λ
i
2
g
¯
i
q
2
2
s.t.
∑
i
=
0
β
-
1
λ
i
=
1
.Equation (41) can be converted into the following optimum problem and easily solved by the Lagrangian approach:(42)
J
λ
=
1
2
v
¯
λ
T
v
¯
λ
+
u
1
-
e
¯
T
λ
s.t.
e
¯
T
λ
=
1
,where λ
=
λ
0
,
λ
1
,
…
,
λ
β
-
1
T, e
¯
=
1,1
,
…
,
1
T is a vector with length β, μ is a Lagrangian parameter, and(43)
v
¯
=
g
¯
0
q
0
⋯
0
0
g
¯
1
q
⋯
0
⋮
⋮
⋱
⋮
0
0
⋯
g
¯
β
-
1
q
.Taking a derivative of J
λ with respect to λ leads to(44)
∂
J
λ
∂
λ
=
v
¯
T
v
¯
λ
-
μ
e
¯
=
0
,then the solution of λ can be obtained from (44):(45)
λ
=
μ
v
¯
T
v
¯
-
1
e
¯
,and putting this solution into constraint condition in (42) to solve μ leads to(46)
λ
=
1
W
1
g
¯
0
q
2
2
,
1
g
¯
1
q
2
2
,
…
,
1
g
¯
β
-
1
q
2
2
,where W
=
∑
i
=
0
β
-
1
1
/
∥
g
¯
i
(
q
)
∥
2
2.Remark 2.
In sparse applications, the synthesis window without considering localization property (λ
=
1
/
β
e
¯) can be used to reconstruct the original signal, in which a certain well-localized window function will be directly utilized as an analysis window.Remark 3.
The proposed algorithm can be easily generalized and applied to other DGT for both the periodic/finite sequences and the long-periodic/infinite sequences including complex-valued (DFT-based) and real-valued (DHT-based, DCT-based) and multiwindow discrete Gabor transforms (M-DGT) because those Gabor basis functions in DGT can lead to the similar form of the biorthogonal relationship equation.


## 3.1. Fast Approach for Computing Analysis Window in the Critical Sampling Case

In the critical sampling case, the oversampling rateβ
=
M
/
ω
=
N
/
a
=
Δ
M
/
Δ
ω
=
1; (21) can be rewritten in following form:(22)
H
¯
q
g
q
=
1
N
·
h
q
,
(23)
H
¯
q
=
H
q
T
H
q
,
(24)
h
q
=
h
q
h
q
+
a
⋮
h
q
+
Δ
M
-
1
a
=
h
q
h
q
+
a
⋮
h
q
+
Δ
ω
-
1
a
.Because H
¯
(
q
) is a right circulant matrix by Δ
M
×
Δ
M (or Δ
ω
×
Δ
ω), so (22) can be written as a circular convolution in following form:(25)
h
¯
q
∗
g
q
=
1
N
·
h
q
,where h
¯
(
q
) is the first column of H
¯
(
q
) as the following form: (26)
h
¯
q
=
h
q
∗
h
^
q
,
(27)
h
^
q
=
h
q
h
q
+
Δ
ω
-
1
a
⋮
h
q
+
Δ
ω
-
Δ
ω
-
1
a
=
h
q
h
q
+
Δ
ω
-
1
a
⋮
h
q
+
a
.By utilizing the circular convolution theorem [28], the FFT algorithm can then be used to transform (25) into component-wise multiplication by recalling (26) as follows: (28)
F
Δ
ω
h
¯
q
∗
g
q
=
F
Δ
ω
h
q
·
F
Δ
ω
h
^
q
·
F
Δ
ω
g
q
=
1
N
·
F
Δ
ω
h
q
,where F
Δ
ω is the Δ
ω-point DFT. Thus, h
(
q
) can be fast computed by(29)
g
q
=
1
N
·
F
Δ
ω
-
1
1
F
Δ
ω
h
^
q
.The computation of (29) is obviously much faster than that using the standard Gaussian elimination method to solve the linear equation set.Remark 1.
More similar result to (29), the author in [11] provides a method, based on Gabor frame theory [20] and discrete Zak transform [29], to obtain dual Gabor window in periodic/finite DGT under the critical sampling. However, in present paper, the proposed method uses the orthogonal analysis approach and FFT algorithm to solve the analysis window for long-periodic/infinite signal sequences.


## 3.2. Fast Approach for Computing Analysis Window in the Oversampling Case

In the oversampling case, the oversampling rateβ
=
M
/
ω
=
N
/
a
=
Δ
M
/
Δ
ω
≥
2 can be a positive integer by setting Δ
M and Δ
ω properly. Because the rank of H
(
q
) is less than the number of rows, (21) is an underdetermined linear equation which could have no solution or have an infinite number of solutions. Equation (21) could be rewritten in the following form in order to use convolution theory and FFT algorithm as that in the critical sampling case.(30)
N
·
H
0
q
,
H
1
q
,
…
,
H
β
-
1
q
g
0
q
g
1
q
⋮
g
β
-
1
q
=
e
,where 0
≤
i
≤
β
-
1 and H
i
(
q
) is a Δ
ω
×
Δ
ω left circulant matrix composed by(31)
H
i
q
=
h
0,0
q
,
i
h
0,1
q
,
i
⋯
h
0
,
Δ
ω
-
1
q
,
i
h
1,0
q
,
i
h
1,1
q
,
i
⋯
h
1
,
Δ
ω
-
1
q
,
i
⋮
⋮
⋱
⋮
h
Δ
ω
-
1,0
q
,
i
h
Δ
ω
-
1,1
q
,
i
⋯
h
Δ
ω
-
1
,
Δ
ω
-
1
q
,
i
,where h
u
,
v
q
,
i
=
h
q
+
u
N
+
v
N
+
i
a and g
i
(
q
) is a vector with length Δ
ω constructed by(32)
g
i
q
=
g
q
+
i
a
g
q
+
N
+
i
a
⋮
g
q
+
Δ
ω
-
1
N
+
i
a
.Then we rewrite (30) as(33)
H
¯
i
q
g
¯
i
q
=
1
N
·
h
i
q
,where(34)
H
¯
i
q
=
H
i
q
T
H
i
q
.Let(35)
g
i
q
=
λ
i
g
¯
i
q
s.t.
∑
i
=
0
β
-
1
λ
i
=
1
,
h
i
q
=
h
q
+
i
a
h
q
+
N
+
i
a
⋮
h
q
+
Δ
ω
-
1
N
+
i
a
.Then, (33) also can be rewritten as a circular convolution:(36)
h
¯
i
q
∗
g
¯
i
q
=
h
i
q
∗
h
^
i
q
∗
g
¯
i
q
=
1
N
·
h
i
q
,where h
¯
i
(
q
) is the first column of H
¯
i
(
q
) as follows:(37)
h
¯
i
q
=
h
i
q
∗
h
^
i
q
,
h
^
i
q
=
g
q
+
i
a
g
q
+
Δ
ω
-
1
N
+
i
a
⋮
g
q
+
Δ
ω
-
Δ
ω
-
1
N
+
i
a
=
g
q
+
i
a
g
q
+
Δ
ω
-
1
N
+
i
a
⋮
g
q
+
N
+
i
a
.By using the circular convolution theorem and the FFT operator, (36) can be expressed in the following form:(38)
F
Δ
ω
h
¯
i
q
∗
g
¯
i
q
=
F
Δ
ω
h
i
q
·
F
Δ
ω
h
^
i
q
·
F
Δ
ω
g
¯
i
q
=
1
N
·
F
Δ
ω
h
i
q
,so g
¯
i
(
q
) can be solved by(39)
g
¯
i
q
=
1
N
·
F
Δ
ω
-
1
1
F
Δ
ω
h
^
i
q
.Due to the fact that g
[
k
] should be close to h
[
k
] in the sense of the least square error (LSE) as shown in [30],(40)
min
N
H
q
g
q
=
e
⁡
g
q
g
q
-
h
q
2
2
.
g
(
q
)
[
k
] has to satisfy the least of l
2 norm which make g
(
q
)
[
k
] a Gaussian-type function of the localization property:(41)
m
i
n
g
q
2
2
=
min
⁡
∑
i
=
0
β
-
1
g
i
q
2
2
=
m
i
n
∑
i
=
0
β
-
1
λ
i
2
g
¯
i
q
2
2
s.t.
∑
i
=
0
β
-
1
λ
i
=
1
.Equation (41) can be converted into the following optimum problem and easily solved by the Lagrangian approach:(42)
J
λ
=
1
2
v
¯
λ
T
v
¯
λ
+
u
1
-
e
¯
T
λ
s.t.
e
¯
T
λ
=
1
,where λ
=
λ
0
,
λ
1
,
…
,
λ
β
-
1
T, e
¯
=
1,1
,
…
,
1
T is a vector with length β, μ is a Lagrangian parameter, and(43)
v
¯
=
g
¯
0
q
0
⋯
0
0
g
¯
1
q
⋯
0
⋮
⋮
⋱
⋮
0
0
⋯
g
¯
β
-
1
q
.Taking a derivative of J
λ with respect to λ leads to(44)
∂
J
λ
∂
λ
=
v
¯
T
v
¯
λ
-
μ
e
¯
=
0
,then the solution of λ can be obtained from (44):(45)
λ
=
μ
v
¯
T
v
¯
-
1
e
¯
,and putting this solution into constraint condition in (42) to solve μ leads to(46)
λ
=
1
W
1
g
¯
0
q
2
2
,
1
g
¯
1
q
2
2
,
…
,
1
g
¯
β
-
1
q
2
2
,where W
=
∑
i
=
0
β
-
1
1
/
∥
g
¯
i
(
q
)
∥
2
2.Remark 2.
In sparse applications, the synthesis window without considering localization property (λ
=
1
/
β
e
¯) can be used to reconstruct the original signal, in which a certain well-localized window function will be directly utilized as an analysis window.Remark 3.
The proposed algorithm can be easily generalized and applied to other DGT for both the periodic/finite sequences and the long-periodic/infinite sequences including complex-valued (DFT-based) and real-valued (DHT-based, DCT-based) and multiwindow discrete Gabor transforms (M-DGT) because those Gabor basis functions in DGT can lead to the similar form of the biorthogonal relationship equation.


## 4. Computational Complexity Analysis and Numerical Experiments

When calculating the multiplication times of related algorithms, we assume that theN-point FFT requires an order of N
l
o
g
2
N multiplications. Due to the fact that the original linear equation of biorthogonal relationship can be split into a unrelated subequation sets in the critical sampling case and a
β subequation sets in the oversampling case, FFT method can be utilized to compute analysis window both in the critical sampling case and in the oversampling case. The computational complexity of the single subequation set which carries Δ
ω-point FFT and Δ
ω-point inverse FFT (IFFT). The computational complexity of λ is at order of β
Δ
ω in the oversampling case while it is zero in the critical sampling case. Therefore, as mentioned above, the computational complexity of proposed approach is equal to that of total a subequation set, which is at the order of(47)
a
×
2
Δ
ω
log
2
⁡
Δ
ω
=
2
L
×
log
2
⁡
Δ
ω
,in the critical sampling case and(48)
a
×
β
×
2
Δ
ω
log
2
⁡
Δ
ω
+
β
Δ
ω
=
2
L
log
2
⁡
Δ
ω
+
L
,in the oversampling case. The comparison of computational complexity and numerical experiments between proposed approach and existing methods have been given in Tables 1 and 2 which clearly shows that the total number of multiplications of proposed approach is less than that of others in both the critical sampling case and the oversampling case. In Tables 1 and 2, the symbols Δ
ω
¯, CS, and OS denote 2
Δ
ω
-
1, the critical sampling case, and the oversampling case, respectively. In Table 2, a detailed numeric comparison experiments on the number of multiplications related to computational time between the proposed algorithm and existing methods under different Gabor sampling scheme are given by using the formula of computational complexity of each algorithm in Table 1, which clearly demonstrates the efficiency and the advantage of decreasing the computation of the proposed approach as compared to existing algorithms. Example for computing analysis window: a Gaussian synthesis window h
[
k
] with length L
=
256 is given (49) and shown in Figure 1.(49)
h
k
=
2
20
exp
⁡
-
π
k
-
127.5
20
2
.The analysis windows g
[
k
] in Figure 2 are computed by the proposed method, [9, 10] in the critical sampling case, with Δ
M
=
16, Δ
ω
=
16 and the oversampling rate β
=
Δ
M
/
Δ
ω
=
1. The analysis windows g
[
k
] in Figures 3 and 4 are computed by the proposed method [9, 10] in the oversampling case, with the oversampling rate β
=
Δ
M
/
Δ
ω
=
4 (Δ
M
=
32, Δ
ω
=
8) and 8 (Δ
M
=
32, Δ
ω
=
4), respectively. The similarity between the synthesis window g
[
k
] and its corresponding analysis window h
[
k
] is proportional to the oversampling rate β, the reason being similar to that given in [30]. The proposed algorithm for the reconstruction of the original signal is also simulated, which is virtually error-free reconstruction (MSE = 1
0
-
18).Table 1
Comparison of computational complexity between proposed approach and other existing methods.
References
Computational complexity
Applicability
[9]
Δ
ω
3
L
Δ
M
+
2
L
×
Δ
ω
2
+
L
×
Δ
ω
CS, OS
[10]
Δ
ω
-
L
Δ
M
3
+
2
L
×
Δ
ω
-
L
Δ
M
2
+
L
×
Δ
ω
-
L
Δ
M
CS, OS
[11]
2
L
×
l
o
g
2
Δ
ω,
CS, OS
(
β
+
2
)
L
×
l
o
g
2
Δ
ω
+
β
L
Proposed algorithm
2
L
×
l
o
g
2
Δ
ω,
CS, OS
2
L
×
l
o
g
2
Δ
ω
+
LTable 2
Numerical comparison of multiplications between proposed approach and other existing methods.
L
Δ
M
Δ
ω
β
Total number of multiplications
Applicability
[9]
[10]
[11]
Proposed
algorithm
256
32
32
1
794624
258209280
2560
2560
CS
64
16
4
151552
9810880
7168
2304
OS
256
8
32
35328
122415
34304
1792
OS
512
64
64
1
6324224
2106322432
6144
6144
CS
128
16
8
286720
17715136
24576
4608
OS
512
8
64
70144
241455
134144
3584
OS
1024
128
128
1
50462720
17014709760
14336
14336
CS
256
32
8
2260992
146317248
59392
11264
OS
1024
16
64
544768
2029663
335872
9216
OSFigure 1
A Gaussian synthesis windowh
[
k
], L
=
256.Figure 2
Analysis windowsg
[
k
] in the critical case (Δ
M
=
16, Δ
ω
=
16, β
=
1) obtained by the proposed method [9, 10].
(a)
(b)
(c)Figure 3
Analysis windowsg
[
k
] in the oversampling case (Δ
M
=
32, Δ
ω
=
8, β
=
4) obtained by the proposed method [9, 10].
(a)
(b)
(c)Figure 4
Analysis windowsg
[
k
] in the oversampling case (Δ
M
=
32, Δ
ω
=
4, β
=
8) obtained by the proposed method [9, 10].
(a)
(b)
(c)


## 5. Conclusion

The DGT for long-periodic/infinite signal sequences has become an important time-frequency analysis tool in many real-time applications, which can use the short window to process and analyze the long-periodic signal sequences. This paper proposed an effective approach to calculate the analysis window of DGT for long-periodic sequences, in which the original biorthogonal equation can be decomposed into a certain number of linear subequation sets that convolution operators and FFT could be utilized to obtain the analysis window for arbitrary given synthesis window function. The computational complexity analysis and comparison between proposed approach and existing methods have been shown in a comparative study described in Section4, which clearly indicates that the proposed approach is more competitive against the existing algorithms. In addition, the numerical experiments have been given to demonstrate the efficiency and validity of proposed approach, which make the long-periodic DGT attractive for real-time signal processing and analysis.



---

*Source: 9039240-2018-05-15.xml*