Off-Grid Direction of Arrival Estimation Based on Joint Spatial Sparsity for Distributed Sparse Linear Arrays

1. Introduction

Direction of arrival (DOA) estimation using sensor arrays plays an important role in many applications of radar, sonar, ultrasonic, acoustic, and communication systems to track and localize sources [1–4]. Conventional DOA estimation methods obtain high freedoms by using arrays with large aperture. The increase in the demand of sensors enlarges the array aperture but also increases the cost of receiver hardware and computational complexity. Co-arrays based method is an effective way to enlarge the array aperture with no sensors added, which means the DOA information of the same sources can be estimated by fewer sensors. Second-order statistics is unitized in the covariance matrix of observed signals in the uniform linear array (ULA) to extend aperture, which achieves O(N) freedoms with O(N) sensors [5–7]. Four-order cumulants and higher-order statistics have been also used to make the array aperture larger [8,9]. The redundancy among the signals of common sources observed by every sensor in different arrays is considered and two or more arrays of specific structure are combined to construct a new virtual array with super large aperture [10–15]. MUSIC [16] and ESPRIT [17] were two famous algorithms to solve the problem of DOA estimation with high resolution. Some new array geometries except for ULA are proposed to further enhance this advantage. Minimization redundancy linear array (MRLA) [18] was used in the sensor array [10] and the multiple-input multiple-output (MIMO) radar [11] to obtain the larger array aperture. However, the implementation difficulty of MRLA blocks the development of this method. Pal and Vaidyanathan nested two or more ULAs and provided a nested array to solve the DOA estimations with high degrees of freedom, which is up to O(N^2k) with 2kN sensors [12]. And then, they proposed a new approach for high resolution line spectrum estimation in both temporal and spatial domain using a co-prime pair of samplers [13]. Two uniform samplers with sample spacings MT and NT are used where M and N are co-prime and T has the dimension of space or time, which achieves O(MN) freedoms with M + N sensors. The implementations of these two array structures are easier than that of MRLA.

However, a more flexible structure of array like sparse linear array (SLA) is expected to estimate the DOA of sources together and developed by the revolution of compressed sensing (CS) [19]. To reduce the demand of sensors with no accuracy decreasing, a convex optimization method was used to deal with the problem of DOA estimation [20–23]. Although, ℓ₀-norm of the incident signals is a rigorous way to model the sparsity constraint on the spatial distribution of sources, the ℓ₀-norm-based optimization problem is not convex, and it is NP-hard to solve it directly [24]. Thus, convex relaxation is used to transform this problem into a convex one [22] and ℓ₁-norm is introduced to solve it via a convex optimization process [20,21,25,26]. The recent development of CS theory [19] has verified the effectiveness of the application of sparse recovery technique with convex optimization [27] to DOA estimation with the same array structure. A sparse representation of signal in the space domain and its corresponding covariance vectors are comprehensively studied in [28,29]. And, Liu and Sha further extended their own wideband covariance matrix sparse representation method to focus on DOA estimation of wideband signals, respectively [30,31]. However, these CS-based methods are all constrained to study the sources sparse distributed on a pre-defined grid. Tan et al., used joint sparsity reconstruction methods based on co-prime array to explore the underlying structure between sparse signals and gird mismatch [14]. Based on the developing theory of super resolution, they utilized the degrees of freedom for the co-prime arrays and proposed a sparse recovery method via total variation to obtain higher resolution [15].

