# Guaranteed Stability of Sparse Recovery in Distributed Compressive Sensing MIMO Radar

Authors: Yu Tao; Gong Zhang; Jindong Zhang
Journal: International Journal of Antennas and Propagation
 (2015)

---

## Abstract

Low SNR condition has been a big challenge in the face of distributed compressive sensing MIMO radar (DCS-MIMO radar) and noise in measurements would decrease performance of radar system. In this paper, we first devise the scheme of DCS-MIMO radar including the joint sparse basis and the joint measurement matrix. Joint orthogonal matching pursuit (JOMP) algorithm is proposed to recover sparse targets scene. We then derive a recovery stability guarantee by employing the average coherence of the sensing matrix, further reducing the least amount of measurements which are necessary for stable recovery of the sparse scene in the presence of noise. Numerical results show that this scheme of DCS-MIMO radar could estimate targets’ parameters accurately and demonstrate that the proposed stability guarantee could further reduce the amount of data to be transferred and processed. We also show the phase transitions diagram of the DCS-MIMO radar system in simulations, pointing out the problem to be further solved in our future work.


---

## Body

## 1. Introduction

Nowadays, detection of targets which are stealth or in strong interference has become an important requirement for radar system. Distributed placed antennas enable the system to view targets from multiple angles, providing spatial diversity and reducing the target radar cross sections (RCS) scintillations. Therefore, distributed MIMO radar can be employed to detect stealth targets. The difference of signals transmitted by each transmitter provides several information channels for distributed MIMO radar, enabling the MIMO radar system to achieve superior spatial resolution as compared to a traditional radar system [1–5]. But the amount of data from these information channels is always too huge to be processed, increasing the difficulty in hardware designing. Compressive sensing is used in MIMO radar to estimate the DOA in [6, 7] and it is shown that CS-MIMO radar system could estimate targets’ parameters accurately, using much fewer data than that needed in conventional MIMO radar.Viewing targets from different angles with separated antennas, we can detect the stealth targets and estimate targets’ parameters as position and velocity [8]. The theory of distributed compressive sensing (DCS) was proposed in [9]. In a standard DCS scenario, signals measured by sensors are each individually sparse on some basis or all the signals share the locations of nonzero coefficients in the sparse vectors. Under the right conditions, a decoder at the collection point can jointly reconstruct all of the signals precisely. Such property of DCS happens to fit the distributed MIMO radar and in this paper we provide a practical scheme for DCS-MIMO radar system. The sparse targets scene of DCS-MIMO radar is shown in Figure 1.Figure 1
Sparse targets scene of DCS-MIMO radar.In the sparse targets scene of DCS-MIMO radar, as Figure1 shows that the antennas are distributed and placed and they detect the region of interest from different angles. The pentagrams in Figure 1 represent the targets. Using distributed compressive sensing, distributed MIMO radar could precisely reconstruct the sparse scene with considerably lower amount of measurements than required by the Nyquist theorem. Many recovery algorithms have been proposed for compressive sensing in recent years. Algorithms inspired by MP include OMP [10], tree matching pursuit [11], stagewise OMP [12], CoSaMP [13], and IHT [14]. Different from algorithms of the match pursuit class, there are also FOCUSS [15] and sparse Bayesian learning (SBL) [16]. In DCS scenario, sparse recovery algorithms need to make the most of the common component and innovations of the received signals which are treated as a signal ensemble [9]. Many joint sparse recovery algorithms were employed to recover the sparse vector jointly, such as OSGA and SOMP [17]. In this paper, we propose a joint orthogonal matching pursuit (JOMP) algorithm to exploit the special structure of the joint sparse vector. It is demonstrated that using DCS with JOMP algorithm is more effective and more accurate than processing signals in each receiver with CS method separately.Nonetheless, in order to ensure that the DCS-MIMO radar system could be realized in the application of engineering, many problems need to be discussed in depth. One of these problems is finding the least amount of measurements to ensure the stable recovery in low signal-to-noise ratio (SNR) condition. Article [18] establishes the possibility of stable recovery under a combination of sufficient sparsity and favorable structure of the overcomplete system. However, the theorem in [18] is too strict for radar application; hence, we can further reduce the amount of data. In this paper, we propose a stability guarantee for stable recovery in DCS-MIMO radar, using the average coherence of sensing matrix. We then find the least amount of measurements for our DCS-MIMO radar system using JOMP algorithm in low SNR condition.This paper is organized as follows. In Section2, we introduce DCS-MIMO radar system and give joint sparse model of the received signal ensemble and we process sparse reconstruction with JOMP algorithm. In Section 3, we propose the method to find the least amount of measurements to ensure stable recovery and we give the stability guarantee of DCS-MIMO radar. Numerical results are shown in Section 4 to demonstrate the effectiveness of the scheme of DCS-MIMO radar and the stability guarantee. Phase transitions diagram is shown to raise a new problem to be solved in future. Finally, Section 5 concludes this paper.


## 2. DCS-MIMO Radar

### 2.1. Signal Model

