# A FPC-ROOT Algorithm for 2D-DOA Estimation in Sparse Array

Authors: Wenhao Zeng; Hongtao Li; Xiaohua Zhu; Chaoyu Wang
Journal: International Journal of Antennas and Propagation
 (2016)

---

## Abstract

To improve the performance of two-dimensional direction-of-arrival (2D DOA) estimation in sparse array, this paper presents a Fixed Point Continuation Polynomial Roots (FPC-ROOT) algorithm. Firstly, a signal model for DOA estimation is established based on matrix completion and it can be proved that the proposed model meets Null Space Property (NSP). Secondly, left and right singular vectors of received signals matrix are achieved using the matrix completion algorithm. Finally, 2D DOA estimation can be acquired through solving the polynomial roots. The proposed algorithm can achieve high accuracy of 2D DOA estimation in sparse array, without solving autocorrelation matrix of received signals and scanning of two-dimensional spectral peak. Besides, it decreases the number of antennas and lowers computational complexity and meanwhile avoids the angle ambiguity problem. Computer simulations demonstrate that the proposed FPC-ROOT algorithm can obtain the 2D DOA estimation precisely in sparse array.


---

## Body

## 1. Introduction

Two-dimensional direction-of-arrival (2D DOA) [1–4] estimation plays an important role in array signal processing, and it usually utilizes L-shaped arrays, planar arrays, vector sensors, and so forth, to estimate the two-dimensional target angle. Compared with 2D DOA estimation of other arrays [5, 6], 2D DOA estimation of planar array is asymptotically unbiased where the target position can be determined precisely without the problem of angle ambiguity. Moreover, the phased-array radar in the planar array can utilize waveform diversity which makes it suitable for multiple targets and complex environments with enhanced performance of target recognition and target tracking. However, the planar array requires a large amount of array elements which results in tremendous demands of hardware equipment and increases the complexity and cost of design. Comparatively, the sparse array needs only a quite smaller number of elements, so it is a feasible remedy for the abovementioned problems, whereas, in this case, the problem of substantially rising average side lobes occurs, which accounts for its uncommon applications so far. Paper [5] lowers computational complexity of DOA estimation by introducing a preprocessing transformation matrix but has poor performance in sparse array. Paper [7] achieves high-resolution DOA estimation in sparse array; however, it only works in uniform linear array (ULA).Matrix completion [8–10] is an extension of compressive sensing (CS) [11, 12] and has been widely applied to image processing, remote sensing, and many other engineering fields [13, 14]. On the basis of low-rank matrix, matrix completion can recover the full matrix from an incomplete set of matrix entries with high probability by solving nuclear-norm optimization. Paper [15] proposed a fixed point and Bregman iterative methods for matrix rank minimization, which is a very fast, robust, and powerful algorithm. Paper [16] introduces a particularly simple yet highly efficient alternating projection algorithm and this algorithm is able to recover matrix from the minimum number of measurements necessary. Paper [17] provides a necessary and sufficient condition that quantifies when this heuristic successfully finds the minimum rank solution of a linear constraint set. The sparse received signal can be recovered to the full received signal by matrix completion, so that matrix completion has been applied to DOA estimation [14, 18].This study proposes a Fixed Point Continuation Polynomial Roots (FPC-ROOT) algorithm. The proposed algorithm establishes a signal model of matrix completion for 2D DOA estimation based on low-rank property of target in two-dimensional space domain, which turns out to meet the Null Space Property (NSP) and ensure the feasibility of 2D DOA estimation via matrix completion. By contrast to conventional algorithms, the proposed algorithm obtains left and right singular vectors of received signal matrix directly from the output of matrix completion algorithm instead of eigendecomposing autocorrelation matrix of received signal, for the benefit of lower dimensions. Besides, the proposed algorithm can avoid scanning of the 2D spectral peak by solving the polynomial roots, which reduces the computational complexity. In addition, it can estimate target angle accurately with less number of array units by adopting matrix completion.


## 2. Signal Model in Sparse Array

### 2.1. The Signal Model of 2D DOA Estimation