In the practical applications of multiple arrays (such as wireless array sensor network, partial discharge location [32], volcano monitoring [33] and underwater monitoring [34]), the localized sources for each array maybe different which makes the existing co-arrays based methods out of action. In this article, we focus on the problem of joint DOA estimations for multiple distributed SLAs with the coexistence of common and innovation sources. The sources are classified according to whether they are observed by all the SLAs (The source observed by all the arrays named the common source and that observed by a specific array named the innovation source). This situation has not been discussed in the existing off-grid methods with co-arrays [15]. We can only obtain these DOA information via the accurate estimation algorithms separately implemented in different arrays. No advantage of joint calculation appears by using the process of centralized processing. But the observed signals of common sources in different arrays have redundancy which brings about repeated calculations in the DOA estimations. In our prior work, a joint frequency sparsity (JFS) model was built up and the distributed compressed sensing (DCS) off the grid was studied [35,36]. We introduce this idea of off-grid DCS into solving the problem of joint DOA estimation with distributed SLAs under the coexistence of common/innovation sources. An off-grid synchronous approach is proposed to utilize the observed signals in different arrays to estimate the DOA information together. We construct a virtual-ULA (VULA) for each SLA and consider the observed signals in a SLA as the random measurements of the observed signal in its corresponding VULA. The relationship between these two signals can be described as a random linear map. As assumed that the observed signal ensemble of each SLA is composed of sparsely distributed common and innovation sources, each ensemble is abstracted as a joint spatial sparsity (JSS) model under continuous atomic basis and described by a concatenated atomic norm (CA-norm). Since the compressed linear relation, the problem of joint DOA estimation is reformulated as the minimization of CA-norm. Semidefine program (SDP) is used to search the accurate solution under the condition of under-sampling. By exploiting the continuous counterpart [37] of the JSS model, off grid estimation results is achieved with no decreasing of freedom. Also, joint calculation exploits the redundancy among the signals of common sources observed by different SLAs to decrease array aperture size. Numerical results are given to illustrate the effectiveness of our approach and its advantage over the conventional methods of separate DOA estimation, which indicate a significant reduction in array aperture with the same estimation accuracy.

In this article, we use capital italic bold letters to represent matrices, and lowercase italic bold letters to represent vectors. For a given matrix A, A* denotes the conjugate transpose of A, A^T denotes the regular transpose, and A^H denotes the conjugate without transpose. For a given p, ‖p‖₀, ‖p‖₁ are the ℓ₀ and ℓ₁ norms, respectively, p_i to represent the i-th element in p. ‖·‖ is the atomic norm and ${\Vert \cdot \Vert }_{\mathcal{A}}^{\ast }$ is the dual norm of it. We use ⊗) to denote the Kronecker product of two matrices, and ⊙ to denote the point-wise multiplication of two vectors with the same dimension.

2. System Model

3. SDP Based Joint DOA Estimation Algorithm

3.1. CA-Norm of JSS Model

The ill-posed inverse problem was studied by Chandrasekaran [38] and a general framework was provided to convert notions of simplicity into convex penalty functions, resulting in convex optimization solutions to linear undetermined inverse problems. Considering a simple model with a nonnegative combination of a few sensors from atomic set, signal x ∈ ℝ^P can be formed as follows:

$$\mathit{x}=\sum _{i=1}^K{c}_i{\mathit{a}}_i,{\mathit{a}}_i\in \mathcal{A},c_i\ge 0$$

(21)

where is a set of atoms that constitutes simple building blocks of general signals. And x is assumed simple so that K is relatively small. Then, the definition of atomic norm was given as [38]

$${\Vert \mathit{x}\Vert }_{\mathcal{A}}=inf\{\sum _{a\in \mathcal{A}}:\mathit{x}=\sum _{a\in \mathcal{A}}{c}_a\mathit{a},c_a\ge 0\forall a\in \Lambda \}$$

(22)

And the support function of is given as:

$${\Vert \mathit{\text{x}}\Vert }_{\mathcal{A}}^{\ast }=sup\{\langle \mathit{x},\mathit{a}\rangle :\mathit{a}\in \mathcal{A}\}$$

(23)

Equipped with a convex penalty function given a set of atoms, a convex optimization method can be used to recover a “simple” model given limited linear measurements. With a known linear map Φ : ℝ^P → ℝ^N, linear information about x* formed according to Equation (21) from a set of atoms is given as:

