# Estimating Frequency by Interpolation Using Least Squares Support Vector Regression

Authors: Changwei Ma
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Discrete Fourier transform- (DFT-) based maximum likelihood (ML) algorithm is an important part of single sinusoid frequency estimation. As signal to noise ratio (SNR) increases and is above the threshold value, it will lie very close to Cramer-Rao lower bound (CRLB), which is dependent on the number of DFT points. However, its mean square error (MSE) performance is directly proportional to its calculation cost. As a modified version of support vector regression (SVR), least squares SVR (LS-SVR) can not only still keep excellent capabilities for generalizing and fitting but also exhibit lower computational complexity. In this paper, therefore, LS-SVR is employed to interpolate on Fourier coefficients of received signals and attain high frequency estimation accuracy. Our results show that the proposed algorithm can make a good compromise between calculation cost and MSE performance under the assumption that the sample size, number of DFT points, and resampling points are already known.


---

## Body

## 1. Introduction

Estimating frequency of a single sinusoid based on discrete Fourier transform (DFT) has attracted considerable attentions for many decades. Rife and Boorstyn exploited the relationship of maximum likelihood estimator (MLE) to DFT and proposed a frequency domain periodogram (FDP) algorithm having two stages: coarse search and fine search [1]. In order to reduce the calculation cost, the frequency step of coarse search is appropriately broadened. As a result, the absolute frequency value is usually not in the DFT points. Hence, a fine search will be necessary for higher frequency estimation accuracy.A great deal of fine search algorithms has erupted mainly from two sides: the dichotomous search and interpolation on Fourier coefficients. During the former, an iterative binary search for the true signal frequency has been presented, which is particularly suited for digital signal processing (DSP) implementation [2]. In [3], the same authors have proposed a number of hybrid estimators that combine the dichotomous search with various interpolation techniques in order to reduce the computational complexity at the expense of acquisition range; and other modified dichotomous search frequency estimators have been addressed in [4–6]. In the latter, complex Fourier coefficients have been utilized to interpolate the true signal frequency between the maximum and the second highest bin [7]. However, it has been shown to have a frequency dependent performance [8]. Two improved estimators have been proposed, which were implemented iteratively [9, 10]. Rational combination of three spectrum lines (RCTSL) has been employed as the fine estimation because of its constant combinational weights in least square approximation [11]. Other methods used for interpolation include Lagrange interpolator [12], L-filter DFT [13], nonlinear filter [14], Kaiser window [15], trigonometric polynomial interpolator [16], and narrowband approximation [17]. However, all of the DFT-based algorithms attain better mean square error (MSE) performance at the expense of calculation cost.As the concrete implementation of statistical learning theory (SLT) and structure risk minimization (SRM) principle, SVR overcomes the overfitting and local minimum problems currently existing in artificial neural network (ANN). Least squares support vector regression (LS-SVR) has the improvements of support vector regression (SVR): inequality constraint is substituted by equality one; a squared loss function is taken for the error variable. Consequently, its good generalizing and learning capabilities are exploited for interpolation on Fourier coefficients, and a novel DFT-based frequency estimation algorithm adopting LS-SVR for fine search is proposed. Our results show that under the assumption that the sample size, number of DFT points, and resampling points are already known, the proposed algorithm can derive low calculation cost while still keeping good MSE performance.The remainder of this paper is organized as follows. Section2 concretely describes the process of our algorithm. In Section 3, interpolation by LS-SVR is analyzed, and its parameters are selected properly to improve generalization capability. Section 4 shows the results of simulations and experiments. The paper is finally concluded in Section 5.


## 2. The Proposed Algorithm

### 2.1. Signal Model

The sinusoid signal polluted by noise is modeled as(1)
r
n
=
A
e
j
2
π
f
n
+
θ
+
w
n
,
n
=
0
,
…
,
N
-
1
.Here, A
>
0, f
∈
[
-
0.5,0.5
), and θ
∈
[
-
π
,
π
) are the amplitude, deterministic but unknown frequency, and initial phase, respectively; w
n is an independent complex additive white Gaussian noise (AWGN) with zero mean and variance σ
2; N is the sample size.


### 2.2. An Interpolation by LS-SVR in DFT-Based Frequency Estimation Algorithm