Suppose that the uniform rectangular array (URA) [3] is depicted in Figure 1. M
x and M
y are the number of elements in x-direction and y-direction, respectively. The corresponding element spacing is d
x and d
y.Figure 1
The uniform rectangular array.Assume that there are multiple targets in the space. The number of snapshots isW and the number of targets is k, where the waveform of the ith (i
=
1,2
,
…
,
k) target is s
i
(
t
) and t
=
1,2
,
…
,
W. The target angles are (
ϕ
i
,
θ
i
), where ϕ
i and θ
i express the elevation and azimuth angles of the ith target, respectively. Suppose the uncorrelated narrow-band signals are received in far field [19]; thus, the received signal of M
x elements in x-direction can be written as(1)
L
x
t
=
A
x
S
t
+
N
x
t
,where S
(
t
)
=
diag
⁡
(
s
i
(
t
)
) is a diagonal matrix of k
×
k dimensions, the first k elements of s
i
(
t
) are nonzero which correspond to k targets, and N
x
(
t
) is the noise vector of the array. A
x is a M
x
×
k dimensional steering vector, which can be given by(2)
A
x
=
a
x
ϕ
1
,
θ
1
,
a
x
ϕ
2
,
θ
2
,
…
,
a
x
ϕ
k
,
θ
k
.Assume the wavelength of received signal is λ; then, a
x
(
ϕ
i
,
θ
i
) is(3)
a
x
ϕ
i
,
θ
i
m
x
=
e
j
2
π
/
λ
d
x
sin
⁡
θ
i
cos
⁡
ϕ
i
m
x
-
1
,
m
x
=
1,2
,
…
,
M
x
.Similarly, the received signal of M
y elements in y-direction can be represented as(4)
L
y
t
=
A
y
S
t
+
N
y
t
,where N
y
(
t
) is the noise vector of the array. A
y is M
y
×
k dimensional steering vector, which can be denoted as(5)
A
y
=
a
y
ϕ
1
,
θ
1
,
a
y
ϕ
2
,
θ
2
,
…
,
a
y
ϕ
k
,
θ
k
,where a
y
(
ϕ
i
,
θ
i
) is defined as(6)
a
y
ϕ
i
,
θ
i
m
y
=
e
j
2
π
/
λ
d
y
sin
⁡
θ
i
sin
⁡
ϕ
i
m
y
-
1
,
m
y
=
1,2
,
…
,
M
y
.In conclusion, the received signal model of full array is demonstrated as(7)
X
t
=
A
x
S
t
A
y
T
+
N
R
t
,
t
=
1
,
…
,
N
.When the power of noise matrixN
R
(
t
) is much smaller than the signal power, we can get that rank
⁡
(
X
(
t
)
)
≤
rank
⁡
(
S
(
t
)
)
=
k; in other words, matrix X
(
t
) is low-rank [10]. And matrix in (7) is consistent with strong incoherence property [15], so it can be recovered precisely with high probability via matrix completion.


### 2.2. Matrix Completion

With regard to the sparsity of signals, CS can sample signals at far lower sampling frequency than Nyquist sampling frequency and meanwhile reconstruct original signals precisely. In CS, the target to be recovered is a vector; however, on some practical occasions, it normally refers to a matrix and is sensitive to data missing, data corruption, and so on.Matrix completion is an extension of CS. CS exploits the sparsity of signals; nevertheless, matrix completion utilizes the sparsity of matrix singular values, namely, the low-rank property, and reconstructs full matrix by solving nuclear-norm optimization.SupposeM
∈
R
n
×
n is an original low-rank matrix, where rank
⁡
(
M
)
=
r, r
≪
n. Matrix completion refers to recovering the whole elements of matrix M from its partial elements. Let the available entries of matrix be {
M
i
j
,
(
i
,
j
)
∈
Ω
}, where Ω is a random sampled subset of the whole elements; then, the matrix completion can be denoted as [10] (8)
min
⁡
X
∗
,
s.t.
X
i
j
=
M
i
j
,
i
,
j
∈
Ω
,where matrix X is the estimated value of matrix M; X
∗ represents the nuclear norm of the matrix X.


### 2.3. The Sparse Array Model