In this section, we describe DCS-MIMO radar system and give joint sparse representation of the received signal ensemble. We consider a system withMt transmitters and Mr receivers and there are K targets in the region of interest. We assume that all targets are moving in a two-dimensional plane. However, without loss of generality, we can also consider the three-dimensional occasion. We further assume that each of the targets contains multiple individual isotropic scatterers. We can express the collection of these scatterers as one point scatterer which represents the RCS center of gravity of these multiple scatterers [8]. The RCS center of the kth target is located at Pk=[pxk,pyk] with a velocity Vk=[vxk,vyk]. The ith transmitter and the jth receiver are, respectively, located at ti=[txi,tyi] and rj=[rxj,ryj]. Orthonormal waveforms are transmitted by each transmitter. Suppose the waveform transmitted by the ith transmitter is si(t). These signals travel in space and reflect off the surfaces of the targets and then are captured by the receivers. Further, we assume that the cross correlations between these waveforms are close to zero for different delays [8]. Let σijk denote the attenuation corresponding to the kth target between the ith transmitter and the jth receiver. The signal arriving at the jth receiver can be expressed as
(1)rj(t)=∑k=1K∑i=1MtσijkSi(t-τijk)ej2πfDijk(t-τijk)+nj(t),
where τijk is the delay and fDijk is the Doppler shift corresponding to the Kth target and n(t) denotes the additive noise in the jth receiver:
(2)τijk=1cPk-ti+Pk-rj,fDijk=fccvk,urjk-vk,utik,
where utik and urjk denote the unit vector from the ith transmitter to the kth target and the unit vector from the kth target to the jth receiver, respectively. 〈·,·〉 is the inner product operator. Hence, 〈vk,urjk〉 is the velocity component from the kth target and the jth receiver, and 〈vk,utik〉 is the velocity component from the ith transmitter to the kth target. fc is the carrier frequency and c is the speed of propagation of the wave in the medium.


### 2.2. Joint Sparse Representation

We define the target state vectorζ=[px,py,vx,vy]; hence, the important properties of the target (position and velocity) are specified by ζ. The whole target’s state space is divided into L possible values {ζl,∀l=1,2,…,L}. Hence, each of the targets is associated with a state vector belonging to this grid. If the presence of a target at ζl contributes to received signal in the jth receiver, then we define
(3)φjl(t)=∑i=1MtSi(t-τijk)ej2πfDijk(t-τijk).The sampled outputs ofφjl(t) are given as φjl(n),n=1,2,…,N. Then, we arrange rjl(n) into a N×L matrix ψj:
(4)ψj=φj1,φj2,…,φjL,
where ψj is the sparse basis corresponding to the jth receiver. Then, the joint sparse basis of all Mr receivers can be expressed as
(5)Ψ=ψ10⋯00ψ2⋯0⋮⋮⋱⋮00⋯ψMr.If theϑl is the state of the kth target, we define θjl=σjk, where σjk denote the attenuation value of the kth target observed by the jth receiver. Otherwise, the θjl=0. We arrange θj into a LMr×1 vector θ=[θ1T,θ2T,…,θjT]T, where [·]T denotes the transpose of [·]. We get joint sparse representation of the signal ensemble as
(6)r(NMr)×(1)=Ψ(NMr)×(LMr)θ(LMr)×1+e(NMr)×(1).In the expression of the measurement vector mentioned above,Ψ is known and only θ depends on the actual targets present in the illuminated area. The nonzero entries of θj represent the target attenuation values and the corresponding indices represent the positions and velocities. Further, the indices of nonzero entries of each θj are always the same; in other words, all signals in each receiver share the location of nonzero entries. So, we call this joint sparse modeling.


### 2.3. Joint Sparse Recovery

