# Sparse Array Design for DOA Estimation of Non-Gaussian Signals: From Global Postage-Stamp Problem Perspective

Authors: Changbo Ye; Luo Chen; Beizuo Zhu
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

In this paper, a sparse array design problem for non-Gaussian signal direction of arrival (DOA) estimation is investigated. Compared with conventional second-order cumulant- (SOC-) based methods, fourth-order cumulant- (FOC-) based methods achieve improved DOA estimation performance by utilizing all information from received non-Gaussian sources. Considering the virtual sensor location of vectorized FOC-based methods can be calculated from the second order difference coarray of sum coarray (2-DCSC) of physical sensors, it is important to devise a sparse array design principle to obtain extended degree of freedom (DOF). Based on the properties of unfolded coprime linear array (UCLA), we formulate the sparse array design problem as a global postage-stamp problem (GPSP) and then present an array design method from GPSP perspective. Specifically, for vectorized FOC-based methods, we divide the process of obtaining physical sensor location into two steps; the first step is to obtain the two consecutive second order sum coarrays (2-SC), which can be modeled as GPSP, and the solutions to GPSP can also be utilized to determine the physical sensor location sets without interelement spacing coefficients. The second step is to adjust the physical sensor sets by multiplying the appropriate coprime coefficients, which is determined by the structure of UCLA. In addition, the 2-DCSC can be calculated from physical sensors directly, and the properties of UCLA are given to confirm the degree of freedom (DOF) of the proposed geometry. Simulation results validate the effectiveness and superiority of the proposed array geometry.


---

## Body

## 1. Introduction

In array signal processing, direction of arrival (DOA) estimation has drawn considerable attention, which has been widely applied in various fields, such as communication, radar, and navigation [1, 2]. To obtain improved DOA estimation performance, the sparse arrays with reduced mutual coupling and enhanced degree of freedom (DOF) have been proposed, whose adjacent sensor spacing is no longer limited to half wavelength, as compared with uniform linear array (ULA). Minimum redundancy array (MRA) [3], minimum holes array (MHA) [4], coprime array (CA) [5], and nested array (NA) [6] have been proposed, which are designed based on the second-order cumulant (SOC) for Gaussian signals. Besides, these arrays utilize second order difference coarray (2-DC) or second order difference coarray of sum coarray (2-DCSC) generated by vectorization operation to obtain virtual sensors, which can be used to construct virtual nonuniform linear array (NLA) or ULA. Once the equivalent received signal of the virtual array is constructed, the DOA estimates can be obtained by compressed sensing (CS) [7], discrete Fourier transform (DFT) algorithm [8], and other algorithms. Nevertheless, there still exist some drawbacks for these sparse arrays. Specifically, there is no closed-form expression of physical sensor positions for the MRA and MHA. The CA structures generate holes in the difference coarray which decreases the consecutive DOF, and the NA structures suffer from severe mutual coupling due to the dense part. In order to tackle these issues, some sparse arrays with enhanced DOA estimation performance based on NA or CA have been proposed, such as augmented NA (ANA) [9], the generalized CA with displaced subarrays (CADiS) [10], unfolded coprime linear array (UCLA) [11, 12], and augmented CA (ACA) [13].It is noteworthy that all aforementioned sparse arrays mentioned above are all designed based on SOC, which is available for Gaussian signals. In practice, most sources are non-Gaussian, and fourth-order cumulant (FOC) matrix is exploited instead of SOC to calculate correlation matrix [14, 15]. In particular, the FOC-based methods employ second order difference coarray of sum coarray (2-DCSC) to obtain virtual sensors with vectorization operation [16, 17]. As the 2-DC and second order sum coarray (2-SC) are utilized successively, it is complicated to obtain the location relationship between physical sensors and 2-DCSC. In [17], Fu et al. employed virtual nested multiple-input multiple-output (MIMO) array [18], which utilized fourth order difference coarray of sum coarray (4-DCSC), termed as NA-MIMO-DCSC. The authors optimized the process of obtaining 4-DCSC separately, i.e., fourth order sum coarray (4-SC) and 2-DC, which further improved DOF greatly when FOC was employed in MIMO systems. Unfortunately, limited to the properties of NA, the virtual sensors still suffered from a lot of redundancy in the steps of optimizing 2-DC. More importantly, the design principle of NA-MIMO-DCSC neglected the discussion of cross-sum coarray generated in the process of obtaining 4-SC.In this paper, we propose a sparse array design method for non-Gaussian signal from the perspective of global postage-stamp problem (GPSP) [19, 20]. To further illustrate this method, the two steps of obtaining sparse array geometry based on the structure of UCLA are described. Specifically, the first step is to get the longest possible two 2-SC from given sensor number of each subarray, which can be modeled as a GPSP. The solution to GPSP can also be used to obtain initial physical sensor location sets with half-wavelength interelement spacing. Subsequently, the second step is to adjust the physical sensor location sets by multiplying the appropriate coefficients, which can be determined based on the structure of UCLA. To verify the priority of the proposed array geometry, the properties of UCLA about DOF and consecutive virtual sensors are also provided. Furthermore, the expression between the DOF of proposed geometry and physical sensors is presented, and the relationship between 2-SC and cross-sum coarray is also analyzed in Section 4.1.In particular, the contributions of this paper are summarized as follows:(1)
We investigate the array design problem of sparse array with non-Gaussian signals and tackle this problem by obtaining the longest possible virtual 2-SC and exploiting the properties of UCLA(2)
We formulate the obtaining longest possible 2-SC problem as a GPSP and give a simple solution to the GPSP, which can be used to determine the location sets. Furthermore, we provide the closed-form expression of maximum DOF and consecutive virtual sensors of UCLA with 2-DC, which is used to analyze the DOF of proposed array geometry(3)
We devise a sparse design principle which divides the process of obtaining sparse array location into two steps, i.e., obtaining the 2-SC from the given number of subarray and determining the location of physical sensors with multiplication operationWe outline this paper as follows. In Section2, we present the sparse array model and mutual coupling effect; besides, the properties of UCLA are also investigated. Section 3 elaborates the GPSP and proposed array geometry with enhanced DOF. Section 4 gives the performance analysis. Section 5 provides simulation results, and the conclusions are drawn in Section 6.Notations. Vectors and matrices are represented by utilizing bold low-case and bold-case characters, respectively. ⊗ is Kronecker product, and ⊙ denotes Khatri-Rao product. ⋅T, ⋅H, ⋅−1, and ⋅∗ stand for the transpose, conjugate transpose, inverse, and complex conjugation of a vector or matrix, respectively. vec⋅ denotes the vectorization operation. diag⋅ is the diagonal matrix operator, and ⋅F means the Frobenius norm.