The key idea proposed in [1] is exploited and a two-step algorithm including coarse search and fine search is proposed. At first, FDP algorithm is employed and the number of DFT points is extended to K by appending K
-
N zeros. Now, the frequency step is 1
/
K, and (2)
m
=
arg
⁡
max
k
⁡
R
f
k
,
k
=
0
,
…
,
K
-
1
,where R
f
k
=
∑
n
=
0
N
-
1
r
n
e
-
j
2
π
f
k
n, f
k
=
k
/
K. For the sake of convenience of fast Fourier transform (FFT) calculation, K is usually set to 2
N
,
4
N
,
8
N
,
….Secondly, a training setS
=
x
n
,
y
n
∣
n
=
1
,
…
,
K is constructed and LS-SVR is utilized to fit it, where x
n
=
n
-
1 and y
n
=
R
n
-
1. Because y
n is a complex series and LS-SVR is only suitable for real number, y
n is divided into real and image part.(
1
) Assuming that f
r
e
a
l
(
x
)
=
(
w
r
e
a
l
·
ϕ
r
e
a
l
(
x
)
)
+
b
r
e
a
l insofar as for ε to completely fit all elements of S
r
e
a
l
=
(
x
n
r
e
a
l
,
y
n
r
e
a
l
)
∣
n
=
1
,
…
,
K, where x
n
r
e
a
l
=
x
n
=
n
-
1, y
n
r
e
a
l
=
R
e
y
n
=
R
e
R
n
-
1, R
e
· is the operation of taking real part, · is an inner product operator, and ϕ
r
e
a
l
· is a nonlinear mapping from low to high dimension feature space. ε-insensitive loss function is defined as(3)
L
y
i
real
,
f
real
x
i
real
=
y
i
real
-
f
real
x
i
real
ε
=
0
,
y
i
real
-
f
real
x
i
real
≤
ε
y
i
real
-
f
real
x
i
real
-
ε
,
else
,
i
=
1
,
…
,
K
,where ε is the coefficient of insensitive loss function. d
i
r
e
a
l is denoted as the distance from point (
x
i
r
e
a
l
,
y
i
r
e
a
l
)
∈
S
r
e
a
l to f
r
e
a
l
(
x
):(4)
d
i
real
=
w
real
·
ϕ
real
x
i
real
+
b
real
-
y
i
real
1
+
w
real
2
≤
ε
1
+
w
real
2
,
i
=
1
,
…
,
K
.According to (4), f
r
e
a
l
(
x
) is optimized through maximizing ε
/
1
+
w
r
e
a
l
2, that is minimizing w
r
e
a
l
2. Thereby, LS-SVR is presented as(5)
min
⁡
J
w
real
,
b
real
=
1
2
w
real
2
,
s.t.
w
real
·
ϕ
real
x
i
real
+
b
real
-
y
i
real
≤
ε
,
i
=
1
,
…
,
K
.In fact, fitting errors larger thanε always exist. By introducing error variables e
i
r
e
a
l and least squares (LS) method, (5) is converted into(6)
min
⁡
J
w
real
,
b
real
=
1
2
w
real
2
+
C
2
∑
i
=
1
K
e
i
real
2
s.t.
y
i
real
=
w
real
·
ϕ
real
x
i
real
+
b
real
+
e
i
real
,
i
=
1
,
…
,
K
,where penalty factor C is a positive constant to take compromise in LS-SVR’s generalization capability and fitting errors which are denoted by the first and second item of J
w
r
e
a
l
,
b
r
e
a
l, respectively.Next step, using Lagrange multiplier method and replacingϕ
r
e
a
l
(
x
i
r
e
a
l
)
·
ϕ
r
e
a
l
(
x
j
r
e
a
l
) with kernel function K
(
x
i
r
e
a
l
,
x
j
r
e
a
l
),(7)
0
1
T
1
Q
+
1
C
I
b
real
α
real
=
0
Y
real
,where 1
=
1
,
…
,
1
︸
K
T, Y
r
e
a
l
=
y
1
r
e
a
l
,
…
,
y
K
r
e
a
l
T, α
r
e
a
l
=
α
1
r
e
a
l
,
…
,
α
K
r
e
a
l
T, I is an unit matrix with K orders, ·
T is a transpose operator, α
1
r
e
a
l
,
…
,
α
K
r
e
a
l are Lagrange multipliers, and Q is a kernel function matrix. Radius basis function (RBF) is adopted in this study, so(8)
Q
i
j
=
K
x
i
real
,
x
j
real
=
exp
⁡
-
x
i
real
-
x
j
real
2
h
2
=
exp
⁡
-
i
-
j
2
h
2
,where Q
i
j is the i
,
jth element of Q and positive constant h is the width of RBF.Solving (7) and deriving the regression as(9)
f
real
x
=
w
real
·
ϕ
real
x
+
b
real
=
∑
i
=
1
K
α
i
real
K
x
i
real
,
x
+
b
real
.(
2
) Assuming that f
i
m
a
g
(
x
)
=
w
i
m
a
g
·
ϕ
i
m
a
g
x
+
b
i
m
a
g insofar as for ε to completely fit all elements of S
i
m
a
g
=
x
n
i
m
a
g
,
y
n
i
m
a
g
∣
n
=
1
,
…
,
K, where x
n
i
m
a
g
=
x
n
=
n
-
1, y
n
i
m
a
g
= and Im
⁡
y
n
=
Im
⁡
R
n
-
1, Im
⁡
· is the operation of taking image part, deriving f
i
m
a
g
(
x
)
=
(
w
i
m
a
g
·
ϕ
i
m
a
g
(
x
)
)
+
b
i
m
a
g
=
∑
i
=
1
K
α
i
i
m
a
g
K
(
x
i
i
m
a
g
,
x
)
+
b
i
m
a
g as (
1
).(
3
)  f
(
x
)
=
f
r
e
a
l
(
x
)
+
j
×
f
i
m
a
g
(
x
).Then,f
(
x
) is interpolated by 1
/
L interval between m
-
1 and m
+
1, where L is usually set to 2,4
,
…. It means that z
l
=
m
-
1
+
l
/
L, l
=
1
,
…
,
2
L
-
1 are substituted into f
x.In the end, searching the seriesf
z
l and deriving f
^
L
S
-
S
V
R
=
(
(
L
(
m
-
1
)
+
arg
max
l
=
1
,
…
,
2
L
-
1
⁡
f
(
z
l
)
)
/
K
L
)
-
0.5
0.5 as the ultimate frequency estimation value, where the modulo-1 operation ·
-
0.5
0.5 means that the value is reduced to the interval -
0.5,0.5.


## 2.1. Signal Model

The sinusoid signal polluted by noise is modeled as(1)
r
n
=
A
e
j
2
π
f
n
+
θ
+
w
n
,
n
=
0
,
…
,
N
-
1
.Here, A
>
0, f
∈
[
-
0.5,0.5
), and θ
∈
[
-
π
,
π
) are the amplitude, deterministic but unknown frequency, and initial phase, respectively; w
n is an independent complex additive white Gaussian noise (AWGN) with zero mean and variance σ
2; N is the sample size.


## 2.2. An Interpolation by LS-SVR in DFT-Based Frequency Estimation Algorithm

