# Joint-2D-SL0 Algorithm for Joint Sparse Matrix Reconstruction

Authors: Dong Zhang; Yongshun Zhang; Cunqian Feng
Journal: International Journal of Antennas and Propagation
 (2017)

---

## Abstract

Sparse matrix reconstruction has a wide application such as DOA estimation and STAP. However, its performance is usually restricted by the grid mismatch problem. In this paper, we revise the sparse matrix reconstruction model and propose the joint sparse matrix reconstruction model based on one-order Taylor expansion. And it can overcome the grid mismatch problem. Then, we put forward the Joint-2D-SL0 algorithm which can solve the joint sparse matrix reconstruction problem efficiently. Compared with the Kronecker compressive sensing method, our proposed method has a higher computational efficiency and acceptable reconstruction accuracy. Finally, simulation results validate the superiority of the proposed method.


---

## Body

## 1. Introduction

Compressive sensing is becoming more and more popular for its superiority in parameter super-resolution estimation using short observation [1–3]. And as extensions to compressed sensing, sparse matrix reconstruction has received a lot of attention [4–6]. Many problems in signal processing can be seemed as sparse matrix reconstruction problem, such as the DOA estimation [7] and STAP [8]. In this paper, we consider the estimation of DOA and DOD in MIMO radar. It can be solved by the traditional subspace method, such as MUSIC and ESPRIT algorithm. But they usually need large snapshots to estimate the covariance matrix. Considering the advantages of sparse matrix reconstruction, here, we research the estimation of DOA and DOD in MIMO radar based on sparse matrix reconstruction method. And many algorithms have been proposed to solve the sparse matrix reconstruction efficiently. For instance, [9] puts forward the 2D-SL0 algorithm, and [10] puts forward the 2D-IAA algorithm. Both of them can reconstruct the sparse matrix efficiently. However, the sparse matrix model has some inherent shortcomings. Its performance is affected by the grid mismatch problem [11]. That is because no matter how thin we divide the mesh, we still cannot guarantee that all the parameters fall on the grid completely [12, 13]. So the estimation accuracy will be affected by the grid number and how much do we divide the mesh.In this paper, we revise the sparse matrix model by the one-order Taylor expansion and propose the joint sparse matrix model. This model eliminates the grid mismatch effect by introducing some joint sparse items. Then, in order to solve the joint sparse matrix reconstruction problem efficiently, we revise the 2D-SL0 algorithm and put forward the Joint-2D-SL0 algorithm. It can get a high estimation accuracy with satisfied speed.Note that our method is different with the methods in [9, 10]. The methods in [9, 10] cannot deal with the off-grid problem. Our method can solve it by introducing some joint sparse items. And these sparse items have the same sparse structure. So the “Joint” means that our Joint-2D-SL0 algorithm can get their estimation simultaneously. However, the “Joint” in [14] means that it is jointly used to reconstruct the images at all available channels simultaneously. That is the difference between our method and the method in [14]. Both our method and the method in [14] are applied to the signal matrix without stacking the signal into 1D vector.


## 2. Problem Formulation