## 2. Preliminaries

In this section, we first present the definitions of 2-DC, 2-SC, and 2-DCSC. Subsequently, considering that the 2-SC of proposed array geometry is constructed based on the UCLA, we exploit the properties of UCLA in terms of DOF and consecutive lag location. Finally, we provide the sparse array model without mutual coupling and with mutual coupling, respectively.


### 2.1. 2-DC, 2-SC, and 2-DCSC

For a linear array withL physical sensors, whose location set can be denoted as S=d1,⋯di,⋯,dL, where di,1≤i≤L represents the location of i-th sensor.Definition 1 (2-DC).
The second order difference coarray locationD can be defined as [6]
(1)D=D+∪D−=di−dj,di,dj∈S,where D+ and D− represent the positive and negative elements of D, respectively.Definition 2 (2-SC).
The second order sum coarray locationSs can be defined as [17]
(2)Ss=di+dj,di,dj∈S.Definition 3 (2-DCSC).
The second order difference coarray of sum coarray locationDdcsc can be defined as
(3)Ddcsc=di−dj,di,dj∈D=di1+dj2−dj1+di2,di1,di2,dj1,dj2∈S,where S and D represent the physical sensors and 2-DC location sets, respectively.


### 2.2. The Properties of UCLA

Figure1 shows the configuration of UCLA, which is composed of two sparse uniform subarrays that overlap at the origin. The sensor position of UCLA can be represented as [11, 12]
(4)SUCLA=−mNd0≤m≤M−1∪nMd0≤n≤N−1,where M and N represent the physical sensors of subarray 1 and subarray 2, respectively. d=λ/2, and λ is the wavelength.Figure 1
Unfolded coprime linear array.According to Definition1, the 2-DC of UCLA can be denoted as DUCLA, and DUCLA=DUCLA+∪DUCLA‐. In addition, the properties of UCLA are derived in the Lemma 4.Lemma 4.
The following properties hold for UCLA:(a)
There areMN distinct lags in set DUCLA+ or DUCLA‐(b)
DUCLA+ contains the consecutive lags with element spacing d=λ/2 in the range of M−1N−1d,MNd−dProof.
See the Appendix A.
As described in Lemma4, the DOF of UCLA can be given by
(5)DOFUCLA=2MN−1.


### 2.3. Sparse Array Model without Mutual Coupling

Assume that there areK far-field narrowband uncorrelated non-Gaussian signals impinging on a nonuniform linear array with DOAs θk,k=1,2,⋯,K, where θk denotes the elevation angle of the k-th target. The location set of nonuniform linear array with L physical sensors can be denoted as S=d1,d2,⋯,dL; then, the received signal xt can be expressed as [21].
(6)xt=Ast+nt,where Aθ=aθ1,aθ2,⋯,aθK∈ℂL×K represents the steering matrix, and aθk=e−j2πd1sinθk/λ,e−j2πd2sinθk/λ,⋯,e−j2πdLsinθk/λT∈ℂL×1 is the steering vector, λ denotes wavelength. st=s1t,s2t,⋯,sKtT∈ℂK×1,1≤t≤J deotes the non-Gaussian signals matrix with mean zero, where J represents the total number of snapshots and nt∈ℂL×1 is the additive Gaussian noise with variance σn2 and mean zero.The FOC matrix of the received signalxt can be calculated by [14, 15]
(7)C4,x=∑k=1Kc4,skaθk⊗a∗θkaθk⊗a∗θkH=∑k=1Kc4,ska4,xθka4,xHθk,where
(8)a4,xθk=aθk⊗a∗θk,1≤k≤K,whose elements can be constructed by aθk with the specific form e−jπdi−djsinθk,di,dj∈S. c4,sk=Cumskt,skt,sk∗t,sk∗t denotes the FOC of sKt, where Cum⋅ is the cumulant operator.To obtain the equivalent received signal from the virtual array, we vectorizeC4,x as [17, 22]
(9)z=vecC4,x=Avecθp,where
(10)Avecθ=a4,x∗θ1⊗a4,xθ1,a4,x∗θ2⊗a4,xθ2,⋯,a4,x∗θK⊗a4,xθK=avecθ1,avecθ2,⋯,avecθK,whose elements are constructed by a4,xθk with the specific form e−jπdi−djsinθk,di,dj∈D, and p=σ12,σ22,⋯,σK2T, σk2k=1,2,⋯,K denotes the power of k-th source.


### 2.4. Sparse Array Model with Mutual Coupling