$$\mathit{y}=\mathbf{\Phi }\tilde{x}$$

(24)

The convex formulation to reconstruct x̃ given y:

$$\begin{array}{ccc}\widehat{\mathit{x}}=arg\underset{x}{min}{\Vert x\Vert }_{\mathcal{A}}& s.t& \mathit{y}=\mathbf{\Phi }x\end{array}$$

(25)

The dual problem of Equation (25) is given as follows:

$$\begin{array}{ccc}\underset{z}{max}{\mathit{y}}^{T}z& s.t.& {\Vert {\mathbf{\Phi }}^{\ast }z\Vert }_{\mathcal{A}}^{\ast }\le 1\end{array}$$

(26)

Obviously, Equation (20) is such an ill-posed inverse problem, when the number of available sensors of SLAs is smaller than the number of sensors in VULAs, i.e., M_j ≪ N. We can construct J + 1 atoms sets for the JSS model in Equation (11), respectively corresponding to the signal of common source s_c(t) and the signal of innovation source s_j(t), which take the same form of

$$\mathcal{A}=\{\begin{array}{cc}{\alpha }_j(\xi ,n):\xi \in [0,1],& n\in [0,1,\dots ,N-1]\end{array}\}$$

(27)

where, α(ξ, n) = e^{−j2π(n−1)ξ}. The sets of variables ${\Omega }_c={\{{\xi }_{c,k}\}}_{k=1}^{K_c}$ and ${\Omega }_j={\{{\xi }_{j,k}\}}_{k=1}^{K_j}$ can lie anywhere on the unite circle, such that ξ_c,_k, ξ_j,_k are continuously valued in [0,1].

In the prior work, we have considered a joint frequency sparsity (JFS) model and extended the atomic norm to JFS setting [35]. To develop a norm description of the JSS, we also extend the atomic norm to JSS setting and give the definition of CA-norm of JSS. The “ℓ₀-norm” type atomic norm [38] is defined as

$${\Vert \mathit{r}\Vert }_{\mathcal{A},0}=inf\left\{s:\mathit{r}=\sum _{k=1}^K{\sigma }_{k}a({\xi }_k)\right\}$$

(28)

and it convex relaxation, the atomic norm [38], is defined as

$${\Vert \mathit{r}\Vert }_{\mathcal{A}}=inf\left\{\sum _k{\sigma }_k:\mathit{r}=\sum _{k=1}^K{\sigma }_{k}a({\xi }_k)\right\}$$

(29)

where, σ_k ≥ 0 as it is denoted as the power of signal.

The “ℓ₀-norm” type CA-norm of signal from VULA is defined as

$${\Vert \mathit{R}\Vert }_{\mathcal{C}\mathcal{A},0}=inf\left\{{\Vert z_c\Vert }_{\mathcal{A},0}+\sum _{j\in \Lambda }{\Vert z_j\Vert }_{\mathcal{A},0}:z_c+z_j=r_j,j\in \Lambda \right\}$$

(30)

With the consideration of Equation (20), the goal of DOA estimation problem becomes the minimization of ‖R‖_cA,0 satisfying the measurement a-priori

$$\begin{array}{ccc}\underset{\mathit{R}}{min}{\Vert \mathit{R}\Vert }_{\mathcal{C}\mathcal{A},0}& s.t.& w_j={\mathbf{\Psi }}_j{r}_j,j\in \Lambda \end{array}$$

(31)

We study the spark of continuous dictionary Φ in Equation (20). The quantity spark of Φ, denoted by spark(Φ), is the smallest number of atomic of Φ which are linearly dependent. spark(Φ) = spark(Φ_c) + Σ_j∈Λ spark(Φ_j) ∈ [2, M + 1]. Considered as a distributed model of [39], $r_j={\sum }_{k=1}^K{\sigma }_k{a}_j({\xi }_k)$, j ∈ Λ is the unique optimizer to Equation (31) if