Assuming there is a bistatic MIMO radar which obtainsK transmitters and L receivers, both the transmitting array and the receiving array are collocated in uniform linear array. d1 and d2 are the element spacing of transmitters and receivers, respectively. fT=d1cosφ/λ and fR=d2cosθ/λ are the normalized DOD and normalized DOA of targets. For convenience, we denote them as the DOD and DOA in our paper. Assuming the transmitting waveforms are normalized orthogonal signals, that is, SSH=IK, where S=s1,s2,…,sKT. After matched filtering, we get the received signal as follows:
(1)Y=∑m=1MamaRfmRaTfmTTS+WSH=∑m=1MamaRfmRaTfmTT+Z,where am is the scattering coefficient of mth target. W represents the noise matrix. Z=WSH. aRfmR=1,…,expjL−12πfmR and aTfmT=1,…,expjK−12πfmT are the receiving steering vectors and transmitting steering vectors corresponding to the DOA and DOD of the mth target, respectively.Considering the sparsity of targets, the sparse reconstruction method can be used to estimate target’s 2D parameters. Then, discretizing the range of DOD and DOA toKd>K and La>L resolution grids, respectively, we can convert (1) into the following form:
(2)Y=ΦRθΞΦTTφ+Z,where Ξ is a spare matrix and we can estimate the DOD and DOA of targets according to the position of nonzero elements. θ=θ1,θ2,…,θKd and φ=φ1,φ2,…,φLa are the predefined grids. ΦRθ=aRf1R,aRf2R,…,aRfKdR and ΦTφ=aTf1T,aTf2T,…,aTfLaT.This sparse matrix reconstruction model requires that the targets must fall on the predefined grids. Practically, no matter how small we divide the mesh, the targets cannot be guaranteed to completely fall on the grids. So the performance of this method will depend on the way how we divide the mesh. Reference [11] puts forward an off-grid model to solve the grid mismatch problem in 1D-DOA estimation; this idea could be extended to the 2D parameter estimation situation.


## 3. Joint Sparse Matrix Reconstruction