We sample elements from URA at random. Let the number of sampled elements bem with the corresponding element positions unchanged and the unsampled units removed; thus, a new sparse array is set up. To recover matrix precisely via matrix completion, the required number of samples is m
≥
r
(
n
1
+
n
2
-
r
) [10], while n
1, n
2 are the numbers of rows and columns of the matrix, and r is the rank of the matrix. Suppose the received signal matrix in sparse array is X
s
(
t
); then, X
s
(
t
) is related to X
(
t
) by (9)
X
s
t
i
j
=
X
t
i
j
,
i
,
j
∈
Ω
,
X
s
t
i
j
=
0
,
i
,
j
∉
Ω
,where Ω is the set of element positions in sparse array.


## 2.1. The Signal Model of 2D DOA Estimation

Suppose that the uniform rectangular array (URA) [3] is depicted in Figure 1. M
x and M
y are the number of elements in x-direction and y-direction, respectively. The corresponding element spacing is d
x and d
y.Figure 1
The uniform rectangular array.Assume that there are multiple targets in the space. The number of snapshots isW and the number of targets is k, where the waveform of the ith (i
=
1,2
,
…
,
k) target is s
i
(
t
) and t
=
1,2
,
…
,
W. The target angles are (
ϕ
i
,
θ
i
), where ϕ
i and θ
i express the elevation and azimuth angles of the ith target, respectively. Suppose the uncorrelated narrow-band signals are received in far field [19]; thus, the received signal of M
x elements in x-direction can be written as(1)
L
x
t
=
A
x
S
t
+
N
x
t
,where S
(
t
)
=
diag
⁡
(
s
i
(
t
)
) is a diagonal matrix of k
×
k dimensions, the first k elements of s
i
(
t
) are nonzero which correspond to k targets, and N
x
(
t
) is the noise vector of the array. A
x is a M
x
×
k dimensional steering vector, which can be given by(2)
A
x
=
a
x
ϕ
1
,
θ
1
,
a
x
ϕ
2
,
θ
2
,
…
,
a
x
ϕ
k
,
θ
k
.Assume the wavelength of received signal is λ; then, a
x
(
ϕ
i
,
θ
i
) is(3)
a
x
ϕ
i
,
θ
i
m
x
=
e
j
2
π
/
λ
d
x
sin
⁡
θ
i
cos
⁡
ϕ
i
m
x
-
1
,
m
x
=
1,2
,
…
,
M
x
.Similarly, the received signal of M
y elements in y-direction can be represented as(4)
L
y
t
=
A
y
S
t
+
N
y
t
,where N
y
(
t
) is the noise vector of the array. A
y is M
y
×
k dimensional steering vector, which can be denoted as(5)
A
y
=
a
y
ϕ
1
,
θ
1
,
a
y
ϕ
2
,
θ
2
,
…
,
a
y
ϕ
k
,
θ
k
,where a
y
(
ϕ
i
,
θ
i
) is defined as(6)
a
y
ϕ
i
,
θ
i
m
y
=
e
j
2
π
/
λ
d
y
sin
⁡
θ
i
sin
⁡
ϕ
i
m
y
-
1
,
m
y
=
1,2
,
…
,
M
y
.In conclusion, the received signal model of full array is demonstrated as(7)
X
t
=
A
x
S
t
A
y
T
+
N
R
t
,
t
=
1
,
…
,
N
.When the power of noise matrixN
R
(
t
) is much smaller than the signal power, we can get that rank
⁡
(
X
(
t
)
)
≤
rank
⁡
(
S
(
t
)
)
=
k; in other words, matrix X
(
t
) is low-rank [10]. And matrix in (7) is consistent with strong incoherence property [15], so it can be recovered precisely with high probability via matrix completion.


## 2.2. Matrix Completion

With regard to the sparsity of signals, CS can sample signals at far lower sampling frequency than Nyquist sampling frequency and meanwhile reconstruct original signals precisely. In CS, the target to be recovered is a vector; however, on some practical occasions, it normally refers to a matrix and is sensitive to data missing, data corruption, and so on.Matrix completion is an extension of CS. CS exploits the sparsity of signals; nevertheless, matrix completion utilizes the sparsity of matrix singular values, namely, the low-rank property, and reconstructs full matrix by solving nuclear-norm optimization.SupposeM
∈
R
n
×
n is an original low-rank matrix, where rank
⁡
(
M
)
=
r, r
≪
n. Matrix completion refers to recovering the whole elements of matrix M from its partial elements. Let the available entries of matrix be {
M
i
j
,
(
i
,
j
)
∈
Ω
}, where Ω is a random sampled subset of the whole elements; then, the matrix completion can be denoted as [10] (8)
min
⁡
X
∗
,
s.t.
X
i
j
=
M
i
j
,
i
,
j
∈
Ω
,where matrix X is the estimated value of matrix M; X
∗ represents the nuclear norm of the matrix X.