The key idea proposed in [1] is exploited and a two-step algorithm including coarse search and fine search is proposed. At first, FDP algorithm is employed and the number of DFT points is extended to K by appending K
-
N zeros. Now, the frequency step is 1
/
K, and (2)
m
=
arg
⁡
max
k
⁡
R
f
k
,
k
=
0
,
…
,
K
-
1
,where R
f
k
=
∑
n
=
0
N
-
1
r
n
e
-
j
2
π
f
k
n, f
k
=
k
/
K. For the sake of convenience of fast Fourier transform (FFT) calculation, K is usually set to 2
N
,
4
N
,
8
N
,
….Secondly, a training setS
=
x
n
,
y
n
∣
n
=
1
,
…
,
K is constructed and LS-SVR is utilized to fit it, where x
n
=
n
-
1 and y
n
=
R
n
-
1. Because y
n is a complex series and LS-SVR is only suitable for real number, y
n is divided into real and image part.(
1
) Assuming that f
r
e
a
l
(
x
)
=
(
w
r
e
a
l
·
ϕ
r
e
a
l
(
x
)
)
+
b
r
e
a
l insofar as for ε to completely fit all elements of S
r
e
a
l
=
(
x
n
r
e
a
l
,
y
n
r
e
a
l
)
∣
n
=
1
,
…
,
K, where x
n
r
e
a
l
=
x
n
=
n
-
1, y
n
r
e
a
l
=
R
e
y
n
=
R
e
R
n
-
1, R
e
· is the operation of taking real part, · is an inner product operator, and ϕ
r
e
a
l
· is a nonlinear mapping from low to high dimension feature space. ε-insensitive loss function is defined as(3)
L
y
i
real
,
f
real
x
i
real
=
y
i
real
-
f
real
x
i
real
ε
=
0
,
y
i
real
-
f
real
x
i
real
≤
ε
y
i
real
-
f
real
x
i
real
-
ε
,
else
,
i
=
1
,
…
,
K
,where ε is the coefficient of insensitive loss function. d
i
r
e
a
l is denoted as the distance from point (
x
i
r
e
a
l
,
y
i
r
e
a
l
)
∈
S
r
e
a
l to f
r
e
a
l
(
x
):(4)
d
i
real
=
w
real
·
ϕ
real
x
i
real
+
b
real
-
y
i
real
1
+
w
real
2
≤
ε
1
+
w
real
2
,
i
=
1
,
…
,
K
.According to (4), f
r
e
a
l
(
x
) is optimized through maximizing ε
/
1
+
w
r
e
a
l
2, that is minimizing w
r
e
a
l
2. Thereby, LS-SVR is presented as(5)
min
⁡
J
w
real
,
b
real
=
1
2
w
real
2
,
s.t.
w
real
·
ϕ
real
x
i
real
+
b
real
-
y
i
real
≤
ε
,
i
=
1
,
…
,
K
.In fact, fitting errors larger thanε always exist. By introducing error variables e
i
r
e
a
l and least squares (LS) method, (5) is converted into(6)
min
⁡
J
w
real
,
b
real
=
1
2
w
real
2
+
C
2
∑
i
=
1
K
e
i
real
2
s.t.
y
i
real
=
w
real
·
ϕ
real
x
i
real
+
b
real
+
e
i
real
,
i
=
1
,
…
,
K
,where penalty factor C is a positive constant to take compromise in LS-SVR’s generalization capability and fitting errors which are denoted by the first and second item of J
w
r
e
a
l
,
b
r
e
a
l, respectively.Next step, using Lagrange multiplier method and replacingϕ
r
e
a
l
(
x
i
r
e
a
l
)
·
ϕ
r
e
a
l
(
x
j
r
e
a
l
) with kernel function K
(
x
i
r
e
a
l
,
x
j
r
e
a
l
),(7)
0
1
T
1
Q
+
1
C
I
b
real
α
real
=
0
Y
real
,where 1
=
1
,
…
,
1
︸
K
T, Y
r
e
a
l
=
y
1
r
e
a
l
,
…
,
y
K
r
e
a
l
T, α
r
e
a
l
=
α
1
r
e
a
l
,
…
,
α
K
r
e
a
l
T, I is an unit matrix with K orders, ·
T is a transpose operator, α
1
r
e
a
l
,
…
,
α
K
r
e
a
l are Lagrange multipliers, and Q is a kernel function matrix. Radius basis function (RBF) is adopted in this study, so(8)
Q
i
j
=
K
x
i
real
,
x
j
real
=
exp
⁡
-
x
i
real
-
x
j
real
2
h
2
=
exp
⁡
-
i
-
j
2
h
2
,where Q
i
j is the i
,
jth element of Q and positive constant h is the width of RBF.Solving (7) and deriving the regression as(9)
f
real
x
=
w
real
·
ϕ
real
x
+
b
real
=
∑
i
=
1
K
α
i
real
K
x
i
real
,
x
+
b
real
.(
2
) Assuming that f
i
m
a
g
(
x
)
=
w
i
m
a
g
·
ϕ
i
m
a
g
x
+
b
i
m
a
g insofar as for ε to completely fit all elements of S
i
m
a
g
=
x
n
i
m
a
g
,
y
n
i
m
a
g
∣
n
=
1
,
…
,
K, where x
n
i
m
a
g
=
x
n
=
n
-
1, y
n
i
m
a
g
= and Im
⁡
y
n
=
Im
⁡
R
n
-
1, Im
⁡
· is the operation of taking image part, deriving f
i
m
a
g
(
x
)
=
(
w
i
m
a
g
·
ϕ
i
m
a
g
(
x
)
)
+
b
i
m
a
g
=
∑
i
=
1
K
α
i
i
m
a
g
K
(
x
i
i
m
a
g
,
x
)
+
b
i
m
a
g as (
1
).(
3
)  f
(
x
)
=
f
r
e
a
l
(
x
)
+
j
×
f
i
m
a
g
(
x
).Then,f
(
x
) is interpolated by 1
/
L interval between m
-
1 and m
+
1, where L is usually set to 2,4
,
…. It means that z
l
=
m
-
1
+
l
/
L, l
=
1
,
…
,
2
L
-
1 are substituted into f
x.In the end, searching the seriesf
z
l and deriving f
^
L
S
-
S
V
R
=
(
(
L
(
m
-
1
)
+
arg
max
l
=
1
,
…
,
2
L
-
1
⁡
f
(
z
l
)
)
/
K
L
)
-
0.5
0.5 as the ultimate frequency estimation value, where the modulo-1 operation ·
-
0.5
0.5 means that the value is reduced to the interval -
0.5,0.5.


## 3. Analyses