The targets’ true and unknown DOA and DOD areα=α1,α2,…,αD and β=β1,β2,…,βD, respectively. Approximating the ΦRα and ΦTβ by the first-order Taylor expansion around the predefined grids θ and φ, respectively,
(3)ΦRα=ΦRθ+ΦRθ′Δ1,ΦTβ=ΦTφ+ΦTφ′Δ2,where ΦRθ′=∂aRθ1/∂θ1,…,∂aRθLa/∂θLa, ΦTφ′=∂aTφ1/∂φ1,…,∂aTφKd/∂φKd, Δ1=diagα−θ, and Δ2=diagβ−φ. We can get the following joint sparse matrix model:
(4)Y=ΦRθ+ΦRθ′Δ1ΞΦTφ+ΦTφ′Δ2T+Z=ΦRθΦRθ′IΔ1ΞIΔ2TΦTφΦTφ′T+Z=ΦRθΦRθ′ΞΞΔ2TΔ1ΞΔ1ΞΔ2TΦTφΦTφ′T+Z=ΦRθΦRθ′ΞP2P1P3ΦTφΦTφ′T+Z,where P1=Δ1Ξ, P2=ΞΔ2T, P3=Δ1ΞΔ2T, and Ξ are joint sparse matrix, that is, they have the same sparse structure. That is because whether left multiplied or right multiplied, a diagonal matrix will not change the sparsity of a sparse matrix. So we can use (4) to estimate the targets’ DOD and DOA, and it will not be affected by the grid mismatch problem.UsingΦR and ΦT to represent ΦRθ and ΦTφ, respectively, (4) can be rewritten as follows:
(5)Y=ΦRΦR′ΞP2P1P3ΦTΦT′T+Z.But how to efficiently solve the joint sparse reconstruction problem? If we use the Kronecker compressive sensing method (solve (5) by converting it into 1D problem), it will bring much more computation burden because of the huge computation complexity of Kronecker product. Can we directly solve the joint sparse matrix reconstruction problem in (5)? Reference [9] proposes the 2D smoothed L0 (2D-SL0) algorithm, and it solves the 2D sparse problem more easily than the 1D-SL0 algorithm. Based on this, we revise the 2D-SL0 algorithm and propose the Joint-2D-SL0 algorithm to solve the joint sparse matrix reconstruction problem. They can be applied to situations where the number of targets is unknown.The Gaussian function adopted in the 2D-SL0 isGσX=∑i,jexp−xi,j2/σ2 [9]. Here, the Gaussian function we adopt in the Joint-2D-SL0 algorithm is
(6)GσΞP2P1P3=∑i,jexp−Ξi,j2+P1i,j2+P2i,j2+P3i,j2σ2.It will lead to a joint sparse ofΞ,P1,P2, and P3, that is, the special case of block sparse of ΞP2P1P3. The joint 2D gradient projection method is put forward to solve the Joint-2D-SL0 function. The gradient of the Joint-2D-SL0 function is
(7)δ≜∇GσΞP2P1P3=−Ξi,jexp−Ξi,j2+P1i,j2+P2i,j2+P3i,j2σ2⋯−P2i,jexp−Ξi,j2+P1i,j2+P2i,j2+P3i,j2σ2⋮⋱⋮−P1i,jexp−Ξi,j2+P1i,j2+P2i,j2+P3i,j2σ2⋯−P3i,jexp−Ξi,j2+P1i,j2+P2i,j2+P3i,j2σ2,where σ1 is chosen as σ1>8maxi,jWi,j and W=Ξ0P20P10P30.The initialization of the joint sparse matrix is(8)Ξ0P20P10P30=ΦRΦR′†YΦTTΦT′T†.The proof is as follows:Proof
(9)
v
e
c
Ξ
0
P
2
0
P
1
0
P
3
0
=
Φ
T
Φ
T
′
⊗
Φ
R
Φ
R
′
†
v
e
c
Y
=
Φ
T
Φ
T
′
†
⊗
Φ
R
Φ
R
′
†
v
e
c
Y
=
v
e
c
Φ
R
Φ
R
′
†
Y
Φ
T
T
Φ
T
′
T
†
.The projection onto the feasible set can be obtained by(10)ΞP2P1P3=ΞlP2lP1lP3l+ΦRΦR′†Y−ΦRΦR′ΞlP2lP1lP3lΦTTΦT′TΦTTΦT′T†.The proof is as follows:Proof.
When reconstructing a sparse matrix using the modelY=ΦRΦR′ΞlP2lP1lP3lΦTΦT′T+Z, we have
(11)Y−ΦRΦR′ΞlP2lP1lP3lΦTΦT′T=ΦRΦR′ΞP2P1P3ΦTΦT′T−ΦRΦR′ΞlP2lP1lP3lΦTΦT′T=ΦRΦR′ΞP2P1P3−ΞlP2lP1lP3lΦTΦT′T.
So the minimumL2 estimate of ΞP2P1P3−ΞlP2lP1lP3l is
(12)ΦRΦR′†Y−ΦRΦR′ΞlP2lP1lP3lΦTΦT′TΦTΦT′T†.
So the projection onto the feasible set can be obtained by(13)ΞP2P1P3=ΞlP2lP1lP3l+ΦRΦR′†Y−ΦRΦR′ΞlP2lP1lP3lΦTTΦT′TΦTTΦT′T†.Now we get the Joint-2D-SL0 algorithm which is shown in Algorithm1.Algorithm 1: The Joint-2D-SL0 algorithm.
Initialize:
(1) LetΞ0P20P10P30=ΦRΦR′†YΦTTΦT′T†.
(2) Choose a suitable decreasing sequence forσ,σ1,σ2,…,σJ.
Forj=1,2,…,J:
(1) Letσ=σJ
(2) Minimise the functionGσΞP2P1P3=∑i,jexp−Ξi,j2+P1i,j2+P2i,j2+P3i,j2σ2,
on the feasible setΞP2P1P3=ΞP2P1P3:ΦRΦR′ΞP2P1P3ΦTTΦT′T−Y2<ε,
usingL iterations of the steepest descent algorithm (then project ΞP2P1P3 onto the feasible set):
Initialize:ΞP2P1P3=Ξj−1P2j−1P1j−1P3j−1
Forl=1,2,…,L
(a) Let
δ≜σ2∇GσΞP2P1P3=−Ξi,jexp−Ξi,j2+P1i,j2+P2i,j2+P3i,j2σ2⋯−P2i,jexp−Ξi,j2+P1i,j2+P2i,j2+P3i,j2σ2⋮⋱⋮−P1i,jexp−Ξi,j2+P1i,j2+P2i,j2+P3i,j2σ2⋯−P3i,jexp−Ξi,j2+P1i,j2+P2i,j2+P3i,j2σ2.
(b) LetΞP2P1P3←ΞP2P1P3+μδ (μ is a small positive constant)
(c) ProjectΞP2P1P3 back onto the feasible set:
ΞP2P1P3←ΞP2P1P3+ΦRΦR′†Y−ΦRΦR′ΞP2P1P3ΦTTΦT′TΦTTΦT′T†.
(3) SetΞjP2jP1jP3j=ΞP2P1P3.
Final answer is:ΞP2P1P3=ΞjP2jP1jP3j.Remark 1.
The internal loop is repeated a fixed and small number of times (L). That is to say, for increasing the speed, we do not wait for the steepest ascent algorithm to converge. This can be justified by the gradual decrease in the value of σ. And for each σ, we do not need the exact maximizer of Gσ. We just need to enter the region near the (global) maximizer of Gσ to escape from its local maximizers.Remark 2.
Steepest ascent consists of iterations of the formΞP2P1P3←ΞP2P1P3+μj∇Gσ. Here, the step-size parameters μj should be decreasing, that is, for smaller values of σ, smaller values of μj should be applied. Note that instead of μj only a constant μ appeared. The reason is that by letting μj=μσ2 for some constant μ, we have ΞP2P1P3←ΞP2P1P3+μσ2∇Gσ=ΞP2P1P3+μδ.
(14)δ=σ2∇Gσ=−Ξi,jexp−Ξi,j2+P1i,j2+P2i,j2+P3i,j2σ2⋯−P2i,jexp−Ξi,j2+P1i,j2+P2i,j2+P3i,j2σ2⋮⋱⋮−P1i,jexp−Ξi,j2+P1i,j2+P2i,j2+P3i,j2σ2⋯−P3i,jexp−Ξi,j2+P1i,j2+P2i,j2+P3i,j2σ2.Remark 3.
The initial value our algorithm is the minimumL2 norm solution of Y=ΦRΦR′ΞlP2lP1lP3lΦTΦT′T+Z, which corresponds to σ→∞. And the specific proof can refer to [15].Remark 4.
Having initiated the algorithm with the minimumL2 norm solution (which corresponds to σ→∞), the next value for σ (i.e., σ1) may be about 6 to 12 times of the maximum absolute value of the obtained sources. Here, we select σ1>8maxi,jWi,j. To see the reason, if we take, for example, σ1>8maxi,jWi,j, then expΞ1i,j2+P1i,j2+P2i,j2+P3i,j2/σ2>0.93≈1 for all i and j. And it shows that this value of σ acts virtually like infinity for all the values of Ξ1i,j2+P1i,j2+P2i,j2+P3i,j20.5.Remark 5.
The smallest value ofσ should be about three to six times of (a rough estimation of) the standard deviation of this noise. This is because, while σ is in this range, the cost function treats small (noisy) samples as zeros (i.e., for which expΞ1i,j2+P1i,j2+P2i,j2+P3i,j2/σ2≈1). However, below this range, the algorithm tries to “learn” these noisy values and moves away from the true answer.Remark 6.
The sequence ofσ is always chosen as a decreasing geometrical sequence σj=cσj−1,j≥2, which is determined by the first and last elements, σ1 and σJ, and the scale factor c. In our simulation, for increasing the speed, we set J=100. So c=σJ/σ11/J.