In the previous section, we get the joint sparse representation of the signal ensemble received byMr receivers. The theory of compressive sensing said that we can reconstruct the vector θ from far fewer samples than that contained in the vector r. If the measurement matrix is represented by Φ, then the coherence between Φ and Ψ measures the largest correlation between them. Φ must be such that it has as little coherence with Ψ as possible. Since random matrices satisfy low coherence properties, we generate the entries of the NCS×N dimensional measurement matrix Φj from independent Gaussian distribution as the measurement matrix of the jth receiver, where NCS≪N. Considering the special structure of the joint sparse basis Ψ, we design the joint measurement matrix Φ as
(7)Φ=Φ10⋯00Φ2⋯0⋮⋮⋱⋮00⋯ΦMr.Employing this structure of joint measurement matrix, we can measure the signal ensemble simultaneously and design submeasurement matrix according to the different situation of each receiver such as the different SNR. On the other hand, it is much more convenient to optimize the joint measurement matrixΦ without ignoring the independence of the receivers.So, the new measurement vector in the presence of noise is(8)y=ΦΨθ+Φe=Γθ+e′,
where Γ=ΦΨ is defined as sensing matrix and e′ is the measured noise.In order to find the properties of targets, we need to recover the joint sparse vectorθ from the measurement y. It is an optimization problem with a noisy setting as follows:
(9)P1,δ:min⁡θθ1subjecttoy-Γθ2≤δ.The recovery of joint sparse vectorθ from measurement y=Γθ+e′ is one of the key points of this paper. Considering the special structure of the joint sparse vector θ, each θj has the same location of nonzero entries, which could be treated as joint sparsity. To define joint sparsity, we view θ as a combination of groups—assumed throughout the paper to be a length Mr—with θl denoting the lth group, that is,
(10)
where Q=MrL. Entries which are corresponding to the same target state vector ζl are arranged into the group θl. Similarly, we can represent Γ as a combination of subgroups Γl:
(11)We propose an extension of matching pursuit algorithm called joint orthogonal matching pursuit (JOMP) that exploits the knowledge of joint sparsity. Based on orthogonal matching pursuit (OMP) algorithm, we divided the columns of the sensing matrixΓ=ΦΨ into L groups as shown in (11). Columns which are in the same group are corresponding to the same information cell (target state vector). In JOMP, we first initialize reconstructed vector θ(0)=0 and the residual r(0)=y. In each subsequent iteration k′, we project the residual vector r(k′-1) onto all the subgroups of Γ and pick the group Γ(k′) that has the highest correlation with the residual. We update the estimated reconstructed vector:
(12)θ(k′)=θ(k′-1)+r(k′-1),Γ(k′)Γ(k′),Γ(k′)Γ(k′).
We finally update the residual as
(13)r(k′)=r(0)-θk′.When the residual was finally updated by calculating the product of these groups and the received signal, we find theK groups which are most correlated with the received signal y. Then, we get the reconstructed sparse vector θ^. The procedure of JOMP algorithm is shown as in Algorithm 1.Algorithm 1:The procedure of JOMP algorithm.
Input: y-sampled measurement vector
Φ-(NCSMr)×(NMr) measurement matrix
Initialize All:reconstruct vector θ(0)=0; the residual r(0)=y; the sparsity K; sensing matrix Γ=ΦΨ; the index set Λ0=⌀;
Loop:  set t=1 and repeat until t>K
(1) Arrange theMr columns of Γ corresponding to the lth cell into the matrix Γ(l), get the product of each Γ(l) (l=1,2,…,L)
and the residual r(0), find the max product and get the corresponding index λt=argmax⁡l=1,2,…,L⁡|rt-1,Γl|
(2) Update the index setΛt=Λt-1∪{λt} and update the set of reconstruct atoms Θt=[Θt-1,Γl]
(3)  Calculates^t=(ΘtTΘt)-1ΘtTy
(4)  Update the residualri=y-Θts^t, t=t+1
End loop
Output:the index set Λ and the nonzero value s^t


## 2.1. Signal Model

In this section, we describe DCS-MIMO radar system and give joint sparse representation of the received signal ensemble. We consider a system withMt transmitters and Mr receivers and there are K targets in the region of interest. We assume that all targets are moving in a two-dimensional plane. However, without loss of generality, we can also consider the three-dimensional occasion. We further assume that each of the targets contains multiple individual isotropic scatterers. We can express the collection of these scatterers as one point scatterer which represents the RCS center of gravity of these multiple scatterers [8]. The RCS center of the kth target is located at Pk=[pxk,pyk] with a velocity Vk=[vxk,vyk]. The ith transmitter and the jth receiver are, respectively, located at ti=[txi,tyi] and rj=[rxj,ryj]. Orthonormal waveforms are transmitted by each transmitter. Suppose the waveform transmitted by the ith transmitter is si(t). These signals travel in space and reflect off the surfaces of the targets and then are captured by the receivers. Further, we assume that the cross correlations between these waveforms are close to zero for different delays [8]. Let σijk denote the attenuation corresponding to the kth target between the ith transmitter and the jth receiver. The signal arriving at the jth receiver can be expressed as
(1)rj(t)=∑k=1K∑i=1MtσijkSi(t-τijk)ej2πfDijk(t-τijk)+nj(t),
where τijk is the delay and fDijk is the Doppler shift corresponding to the Kth target and n(t) denotes the additive noise in the jth receiver:
(2)τijk=1cPk-ti+Pk-rj,fDijk=fccvk,urjk-vk,utik,
where utik and urjk denote the unit vector from the ith transmitter to the kth target and the unit vector from the kth target to the jth receiver, respectively. 〈·,·〉 is the inner product operator. Hence, 〈vk,urjk〉 is the velocity component from the kth target and the jth receiver, and 〈vk,utik〉 is the velocity component from the ith transmitter to the kth target. fc is the carrier frequency and c is the speed of propagation of the wave in the medium.


## 2.2. Joint Sparse Representation