Taking the real part ofy
n, for example, now Y
r
e
a
l
=
y
1
r
e
a
l
,
…
,
y
K
r
e
a
l
T
=
R
e
R
0
,
…
,
R
e
R
K
-
1. And, from (7),(10)
b
real
=
1
K
T
Q
+
1
/
C
I
-
1
Y
real
1
K
T
Q
+
1
/
C
I
-
1
1
K
+
1
,
α
real
=
Q
+
1
C
I
-
1
Y
real
-
1
K
b
real
,where ·
-
1 is the inverse operation.Y
^
r
e
a
l
=
(
y
^
1
r
e
a
l
,
…
,
y
^
2
L
-
1
r
e
a
l
)
T
=
(
f
r
e
a
l
(
z
1
)
,
…
,
f
r
e
a
l
(
z
2
L
-
1
)
)
T is defined as LS-SVR’s output of Y
r
e
a
l, and by substituting (10) into (9), we have(11)
Y
^
real
=
Q
′
α
real
+
1
2
L
-
1
b
real
=
Q
′
Q
+
1
C
I
-
1
Y
real
+
I
′
-
Q
′
Q
+
1
C
I
-
1
1
K
b
real
=
Q
′
Q
+
1
C
I
-
1
+
I
′
-
Q
′
Q
+
1
C
I
-
1
1
K
1
K
T
Q
+
1
/
C
I
-
1
1
K
T
Q
+
1
/
C
I
-
1
1
K
·
Y
real
=
β
Y
real
,where 1
2
L
-
1
=
1
,
…
,
1
︸
2
L
-
1
T, Q
i
j
′
=
K
z
i
,
x
j
r
e
a
l is the i
,
jth element of matrix Q
′ with 2
L
-
1 rows and K columns, I
′
=
1
2
L
-
1
0
2
L
-
1
×
K
-
1, 1
2
L
/
K
-
1
=
1
,
…
,
1
︸
2
L
/
K
-
1
T, and 0
(
2
L
-
1
)
×
(
K
-
1
) is an all-zero matrix with 2
L
-
1 rows and K
-
1 columns.From (11), the LS-SVR process can be regarded as a linear interpolator whose output is the linear weighted sum of all inputs, where the weighted coefficients are dependent on β
=
{
Q
′
Q
+
(
1
/
C
)
I
-
1 + I
′
-
Q
′
Q
+
(
1
/
C
)
I
-
1
(
1
K
1
K
T
Q
+
(
1
/
C
)
I
-
1
/
1
K
T
Q
+
(
1
/
C
)
I
-
1
1
K
)
}, which means it is totally related with Q, Q
′ and C.WhenC decreases rapidly, Q
+
(
1
/
C
)
I
≈
(
1
/
C
)
I, β
≈
1
K
1
K
T
/
K. From (11), y
^
n
r
e
a
l at the different moments keep the same value obviously, which means the LS-SVR process can not fit Y
r
e
a
l accurately. Hence, C is set as large as possible. f
=
0.1, θ
=
0, N
=
32, K
=
2
N, L
=
8, and h
=
1 are set and the number of Monte Carlo experiments is 10000. Figure 1 illustrates the impact of C on the estimation performance, which is consistent with all analyses above. When C is larger than 100, its MSE performance will almost not increase anymore, so C
=
100 is set.Figure 1
Impact ofC on MSE with f
=
0.1, θ
=
0, N
=
32, K
=
2
N, L
=
8, and h
=
1.At the same time, according toK
(
x
i
r
e
a
l
,
x
j
r
e
a
l
)
=
e
x
p
⁡
[
-
(
i
-
j
)
2
/
h
2
] and the definitions of Q
i
j and Q
i
j
′ in (8) and (11), it is concluded that(12)
lim
h
→
0
⁡
Q
i
j
=
1
,
if
i
=
j
0
,
otherwise,
lim
h
→
0
⁡
Q
i
j
′
=
1
,
if
i
=
L
,
j
=
1
0
,
otherwise.So when(13)
C
=
100
,
N
=
32
,
lim
h
→
0
⁡
β
i
j
=
1
,
if
i
=
L
,
j
=
1
0
,
if
i
=
L
,
except
j
=
1
1
K
,
otherwise
,where β
i
j is i
,
jth element of matrix β with 2
L
-
1 rows and K columns. It means now the LS-SVR process can only make ensure the accuracy of spectrum of original signals but not interpolate effectively. On the contrary, as a result of lim
h
→
+
∞
⁡
Q
i
j
=
1, lim
h
→
+
∞
⁡
Q
i
j
′
=
1, now lim
h
→
+
∞
⁡
β
i
j
=
1
/
K, which means that now the LS-SVR process can also not fit Y
r
e
a
l accurately. Everything is as in Figure 1 except that C
=
100; Figure 2 illustrates the impact of h on the estimation performance when h is 0.1, 1, 10, and 100, respectively, which is consistent with all analyses above. So h
=
1 is set.Figure 2
Impact ofh on MSE with f
=
0.1, θ
=
0, N
=
32, K
=
2
N, L
=
8, and C
=
100.Assuming that the received signal isr
n
=
g
n
+
w
n, where g
n
=
A
e
x
p
j
2
π
f
n
+
θ
,
w
n are signal and noise components of r
n, the true interpolation value of spectrum of r
n at point z
l is(14)
R
z
l
=
1
K
∑
n
=
0
N
-
1
r
n
exp
⁡
-
j
2
π
n
z
l
K
=
1
K
∑
n
=
0
N
-
1
g
n
+
w
n
exp
⁡
-
j
2
π
n
z
l
K
=
1
K
∑
n
=
0
N
-
1
g
n
exp
⁡
-
j
2
π
n
z
l
K
+
1
K
∑
n
=
0
N
-
1
w
n
exp
⁡
-
j
2
π
n
z
l
K
.At the same time, the estimating interpolation value of spectrum ofr
n at point z
l is attained through LS-SVR. Consider(15)
f
z
l
=
f
real
z
l
+
j
f
imag
z
l
=
∑
i
=
1
K
β
l
i
Re
⁡
R
i
-
1
+
j
∑
i
=
1
K
β
l
i
Im
⁡
R
i
-
1
=
∑
i
=
1
K
β
l
i
R
i
-
1
=
∑
i
=
1
K
β
l
i
1
K
∑
n
=
0
N
-
1
g
n
exp
⁡
-
j
2
π
n
i
-
1
K
+
1
K
∑
n
=
0
N
-
1
w
n
exp
⁡
-
j
2
π
n
i
-
1
K
=
1
K
·
∑
n
=
0
N
-
1
g
n
∑
i
=
1
K
β
l
i
exp
⁡
-
j
2
π
n
i
-
1
K
+
1
K
·
∑
n
=
0
N
-
1
w
n
∑
i
=
1
K
β
l
i
exp
⁡
-
j
2
π
n
i
-
1
K
.As a result, the error between (14) and (15) is(16)
e
z
l
=
R
z
l
-
f
z
l
=
1
K
∑
n
=
0
N
-
1
g
n
exp
⁡
-
j
2
π
n
z
l
K
-
∑
i
=
1
K
β
l
i
exp
⁡
-
j
2
π
n
i
-
1
K
+
1
K
·
∑
n
=
0
N
-
1
w
n
exp
⁡
-
j
2
π
n
z
l
K
-
∑
i
=
1
K
β
l
i
exp
⁡
-
j
2
π
n
i
-
1
K
,where the noise item w
z
l
=
(
1
/
K
)
∑
n
=
0
N
-
1
w
n
exp
⁡
(
-
j
2
π
n
z
l
/
K
)
-
∑
i
=
1
K
β
l
i
exp
⁡
-
j
2
π
n
i
-
1
/
K is still an independent complex AWGN. Its mean and variance are listed as follows:(17)
ξ
w
z
l
=
E
w
z
l
=
E
1
K
∑
n
=
0
N
-
1
w
n
exp
⁡
-
j
2
π
n
z
l
K
-
∑
i
=
1
K
β
l
i
exp
⁡
-
j
2
π
n
i
-
1
K
=
0
,
σ
w
2
z
l
=
E
w
z
l
-
E
w
z
l
2
=
E
w
l
2
=
σ
2
K
2
·
∑
n
=
0
N
-
1
exp
⁡
-
j
2
π
n
z
l
K
-
∑
i
=
1
K
β
l
i
exp
⁡
-
j
2
π
n
i
-
1
K
2
.Then, the mean and variance ofe
z
l are(18)
ξ
e
z
l
=
E
e
z
l
=
1
K
2
∑
n
=
0
N
-
1
g
n
exp
⁡
-
j
2
π
n
z
l
K
-
∑
i
=
1
K
β
l
i
exp
⁡
-
j
2
π
n
i
-
1
K
,
σ
e
2
z
l
=
E
e
z
l
-
E
e
z
l
2
=
E
w
z
l
-
E
w
z
l
2
=
σ
2
K
2
∑
n
=
0
N
-
1
exp
⁡
-
j
2
π
n
z
l
K
-
∑
i
=
1
K
β
l
i
exp
⁡
-
j
2
π
n
i
-
1
K
2
.Define(19)
E
σ
e
2
z
l
E
R
z
l
2
=
σ
2
E
∑
n
=
0
N
-
1
exp
⁡
-
j
2
π
n
z
l
/
K
-
∑
i
=
1
K
β
l
i
exp
⁡
-
j
2
π
n
i
-
1
/
K
2
E
∑
n
=
0
N
-
1
r
n
exp
⁡
-
j
2
π
n
z
l
/
K
2
,
E
ξ
e
z
l
2
E
R
z
l
2
=
E
∑
n
=
0
N
-
1
g
n
exp
⁡
-
j
2
π
n
z
l
/
K
-
∑
i
=
1
K
β
l
i
exp
⁡
-
j
2
π
n
i
-
1
/
K
2
E
∑
n
=
0
N
-
1
r
n
exp
⁡
-
j
2
π
n
z
l
/
K
2
.Everything is as in Figure1 except that C
=
100, L
=
4, and S
N
R
=
0 dB; the values of (19) with different z
l are calculated:(20)
E
σ
e
2
z
1
E
ξ
e
z
1
2
,
…
,
E
σ
e
2
z
7
E
ξ
e
z
7
2
T
=
7.59
×
10
-
5
,
1.04
×
10
-
4
,
7.43
×
10
-
5
,
4.51
×
10
-
5
,
7.39
×
10
-
5
,
1.03
×
10
-
4
,
7.48
×
10
-
5
T
,
E
ξ
e
z
1
2
E
R
z
1
2
,
…
,
E
ξ
e
z
7
2
E
R
z
7
2
T
=
2.32
×
10
-
6
,
4.27
×
10
-
6
,
2.39
×
10
-
6
,
1.23
×
10
-
6
,
4.52
×
10
-
6
,
7.15
×
10
-
6
,
4.69
×
10
-
6
T
.The values of (20) are very small, which means when SNR is higher than threshold, the estimating value through LS-SVR and true value of spectrum of r
n at point z
l are almost the same. It validates the validity of interpolation in our proposed algorithm.