## 4. Simulation Results

In this section, we conduct several simulation experiments to verify the performance of the proposed model and algorithm.In the first simulation, we show the correctness of the proposed Joint-2D-SL0 algorithm. Assume there are 5 targets, their normalized DOA and DOD are [0.34, 0.14, −0.13, −0.35, and −0.47] and [−0.35, −0.22, −0.13, 0.32, and 0.41], respectively. There are 20 transmitters and 20 receivers. The grid number of DOD and DOA is 60 and 60, respectively. The noise is white Gaussian noise. And the SNR is 20 dB. The input parameters areσmin=0.1, J=100, μ=2, and L=3. The result is shown in Figure 1(a). We can see that the proposed Joint-2D-SL0 algorithm can accurately estimate the parameters of the target which verifies the correctness of the proposed algorithm.Figure 1
The estimation performance of the proposed algorithms.
(a)
Algorithm correctness verification
(b)
Estimation accuracy comparison of the proposed algorithmThen, we compare the estimation accuracy of the proposed Joint-2D-SL0 algorithm with the estimation accuracy of Joint-K-SL0 algorithm (solving (5) using Kronecker compressive sensing method) and K-SL0 algorithm (solving (2) using Kronecker compressive sensing method) and 2D-SL0 algorithm (solving (2) using the method in [9]). The SNR varies from −5 dB to 30 dB. And the other parameters remain the same. 200 times simulation is conducted in each SNR. The simulation result is in Figure 1(b). We can see that the estimation error of the proposed model decreases significantly with the increase of SNR while the estimated error of the traditional model does not decrease when the SNR is bigger than 0 dB. That is because when SNR > 0 dB, the estimation error of traditional model is mainly affected by the grid mismatch problem. And the increase of SNR will not bring accuracy improvement. So the proposed off-grid model has a better performance than the model without considering grid mismatch problem which proves the validity of the proposed model. From Figure 1(b), we can see that the estimation accuracy of standard 2D-SL0 is similar with the estimation accuracy of K-SL0 algorithm. And their estimation accuracy is much lower than the estimation accuracy of Joint-2D-SL0. We also can see that the proposed Joint-2D-SL0 algorithm has a similar performance with Joint-K-SL0 algorithm which verifies the effectiveness of the proposed algorithm.In the third simulation, we compare the running time of these algorithms. For the convenience of comparison, we conduct two kinds of contrast experiment. In the first comparative experiment, we set the grid number of DOD and DOA both to be 60, the number of transmitter and receiver elements is set to the same value which varies from 15 to 30. And the result is shown in Figure2(a). In the second comparative experiment, the number of transmitter and receiver elements is both set to be 20 while the grid number of DOD and DOA is set to the same value which varies from 60 to 80. And the result is shown in Figure 2(b). The other simulation parameters are the same with the first simulation. We can see that the runtime of the proposed 2D algorithm is the fastest algorithm compared with the K-SL0 and Joint-K-SL0 algorithms in the two contrast simulation. And the runtime increasing tendency of the proposed 2D method is the lowest compared with the runtime increasing tendency of the other two algorithms which proves the efficiency of the proposed Joint-2D-SL0 algorithm. From Figure 2, we can see that the runtime of standard 2D-SL0 is shorter than that of Joint-2D-SL0. But the estimation accuracy of standard 2D-SL0 is much lower than that of Joint-2D-SL0, so we can say that the proposed Joint-2D-SL0 algorithm can get high estimation accuracy with acceptable computation complexity.Figure 2
Runtime comparison of algorithm.
(a)
Grid number of DOD and DOA both set to be 60
(b)
The number of transmitter and receiver array elements both set to be 20In the fourth experiment, to show the affection of the number of iterations, we setJ = 25, 50, 75, 100, 125, and 150, respectively. The other parameters are same with the second experiment. And the result is shown in Figure 3. From this figure, we can see that the estimation accuracy improved with the increase of J. However, when J reaches to a certain number, the estimation accuracy remains constant and does not increase anymore. So, the optimal choice of J depends on the application. When SNR is the essential criterion, J should be chosen large, but this will result in a higher computational cost. Therefore, the choice of J is a trade-off between SNR and computational cost.Figure 3
Comparison of differentJ.


## 5. Conclusion

In this paper, we propose the joint sparse matrix reconstruction model based on the one-order Taylor expansion and it can overcome the grid mismatch problem efficiently. Then, we put forward the Joint-2D-SL0 algorithm to solve the joint sparse matrix reconstruction problem. Our algorithm can get high estimation accuracy with acceptable computational complexity. Simulation experiences verify the effectiveness of the proposed model and algorithm.



---

*Source: 6862852-2017-12-20.xml*