$$K<\frac{\text{spark}({\mathbf{\Phi }}_c)+{\sum }_{j\in \Lambda }\text{spark}({\mathbf{\Phi }}_j)-1+{\sum }_{j\in \Lambda }\text{rank}({\omega }_j)}{2}$$

(32)

where, the atomic decomposition above ia the unique one satisfying that K = ‖R‖ _,0. It is the theoretical guarantees of the “ℓ₀-norm” type CA norm minimization in Equation (31).

4. Numerical Experiments

In this section, we evaluated the proposed approach by performing numerical experiments. We choose the probability of success as the major performance. The DOA estimation is considered as successful if the DOA estimation error of each source satisfies the following condition

We focus on the key impact factor of array aperture size and evaluate the demand of sensors in each SLA via different DOA estimation methods with multiple parameter settings. DOAs were generated uniformly random on [0,1] with an additional constraint on minimum separation Δ as follows

The inter-element spacings of SLAs were generated uniformly random on [λ/2, 40(λ/2)], which is integer multiple of the half wavelength. JSDP in Equation (38) was solved via SDPT3-4.0 toolbox [41].

Firstly, we compare the proposed JSDP with the original separate-SDP (SSDP) approach in the ULAs. SSDP means joint calculation of the observed signals without any co-arrays methods. We set K_c = 4, K_j = 2 in each signal ensemble. We performed Monte Carlo experiments for M_j from 2 to 18 and J = 1, 2, 4, 8, and recorded the probability of success from 2000 trials. The number of sensors in the VULA in JSDP is assumed as N = 40 to ensure that all the sources for SLAs in system can be localized. Figure 4 shows the performance curves.

The JSDP approach exhibits a definite advantage over its separate counterpart. In SSDP, one SLA requires at least 7 sensors to possibly localize 6 sources, and the increase of array number brings about larger calculation errors so as to decrease the probability of success. JSDP is equality to SSDP when J = 1, which requires approximately 11.7 sensors to successfully localize 6 sources with high probability. The JSDP approach achieves exact DOA estimation after M_j exceeds a certain threshold, which is the demand of approximately 8.9 sensors in each SLA for J = 2, while at least 12.6 sensors per SLA are required for SSDP to achieve comparable performance. The gap increases with the increase of J, implying the promise of application to multi-arrays systems. When J = 4 and J = 8, JSDP respectively requires approximately 7.1 and 6.4 sensors to address the requirement of successful DOA estimations; SSDP respectively requires at least 15 sensors. Obliviously, JSDP makes the sensors in all the SLAs virtually construct a larger array to implement the DOA estimation of common sources which brings about larger degrees of freedom. In other words, we can use the arrays with smaller aperture size via JSDP to satisfy the same demand of sources localized via SSDP. The increase of J decreases the aperture requirement and system cost of SLAs.

Then, we discuss the parameter impact of source number in detail. The number of common sources is the key object in the research closely related to the performance of JSDP. In the case of 4 SLAs system, 4 signal ensembles with 2 innovation sources are assumed. We performed Monte Carlo experiments for M_j from 2 to 18 and the number of common sources K_c = 1, 2, 4, 8, and recorded the probability of success from 2000 trials. The performance curves are shown in Figure 5.

When J = 1, approximately 6.2 sensors per SLA can successfully localize all 9 sources with high probability. As the increase of number of common sources, JSDP with original array aperture cannot obtain so many successful estimation and more sensors are required to allow more sources localized. In the situation with more localized sources, the sensors In short, an increasing number of common sources will increase the workloads of SLAs. The increase of J decreases the increment of sensors in each SLA. The total amount of sensors in the system is approximately proportional to the number of common sources according to the simulation results. We believe there has a relationship of the number of sensors and common sources. The theoretical bound will be studied in our next work.