## 4. Simulations and Experiments

The proposed algorithm entitled LS-SVR is compared with other fives: FDP proposed in [1]; dichotomous search (DS) proposed in [2]; modify dichotomous search (Modify DS) proposed in [4]; iterative interpolation on Fourier coefficients (IIFC) proposed in [9]; RCTSL proposed in [11]. Analyzing these five algorithms, it is known that the MSE performances of FDP and RCTSL algorithms will be improved as their DFT points increase, and the MSE performances of DS, Modified DS, and IIFC algorithms will be improved as their iterative numbers increase. In order to compare these algorithms’ calculation cost under nearly the same precondition, K
=
32
N in FDP, K
=
2
N, Q
D
S
=
20 in DS, Q
M-DS
=
20 in Modified DS, Q
I
I
F
C
=
10 in IIFC, K
=
8
N in RCTSL, K
=
2
N, and L
=
8 in LS-SVR are set to keep their MSE performance almost the same.


### 4.1. Mean Performance

Everything is as in Figure1 except that C
=
100. Figure 3 illustrates the mean of these six algorithms, while SNR is −4 dB and 0 dB, respectively. Obviously, when SNR is low, the unbiased performances of Modified DS and IIFC algorithms are worse than the other four.Figure 3
(a) Mean withθ
=
0, N
=
32, K
=
2
N, L
=
8, C
=
100, h
=
1, and S
N
R
=
-
4
d
B. (b) Mean with θ
=
0, N
=
32, K
=
2
N, L
=
8, C
=
100, h
=
1, and S
N
R
=
0
d
B.
(a)
(b)


### 4.2. Frequency Estimation Performance

As in Figure3, Figure 4 illustrates the MSE curves of these six algorithms versus SNR. From Figure 4, the threshold values of DS, Modified DS, and IIFC algorithms are higher than other three ones. And, these six algorithms’ MSEs are kept almost the same when they are all above their threshold values, where LS-SVR one is the best one.Figure 4
(a) MSE of frequency estimation versus SNR withf
=
0.1, θ
=
0, N
=
32, K
=
2
N, L
=
8, C
=
100, h
=
1, and S
N
R
∈
-
6,3
d
B. (b) MSE of frequency estimation versus SNR with f
=
0.1, θ
=
0, N
=
32, K
=
2
N, L
=
8, C
=
100,  h
=
1,  and S
N
R
∈
0,2
d
B.
(a)
(b)


### 4.3. Impact of DFT PointsK

As in Figure3, the MSE curves of LS-SVR algorithm versus SNR are plotted in Figure 5, while K is N, 2
N, 4
N, and 8
N, respectively. Now, the sample size and interpolation times are fixed. From Figure 5, when K
=
N, its MSE value will not approach Cramer-Rao lower bound (CRLB) as SNR increases, which means now the LS-SVR algorithm is ineffective; when K
=
2
N, 4
N, and 8
N, their MSE values are nearly the same, and the K
=
2
N condition is a little better than the two others. The reason is the fact that the proposed interpolation process is fulfilled by LS-SVR fitting in the paper; too many interpolation numbers during the adjacent DFT points will result in overfitting. Besides, the calculation cost of K
=
2
N is less than K
=
4
N and 8
N; hence K
=
2
N is set in this paper.Figure 5
(a) Impact ofK on MSE with f
=
0.1, θ
=
0, N
=
32, L
=
8, C
=
100, h
=
1, and S
N
R
∈
-
6,3
d
B. (b) Impact of K on MSE with f
=
0.1, θ
=
0, N
=
32, L
=
8, C
=
100, h
=
1, and S
N
R
∈
-
1,1
d
B.
(a)
(b)


### 4.4. Impact of Interpolation TimesL

As in Figure3, the MSE curves of LS-SVR algorithm versus SNR are plotted in Figure 6, while L is 2, 4, 8, and 16, respectively. Now, the sample size and DFT points are fixed. From Figure 6, its MSE performance will be improved as L increases.Figure 6
(a) Impact ofL on MSE with f
=
0.1, θ
=
0, N
=
32, K
=
2
N, C
=
100, h
=
1, and S
N
R
∈
-
6,3
d
B. (b) Impact of L on MSE with f
=
0.1, θ
=
0, N
=
32, K
=
2
N, C
=
100, h
=
1, and S
N
R
∈
-
1,1
d
B.
(a)
(b)


### 4.5. Impact of Sample SizeN

As in Figure3, the MSE curves of LS-SVR algorithm versus SNR are plotted in Figure 7, while N is 8, 16, 32, and 64, respectively. Now, the interpolation times are fixed, and DFT points are directly proportional to N with a fixed value. From Figure 7, its threshold value will decrease and MSE performance will be improved as N increases.Figure 7
Impact ofN on MSE with f
=
0.1, θ
=
0, K
=
2
N, L
=
8, C
=
100, h
=
1, and S
N
R
∈
-
6,3
d
B.