In practice, each sensor will inevitably be affected by the radiation of from its adjacent sensors, and consequently, the received signal should be modified in the presence of mutual coupling. That means the mutual coupling effect must be taken into consideration. Specifically, the signal model in (6) can be refined as
(11)x~t=CAst+nt,where C represents the mutual coupling matrix. By utilizing the B-band model in [23], the elements in the mutual coupling matrix can be represented by
(12)Ci,j=0di−dj>Bcdi−djdi−dj≤B,1=c0>c1>⋯>cB>cB+1=0,where di,dj∈S and c1=0.3ejπ/3,cl=c1e−jl−1π/8/l,l∈2,B, B=100 represents the maximum spacing between the coupled sensor pairs [23]. In order to measure the strength of the mutual coupling effect, the coupling leakage is introduced and is defined as
(13)LM=C−diagCFCF.Based on the mutual coupling model in (12), the equivalent signal model in (9) can be reconstructed as
(14)z~=CvecAvecp,where Cvec=C⊗C∗∗⊗C⊗C∗.


## 2.1. 2-DC, 2-SC, and 2-DCSC

For a linear array withL physical sensors, whose location set can be denoted as S=d1,⋯di,⋯,dL, where di,1≤i≤L represents the location of i-th sensor.Definition 1 (2-DC).
The second order difference coarray locationD can be defined as [6]
(1)D=D+∪D−=di−dj,di,dj∈S,where D+ and D− represent the positive and negative elements of D, respectively.Definition 2 (2-SC).
The second order sum coarray locationSs can be defined as [17]
(2)Ss=di+dj,di,dj∈S.Definition 3 (2-DCSC).
The second order difference coarray of sum coarray locationDdcsc can be defined as
(3)Ddcsc=di−dj,di,dj∈D=di1+dj2−dj1+di2,di1,di2,dj1,dj2∈S,where S and D represent the physical sensors and 2-DC location sets, respectively.


## 2.2. The Properties of UCLA

Figure1 shows the configuration of UCLA, which is composed of two sparse uniform subarrays that overlap at the origin. The sensor position of UCLA can be represented as [11, 12]
(4)SUCLA=−mNd0≤m≤M−1∪nMd0≤n≤N−1,where M and N represent the physical sensors of subarray 1 and subarray 2, respectively. d=λ/2, and λ is the wavelength.Figure 1
Unfolded coprime linear array.According to Definition1, the 2-DC of UCLA can be denoted as DUCLA, and DUCLA=DUCLA+∪DUCLA‐. In addition, the properties of UCLA are derived in the Lemma 4.Lemma 4.
The following properties hold for UCLA:(a)
There areMN distinct lags in set DUCLA+ or DUCLA‐(b)
DUCLA+ contains the consecutive lags with element spacing d=λ/2 in the range of M−1N−1d,MNd−dProof.
See the Appendix A.
As described in Lemma4, the DOF of UCLA can be given by
(5)DOFUCLA=2MN−1.


## 2.3. Sparse Array Model without Mutual Coupling

Assume that there areK far-field narrowband uncorrelated non-Gaussian signals impinging on a nonuniform linear array with DOAs θk,k=1,2,⋯,K, where θk denotes the elevation angle of the k-th target. The location set of nonuniform linear array with L physical sensors can be denoted as S=d1,d2,⋯,dL; then, the received signal xt can be expressed as [21].
(6)xt=Ast+nt,where Aθ=aθ1,aθ2,⋯,aθK∈ℂL×K represents the steering matrix, and aθk=e−j2πd1sinθk/λ,e−j2πd2sinθk/λ,⋯,e−j2πdLsinθk/λT∈ℂL×1 is the steering vector, λ denotes wavelength. st=s1t,s2t,⋯,sKtT∈ℂK×1,1≤t≤J deotes the non-Gaussian signals matrix with mean zero, where J represents the total number of snapshots and nt∈ℂL×1 is the additive Gaussian noise with variance σn2 and mean zero.The FOC matrix of the received signalxt can be calculated by [14, 15]
(7)C4,x=∑k=1Kc4,skaθk⊗a∗θkaθk⊗a∗θkH=∑k=1Kc4,ska4,xθka4,xHθk,where
(8)a4,xθk=aθk⊗a∗θk,1≤k≤K,whose elements can be constructed by aθk with the specific form e−jπdi−djsinθk,di,dj∈S. c4,sk=Cumskt,skt,sk∗t,sk∗t denotes the FOC of sKt, where Cum⋅ is the cumulant operator.To obtain the equivalent received signal from the virtual array, we vectorizeC4,x as [17, 22]
(9)z=vecC4,x=Avecθp,where
(10)Avecθ=a4,x∗θ1⊗a4,xθ1,a4,x∗θ2⊗a4,xθ2,⋯,a4,x∗θK⊗a4,xθK=avecθ1,avecθ2,⋯,avecθK,whose elements are constructed by a4,xθk with the specific form e−jπdi−djsinθk,di,dj∈D, and p=σ12,σ22,⋯,σK2T, σk2k=1,2,⋯,K denotes the power of k-th source.


## 2.4. Sparse Array Model with Mutual Coupling