We define the target state vectorζ=[px,py,vx,vy]; hence, the important properties of the target (position and velocity) are specified by ζ. The whole target’s state space is divided into L possible values {ζl,∀l=1,2,…,L}. Hence, each of the targets is associated with a state vector belonging to this grid. If the presence of a target at ζl contributes to received signal in the jth receiver, then we define
(3)φjl(t)=∑i=1MtSi(t-τijk)ej2πfDijk(t-τijk).The sampled outputs ofφjl(t) are given as φjl(n),n=1,2,…,N. Then, we arrange rjl(n) into a N×L matrix ψj:
(4)ψj=φj1,φj2,…,φjL,
where ψj is the sparse basis corresponding to the jth receiver. Then, the joint sparse basis of all Mr receivers can be expressed as
(5)Ψ=ψ10⋯00ψ2⋯0⋮⋮⋱⋮00⋯ψMr.If theϑl is the state of the kth target, we define θjl=σjk, where σjk denote the attenuation value of the kth target observed by the jth receiver. Otherwise, the θjl=0. We arrange θj into a LMr×1 vector θ=[θ1T,θ2T,…,θjT]T, where [·]T denotes the transpose of [·]. We get joint sparse representation of the signal ensemble as
(6)r(NMr)×(1)=Ψ(NMr)×(LMr)θ(LMr)×1+e(NMr)×(1).In the expression of the measurement vector mentioned above,Ψ is known and only θ depends on the actual targets present in the illuminated area. The nonzero entries of θj represent the target attenuation values and the corresponding indices represent the positions and velocities. Further, the indices of nonzero entries of each θj are always the same; in other words, all signals in each receiver share the location of nonzero entries. So, we call this joint sparse modeling.


## 2.3. Joint Sparse Recovery

In the previous section, we get the joint sparse representation of the signal ensemble received byMr receivers. The theory of compressive sensing said that we can reconstruct the vector θ from far fewer samples than that contained in the vector r. If the measurement matrix is represented by Φ, then the coherence between Φ and Ψ measures the largest correlation between them. Φ must be such that it has as little coherence with Ψ as possible. Since random matrices satisfy low coherence properties, we generate the entries of the NCS×N dimensional measurement matrix Φj from independent Gaussian distribution as the measurement matrix of the jth receiver, where NCS≪N. Considering the special structure of the joint sparse basis Ψ, we design the joint measurement matrix Φ as
(7)Φ=Φ10⋯00Φ2⋯0⋮⋮⋱⋮00⋯ΦMr.Employing this structure of joint measurement matrix, we can measure the signal ensemble simultaneously and design submeasurement matrix according to the different situation of each receiver such as the different SNR. On the other hand, it is much more convenient to optimize the joint measurement matrixΦ without ignoring the independence of the receivers.So, the new measurement vector in the presence of noise is(8)y=ΦΨθ+Φe=Γθ+e′,
where Γ=ΦΨ is defined as sensing matrix and e′ is the measured noise.In order to find the properties of targets, we need to recover the joint sparse vectorθ from the measurement y. It is an optimization problem with a noisy setting as follows:
(9)P1,δ:min⁡θθ1subjecttoy-Γθ2≤δ.The recovery of joint sparse vectorθ from measurement y=Γθ+e′ is one of the key points of this paper. Considering the special structure of the joint sparse vector θ, each θj has the same location of nonzero entries, which could be treated as joint sparsity. To define joint sparsity, we view θ as a combination of groups—assumed throughout the paper to be a length Mr—with θl denoting the lth group, that is,
(10)
where Q=MrL. Entries which are corresponding to the same target state vector ζl are arranged into the group θl. Similarly, we can represent Γ as a combination of subgroups Γl:
(11)We propose an extension of matching pursuit algorithm called joint orthogonal matching pursuit (JOMP) that exploits the knowledge of joint sparsity. Based on orthogonal matching pursuit (OMP) algorithm, we divided the columns of the sensing matrixΓ=ΦΨ into L groups as shown in (11). Columns which are in the same group are corresponding to the same information cell (target state vector). In JOMP, we first initialize reconstructed vector θ(0)=0 and the residual r(0)=y. In each subsequent iteration k′, we project the residual vector r(k′-1) onto all the subgroups of Γ and pick the group Γ(k′) that has the highest correlation with the residual. We update the estimated reconstructed vector:
(12)θ(k′)=θ(k′-1)+r(k′-1),Γ(k′)Γ(k′),Γ(k′)Γ(k′).
We finally update the residual as
(13)r(k′)=r(0)-θk′.When the residual was finally updated by calculating the product of these groups and the received signal, we find theK groups which are most correlated with the received signal y. Then, we get the reconstructed sparse vector θ^. The procedure of JOMP algorithm is shown as in Algorithm 1.Algorithm 1:The procedure of JOMP algorithm.
Input: y-sampled measurement vector
Φ-(NCSMr)×(NMr) measurement matrix
Initialize All:reconstruct vector θ(0)=0; the residual r(0)=y; the sparsity K; sensing matrix Γ=ΦΨ; the index set Λ0=⌀;
Loop:  set t=1 and repeat until t>K
(1) Arrange theMr columns of Γ corresponding to the lth cell into the matrix Γ(l), get the product of each Γ(l) (l=1,2,…,L)
and the residual r(0), find the max product and get the corresponding index λt=argmax⁡l=1,2,…,L⁡|rt-1,Γl|
(2) Update the index setΛt=Λt-1∪{λt} and update the set of reconstruct atoms Θt=[Θt-1,Γl]
(3)  Calculates^t=(ΘtTΘt)-1ΘtTy
(4)  Update the residualri=y-Θts^t, t=t+1
End loop
Output:the index set Λ and the nonzero value s^t