### 4.6. Calculation Cost

Calculation cost is an important factor to impact the real time of frequency estimation algorithm. The calculation cost of these six algorithms is analyzed through calculating the operation number of their real multiplication and real addition under the same parameter setting as Figure3.The DFT value withK points can be derived by fast Fourier transform (FFT), that is, K
log
2
⁡
K
/
2 complex multiplication and K
log
2
⁡
K complex addition. Besides, 1 complex multiplication needs 4 real multiplications and 2 real additions; 1 complex addition needs 2 real additions. In order to decrease the calculation cost, FDP algorithm also integrates coarse and fine search, where the point of coarse search is 2
N. Contemporarily, 1 modular operation needs 2 real multiplications and 1 real addition; 1 comparing operation needs 1 real addition. Consequently, the operation numbers of real multiplication M
F
D
P and real addition A
F
D
P of FDP algorithm are
(21)
M
FDP
=
32
N
log
2
⁡
32
N
2
×
4
+
2
N
×
2
+
2
×
16
-
2
×
2
=
64
N
log
2
⁡
N
+
324
N
+
60
=
20668
,
A
FDP
=
32
N
log
2
⁡
32
N
2
×
2
+
32
N
log
2
⁡
32
N
×
2
+
2
N
+
2
N
-
1
+
2
×
16
-
2
+
2
×
16
-
2
=
96
N
log
2
⁡
N
+
484
N
+
59
=
30907
.The coarse search of DS algorithm adopts FDP one withK
=
2
N points, so it needs 4
N
log
2
⁡
N
+
8
N real multiplication and 6
N
log
2
⁡
N
+
10
N
-
1 real addition. Also, 1 iteration needs N complex multiplication, N
-
1 complex addition, 4 real additions, and 1 modular operation. Accordingly, the operation numbers of real multiplication M
D
S and real addition A
D
S of DS algorithm are(22)
M
DS
=
4
N
log
2
⁡
N
+
8
N
+
N
×
4
+
2
Q
DS
=
4
N
log
2
⁡
N
+
88
N
+
40
=
3496
,
A
DS
=
6
N
log
2
⁡
N
+
10
N
-
1
+
N
×
2
+
N
-
1
×
2
+
4
+
1
Q
DS
=
6
N
log
2
⁡
N
+
90
N
+
59
=
3899
.The coarse search of Modified DS algorithm adopts FDP one withK
=
N points, so it needs 2
N
log
2
⁡
N
+
2
N real multiplication and 3
N
log
2
⁡
N
+
2
N
-
1 real addition. Also, 1 iteration needs 2
N complex multiplication, 2
N
-
2 complex addition, 6 real additions, and 2 modular operations. Accordingly, the operation numbers of real multiplication M
M
-
D
S and real addition A
M-DS of Modified DS algorithm are(23)
M
M-DS
=
2
N
log
2
⁡
N
+
2
N
+
2
N
×
4
+
2
×
2
Q
M-DS
=
2
N
log
2
⁡
N
+
162
N
+
80
=
5584
,
A
M-DS
=
3
N
log
2
⁡
N
+
2
N
-
1
+
2
N
×
2
+
2
N
-
2
×
2
+
6
+
1
Q
M-DS
=
3
N
log
2
⁡
N
+
162
N
+
59
=
5723
.The coarse search of IIFC algorithm adopts FDP one withK
=
N points, so it needs 2
N
log
2
⁡
N
+
2
N real multiplication and 3
N
log
2
⁡
N
+
2
N
-
1 real addition. Also, 1 iteration needs 2
N complex multiplication, 2
N
-
2 complex addition, 6 real additions, and 2 modular operations. Accordingly, the operation numbers of real multiplication M
I
I
F
C and real addition A
I
I
F
C of IIFC algorithm are(24)
M
IIFC
=
2
N
log
2
⁡
N
+
2
N
+
2
N
+
1
×
4
+
1
Q
IIFC
=
2
N
log
2
⁡
N
+
82
N
+
50
=
2994
,
A
IIFC
=
3
N
log
2
⁡
N
+
2
N
-
1
+
2
N
+
1
×
2
+
2
N
×
2
+
6
Q
IIFC
=
3
N
log
2
⁡
N
+
82
N
+
79
=
3183
.The coarse search of RCTSL algorithm adopts FDP one withK
=
4
N points, so it needs 8
N
log
2
⁡
N
+
24
N real multiplication and 12
N
log
2
⁡
N
+
32
N
-
1 real addition. Also, it needs 7 real multiplications and 4 real additions. Accordingly, the operation numbers of real multiplication M
R
C
T
S
L and real addition A
R
C
T
S
L of RCTSL algorithm are(25)
M
RCTSL
=
8
N
log
2
⁡
N
+
24
N
+
7
=
2055
,
A
RCTSL
=
12
N
log
2
⁡
N
+
32
N
-
1
+
4
=
12
N
log
2
⁡
N
+
32
N
+
3
=
2947
.The coarse search of LS-SVR algorithm adopts FDP one withK
=
2
N points, so it needs 4
N
log
2
⁡
N
+
8
N real multiplication and 6
N
log
2
⁡
N
+
10
N
-
1 real addition. Also, if N, K, and L are fixed, matrices Q and Q
′ are already known, so the value of matrix β with 2
L
-
1 rows and K columns can be calculated. As a result, it only has to add the calculation cost for (11) and comparison of 2
L
-
1 real number. It is worth stressing that (11) is used for real and image part, respectively. Accordingly, the operation numbers of real multiplication M
L
S
-
S
V
R and real addition A
L
S
-
S
V
R of LS-SVR algorithm are(26)
M
LS-SVR
=
4
N
log
2
⁡
N
+
8
N
+
2
N
×
2
×
8
-
1
×
2
+
2
×
8
-
1
×
2
=
4
N
log
2
⁡
N
+
68
N
+
30
=
2846
,
A
LS-SVR
=
6
N
log
2
⁡
N
+
10
N
-
1
+
2
N
-
1
×
2
×
8
-
1
×
2
+
2
×
8
-
1
+
2
×
8
-
1
=
6
N
log
2
⁡
N
+
70
N
-
1
=
3199
.As in Figure7, the operation numbers of real multiplication and real addition of these six algorithms are listed in Table 1. Additionally, N
=
32 is taken, for example, to compare. From Table 1, the calculation cost of FDP one is much larger than the other five; second larger is Modified DS one and the next is DS one. The calculation cost of LS-SVR one is between IIFC and RCTSL one, and the distances between each of two are very small.Table 1
Calculation cost of all these six algorithms.
Real multiplication
N
=
32
Real addition
N
=
32
FDP
64
N
log
2
⁡
N
+
324
N
+
60
20668
96
N
log
2
⁡
N
+
484
N
+
59
30907
DS
4
N
log
2
⁡
N
+
88
N
+
40
3496
6
N
log
2
⁡
N
+
90
N
+
59
3899
Modified DS
2
N
log
2
⁡
N
+
162
N
+
80
5584
3
N
log
2
⁡
N
+
162
N
+
59
5723
IIFC
2
N
log
2
⁡
N
+
82
N
+
50
2994
3
N
log
2
⁡
N
+
82
N
+
79
3183
RCTSL
8
N
log
2
⁡
N
+
24
N
+
7
2055
12
N
log
2
⁡
N
+
32
N
+
3
2947
LS-SVR
4
N
log
2
⁡
N
+
68
N
+
30
2846
6
N
log
2
⁡
N
+
70
N
-
1
3199