In practice, each sensor will inevitably be affected by the radiation of from its adjacent sensors, and consequently, the received signal should be modified in the presence of mutual coupling. That means the mutual coupling effect must be taken into consideration. Specifically, the signal model in (6) can be refined as
(11)x~t=CAst+nt,where C represents the mutual coupling matrix. By utilizing the B-band model in [23], the elements in the mutual coupling matrix can be represented by
(12)Ci,j=0di−dj>Bcdi−djdi−dj≤B,1=c0>c1>⋯>cB>cB+1=0,where di,dj∈S and c1=0.3ejπ/3,cl=c1e−jl−1π/8/l,l∈2,B, B=100 represents the maximum spacing between the coupled sensor pairs [23]. In order to measure the strength of the mutual coupling effect, the coupling leakage is introduced and is defined as
(13)LM=C−diagCFCF.Based on the mutual coupling model in (12), the equivalent signal model in (9) can be reconstructed as
(14)z~=CvecAvecp,where Cvec=C⊗C∗∗⊗C⊗C∗.


## 3. Sparse Array Design Principle

Motivated by the advantages of the sparse arrays over the uniform arrays, several sparse array configurations as well as design methods have been proposed. Unfortunately, most existing array design methods generate the difference coarray based on the SOC while the FOC with great potentiality in improving array performance is neglected. In this part, we devise a sparse array principle based on 2-DCSC employed by vectorized FOC-based method.In fact, because 2-DCSC performs twice 2-DC operations on physical sensors, which can also be converted into 2-SC and 2-DC operations, successively, as described in (3). The relationship between virtual sensors and physical sensors is complicated; it is difficult to obtain the closed-form expression of physical location with large DOF. We optimize the process of obtaining the location of physical sensor location into two steps, i.e., obtaining longest possible 2-SC of each subarray, constructing physical sensor location set based on the structure of UCLA. Specifically, the first step can be modeled as GPSP, whose solution can be used to determine the physical sensor set lacking interelement spacing coefficients. The second step employs the structure of UCLA to adjust the self-sum coarray set obtained by the first step, which can also be used to determine the spacing of physical sensors. As a result, the physical sensor location set can be obtained. According to (3), the 2-DCSC can be calculated from physical sensor set directly.


### 3.1. Global Postage-Stamp Problem (GPSP)

The GPSP is a well-known combination problem that has not yet been fully solved, which can be described as follows: for given positive integersh and k, a set with k nonnegative integers is determined by
(15)Sk=0=a1<⋯<ak.Remark 5.
The elements inSk need to be summed h times to realize the consecutive numbers 0,1,2,⋯,nhSk. Besides, the value of nhSk should be as large as possible.
The solution to the GPSP has been investigated in [19, 20]. Herein, we also give a simple method to solve GPSP. Specifically, h can be considered as the maximum number of stamps on an envelope; Sk is the set of stamp denominations with k non-negative value. Then, the computational complexity of obtaining all possible combinations is Okh. An example is given to illustrate the solution method to GPSP explicitly. When Sk=1,3, in this case, 1 and 2 stamps are required to obtain postages 1 and 2, respectively. For postage 3, there are two combinations, i.e., one stamp with postage 3 or three stamps with postage 1. According to Remark 5, because of the existence of postage 0, the number of stamps currently required should be as small as possible. Besides, it can be concluded that the minimum k can be obtained by comparing all the postage combinations. The process of this method is summarized in Algorithm 1, where h=2. It is noteworthy that Sk is treated as prior information to obtain nhSk. When Sk is unknown, its (i+1)-th element should satisfy
(16)ai+1∈ai+1,ai×h+1,where ai represents i-th element of Sk, 1≤i≤k. Then, all elements of can be obtained by enumerating all the values of ai. The result of Algorithm 1 is listed in Table 1, which is also provided in [20].Algorithm 1: The algorithm of solving the GPSP with known Sk.
Input: stamps value set Sk, number of stamps types k, sum times h=2Output: Maximum consecutive postage nhSk1:initialize:dp0=0,i=02:whiledpi<hdo3:i++, dpi=i, j=04:whilej<k&Skj≤ido5:ifdpi−Skj+1<dpithen6:dpi=dpi−Skj+1,j++7:  end if8:end while9:end while10:returni−1nhSkTable 1
Result of Algorithm1.
kn2SkSk480134512013566160135787200125891072001348911720013491116720013561314720013579108260125811121382601349101213826013578171893201258111415169320135791021221040013491116171920114601237111519212224114601257111519212224125401237111519232526281254012571115192325262812540134911161823242627125401356131421222426271364013491116212328293132


### 3.2. Sparse Array Design Based on UCLA