## 2.3. The Sparse Array Model

We sample elements from URA at random. Let the number of sampled elements bem with the corresponding element positions unchanged and the unsampled units removed; thus, a new sparse array is set up. To recover matrix precisely via matrix completion, the required number of samples is m
≥
r
(
n
1
+
n
2
-
r
) [10], while n
1, n
2 are the numbers of rows and columns of the matrix, and r is the rank of the matrix. Suppose the received signal matrix in sparse array is X
s
(
t
); then, X
s
(
t
) is related to X
(
t
) by (9)
X
s
t
i
j
=
X
t
i
j
,
i
,
j
∈
Ω
,
X
s
t
i
j
=
0
,
i
,
j
∉
Ω
,where Ω is the set of element positions in sparse array.


## 3. The Proposed Algorithm

### 3.1. The Signal Model for 2D-DOA Estimation Based on Matrix Completion

According to (7), the received signal matrix X
(
t
) in URA is low-rank. Regard X
R
(
t
) as the recovered matrix by matrix completion, so it can be deduced that(10)
min
⁡
X
R
t
∗
s.t.
X
R
t
i
j
=
X
s
t
i
j
,
i
,
j
∈
Ω
.If a signal model meets NSP, the rank minimization of this model is equivalent to its nuclear-norm minimization [13]. So we introduce the projection P
Ω as follows:(11)
P
Ω
M
=
M
i
j
,
i
,
j
∈
Ω
0
,
i
,
j
∉
Ω
.From (11), we can see that (10) can be expressed as(12)
min
⁡
X
R
t
∗
,
s.t.
P
Ω
X
R
t
=
P
Ω
X
s
t
,where X
R
(
t
) is the estimated matrix. The null space of projection P
Ω is (13)
Null
P
Ω
=
M
∈
R
n
1
×
n
2
:
P
Ω
M
=
0
.According to NSP, we are unable to recover a matrix if it belongs to the null space of projectionP
Ω. From (4), we can get that(14)
a
x
ϕ
i
,
θ
i
m
x
=
e
j
2
π
/
λ
d
x
sin
⁡
θ
i
cos
⁡
ϕ
i
m
x
-
1
≠
0
,
m
x
=
1,2
,
…
,
M
x
.In (7), the arbitrary elements of A
x and A
y are both nonzero and the first k elements in s
i
(
t
) are nonzero, so the diagonal elements of k
×
k dimensional diagonal matrix are nonzero. Arbitrary elements of X
(
t
) are nonzero based on matrix multiplication property. Therefore, it can be concluded that whichever sampling operator is selected, there is always P
Ω
(
X
(
t
)
)
≠
0; in other words, P
Ω
(
X
(
t
)
)
∉
N
u
l
l
(
P
Ω
), which meets the Null Space Property.


### 3.2. The FPC-ROOT Algorithm