Of course, the impact of the number of innovation sources should also be studied to fully prove the high efficiency of JSDP. We discuss a SLAs system with 8 innovation sources in all, which means J × K_j is a constant set as 8. Thus, J = 1, 2, 4, 8, corresponding to K_j = 8, 4, 2, 1. And the number of common sources is still 4. We performed Monte Carlo experiments for M_j from 2 to 25 and recorded the probability of success form 2000 trials. The number of sensors in the VULA is assumed as N = 80 to ensure that all the sources for SLAs in system can be localized. Figure 6 shows the performance curves.

As the average number of common and innovation sources per SLA is isocon descending with the number of SLAs, the demand of sensors per SLA is approximately proportional to the number of SLAs too. The demand of sensors when J = 1 is twice times as that when J = 2, and so on. The results fully indicate that all the sensors undertake the equal number of estimation task for common sources. On the other hand, the array aperture size is closely related to the number of sources in each SLA, which supports the definition of degree of freedom.

From the above simulation results, we can draw a conclusion that one source need about 2.3 sensors to estimate its DOA, which is similar to the conclusion in [37] to require at least two samples for a spike.

Moreover, we also discuss the demand of sensors for the aperture size assumed in the VULA. We set K_c = 4, K_j = 2 in each ensemble. We performed Monte Carlo experiments for M_j from 2 to 18 and N = 40, 80, 160, and recorded the probability of success from 2000 trials. The number of SLAs is set as J = 4. Figure 7 shows the performance curves.

Similar to all kind of DOA estimation methods, the aperture size of VULA has a threshold for enough degree of freedoms, in terms of the largest spacing difference of any two sensors in a SLA. If the array aperture addresses the requirement, the performance enhancement of algorithm becomes slow. Of courses, the ULA with larger aperture has higher degree of freedoms. However, the estimation accuracy is depended on the solution methods. In JSDP, the minimum resolution is determined by sensor numbers described in Equation (45). The finer resolution makes the DOA information in the case of two sources with a small DOA difference estimated more accurate so as to increase the probability of success.

5. Conclusions

The array aperture size is one of the most important parameters in array signal processing, highly effecting the accuracy of DOA estimations and the cost of location system. In this article, we discussed the application of multiple distributed SLAs with the coexistence of common and innovation sources, which was not referred to in the existing co-arrays methods. The separate algorithm for each SLA brings about the repeated calculations of DOA estimations for the common sources. The redundancy of the signal of common sources motivated us to address this problem with a joint DOA estimation method. All the sources for each SLA were classified into the common sources and the innovation ones. The common source was defined as the signal of which can imping on all SLAs in the system and the innovation one was defined as that can only imping on a specific SLA. Considering that the sources are sparse spatial distributed, we can use a JSS model to describe the problem of joint DOA estimation. We constructed a VULA for each SLA to obtain O(N) freedoms with M_j sensors, and considered the signals observed by SLAs as the samplers of those observed by their corresponding VULAs. The relationship between these two kinds of signals is a random linear map. An off-grid synchronous approach was proposed to combine the observed signals in all the SLAs and jointly estimate the DOA information of all sources. A CA-norm was used to reformulate the problem of joint DOA estimation into the minimization problem, which was solved via JSDP. By exploiting the continuous counterpart of the JSS model, the DOAs of all sources can be simultaneously estimated with off-grid estimation accuracy. And the sources are localized with the arrays of smaller aperture in terms of the decrease of sensors via JSDP. From the numerical results, we can find the joint approach has more advantages than the existing separated one. All the estimation tasks are shared by all the SLAs which brings about at least 20% decrease of demand of sensors per SLA.

Of course, in this article we did the initial researches on the joint DOA estimation with distributed SLAs. Some more complex conditions such as the noise environment and different number of sensors per SLA (like co-prime arrays) should be considered in our next works. Although we conclusion the impacts of SLA number, source number and sensor number per VLUA on the demand of sensors in the SLAs, the formulation indicating the relationship between sensor number and the above parameters will be studied in detail.