The design methods for sparse arrays based on SOC only utilize 2-DC or 2-SC once, which can be extended to FOC-based array directly by adding 2-DC calculation. But this approach neglects the specifical output of first operation, resulting in a large amount of redundancy, and the DOF loss is inevitable. Suppose that the physical sensors are composed of multiple linear subarrays, and the number of elements in each subarray has been given.Without loss of generality, assume that the physical sensors are composed of two subarrays withM and N elements, respectively. As illustrated in Section 3, to obtain the longest possible 2-SC of each subarray, the integer sets SM and SN are solved from GPSP in (15) with k=M,N,h=2, which can be used to determine the largest possible lags n2SM and n2SN. It is noteworthy that the sets SM and SN can be considered as the initial physical location sets without coefficients. Based on Remark 5, if all elements of SM are negative, the consecutive integer set obtained from M is
(17)−n2SM,⋯,−2,−1,0,where SM represents a set with M elements and n2SM is the largest possible integer mentioned in Remark 5. Similarly, the consecutive positive integer set obtained from N is
(18)0,1,2,⋯,n2SN.Based on the structure of UCLA, we multiply all the elements in (17) and (18) by certain coefficients d1 and d2, respectively; then, the new sets can be constructed as the two cosubarrays of UCLA. Specifically, the cosubarray 1 of UCLA location set associated with (17) can be expressed as
(19)SsM=−n2SMd1,⋯,−2d1,d1,0,where d1=n2SN+1d is the interelement spacing of cosubarray 1; d=λ/2, and λ is wavelength. The cosubarray 2 location set associated with (18) can be expressed as
(20)SsN=0,d2,2d2,⋯,n2SNd2,where d2=n2SM+1d is the interelement spacing of cosubarray 2. Note that d1 and d2 should be set as coprime integers.Finally, we calculate the location set of physical sensors according to the correspondence between the physical arrayS and coarrays Ssc. The coarrays Ssc=SsM∪SsN determined by (19) and (20) can be considered as the 2-SC result of each subarray or the self-sum coarray of S. Considering that the 2-SC of SM and SN have been multiplied by d1 or d2, then the physical sensor location S can be determined by multiplication operation,
(21)S=d1SM∪d2SN.Based on the discussion described above, we give an example of the proposed geometry shown in Figure2 to verify. For given element number in two subarrays with M=5,N=4, firstly, the initial consecutive integer sets SM=−6,−5,−3,−1,0, SN=0,1,3,4, and the largest possible values n2SM=12,n2SN=8 can be obtained by the solution to GPSP, which have been listed in Table 1. Subsequently, the cosubarrays spacing d1=9d,d2=13d can be obtained by the specifical structure of UCLA. The two 2-SC cosubarray locations can be expressed as SsM=9d×−12,⋯,−1,0, SsN=13d×0,1,⋯,8. Consequently, the physical sensor location set is represented by S=9d×−6,−5,−3,−1,0∪13d×0,1,3,4.Figure 2
(a) Physical sensors locationS; (b) sum coarray Ssc=SsM∪SsN.
(a)(b)


### 3.3. The Design Procedure of the Proposed Array Structure

We summarize the detailed steps for implementation of obtaining the proposed array geometry as follows:(1)
Based on Table1, the integer sets SM and SN and the longest possible consecutive numbers n2SM and n2SN can be determined by the solution to GPSP from given number of sensors M and N(2)
Obtain the location sets of two 2-SCSsM and SsN(3)
Determine the physical sensor setS by performing multiplication operation on SM and SN


## 3.1. Global Postage-Stamp Problem (GPSP)

The GPSP is a well-known combination problem that has not yet been fully solved, which can be described as follows: for given positive integersh and k, a set with k nonnegative integers is determined by
(15)Sk=0=a1<⋯<ak.Remark 5.
The elements inSk need to be summed h times to realize the consecutive numbers 0,1,2,⋯,nhSk. Besides, the value of nhSk should be as large as possible.
The solution to the GPSP has been investigated in [19, 20]. Herein, we also give a simple method to solve GPSP. Specifically, h can be considered as the maximum number of stamps on an envelope; Sk is the set of stamp denominations with k non-negative value. Then, the computational complexity of obtaining all possible combinations is Okh. An example is given to illustrate the solution method to GPSP explicitly. When Sk=1,3, in this case, 1 and 2 stamps are required to obtain postages 1 and 2, respectively. For postage 3, there are two combinations, i.e., one stamp with postage 3 or three stamps with postage 1. According to Remark 5, because of the existence of postage 0, the number of stamps currently required should be as small as possible. Besides, it can be concluded that the minimum k can be obtained by comparing all the postage combinations. The process of this method is summarized in Algorithm 1, where h=2. It is noteworthy that Sk is treated as prior information to obtain nhSk. When Sk is unknown, its (i+1)-th element should satisfy
(16)ai+1∈ai+1,ai×h+1,where ai represents i-th element of Sk, 1≤i≤k. Then, all elements of can be obtained by enumerating all the values of ai. The result of Algorithm 1 is listed in Table 1, which is also provided in [20].Algorithm 1: The algorithm of solving the GPSP with known Sk.
Input: stamps value set Sk, number of stamps types k, sum times h=2Output: Maximum consecutive postage nhSk1:initialize:dp0=0,i=02:whiledpi<hdo3:i++, dpi=i, j=04:whilej<k&Skj≤ido5:ifdpi−Skj+1<dpithen6:dpi=dpi−Skj+1,j++7:  end if8:end while9:end while10:returni−1nhSkTable 1
Result of Algorithm1.
kn2SkSk480134512013566160135787200125891072001348911720013491116720013561314720013579108260125811121382601349101213826013578171893201258111415169320135791021221040013491116171920114601237111519212224114601257111519212224125401237111519232526281254012571115192325262812540134911161823242627125401356131421222426271364013491116212328293132


## 3.2. Sparse Array Design Based on UCLA