## 3. Stability Guarantee for DCS-MIMO Radar

Large amounts of data will bring great difficulties for the design of hardware system. So, it is important to find a lower limit of data amount to guarantee the stability of sparse recovery, providing benefits for implementation of the DCS-MIMO radar system. Hence, the stability guarantee for DCS-MIMO radar is the focus of this paper.In most practical situations, it is not sensible to assume that the available datay obey precise equality y=Γθ, where Γ∈RN×L. A more plausible scenario assumes sparse approximate representation: that there is an ideal noiseless signal x0=Γθ0, but that we can observe only a noisy version y=x0+e, where e2≤ϵ.The concept of coherence of the sensing matrixΓ is usually used as a criterion of the property of the sensing matrix. Assuming that the columns of Γ are normalized to unit l2-norm, it is defined in terms of the Gram matrix G=ΓTΓ. With G(k,j) denoting entries of this matrix, the coherence is
(14)μ=μΓ=max⁡1≤k,j≤L,k≠jGk,j.The theorem proposed in [18] said that if a noiseless sparse signal x0=Γθ0 satisfies the inequality K=θ00<(1/μ+1)/4, the deviation of the (P1,δ) representation from θ0, assuming δ≥ϵ, can be bounded by ‖θ^1,δ-θ0‖22≤(ϵ+δ)2/[1-μ(4K-1)].The parameterμ in Donoho’s theorem indicates the worst case of the coherence between some columns of the sensing matrix Γ. Since the sensing matrix Γ of DCS-MIMO radar is overcomplete and it could be regarded as a redundant dictionary, some columns would not be chosen during the process of sparse recovery; that is, even if μ is too large to guarantee the incoherentness of the sensing matrix Γ, DCS-MIMO radar may still estimate targets’ positions correctly by choosing the incoherent columns of Γ when the targets are in proper positions.We simulated the distribution of the normalized cross correlation between the columns of the sensing matrix as Figure2 shows. According to the definition, the coherence μ of the simulated sensing matrix is 0.8837. The value of μ is so large that the simulated sensing matrix seems not qualified according to the theorem in [18]. However, in practice, the sensing matrix is incoherent enough for DCS-MIMO radar since most of the cross correlation values are small. It is also demonstrated in a particular experiment as simulation 4.1 that DCS-MIMO radar is able to estimate the targets’ parameters accurately based on this sensing matrix. So, the parameter μ is too strict to assess the coherence of the sensing matrix of DCS-MIMO radar. A new evaluation criterion which could indicate the overall coherence of the redundant dictionary of DCS-MIMO radar is needed. Therefore, we use μt to denote the average value of the coherence of each pair of columns in the sensing matrix Γ:
(15)μtΓ=∑1≤k,j≤L,k≠jGk,j>0·Gk,j∑1≤k,j≤L,k≠jGk,j>0,
where μt is the mean of the nonzero absolute values of these off-diagonal elements in the Gram matrix G. Compared to μ,μt indicates the overall coherence of the redundant dictionary rather than the extreme conditions. By calculating the results in Figure 2, we get the average coherence μt of the simulated sensing matrix which is 0.1792. That is, even if the μ is large, small μt could still guarantee DCS-MIMO radar’s estimation accuracy. Hence, using μt to indicate the performance of DCS-MIMO radar is more practical than using μ. In this paper, we use the average coherence μt to assess the coherence of the sensing matrix Γ. Then, the stability guarantee for DCS-MIMO radar system with μt is proposed.Figure 2
The distribution of normalized cross correlation between the columns ofΓ.Theorem 1.
Let the overcomplete sensing matrixΓ have average coherence μt(Γ). If the sparse representation of the noiseless signal x0=Γθ0 satisfies
(16)K=θ0<181μt+2,
then the deviation of the (P1,δ) representation from θ0, assuming δ≥ϵ, can be bounded by
(17)θ^1,δ-θ022≤ϵ+δ21-2μt4N-1.Proof.
The stability bound can be posed as the solution to an optimization problem of the form(18)max⁡θ0,eθ^-θ022subjecttoθ^=arg minθ⁡θ1subjecttoΓθ-y22≤δ,y=Γθ0+e,e2≤ϵ,θ00≤Narg minθ⁡θ1subjecttoΓθ-y22≤δ,.
Put in words, we consider all representation vectorsθ0 of bounded support, all possible realizations of bounded noise, and we ask for the largest error between the ideal sparse decomposition and its reconstruction from noisy data. Defining v=θ-θ0 and similarly w=θ^-θ0, we can rewrite the above problem as
(19)max⁡θ0,ew22subjecttow=arg minv⁡θ0+v1subjecttoΓv-e2≤δ,e2≤ϵ,θ00≤Nw=arg minv⁡θ0+v1subjecttoΓv-e2≤δ,.
Note that if w is the minimizer of θ0+v1 under these constraints, then relaxing the constraints to all w satisfying θ0+w1 expands the feasible set. However, this is true only if δ≥ϵ since otherwise v=0 is not a feasible solution. Thus, we consider
(20)w∣θ0+w1≤θ01,Γw-e2≤δ,e2≤ϵ,θ0≤Nθ0+w1≤θ01,Γw-e2.
We now use |a+b|-|a|≥|a|-|b|-|a|=-|b| and expand this set by exploiting the relation
(21)θ0+w1-θ01≥w1-2∑k∈Qw(k),
where Q is the support of nonzero entries in θ0 with complement Qc. Therefore, we get a further increase in value by replacing the feasible set in (20) with
(22)w∣w1≤2∑k∈Swk,Γw-e2≤δ,e2≤ϵ,#Q≤N∑k∈Swk,Γw-e2≤δ.
Writing this out yields a new optimization problem with still larger value:
(23)max⁡w,Q,ew22subjecttow1≤2∑k∈Qwk,Γ-e2≤δ,e2≤ϵ,#Q≤N∑k∈Qwk,Γ-e2≤δ.
Then, we eliminate the noise vector e, using
(24){w∣Γw-e2≤δ,e2≤ϵ}⊆{w∣Γw2≤ϵ+δ}.
Expanding the feasible set of (21) using this observation gives
(25)max⁡Q,ww22subjecttow1<2∑k∈Swk,Γw2≤Δ,#Q≤N∑k∈Swk,Γw2≤Δ,
where we denote Δ=ϵ+δ.
The constraint‖Γw‖2≤Δ is not posed in terms of the absolute values in the vector w, complicating the analysis; we now relax this constraint using incoherence of Γ. The Gram matrix of Γ is G=ΓTΓ, and the coherence used in this paper is the average off-diagonal amplitude μt. Let 1 be the m-by-m matrix of all ones. Let Gmin⁡ denote the matrix whose off-diagonal elements are the smallest one of the off-diagonal entries of the Gram matrix G. Similarly, let Gt denote the matrix whose off-diagonal elements are μt. The constraint
(26)Γw22=wTGw≤Δ2
can be relaxed:
(27)Δ2≥wTGw=w22+wTG-Iw≥w22+wTG-Iw-wTGt-Iw≥w22+wTGmin⁡-Iw-wTGt-Iw≥w22-wTGmin⁡-Iw-wTGt-Iw≥w22-wTGt-Iw-wTGt-Iw≥w22-2μtwT1-Iw=1+2μtw22-2μtw12.
Using this, (25) is bounded above by the value
(28)max⁡Q,ww22subjecttow1<2∑k∉Qwk,(1+2μt)w22-2μtw12≤Δ2,#Q≤N∑k∉Qwk.
This problem is invariant under permutations of the entries inw which preserve membership in Q and Qc. It is also invariant under relabeling of coordinates. So, assume that all nonzero entries in θ0 are concentrated in the initial slots of the vector; that is, Q=1,2,…,K.
Puttingw=(w0,w1) where w0 gives the first P entries in w and w1 gives the remaining m-P entries of w, we obviously have
(29)w22=w022+w122,w1=w01+w11.
The l1 norm on Rk dominates the l2 norm and is dominated by k times the l2 norm. Thus,
(30)w01≥w02≥w01K,w1≥w12≥w11m-K.
We define
(31)A=w01,B=w11c0=w02w012,c1=w12w112.
Returning to (25) and using the definition above, we obtain a further reduction from an optimization problem on Rm to an optimization problem on (A,B,c0,c1)∈R4 as
(32)max⁡c0A2+c1B2subjectto1KA>B,(1+2μt)(c0A2+c1B2)-2μtA+B2≤Δ2,A,B≥0,1K≤c0≤1,0<c1≤1.
We further define B=ρA, where 0≤ρ<1, and rewrite (32) as
(33)max⁡⁡c0+ρ2c1A2subjectto1K1+2μtc0+ρ2c1A2-2μt1+ρ2A2≤Δ2,A≥0,1K≤c0≤1,0≤c1≤1,0≤ρ<1.
Then, we define Ω=(1+ρ)2/(c0+ρ2c1). Then, 1≤Ω≤4K over the region (33). Denoting V=A2(c0+ρ2c1), the first constraint defining that region takes the form
(34)1+2μtV-2μtΩV≤Δ2.
SinceΩ≤4K, sparsity requirement (9) leads to
(35)(1+2μt)-2μtΩ≥(1+2μt)-8Kμt>0.
Hence,
(36)V≤Δ21-2μtΩ-1≤Δ21-2μt4K-1,
with the choice Ω=4K.
Requirement (35) puts a restriction on K and μt, being free parameters of the problem. Using Ω=4K leads to the sparsity requirement in (16), since (1+2μt)-8Kμt>0.We can use (16) to find the least amount of measurements for stable recovery and confirm the guaranteed stability of DCS-MIMO radar. Compared to theorem proposed by Donoho et al. in [18], stability guarantee proposed in this paper further reduces the amount of data necessarily to be transferred and processed in DCS-MIMO radar for stable recovery of the sparse targets scene. This stability guarantee gives theoretical foundation for hardware implementation of DCS-MIMO radar and it also demonstrates the feasibility of targets’ parameters estimation in low SNR condition by DCS-MIMO radar.