## 4.1. Mean Performance

Everything is as in Figure1 except that C
=
100. Figure 3 illustrates the mean of these six algorithms, while SNR is −4 dB and 0 dB, respectively. Obviously, when SNR is low, the unbiased performances of Modified DS and IIFC algorithms are worse than the other four.Figure 3
(a) Mean withθ
=
0, N
=
32, K
=
2
N, L
=
8, C
=
100, h
=
1, and S
N
R
=
-
4
d
B. (b) Mean with θ
=
0, N
=
32, K
=
2
N, L
=
8, C
=
100, h
=
1, and S
N
R
=
0
d
B.
(a)
(b)


## 4.2. Frequency Estimation Performance

As in Figure3, Figure 4 illustrates the MSE curves of these six algorithms versus SNR. From Figure 4, the threshold values of DS, Modified DS, and IIFC algorithms are higher than other three ones. And, these six algorithms’ MSEs are kept almost the same when they are all above their threshold values, where LS-SVR one is the best one.Figure 4
(a) MSE of frequency estimation versus SNR withf
=
0.1, θ
=
0, N
=
32, K
=
2
N, L
=
8, C
=
100, h
=
1, and S
N
R
∈
-
6,3
d
B. (b) MSE of frequency estimation versus SNR with f
=
0.1, θ
=
0, N
=
32, K
=
2
N, L
=
8, C
=
100,  h
=
1,  and S
N
R
∈
0,2
d
B.
(a)
(b)


## 4.3. Impact of DFT PointsK

As in Figure3, the MSE curves of LS-SVR algorithm versus SNR are plotted in Figure 5, while K is N, 2
N, 4
N, and 8
N, respectively. Now, the sample size and interpolation times are fixed. From Figure 5, when K
=
N, its MSE value will not approach Cramer-Rao lower bound (CRLB) as SNR increases, which means now the LS-SVR algorithm is ineffective; when K
=
2
N, 4
N, and 8
N, their MSE values are nearly the same, and the K
=
2
N condition is a little better than the two others. The reason is the fact that the proposed interpolation process is fulfilled by LS-SVR fitting in the paper; too many interpolation numbers during the adjacent DFT points will result in overfitting. Besides, the calculation cost of K
=
2
N is less than K
=
4
N and 8
N; hence K
=
2
N is set in this paper.Figure 5
(a) Impact ofK on MSE with f
=
0.1, θ
=
0, N
=
32, L
=
8, C
=
100, h
=
1, and S
N
R
∈
-
6,3
d
B. (b) Impact of K on MSE with f
=
0.1, θ
=
0, N
=
32, L
=
8, C
=
100, h
=
1, and S
N
R
∈
-
1,1
d
B.
(a)
(b)


## 4.4. Impact of Interpolation TimesL

As in Figure3, the MSE curves of LS-SVR algorithm versus SNR are plotted in Figure 6, while L is 2, 4, 8, and 16, respectively. Now, the sample size and DFT points are fixed. From Figure 6, its MSE performance will be improved as L increases.Figure 6
(a) Impact ofL on MSE with f
=
0.1, θ
=
0, N
=
32, K
=
2
N, C
=
100, h
=
1, and S
N
R
∈
-
6,3
d
B. (b) Impact of L on MSE with f
=
0.1, θ
=
0, N
=
32, K
=
2
N, C
=
100, h
=
1, and S
N
R
∈
-
1,1
d
B.
(a)
(b)


## 4.5. Impact of Sample SizeN

As in Figure3, the MSE curves of LS-SVR algorithm versus SNR are plotted in Figure 7, while N is 8, 16, 32, and 64, respectively. Now, the interpolation times are fixed, and DFT points are directly proportional to N with a fixed value. From Figure 7, its threshold value will decrease and MSE performance will be improved as N increases.Figure 7
Impact ofN on MSE with f
=
0.1, θ
=
0, K
=
2
N, L
=
8, C
=
100, h
=
1, and S
N
R
∈
-
6,3
d
B.


## 4.6. Calculation Cost