The design methods for sparse arrays based on SOC only utilize 2-DC or 2-SC once, which can be extended to FOC-based array directly by adding 2-DC calculation. But this approach neglects the specifical output of first operation, resulting in a large amount of redundancy, and the DOF loss is inevitable. Suppose that the physical sensors are composed of multiple linear subarrays, and the number of elements in each subarray has been given.Without loss of generality, assume that the physical sensors are composed of two subarrays withM and N elements, respectively. As illustrated in Section 3, to obtain the longest possible 2-SC of each subarray, the integer sets SM and SN are solved from GPSP in (15) with k=M,N,h=2, which can be used to determine the largest possible lags n2SM and n2SN. It is noteworthy that the sets SM and SN can be considered as the initial physical location sets without coefficients. Based on Remark 5, if all elements of SM are negative, the consecutive integer set obtained from M is
(17)−n2SM,⋯,−2,−1,0,where SM represents a set with M elements and n2SM is the largest possible integer mentioned in Remark 5. Similarly, the consecutive positive integer set obtained from N is
(18)0,1,2,⋯,n2SN.Based on the structure of UCLA, we multiply all the elements in (17) and (18) by certain coefficients d1 and d2, respectively; then, the new sets can be constructed as the two cosubarrays of UCLA. Specifically, the cosubarray 1 of UCLA location set associated with (17) can be expressed as
(19)SsM=−n2SMd1,⋯,−2d1,d1,0,where d1=n2SN+1d is the interelement spacing of cosubarray 1; d=λ/2, and λ is wavelength. The cosubarray 2 location set associated with (18) can be expressed as
(20)SsN=0,d2,2d2,⋯,n2SNd2,where d2=n2SM+1d is the interelement spacing of cosubarray 2. Note that d1 and d2 should be set as coprime integers.Finally, we calculate the location set of physical sensors according to the correspondence between the physical arrayS and coarrays Ssc. The coarrays Ssc=SsM∪SsN determined by (19) and (20) can be considered as the 2-SC result of each subarray or the self-sum coarray of S. Considering that the 2-SC of SM and SN have been multiplied by d1 or d2, then the physical sensor location S can be determined by multiplication operation,
(21)S=d1SM∪d2SN.Based on the discussion described above, we give an example of the proposed geometry shown in Figure2 to verify. For given element number in two subarrays with M=5,N=4, firstly, the initial consecutive integer sets SM=−6,−5,−3,−1,0, SN=0,1,3,4, and the largest possible values n2SM=12,n2SN=8 can be obtained by the solution to GPSP, which have been listed in Table 1. Subsequently, the cosubarrays spacing d1=9d,d2=13d can be obtained by the specifical structure of UCLA. The two 2-SC cosubarray locations can be expressed as SsM=9d×−12,⋯,−1,0, SsN=13d×0,1,⋯,8. Consequently, the physical sensor location set is represented by S=9d×−6,−5,−3,−1,0∪13d×0,1,3,4.Figure 2
(a) Physical sensors locationS; (b) sum coarray Ssc=SsM∪SsN.
(a)(b)


## 3.3. The Design Procedure of the Proposed Array Structure

We summarize the detailed steps for implementation of obtaining the proposed array geometry as follows:(1)
Based on Table1, the integer sets SM and SN and the longest possible consecutive numbers n2SM and n2SN can be determined by the solution to GPSP from given number of sensors M and N(2)
Obtain the location sets of two 2-SCSsM and SsN(3)
Determine the physical sensor setS by performing multiplication operation on SM and SN


## 4. Performance Analysis

In this part, we evaluate the performance of the proposed array geometry compared to other arrays from the viewpoints of achievable DOF, mutual coupling, redundancy ratio, and Cramer-Rao Bound.


### 4.1. Achievable DOF

We analyze the achievable DOF of the proposed array geometry. Considering that theSsM and SsN can be associated with the cosubarrays of UCLA Ssc, then according to Lemma 4, the DOF for the 2-DC of Ssc is 2n2SN+1n2SM+1−1. Based on Definition 1, the position of 2-DC is symmetric about the origin. To illustrate this, we present the nonnegative part of the 2-DC of Ssc, as shown in the upper part of Figure 3. Besides, the DOF of NA-MIMO-DCSC has been given in [17], which can be expressed as
(22)DOFNA‐MIMO‐DCSC=2n2SMn2SN+1+1,where DOFNA‐MIMO‐DCSC represents the DOF of array NA-MIMO-DCSC. As for the proposed array geometry, we can obtain the following relationship
(23)DOFproposed≥2n2SN+1n2SM+1−1,where DOFproposed represents the DOF of the proposed array geometry.Figure 3
Comparison of the 2-DC ofSsc and 2-DCSC of S.As expounded in the appendix, the 2-DC can be decomposed into self-difference coarray and cross-difference coarray; similarly, the 2-SC can also be decomposed into self-sum coarray and cross-sum coarray. For the proposed geometry, the processes of obtaining two 2-SC of the two subarrays are separated, where only self-sum coarray is utilized while the cross-sum coarray is neglected, i.e., all elements inSsc are included in the 2-SC of S. Thus, the 2-DCSC of S contains all elements in the 2-DC of Ssc. Consequently, equation (23) is established. The nonnegative part of 2-DCSC of the proposed geometry is also given in the bottom part of Figure 3 to verify analysis mentioned above.However, the DOF of proposed geometry only has lower bound without closed-form expression, because the location of cross-sum coarray of the 2-SC is not available. Interestingly, for NA-MIMO-DCSC, the 2-DCSC and the 2-DC ofSsc exactly coincide.According to (22) and (23), we have
(24)DOFproposed‐DOFNA‐MIMO‐DCSC≥2n2SN.It can be concluded that the proposed array geometry can offer larger DOF than NA-MIMO-DCSC, which is also verified in Figure4 below.Definition 6 (redundancy ratio).
For a physical array with total number of virtual sensorsT obtained from difference coarray and the achievable DOF is given by DOFp, we define the redundancy ratios as
(25)η=1−DOFpT.
For a linear array withL physical sensors, in general, the number of virtual sensors is T=L2 when the correlation matrix is calculated by SOC-based method, and when FOC-based method is exploited, T=L4. Redundancy ratio can be considered as an important indicator which reflects the efficiency of virtual sensors.Figure 4
The 2-SC, 2-DCSC, and DOF comparison of different arrays and their CS spectrum with mutual coupling.


### 4.2. Cramer-Rao Bound