## 4. Numerical Results

### 4.1. Targets’ Parameters Estimation

In order to prove the effectiveness of the DCS-MIMO radar, we simulated a small scene with2 transmitters and 2 receivers. We use the common Cartesian coordinate system. The transmitters are located at t1=[100,0]m and t2=[200,0]m, respectively. The receivers are located at r1=[0,100]m and r2=[0,200]m, respectively. The sample rate is fc=100MHz. We choose the number of samples in each receiver to be N=80; therefore, y has 160 entries. We divided the position space of the target into 11×13 grid points and the target’s velocity space into 5×5 grid points. Therefore, the total number of possible target states L=3575. We consider the presence of 2 targets. Hence, the sparse vector θ formed by 7150 entries has only K×Mr=4 nonzero entries corresponding to the targets.The positions and the velocities of the targets are given as(37)P1=80,260m,P2=110,290m,V1=[120,120]m/s,V2=[100,100]m/s.
The attenuations corresponding to the two targets are
(38)a111,a121,a211,a221=0.3,0.3,0.7,0.8,a112,a122,a212,a222=0.4,0.5,0.3,0.2.We assume the SNR for the receivers areSNR1=2dB and SNR2=3dB.From Figure3, we can see that, using JOMP algorithm, the DCS-MIMO radar system is able to estimate the positions and velocities of the targets accurately in the presence of noise. Since it is not possible to plot the position and velocity on the same plot, we plotted the estimates of position and velocity separately.Targets’ parameters estimation using JOMP.
(a)
Position estimation
(b)
Velocity estimationIn order to compare with the conventional CS method that uses CS to reconstruct the sparse vector in each receiver separately, we use 1000 independent Monte Carlo runs to generate these results. Here, we define that a successful estimation is that every receiver estimates the positions of targets accurately. Then, in Figure4, we can see that reconstruction using joint sparse modeling has a higher reconstruction probability than the conventional CS approach. Therefore, we demonstrate the advantages of the reconstruction using joint sparse modeling and JOMP algorithm.Figure 4
Reconstruction probability for the system using joint sparse modeling and the system using CS in each receiver separately as a function of SNR.