Calculation cost is an important factor to impact the real time of frequency estimation algorithm. The calculation cost of these six algorithms is analyzed through calculating the operation number of their real multiplication and real addition under the same parameter setting as Figure3.The DFT value withK points can be derived by fast Fourier transform (FFT), that is, K
log
2
⁡
K
/
2 complex multiplication and K
log
2
⁡
K complex addition. Besides, 1 complex multiplication needs 4 real multiplications and 2 real additions; 1 complex addition needs 2 real additions. In order to decrease the calculation cost, FDP algorithm also integrates coarse and fine search, where the point of coarse search is 2
N. Contemporarily, 1 modular operation needs 2 real multiplications and 1 real addition; 1 comparing operation needs 1 real addition. Consequently, the operation numbers of real multiplication M
F
D
P and real addition A
F
D
P of FDP algorithm are
(21)
M
FDP
=
32
N
log
2
⁡
32
N
2
×
4
+
2
N
×
2
+
2
×
16
-
2
×
2
=
64
N
log
2
⁡
N
+
324
N
+
60
=
20668
,
A
FDP
=
32
N
log
2
⁡
32
N
2
×
2
+
32
N
log
2
⁡
32
N
×
2
+
2
N
+
2
N
-
1
+
2
×
16
-
2
+
2
×
16
-
2
=
96
N
log
2
⁡
N
+
484
N
+
59
=
30907
.The coarse search of DS algorithm adopts FDP one withK
=
2
N points, so it needs 4
N
log
2
⁡
N
+
8
N real multiplication and 6
N
log
2
⁡
N
+
10
N
-
1 real addition. Also, 1 iteration needs N complex multiplication, N
-
1 complex addition, 4 real additions, and 1 modular operation. Accordingly, the operation numbers of real multiplication M
D
S and real addition A
D
S of DS algorithm are(22)
M
DS
=
4
N
log
2
⁡
N
+
8
N
+
N
×
4
+
2
Q
DS
=
4
N
log
2
⁡
N
+
88
N
+
40
=
3496
,
A
DS
=
6
N
log
2
⁡
N
+
10
N
-
1
+
N
×
2
+
N
-
1
×
2
+
4
+
1
Q
DS
=
6
N
log
2
⁡
N
+
90
N
+
59
=
3899
.The coarse search of Modified DS algorithm adopts FDP one withK
=
N points, so it needs 2
N
log
2
⁡
N
+
2
N real multiplication and 3
N
log
2
⁡
N
+
2
N
-
1 real addition. Also, 1 iteration needs 2
N complex multiplication, 2
N
-
2 complex addition, 6 real additions, and 2 modular operations. Accordingly, the operation numbers of real multiplication M
M
-
D
S and real addition A
M-DS of Modified DS algorithm are(23)
M
M-DS
=
2
N
log
2
⁡
N
+
2
N
+
2
N
×
4
+
2
×
2
Q
M-DS
=
2
N
log
2
⁡
N
+
162
N
+
80
=
5584
,
A
M-DS
=
3
N
log
2
⁡
N
+
2
N
-
1
+
2
N
×
2
+
2
N
-
2
×
2
+
6
+
1
Q
M-DS
=
3
N
log
2
⁡
N
+
162
N
+
59
=
5723
.The coarse search of IIFC algorithm adopts FDP one withK
=
N points, so it needs 2
N
log
2
⁡
N
+
2
N real multiplication and 3
N
log
2
⁡
N
+
2
N
-
1 real addition. Also, 1 iteration needs 2
N complex multiplication, 2
N
-
2 complex addition, 6 real additions, and 2 modular operations. Accordingly, the operation numbers of real multiplication M
I
I
F
C and real addition A
I
I
F
C of IIFC algorithm are(24)
M
IIFC
=
2
N
log
2
⁡
N
+
2
N
+
2
N
+
1
×
4
+
1
Q
IIFC
=
2
N
log
2
⁡
N
+
82
N
+
50
=
2994
,
A
IIFC
=
3
N
log
2
⁡
N
+
2
N
-
1
+
2
N
+
1
×
2
+
2
N
×
2
+
6
Q
IIFC
=
3
N
log
2
⁡
N
+
82
N
+
79
=
3183
.The coarse search of RCTSL algorithm adopts FDP one withK
=
4
N points, so it needs 8
N
log
2
⁡
N
+
24
N real multiplication and 12
N
log
2
⁡
N
+
32
N
-
1 real addition. Also, it needs 7 real multiplications and 4 real additions. Accordingly, the operation numbers of real multiplication M
R
C
T
S
L and real addition A
R
C
T
S
L of RCTSL algorithm are(25)
M
RCTSL
=
8
N
log
2
⁡
N
+
24
N
+
7
=
2055
,
A
RCTSL
=
12
N
log
2
⁡
N
+
32
N
-
1
+
4
=
12
N
log
2
⁡
N
+
32
N
+
3
=
2947
.The coarse search of LS-SVR algorithm adopts FDP one withK
=
2
N points, so it needs 4
N
log
2
⁡
N
+
8
N real multiplication and 6
N
log
2
⁡
N
+
10
N
-
1 real addition. Also, if N, K, and L are fixed, matrices Q and Q
′ are already known, so the value of matrix β with 2
L
-
1 rows and K columns can be calculated. As a result, it only has to add the calculation cost for (11) and comparison of 2
L
-
1 real number. It is worth stressing that (11) is used for real and image part, respectively. Accordingly, the operation numbers of real multiplication M
L
S
-
S
V
R and real addition A
L
S
-
S
V
R of LS-SVR algorithm are(26)
M
LS-SVR
=
4
N
log
2
⁡
N
+
8
N
+
2
N
×
2
×
8
-
1
×
2
+
2
×
8
-
1
×
2
=
4
N
log
2
⁡
N
+
68
N
+
30
=
2846
,
A
LS-SVR
=
6
N
log
2
⁡
N
+
10
N
-
1
+
2
N
-
1
×
2
×
8
-
1
×
2
+
2
×
8
-
1
+
2
×
8
-
1
=
6
N
log
2
⁡
N
+
70
N
-
1
=
3199
.As in Figure7, the operation numbers of real multiplication and real addition of these six algorithms are listed in Table 1. Additionally, N
=
32 is taken, for example, to compare. From Table 1, the calculation cost of FDP one is much larger than the other five; second larger is Modified DS one and the next is DS one. The calculation cost of LS-SVR one is between IIFC and RCTSL one, and the distances between each of two are very small.Table 1
Calculation cost of all these six algorithms.
Real multiplication
N
=
32
Real addition
N
=
32
FDP
64
N
log
2
⁡
N
+
324
N
+
60
20668
96
N
log
2
⁡
N
+
484
N
+
59
30907
DS
4
N
log
2
⁡
N
+
88
N
+
40
3496
6
N
log
2
⁡
N
+
90
N
+
59
3899
Modified DS
2
N
log
2
⁡
N
+
162
N
+
80
5584
3
N
log
2
⁡
N
+
162
N
+
59
5723
IIFC
2
N
log
2
⁡
N
+
82
N
+
50
2994
3
N
log
2
⁡
N
+
82
N
+
79
3183
RCTSL
8
N
log
2
⁡
N
+
24
N
+
7
2055
12
N
log
2
⁡
N
+
32
N
+
3
2947
LS-SVR
4
N
log
2
⁡
N
+
68
N
+
30
2846
6
N
log
2
⁡
N
+
70
N
-
1
3199


## 5. Conclusions

The MSE performance and the calculation cost in DFT-based frequency estimation algorithm are a pair relationship of interaction and interrestriction. The better its MSE performance is, the higher its calculation cost is. However, very high calculation cost will restrict the algorithm’s real time capacity. So, how to compromise between these two factors is a hot and key point.This paper utilizes LS-SVR’s good generalizing and fitting capabilities while keeping lower computational complexity and proposes a LS-SVR-based interpolation frequency estimation algorithm. Firstly, the sparser DFT points are learned and the continuous spectrum with less fitting errors is predicted. Then, because any output of LS-SVR is the linear weighted sum of all inputs, LS-SVR is used as a linear interpolator to resample the DFT points densely and decrease the calculation cost. At last, the resampling DFT points between the left and right of its maximum value are searched to derive the frequency estimation value.In order to compare the calculation cost of the proposed and other DFT-based algorithms, the parameters of all these algorithms are set to ensure nearly the same precondition. Stressed that, the sample size, number of DFT points, and re-sampling points are already known. Our results show that the proposed algorithm can make a good compromise between MSE performance and calculation cost under the assumption mentioned above.At the same time, the proper ranges of LS-SVR’s parameters are obtained. As a next step, how to select them exactly is an important research point.



---

*Source: 648707-2015-10-25.xml*