Supposes
v
d
(
X
R
(
t
)
)
=
U
Σ
V and matrices U and V are the left and right singular value matrix of X
R
(
t
). FPC-ROOT algorithm can obtain U and V directly by matrix completion based on the low-rank property of X
(
t
) and realizes 2D DOA estimation by computing the polynomial roots.Firstly, to solve problem (12), we achieve the left and right singular value matrices U and V of estimated value X
R
(
t
) in full array by FPC algorithm. And then, we solve the autocorrelation matrix of received signal X
(
t
) in full array, so the eigendecomposition of the autocorrelation matrix is(15)
R
X
=
X
t
X
t
H
=
A
x
S
t
A
y
T
A
y
∗
S
t
∗
A
x
H
+
N
m
1
=
A
x
R
m
1
A
x
H
+
N
m
1
=
U
S
Σ
S
U
S
H
+
U
N
Σ
N
U
N
H
,where t
=
1
,
…
,
W, X
(
t
)
H is the conjugate transpose matrix of X
(
t
), U
S is the signal subspace, U
N is the noise subspace, and R
m
1 is(16)
R
m
1
=
S
t
A
y
T
A
y
∗
S
t
∗
.And N
m
1 in (15) can be expressed as(17)
N
m
1
=
A
x
S
t
A
y
T
N
R
t
H
+
N
R
t
A
y
∗
S
t
∗
A
x
H
+
N
R
t
N
R
t
H
.It is obvious that the spanned subspaces of A
x and U
S are identical. We solve the conjugate transpose of autocorrelation matrix R
X and then it can be concluded that(18)
R
X
H
=
X
t
H
X
t
=
A
y
∗
S
t
∗
A
x
H
A
x
S
t
A
y
T
+
N
m
2
=
A
y
∗
R
m
2
A
y
T
+
N
m
2
=
V
S
Σ
S
V
S
H
+
V
N
Σ
N
V
N
H
,where t
=
1
,
…
,
N, and similarly R
m
2 is(19)
R
m
2
=
S
t
∗
A
x
H
A
x
S
t
N
m
2 can be expressed as(20)
N
m
2
=
A
y
∗
S
t
∗
A
x
H
N
R
t
+
N
R
t
H
A
x
S
t
A
y
T
+
N
R
t
H
N
R
t
.So the space spanned by A
y
∗ is the same as the space spanned by V
S.Based on singular value decomposition, it is easy to know that left and right singular value matricesU and V are related to the eigendecomposition of autocorrelation matrix R
X by(21)
U
=
U
S
+
U
N
,
V
=
V
S
+
V
N
.So the left and right singular vectors of received signal matrix can be obtained directly from the output of matrix completion algorithm instead of eigendecomposing autocorrelation matrix of received signal and the computational complexity of the proposed algorithm obtained a corresponding reduction.Consider a polynomial as(22)
f
z
=
u
l
H
p
z
l
=
k
+
1
,
k
+
2
,
…
,
N
,where u
l is the lth eigenvector of matrix R
X and p
(
z
)
=
[
1
,
z
,
…
,
z
N
-
1
]
T. It can be deduced that the corresponding ROOT-MUSIC polynomial is(23)
f
x
z
=
z
N
-
1
p
T
z
-
1
U
N
U
N
H
p
z
.By solving the polynomial roots, the proposed algorithm can avoid scanning of the 2D spectral peak. Taking use of the orthogonality of signal subspace, the above equation can be converted to(24)
P
x
z
=
z
N
-
1
p
T
z
-
1
I
-
U
S
U
S
H
p
z
.The dimensionality ofU
S is smaller than U
N; hence, the proposed algorithm effectively reduced the computational complexity by reducing the dimension of the subspace matrix. Then, the vector corresponding to the roots of polynomial is(25)
z
x
=
exp
⁡
j
2
π
d
x
cos
⁡
ϕ
1
sin
⁡
θ
1
λ
,
…
,
exp
⁡
j
2
π
d
x
cos
⁡
ϕ
k
sin
⁡
θ
k
λ
.Thus,(26)
r
x
=
cos
⁡
ϕ
1
sin
⁡
θ
1
,
…
,
cos
⁡
ϕ
k
sin
⁡
θ
k
.Similarly, it can be obtained that(27)
r
y
=
sin
⁡
ϕ
1
sin
⁡
θ
1
,
…
,
sin
⁡
ϕ
k
sin
⁡
θ
k
.Hence, the estimated angles of targets are(28)
θ
1
,
θ
2
,
…
,
θ
k
=
arcsin
⁡
r
x
2
+
r
y
2
ϕ
1
,
ϕ
2
,
…
,
ϕ
k
=
arctan
⁡
r
x
r
y
.In summary, the proposed FPC-ROOT algorithm in this paper can be programmed as follows.Fixed Point Continuation Polynomial Roots (FPC-ROOT) Algorithm
Initialize. Given X
s
(
t
), the projection P
Ω is corresponding to element positions in the sparse array:
(1)
Solve (12) to get left and right singular value matrices U
S and V
S.
(2)
Construct the polynomial roots (24).
(3)
Solve (24) to get (29)
r
x
=
cos
⁡
ϕ
1
sin
⁡
θ
1
,
…
,
cos
⁡
ϕ
k
sin
⁡
θ
k
,
r
y
=
sin
⁡
ϕ
1
sin
⁡
θ
1
,
…
,
sin
⁡
ϕ
k
sin
⁡
θ
k
.
(4)
Determine the targets angles(30)
θ
1
,
θ
2
,
…
,
θ
k
=
arcsin
⁡
r
x
2
+
r
y
2
,
ϕ
1
,
ϕ
2
,
…
,
ϕ
k
=
arctan
⁡
r
x
r
y
.
End.