### 4.2. Guaranteed Stability of Joint Sparse Recovery

According to the theorem in Section3, we simulated the Gram matrix of the sensing matrix of the DCS-MIMO radar system. After calculating the average off-diagonal amplitude μt, we show the relationship between μt and the number of measurements M. For comparison, we also show the relationship between μ and the number of measurements M according to Donoho’s theorem in [18].Considering the joint sparsity of the received signal ensemble, we get the stability guarantee of the DCS-MIMO radar system based on the theorem proposed in Section3. In Figure 5, when the value of the average coherence μt or the coherence μ is lower than the stability guarantee, stable recovery of sparse targets scene could be achieved. By comparison of Figures 5(a) and 5(b), we can find that the necessary number of measurements reduced from 120 to 80 in our simulation settings by the stability guarantee in this paper.Coherenceμ and average coherence μt of the sensing matrix of different number of measurements with the different stability guarantee.
(a)
Donoho’s stability guarantee
(b)
Stability guarantee in this paperFigure6 shows the probability of reconstruction with different SNR. We can see that when the measurements reach 80 which satisfy the stability guarantee proposed in this paper, the reconstruction probability is close to that which is corresponding to the 120 measurements. Therefore, it is demonstrated that our stability guarantee further reduces the necessary measurements for stable recovery of DCS-MIMO radar in low SNR condition, compared to Donoho’s stability guarantee.Figure 6
Reconstruction probability for single target under different SNR condition.


### 4.3. Phase Transitions Diagram

In order to further study the impact of the joint sparsity and the amount of measurements on the performance of sparse reconstruction, we showed the phenomenon of phase transitions of joint sparse recovery in our DCS-MIMO radar system based on a large number of experiments. The phase transitions diagram would visually show the relationship between the joint sparsity, the amount of measurements, and the probability of sparse reconstruction.Theρ in Figure 7 denotes the ratio of the length of signal N to the number of measurements M. Success rates of 90%, 50%, and 10% are indicated by the lower set of blue, green, and red curves, respectively. When the [K,ρ] drops in the area under these curves, the DCS-MIMO radar system could reconstruct the sparse scene by the probability of the curve or higher probability.Phase transitions diagram.
(a)
Noiseless
(b)
With the noise of 2 dBWe can find that when DCS-MIMO radar system is in the condition of low SNR, the performance falls rapidly while the joint sparsityK increases. Hence, the new problem appears and we will somehow need to solve the joint sparse recovery with higher joint sparsity. This is the main content of our latter part of study.


## 4.1. Targets’ Parameters Estimation