The Cramer-Rao Bound (CRB) can be obtained from the inverse of the Fisher information matrix (FIM). According to [24, 25], we give the FIM for the signal model in (9) via vectorization-based methods as
(26)FIM=J∂z∂βHC4,xT⊗C4,x−1∂z∂β,where J denotes the number of snapshots, z=vecC4,x and C4,x can be obtained by (7). β=θ1,⋯,θK,σ12,⋯,σK2T, σ12,⋯,σK2, represent the power of non-Gaussian signals. Consequently, the CRB of the DOA estimation with the proposed geometry via vectorization operation can be expressed as
(27)CRBθk=FIM−1θk,k,θ=θ1,⋯,θK,1≤k≤K.


## 4.1. Achievable DOF

We analyze the achievable DOF of the proposed array geometry. Considering that theSsM and SsN can be associated with the cosubarrays of UCLA Ssc, then according to Lemma 4, the DOF for the 2-DC of Ssc is 2n2SN+1n2SM+1−1. Based on Definition 1, the position of 2-DC is symmetric about the origin. To illustrate this, we present the nonnegative part of the 2-DC of Ssc, as shown in the upper part of Figure 3. Besides, the DOF of NA-MIMO-DCSC has been given in [17], which can be expressed as
(22)DOFNA‐MIMO‐DCSC=2n2SMn2SN+1+1,where DOFNA‐MIMO‐DCSC represents the DOF of array NA-MIMO-DCSC. As for the proposed array geometry, we can obtain the following relationship
(23)DOFproposed≥2n2SN+1n2SM+1−1,where DOFproposed represents the DOF of the proposed array geometry.Figure 3
Comparison of the 2-DC ofSsc and 2-DCSC of S.As expounded in the appendix, the 2-DC can be decomposed into self-difference coarray and cross-difference coarray; similarly, the 2-SC can also be decomposed into self-sum coarray and cross-sum coarray. For the proposed geometry, the processes of obtaining two 2-SC of the two subarrays are separated, where only self-sum coarray is utilized while the cross-sum coarray is neglected, i.e., all elements inSsc are included in the 2-SC of S. Thus, the 2-DCSC of S contains all elements in the 2-DC of Ssc. Consequently, equation (23) is established. The nonnegative part of 2-DCSC of the proposed geometry is also given in the bottom part of Figure 3 to verify analysis mentioned above.However, the DOF of proposed geometry only has lower bound without closed-form expression, because the location of cross-sum coarray of the 2-SC is not available. Interestingly, for NA-MIMO-DCSC, the 2-DCSC and the 2-DC ofSsc exactly coincide.According to (22) and (23), we have
(24)DOFproposed‐DOFNA‐MIMO‐DCSC≥2n2SN.It can be concluded that the proposed array geometry can offer larger DOF than NA-MIMO-DCSC, which is also verified in Figure4 below.Definition 6 (redundancy ratio).
For a physical array with total number of virtual sensorsT obtained from difference coarray and the achievable DOF is given by DOFp, we define the redundancy ratios as
(25)η=1−DOFpT.
For a linear array withL physical sensors, in general, the number of virtual sensors is T=L2 when the correlation matrix is calculated by SOC-based method, and when FOC-based method is exploited, T=L4. Redundancy ratio can be considered as an important indicator which reflects the efficiency of virtual sensors.Figure 4
The 2-SC, 2-DCSC, and DOF comparison of different arrays and their CS spectrum with mutual coupling.


## 4.2. Cramer-Rao Bound

The Cramer-Rao Bound (CRB) can be obtained from the inverse of the Fisher information matrix (FIM). According to [24, 25], we give the FIM for the signal model in (9) via vectorization-based methods as
(26)FIM=J∂z∂βHC4,xT⊗C4,x−1∂z∂β,where J denotes the number of snapshots, z=vecC4,x and C4,x can be obtained by (7). β=θ1,⋯,θK,σ12,⋯,σK2T, σ12,⋯,σK2, represent the power of non-Gaussian signals. Consequently, the CRB of the DOA estimation with the proposed geometry via vectorization operation can be expressed as
(27)CRBθk=FIM−1θk,k,θ=θ1,⋯,θK,1≤k≤K.


## 5. Simulation Results

In this section, 500 Monte-Carlo simulations via CS algorithm are employed to validate the superiority of the proposed array geometry in the presence of mutual coupling. Define the root mean square error (RMSE) as(28)RMSE=1K∑k=1K1500∑i=1500θ∧k,i−θk2,where θk denotes the true elevation of the k-th target and θ^k,i is the estimated value of θk in the i-th i=1,⋯,500 Monte Carlo simulation. K is the total number of the incident signals which are uncorrelated far-field non-Gaussian. Besides, the searching interval of CS algorithm is Δ=0.01∘, and the coefficients of mutual coupling are set as shown in Section 2.4.


### 5.1. RMSE Performance Comparison of Different Sparse Arrays versus SNR

In this part, we compare the RMSE performance of the different sparse arrays involved in Figure4, including the CA [5], NA [6], ACA [13], unfolded ACA, UCLA [11], ANAI-1 [9], ANAI-2 [9], MRA [3], proposed geometry, and NA-MIMO-DCSC [17]. Besides, the location sets of physical sensors in the above arrays with 8 sensors are also given in Figure 4. Figures 5 and 6 depict the DOA estimation performance and CRB performance comparison of different arrays versus SNR, respectively, where J=1300 and θ=−40∘,−30∘,−20∘,−10∘,0∘,10∘,20∘,30∘,40∘.Figure 5
CRB performance of different arrays versus SNR.Figure 6
DOA estimation performance of different arrays versus SNR.As shown in Figures5 and 6, it is observed that the DOA estimation performance of all arrays improves with the increase of SNR, and in particular, the proposed array geometry outperforms the other sparse arrays. The ACA and CA achieve the worst RMSE performance due to the reduced DOF, and the dense part of the NA results in significantly higher mutual coupling. The UCLA enjoys the maximum DOF and the minimum coupling leakage among the arrays design based on SOC, leading to better performance. The self-sum coarray of proposed array geometry is devised to the UCLA, which takes full advantage of the UCLA. According to Figure 4, the coupling leakage of the proposed geometry is much lower than the others, and the DOF is also significantly higher than other arrays, especially those based on SOC design. Due to the optimization of DOF and mutual coupling, the proposed array geometry achieves the best RMSE performance which is superior to CA, NA, ACA, UACA, UCLA, ANAI-1, ANAI-2, MRA, and NA-MIMO-DCSC.