### 3.3. Dimensionality Reduction

In normal 2D-DOA estimation, DOA estimation is achieved through autocorrelation matrix of a vector which is transformed from the signal matrix. Suppose the signal matrix isM
x
×
M
y, so the dimension of the transformed vector is M
x
M
y
×
1; then, the dimension of the autocorrelation matrix is M
x
M
y
×
M
x
M
y. In the proposed method, we obtain left and right singular vector directly from the signal matrix, avoiding solving the autocorrelation matrix, greatly reducing the dimension of the target matrix.


## 3.1. The Signal Model for 2D-DOA Estimation Based on Matrix Completion

According to (7), the received signal matrix X
(
t
) in URA is low-rank. Regard X
R
(
t
) as the recovered matrix by matrix completion, so it can be deduced that(10)
min
⁡
X
R
t
∗
s.t.
X
R
t
i
j
=
X
s
t
i
j
,
i
,
j
∈
Ω
.If a signal model meets NSP, the rank minimization of this model is equivalent to its nuclear-norm minimization [13]. So we introduce the projection P
Ω as follows:(11)
P
Ω
M
=
M
i
j
,
i
,
j
∈
Ω
0
,
i
,
j
∉
Ω
.From (11), we can see that (10) can be expressed as(12)
min
⁡
X
R
t
∗
,
s.t.
P
Ω
X
R
t
=
P
Ω
X
s
t
,where X
R
(
t
) is the estimated matrix. The null space of projection P
Ω is (13)
Null
P
Ω
=
M
∈
R
n
1
×
n
2
:
P
Ω
M
=
0
.According to NSP, we are unable to recover a matrix if it belongs to the null space of projectionP
Ω. From (4), we can get that(14)
a
x
ϕ
i
,
θ
i
m
x
=
e
j
2
π
/
λ
d
x
sin
⁡
θ
i
cos
⁡
ϕ
i
m
x
-
1
≠
0
,
m
x
=
1,2
,
…
,
M
x
.In (7), the arbitrary elements of A
x and A
y are both nonzero and the first k elements in s
i
(
t
) are nonzero, so the diagonal elements of k
×
k dimensional diagonal matrix are nonzero. Arbitrary elements of X
(
t
) are nonzero based on matrix multiplication property. Therefore, it can be concluded that whichever sampling operator is selected, there is always P
Ω
(
X
(
t
)
)
≠
0; in other words, P
Ω
(
X
(
t
)
)
∉
N
u
l
l
(
P
Ω
), which meets the Null Space Property.


## 3.2. The FPC-ROOT Algorithm