In order to prove the effectiveness of the DCS-MIMO radar, we simulated a small scene with2 transmitters and 2 receivers. We use the common Cartesian coordinate system. The transmitters are located at t1=[100,0]m and t2=[200,0]m, respectively. The receivers are located at r1=[0,100]m and r2=[0,200]m, respectively. The sample rate is fc=100MHz. We choose the number of samples in each receiver to be N=80; therefore, y has 160 entries. We divided the position space of the target into 11×13 grid points and the target’s velocity space into 5×5 grid points. Therefore, the total number of possible target states L=3575. We consider the presence of 2 targets. Hence, the sparse vector θ formed by 7150 entries has only K×Mr=4 nonzero entries corresponding to the targets.The positions and the velocities of the targets are given as(37)P1=80,260m,P2=110,290m,V1=[120,120]m/s,V2=[100,100]m/s.
The attenuations corresponding to the two targets are
(38)a111,a121,a211,a221=0.3,0.3,0.7,0.8,a112,a122,a212,a222=0.4,0.5,0.3,0.2.We assume the SNR for the receivers areSNR1=2dB and SNR2=3dB.From Figure3, we can see that, using JOMP algorithm, the DCS-MIMO radar system is able to estimate the positions and velocities of the targets accurately in the presence of noise. Since it is not possible to plot the position and velocity on the same plot, we plotted the estimates of position and velocity separately.Targets’ parameters estimation using JOMP.
(a)
Position estimation
(b)
Velocity estimationIn order to compare with the conventional CS method that uses CS to reconstruct the sparse vector in each receiver separately, we use 1000 independent Monte Carlo runs to generate these results. Here, we define that a successful estimation is that every receiver estimates the positions of targets accurately. Then, in Figure4, we can see that reconstruction using joint sparse modeling has a higher reconstruction probability than the conventional CS approach. Therefore, we demonstrate the advantages of the reconstruction using joint sparse modeling and JOMP algorithm.Figure 4
Reconstruction probability for the system using joint sparse modeling and the system using CS in each receiver separately as a function of SNR.


## 4.2. Guaranteed Stability of Joint Sparse Recovery

According to the theorem in Section3, we simulated the Gram matrix of the sensing matrix of the DCS-MIMO radar system. After calculating the average off-diagonal amplitude μt, we show the relationship between μt and the number of measurements M. For comparison, we also show the relationship between μ and the number of measurements M according to Donoho’s theorem in [18].Considering the joint sparsity of the received signal ensemble, we get the stability guarantee of the DCS-MIMO radar system based on the theorem proposed in Section3. In Figure 5, when the value of the average coherence μt or the coherence μ is lower than the stability guarantee, stable recovery of sparse targets scene could be achieved. By comparison of Figures 5(a) and 5(b), we can find that the necessary number of measurements reduced from 120 to 80 in our simulation settings by the stability guarantee in this paper.Coherenceμ and average coherence μt of the sensing matrix of different number of measurements with the different stability guarantee.
(a)
Donoho’s stability guarantee
(b)
Stability guarantee in this paperFigure6 shows the probability of reconstruction with different SNR. We can see that when the measurements reach 80 which satisfy the stability guarantee proposed in this paper, the reconstruction probability is close to that which is corresponding to the 120 measurements. Therefore, it is demonstrated that our stability guarantee further reduces the necessary measurements for stable recovery of DCS-MIMO radar in low SNR condition, compared to Donoho’s stability guarantee.Figure 6
Reconstruction probability for single target under different SNR condition.


## 4.3. Phase Transitions Diagram

In order to further study the impact of the joint sparsity and the amount of measurements on the performance of sparse reconstruction, we showed the phenomenon of phase transitions of joint sparse recovery in our DCS-MIMO radar system based on a large number of experiments. The phase transitions diagram would visually show the relationship between the joint sparsity, the amount of measurements, and the probability of sparse reconstruction.Theρ in Figure 7 denotes the ratio of the length of signal N to the number of measurements M. Success rates of 90%, 50%, and 10% are indicated by the lower set of blue, green, and red curves, respectively. When the [K,ρ] drops in the area under these curves, the DCS-MIMO radar system could reconstruct the sparse scene by the probability of the curve or higher probability.Phase transitions diagram.
(a)
Noiseless
(b)
With the noise of 2 dBWe can find that when DCS-MIMO radar system is in the condition of low SNR, the performance falls rapidly while the joint sparsityK increases. Hence, the new problem appears and we will somehow need to solve the joint sparse recovery with higher joint sparsity. This is the main content of our latter part of study.


## 5. Conclusion

In this paper, we have devised the scheme of the DCS-MIMO radar system and proposed the joint sparse modeling to get joint sparse representation of the received signal ensemble. This scheme provided us with the method for processing signal from different channels simultaneously and getting better performance in low SNR condition. We also proposed a modificatory stability guarantee for sparse recovery in the DCS-MIMO radar, employing the average coherence of the sensing matrix. This stability guarantee is demonstrated to be effective for the DCS-MIMO radar and could further reduce the necessary amount of measurements for stable recovery. On the other hand, since the stability guarantee has given us the least amount of measurements which is needed for stable recovery in low SNR condition, we will have theoretical foundation when designing the hardware of the DCS-MIMO radar. We have provided analytical results to show the feasibility of the DCS-MIMO radar system and the reliability of the proposed stability guarantee. At last, we raised a new problem with higher joint sparsity by analyzing the phase transitions diagram of DCS-MIMO radar, which points out the next research priorities in our future work.



---

*Source: 421740-2015-01-01.xml*