### 5.2. RMSE Performance Comparison of Different Sparse Arrays versus Snapshots

Figures7 and 8 depict the RMSE performance of different arrays versus snapshots, where SNR=0dB and θ=−40°,−30°,−20°,−10°,0°,10°,20°,30°,40°. As can be seen in Figures 7 and 8 that with the increased number of snapshots, the CRB and DOA performance become better due to the more accurate FOC matrix.Figure 7
CRB performance of different arrays versus snapshots.Figure 8
DOA estimation performance of different arrays versus snapshots.It is also shown clearly in Figures7 and 8 that the proposed geometry achieves the best DOA estimation performance among all the compared sparse arrays. The 2-DCSC of CA, NA, ACA, UACA, UCLA, ANAI-1, ANAI-2, and MRA are obtained from extending SOC to FOC directly, which perform twice 2-DC on arrays manifolds successively. As a result, lots of redundancy is generated, which means a reduction in DOF, but NA-MIMO-DCSC and the proposed geometry are all based on the solution to GPSP, which reduces redundancy ratio greatly, resulting in the superior DOA estimation and CRB performance to the other sparse arrays.


## 5.1. RMSE Performance Comparison of Different Sparse Arrays versus SNR

In this part, we compare the RMSE performance of the different sparse arrays involved in Figure4, including the CA [5], NA [6], ACA [13], unfolded ACA, UCLA [11], ANAI-1 [9], ANAI-2 [9], MRA [3], proposed geometry, and NA-MIMO-DCSC [17]. Besides, the location sets of physical sensors in the above arrays with 8 sensors are also given in Figure 4. Figures 5 and 6 depict the DOA estimation performance and CRB performance comparison of different arrays versus SNR, respectively, where J=1300 and θ=−40∘,−30∘,−20∘,−10∘,0∘,10∘,20∘,30∘,40∘.Figure 5
CRB performance of different arrays versus SNR.Figure 6
DOA estimation performance of different arrays versus SNR.As shown in Figures5 and 6, it is observed that the DOA estimation performance of all arrays improves with the increase of SNR, and in particular, the proposed array geometry outperforms the other sparse arrays. The ACA and CA achieve the worst RMSE performance due to the reduced DOF, and the dense part of the NA results in significantly higher mutual coupling. The UCLA enjoys the maximum DOF and the minimum coupling leakage among the arrays design based on SOC, leading to better performance. The self-sum coarray of proposed array geometry is devised to the UCLA, which takes full advantage of the UCLA. According to Figure 4, the coupling leakage of the proposed geometry is much lower than the others, and the DOF is also significantly higher than other arrays, especially those based on SOC design. Due to the optimization of DOF and mutual coupling, the proposed array geometry achieves the best RMSE performance which is superior to CA, NA, ACA, UACA, UCLA, ANAI-1, ANAI-2, MRA, and NA-MIMO-DCSC.


## 5.2. RMSE Performance Comparison of Different Sparse Arrays versus Snapshots

Figures7 and 8 depict the RMSE performance of different arrays versus snapshots, where SNR=0dB and θ=−40°,−30°,−20°,−10°,0°,10°,20°,30°,40°. As can be seen in Figures 7 and 8 that with the increased number of snapshots, the CRB and DOA performance become better due to the more accurate FOC matrix.Figure 7
CRB performance of different arrays versus snapshots.Figure 8
DOA estimation performance of different arrays versus snapshots.It is also shown clearly in Figures7 and 8 that the proposed geometry achieves the best DOA estimation performance among all the compared sparse arrays. The 2-DCSC of CA, NA, ACA, UACA, UCLA, ANAI-1, ANAI-2, and MRA are obtained from extending SOC to FOC directly, which perform twice 2-DC on arrays manifolds successively. As a result, lots of redundancy is generated, which means a reduction in DOF, but NA-MIMO-DCSC and the proposed geometry are all based on the solution to GPSP, which reduces redundancy ratio greatly, resulting in the superior DOA estimation and CRB performance to the other sparse arrays.


## 6. Conclusion

In this paper, a sparse array design method for non-Gaussian signals DOA estimation is presented from the perspective of GPSP, and a sparse array geometry based on UCLA is given to illustrate. For vectorized FOC-based DOA estimation algorithms, we divide the process of obtaining physical sensor location sets into two steps. Specifically, the first step of obtaining the longest possible 2-SC is modeled as a GPSP, whose solutions can also be employed to determine the initial physical location sets without spacing coefficients. Then, the second step is to multiply the physical sensor sets by appropriate coefficients based on the structure of UCLA. Besides, the properties of UCLA in terms of DOF and the location of consecutive lags are exploited. Numerical simulations corroborate the superiority of the proposed geometry in terms of DOF, mutual coupling, CRB, and DOA estimation performance. Considering the relationship between 2-DCSC and physical sensors is quite complicated, the design principle with splitting 2-DCSC into 2-SC and 2-DC will contribute to our future work effectively.



---

*Source: 6616112-2021-02-24.xml*