Supposes
v
d
(
X
R
(
t
)
)
=
U
Σ
V and matrices U and V are the left and right singular value matrix of X
R
(
t
). FPC-ROOT algorithm can obtain U and V directly by matrix completion based on the low-rank property of X
(
t
) and realizes 2D DOA estimation by computing the polynomial roots.Firstly, to solve problem (12), we achieve the left and right singular value matrices U and V of estimated value X
R
(
t
) in full array by FPC algorithm. And then, we solve the autocorrelation matrix of received signal X
(
t
) in full array, so the eigendecomposition of the autocorrelation matrix is(15)
R
X
=
X
t
X
t
H
=
A
x
S
t
A
y
T
A
y
∗
S
t
∗
A
x
H
+
N
m
1
=
A
x
R
m
1
A
x
H
+
N
m
1
=
U
S
Σ
S
U
S
H
+
U
N
Σ
N
U
N
H
,where t
=
1
,
…
,
W, X
(
t
)
H is the conjugate transpose matrix of X
(
t
), U
S is the signal subspace, U
N is the noise subspace, and R
m
1 is(16)
R
m
1
=
S
t
A
y
T
A
y
∗
S
t
∗
.And N
m
1 in (15) can be expressed as(17)
N
m
1
=
A
x
S
t
A
y
T
N
R
t
H
+
N
R
t
A
y
∗
S
t
∗
A
x
H
+
N
R
t
N
R
t
H
.It is obvious that the spanned subspaces of A
x and U
S are identical. We solve the conjugate transpose of autocorrelation matrix R
X and then it can be concluded that(18)
R
X
H
=
X
t
H
X
t
=
A
y
∗
S
t
∗
A
x
H
A
x
S
t
A
y
T
+
N
m
2
=
A
y
∗
R
m
2
A
y
T
+
N
m
2
=
V
S
Σ
S
V
S
H
+
V
N
Σ
N
V
N
H
,where t
=
1
,
…
,
N, and similarly R
m
2 is(19)
R
m
2
=
S
t
∗
A
x
H
A
x
S
t
N
m
2 can be expressed as(20)
N
m
2
=
A
y
∗
S
t
∗
A
x
H
N
R
t
+
N
R
t
H
A
x
S
t
A
y
T
+
N
R
t
H
N
R
t
.So the space spanned by A
y
∗ is the same as the space spanned by V
S.Based on singular value decomposition, it is easy to know that left and right singular value matricesU and V are related to the eigendecomposition of autocorrelation matrix R
X by(21)
U
=
U
S
+
U
N
,
V
=
V
S
+
V
N
.So the left and right singular vectors of received signal matrix can be obtained directly from the output of matrix completion algorithm instead of eigendecomposing autocorrelation matrix of received signal and the computational complexity of the proposed algorithm obtained a corresponding reduction.Consider a polynomial as(22)
f
z
=
u
l
H
p
z
l
=
k
+
1
,
k
+
2
,
…
,
N
,where u
l is the lth eigenvector of matrix R
X and p
(
z
)
=
[
1
,
z
,
…
,
z
N
-
1
]
T. It can be deduced that the corresponding ROOT-MUSIC polynomial is(23)
f
x
z
=
z
N
-
1
p
T
z
-
1
U
N
U
N
H
p
z
.By solving the polynomial roots, the proposed algorithm can avoid scanning of the 2D spectral peak. Taking use of the orthogonality of signal subspace, the above equation can be converted to(24)
P
x
z
=
z
N
-
1
p
T
z
-
1
I
-
U
S
U
S
H
p
z
.The dimensionality ofU
S is smaller than U
N; hence, the proposed algorithm effectively reduced the computational complexity by reducing the dimension of the subspace matrix. Then, the vector corresponding to the roots of polynomial is(25)
z
x
=
exp
⁡
j
2
π
d
x
cos
⁡
ϕ
1
sin
⁡
θ
1
λ
,
…
,
exp
⁡
j
2
π
d
x
cos
⁡
ϕ
k
sin
⁡
θ
k
λ
.Thus,(26)
r
x
=
cos
⁡
ϕ
1
sin
⁡
θ
1
,
…
,
cos
⁡
ϕ
k
sin
⁡
θ
k
.Similarly, it can be obtained that(27)
r
y
=
sin
⁡
ϕ
1
sin
⁡
θ
1
,
…
,
sin
⁡
ϕ
k
sin
⁡
θ
k
.Hence, the estimated angles of targets are(28)
θ
1
,
θ
2
,
…
,
θ
k
=
arcsin
⁡
r
x
2
+
r
y
2
ϕ
1
,
ϕ
2
,
…
,
ϕ
k
=
arctan
⁡
r
x
r
y
.In summary, the proposed FPC-ROOT algorithm in this paper can be programmed as follows.Fixed Point Continuation Polynomial Roots (FPC-ROOT) Algorithm
Initialize. Given X
s
(
t
), the projection P
Ω is corresponding to element positions in the sparse array:
(1)
Solve (12) to get left and right singular value matrices U
S and V
S.
(2)
Construct the polynomial roots (24).
(3)
Solve (24) to get (29)
r
x
=
cos
⁡
ϕ
1
sin
⁡
θ
1
,
…
,
cos
⁡
ϕ
k
sin
⁡
θ
k
,
r
y
=
sin
⁡
ϕ
1
sin
⁡
θ
1
,
…
,
sin
⁡
ϕ
k
sin
⁡
θ
k
.
(4)
Determine the targets angles(30)
θ
1
,
θ
2
,
…
,
θ
k
=
arcsin
⁡
r
x
2
+
r
y
2
,
ϕ
1
,
ϕ
2
,
…
,
ϕ
k
=
arctan
⁡
r
x
r
y
.
End.


## 3.3. Dimensionality Reduction

In normal 2D-DOA estimation, DOA estimation is achieved through autocorrelation matrix of a vector which is transformed from the signal matrix. Suppose the signal matrix isM
x
×
M
y, so the dimension of the transformed vector is M
x
M
y
×
1; then, the dimension of the autocorrelation matrix is M
x
M
y
×
M
x
M
y. In the proposed method, we obtain left and right singular vector directly from the signal matrix, avoiding solving the autocorrelation matrix, greatly reducing the dimension of the target matrix.


## 4. Simulations

In this section, several simulations for 2D DOA estimation are conducted to demonstrate the feasibility and effectiveness of the proposed algorithm in sparse array. In these experiments, we sample 1200 elements from full array at random to formulate a sparse array. The full array is an URA of64
×
64 elements, where the total number of elements is m
=
4096 and the corresponding element spacing in x-direction and y-direction is d
x
=
d
y
=
λ
/
2.In the first examples, 2D DOA estimation of sparse array is shown. Let three targets be in the space domain, whose elevation and azimuth angles of 2D-DOA are(
10
°
,
15
°
), (
20
°
,
25
°
), and (
30
°
,
35
°
), respectively, and input signal-to-noise ratio (SNR) is 20 dB. Let the number of snapshots be 50. Suppose the received signals are narrow-band in far field and the signal sources are uncorrelated; then, 100 experiment results of 2D-DOA estimation by FPC-ROOT algorithm are depicted in Figure 2. The proposed algorithm samples 1200 elements to construct a sparse array; in other words, 70% units are removed from full array. From Figure 2, it can be seen that the targets’ angles can be achieved precisely by the proposed algorithm in sparse array.Figure 2
2D DOA estimation via FPC-ROOT algorithm.In the second experiment, recovery errors by matrix completion in sparse array with different SNR are examined. We recover a full matrix from a sparse matrix using FPC algorithm. Suppose the full matrix isM and the recovered matrix is X; then, the measurement criterion of recovery errors by matrix completion is M
-
X
2
/
M
2. Figure 3 illustrates the variation of recovery errors by matrix completion with different SNR when the numbers of sparse array elements are 900, 1200, and 1500, respectively. It can be deduced easily from this experiment that recovery errors by FPC algorithm are inversely proportional to SNR. The larger the SNR is, the more similar the matrix M is to low-rank matrix. Simultaneously, the more elements the sparse array has, the closer the recovered signals are to the full array and the smaller the corresponding recovery errors are.Figure 3
Recovery errors by matrix completion with different elements and SNR.In the third experiment, root mean square error (RMSE) of 2D DOA estimation based on matrix completion is discussed. When 500 Monte Carlo simulations are performed, Figure4 exhibits RMSE with different SNR via various algorithms. When the SNR is high, the recovery of matrix completion has a high precision, so the RMSE of DOA estimation is decreased. And it is evident that the proposed algorithm has higher accuracy for both elevation and azimuth angles estimation than 2D-MUSIC algorithms.Figure 4
RMSE of 2D DOA estimation based on matrix completion.In the last experiment, RMSE by FPC-ROOT algorithm with different SNR and elements is demonstrated. Let the number of snapshots be 50 and let 500 Monte Carlo experiments be implemented. Figure5 shows RMSE by FPC-ROOT algorithm when SNR and the number of elements vary. As the recovery errors by FPC algorithm are inversely proportional to SNR, the RMSE of DOA estimation is decreased at high SNR. From this simulation, it can be concluded that the estimation accuracy by FPC-ROOT algorithm is proportional to the number of elements.Figure 5
RMSE versus SNR with different elements by FPC-ROOT algorithm.


## 5. Conclusion

In this paper, a FPC-ROOT algorithm is proposed based on matrix completion, which can achieve high accuracy of 2D DOA estimation with reduced antenna units. The proposed algorithm obtains left and right singular vectors of received signal by the output of matrix completion algorithm directly instead of eigendecomposing the autocorrelation matrix of received signal, for the benefit of lower dimensions. Besides, by computing polynomial roots, the proposed algorithm can avoid the scanning of two-dimensional spectral peak, which cuts down the computational complexity.



---

*Source: 5951717-2016-06-28.xml*