# Two-Dimensional Multiple-Snapshot Grid-Free Compressive Beamforming Using Alternating Direction Method of Multipliers

Authors: Yang Yang; Zhigang Chu
Journal: Shock and Vibration
 (2020)

---

## Abstract

Compressive beamforming with planar microphone arrays is capable of estimating the two-dimensional direction-of-arrivals (DOAs) and quantifying the strengths of acoustic sources effectively. The multiple-snapshot grid-free method has recently been concerned due to the advantages that it can circumvent the basis mismatch conundrum of the conventional grid-based method and improve the performance of the single-snapshot grid-free method. The existing atomic norm minimization based strategy uses an off-the-peg interior point method (IPM) based solver to solve the positive semidefinite programming equivalent to the atomic norm minimization. We present an alternative algorithm based on alternating direction method of multipliers (ADMM) in this paper. Both simulations and experiments demonstrate that whether a standard uniform rectangular array or a non-uniform array constituted by a small number of microphones is employed, the two-dimensional multiple-snapshot grid-free compressive beamforming using our ADMM based algorithm can estimate the DOAs and quantify the strengths of acoustic sources well, and reaching the same or even better DOA estimation accuracy as the one using the IPM based solver, our ADMM based algorithm is distinctly faster.


---

## Body

## 1. Introduction

Compressive beamforming, or concretely compressive sensing [1–3] based beamforming, is an emerging and powerful approach to realize the direction-of-arrival (DOA) estimation and strength quantification of acoustic sources. By virtue of the superiorities of small number demand for microphones, strong anti-interference, unambiguous source imaging and so on, it has recently aroused much concern [4–8].In conventional compressive beamforming, the DOA domain is gridded/discretized into a finite set of look directions and all the sources are assumed to fall in these look directions. A linear system of equations relating the signals measured by an array of microphones to the source distribution is established. The source distribution is retrieved from the linear system of equations by imposing a sparsity constraint, i.e., minimizing theℓ1-norm of the vector (for the single-snapshot case) or the ℓ2,1-norm of the matrix (for the multiple-snapshot case) composed by the source strengths in all the look directions. Its results become inaccurate when the DOAs of sources do not conform with these look directions. The problem is called basis mismatch [4, 9] and can be often encountered in practical applications. Adopting finer grids mitigates basis mismatch at the cost of increased computational complexity. More seriously, grid refinement leads to increased coherence of the measuring process, which can cause offset in the estimates [4]. To conquer the conundrum fundamentally, the idea of utilizing a continuous grid-free setting [10–12] is proposed. In 2015, Xenaki and Gerstoft [13] presented a one-dimensional grid-free compressive beamforming strategy for the measurements with linear microphone arrays based on the minimization of the atomic norm of source strength and the polynomial rooting method. In 2017-2018, the authors [14, 15] presented a two-dimensional grid-free compressive beamforming strategy for the measurements with planar microphone arrays based on the minimization of the atomic norm of microphone pressure induced by sources and the matrix enhancement and matrix pencil method [16]. Both these strategies are based on the single-snapshot data model and thus suitable to identify the transient or the moving sources. In 2018, Park et al. [17] extended Xenaki and Gerstoft’s strategy into the multiple-snapshot case through a group atomic norm. The same year, the authors [18] realize the two-dimensional multiple-snapshot grid-free compressive beamforming based on the minimization of the atomic norm of multiple-snapshot microphone pressure induced by sources and the matrix pencil and pairing (MaPP) method [19]. They all have demonstrated that for sources that are active across multiple snapshots, for example, stationary sources, the multiple-snapshot grid-free compressive beamforming is distinctly superior to the single-snapshot one.The atomic norm minimization in the grid-free compressive beamforming is a convex optimization problem [20] and can be characterized as a positive semidefinite programming. In Refs. [13–15, 17, 18], the positive semidefinite programming is solved by the off-the-peg SDPT3 solver in CVX toolbox [21]. The solver is based on interior point method (IPM) [20] and becomes time-consuming for problems with large dimensional matrices [22]. In the two-dimensional multiple-snapshot grid-free compressive beamforming with planar microphone arrays, the dimensions of the matrices are usually large because of the large number of microphones and snapshots. Therefore, it is necessary to develop a faster solving algorithm. A feasible algorithm based on alternating direction method of multipliers (ADMM) [23] is proposed in this paper.The remainder of this paper is organized as follows. Section2 deduces the formulations of ADMM that can solve the positive semidefinite programming equivalent to the minimization of the atomic norm of multiple-snapshot microphone pressure induced by sources, after illuminating the theory of the two-dimensional multiple-snapshot grid-free compressive beamforming. Section 3 and 4 compares the performance of the two-dimensional multiple-snapshot grid-free compressive beamforming using the IPM based SDPT3 solver and our ADMM based algorithm with simulations and experiments respectively. Section 5 summarizes this paper.


## 2. Theory

### 2.1. Two-Dimensional Multiple-Snapshot Grid-Free Compressive Beamforming

The two-dimensional multiple-snapshot grid-free compressive beamforming can employ a standard uniform rectangular microphone array, such as the one in Figure1(a), to measure the sound signal. Denoting by A and B the row and the column number of microphones respectively, L the number of snapshots, ℂ the set of complex numbers, P★∈ℂAB×L the matrix of the pressure measured by each microphone under each snapshot, P∈ℂAB×L the matrix of the pressure induced by sources at each microphone under each snapshot, and N∈ℂAB×L the matrix of the noise borne by each microphone under each snapshot, we have(1)P★=P+N.Figure 1
Sketch maps of (a) standard uniform rectangular and (b) non-uniform microphone arrays.
(a)
(b)In the follow-up simulations, the noise is generated as independent and identically distributed complex Gaussian. The array signal-to-noise ratio (SNR) is defined asSNR=20log10PF/NF, where ·F denotes the Frobenius norm. The noise Frobenius norm can be got by NF=PF10−SNR/20.The first postprocessing step of the two-dimensional multiple-snapshot grid-free compressive beamforming is to denoiseP★ and thus reconstruct P. This can be realized by imposing a sparsity constraint, i.e., minimizing the number of sources [18]. Establish a Cartesian coordinate system, whose origin is at one vertex of the array, xoy plane is the array plane, and z axis is perpendicular to the array plane. For a point in the space, form a line segment between the point and the origin. The elevation angle θ of the point is defined as the angle from the positive z axis to the line segment. The azimuth angle ϕ of the point is defined as the angle from the positive x axis to the orthogonal projection of the line segment on the xoy plane. The hemisphere which the positive z axis falls in is considered as the source region, i.e., 0∘≤θ≤90∘ and 0∘≤ϕ≤360∘. Under the grid-free setting, the atomic norm of P is utilized to measure the sparsity of sources. Its definition is(2)PA=infsi∈ℝ+Dθi,ϕi∈A∑isiP=∑isiDθi,ϕi,where i indexes the sources, si is the ℓ2-norm of the vector composed by the strength of the i-th source under each snapshot, ℝ+ is the set of positive real numbers, θi,ϕi indicates the DOA of the i-th source, Dθi,ϕi is the transfer matrix from si to the microphone pressure, A=Dθ,ϕ0∘≤θ≤90∘,0∘≤ϕ≤360∘ is the atomic set, and inf denotes the infimum. The reconstruction problem of P can be formulated as(3)P^=argminP∈ℂAB×LPAsubject toP★−PF≤ε,where ε is the noise control parameter. Normally, let ε=NF. Equation (3) can be characterized as the following positive semidefinite programming [18]:(4)u^,p^,E^=argminu∈ℂNu,P∈ℂAB×L,E∈ℂL×L12ABtrTbu+trEsubject toTbuPPHE⪰¯0,P★−PF≤ε,where both u and E are the auxiliary quantities, Nu=A−12B−1+B, E is a Hermitian matrix, tr⋅ calculates the trace of a matrix, Tb⋅ denotes the two-fold Toeplitz operator [14, 15, 18, 22], Tbu is a AB×AB Hermitian two-fold Toeplitz matrix, ⋅H denotes the conjugate operator, and ⪰¯0 means a positive semidefinite matrix.The second postprocessing step of the two-dimensional multiple-snapshot grid-free compressive beamforming is to estimate the number and DOAs and quantify the strengths of sources. This can be realized by using the MaPP method to process theTbu^ and P^ obtained by equation (4). The detailed procedure can be seen in Ref. [18]. The array constructed by randomly choosing partial microphones from the standard uniform rectangular array is referred to as a non-uniform or sparse rectangular array, as shown in Figure 1(b). Employing the pressures measured by the partial microphones, the two-dimensional multiple-snapshot grid-free compressive beamforming also can obtain the Tbu^, reconstruct the full microphone pressure induced by sources, and eventually realize the DOA estimation and strength quantification of acoustic sources [18]. In this case, P★, P and N in equation (1) become PΩ★, PΩ and NΩ, and P★−P in equations (3) and (4) becomes PΩ★−PΩ, where Ω represents the set of the indices of the chosen microphones, Ω is the cardinality of Ω, PΩ★∈ℂΩ×L represents the matrix of the pressures measured by the chosen microphones, PΩ∈ℂΩ×L represents the matrix of the pressures induced by sources at the chosen microphones, and NΩ∈ℂΩ×L represents the matrix of the noises borne the chosen microphones.


### 2.2. Alternating Direction Method of Multipliers to Solve Positive Semidefinite Programming

In this section, we deduce the formulations of ADMM that can solve the positive semidefinite programming in equation (4). A detailed survey about ADMM can be seen in Ref. [23]. Because P★−P is a special case of PΩ★−PΩ with Ω including the indices of the full microphones, we conduct the derivation on PΩ★−PΩ. To apply ADMM, we reformulate equation (4) as(5)u^,P^,E^,Z^=argminu∈ℂNu,P∈ℂAB×L,E∈ℂL×L,Z∈ℂAB+L×AB+L12PΩ★−PΩF2+τ2ABtrTbu+trEsubject toZ=TbuPPHE⪰¯0,where Z is an auxiliary matrix and τ is a regularization parameter. The value of τ can be determined according to Ref. [24]. The augmented Lagrangian function of equation (5) is(6)ℒρE,u,P,Z,Λ=12PΩ★−PΩF2+τ2ABtrTbu+trE+Λ,Z−TbuPPHE+ρ2Z−TbuPPHEF2,where the Hermitian matrix Λ∈ℂAB+L×AB+L is the Lagrangian multiplier, ρ>0 is the penalty parameter and ⋅,⋅ represents the inner product. The ADMM solves equation (5) iteratively. Initializing Z0=Λ0=0, the updates in q+1-th iteration are as follows:(7)Eq+1,uq+1,Pq+1=argminE∈ℂL×L,u∈ℂNu,P∈ℂAB×LℒρE,u,P,Zq,Λq,(8)Zq+1=argminZ⪰¯0ℒρEq+1,uq+1,Pq+1,Z,Λq,(9)Λq+1=Λq+ρZq+1−Tbuq+1Pq+1Pq+1HEq+1.Introduce the partitions(10)Λq=Λ0q∈ℂAB×ABΛ1q∈ℂAB×LΛ1qH∈ℂL×ABΛ2q∈ℂL×L,Zq=Z0q∈ℂAB×ABZ1q∈ℂAB×LZ1qH∈ℂL×ABZ2q∈ℂL×L.Denote byΛ1Ωq∈ℂΩ×L and Z1Ωq∈ℂΩ×L, respectively, the matrices of the rows in Λ1q and Z1q corresponding to the chosen microphones, Ωc the set of the indices of the unchosen microphones, Ωc the cardinality of Ωc, PΩc∈ℂΩc×L the matrix of the pressures induced by sources at the unchosen microphones, Λ1Ωcq∈ℂΩc×L and Z1Ωcq∈ℂΩc×L, respectively, the matrices of the rows in Λ1q and Z1q corresponding to the unchosen microphones, and I1∈ℝL×L and I2∈ℝAB×AB, both, the identity matrices. It can be derived that the variable updates in equation (7) have the following closed forms:(11)Eq+1=Z2q+1ρΛ2q−τ2ABI1,(12)Tbuq+1=Z0q+1ρΛ0q−τ2ABI2,(13)PΩq+1=11+2ρPΩ★+2Λ1Ωq+2ρZ1Ωq,(14)PΩcq+1=Z1Ωcq+1ρΛ1Ωcq.The derivation can be seen in Appendix. LetM=diagAB,AB−A,…,A,A−1,A−2,…,1⊗1,2,…,B,B−1,B−2,…,1∈ℝNu×Nu, where diag⋅ forms a square matrix with off-diagonal elements being zeros and diagonal being the vector in the parentheses, ⊗ represents the Kronecker product and ℝ is the set of real numbers. Denote by Tb∗⋅ be the adjoint of Tb⋅. For a given matrix A∈ℂAB×AB, Tb∗A=trΘk1⊗Θk2Ak1,k2∈ℋ∈ℂNu. Here, Θk is an elementary Toeplitz matrix with ones on the k-th diagonal and zeros elsewhere, and ℋ is a halfspace [25] of A−1,B−1. k1,k2∈ℋ means k2∈0,1,…,B−1 when k1=0 and k2∈−B−1,−B−2,…,B−1 when k1∈1,2,…,A−1. Then,(15)uq+1=M−1Tb∗Tbuq+1.The update ofZ in equation (8) can be reformulated as(16)Zq+1=argminZ⪰¯0Z−Tbuq+1Pq+1Pq+1HEq+1+ΛqρF2,which can be performed by conducting the eigenvalue decomposition of the Hermitian matrix Tbuq+1Pq+1Pq+1HEq+1−Λq/ρ and setting all negative eigenvalues to zero.


## 2.1. Two-Dimensional Multiple-Snapshot Grid-Free Compressive Beamforming

The two-dimensional multiple-snapshot grid-free compressive beamforming can employ a standard uniform rectangular microphone array, such as the one in Figure1(a), to measure the sound signal. Denoting by A and B the row and the column number of microphones respectively, L the number of snapshots, ℂ the set of complex numbers, P★∈ℂAB×L the matrix of the pressure measured by each microphone under each snapshot, P∈ℂAB×L the matrix of the pressure induced by sources at each microphone under each snapshot, and N∈ℂAB×L the matrix of the noise borne by each microphone under each snapshot, we have(1)P★=P+N.Figure 1
Sketch maps of (a) standard uniform rectangular and (b) non-uniform microphone arrays.
(a)
(b)In the follow-up simulations, the noise is generated as independent and identically distributed complex Gaussian. The array signal-to-noise ratio (SNR) is defined asSNR=20log10PF/NF, where ·F denotes the Frobenius norm. The noise Frobenius norm can be got by NF=PF10−SNR/20.The first postprocessing step of the two-dimensional multiple-snapshot grid-free compressive beamforming is to denoiseP★ and thus reconstruct P. This can be realized by imposing a sparsity constraint, i.e., minimizing the number of sources [18]. Establish a Cartesian coordinate system, whose origin is at one vertex of the array, xoy plane is the array plane, and z axis is perpendicular to the array plane. For a point in the space, form a line segment between the point and the origin. The elevation angle θ of the point is defined as the angle from the positive z axis to the line segment. The azimuth angle ϕ of the point is defined as the angle from the positive x axis to the orthogonal projection of the line segment on the xoy plane. The hemisphere which the positive z axis falls in is considered as the source region, i.e., 0∘≤θ≤90∘ and 0∘≤ϕ≤360∘. Under the grid-free setting, the atomic norm of P is utilized to measure the sparsity of sources. Its definition is(2)PA=infsi∈ℝ+Dθi,ϕi∈A∑isiP=∑isiDθi,ϕi,where i indexes the sources, si is the ℓ2-norm of the vector composed by the strength of the i-th source under each snapshot, ℝ+ is the set of positive real numbers, θi,ϕi indicates the DOA of the i-th source, Dθi,ϕi is the transfer matrix from si to the microphone pressure, A=Dθ,ϕ0∘≤θ≤90∘,0∘≤ϕ≤360∘ is the atomic set, and inf denotes the infimum. The reconstruction problem of P can be formulated as(3)P^=argminP∈ℂAB×LPAsubject toP★−PF≤ε,where ε is the noise control parameter. Normally, let ε=NF. Equation (3) can be characterized as the following positive semidefinite programming [18]:(4)u^,p^,E^=argminu∈ℂNu,P∈ℂAB×L,E∈ℂL×L12ABtrTbu+trEsubject toTbuPPHE⪰¯0,P★−PF≤ε,where both u and E are the auxiliary quantities, Nu=A−12B−1+B, E is a Hermitian matrix, tr⋅ calculates the trace of a matrix, Tb⋅ denotes the two-fold Toeplitz operator [14, 15, 18, 22], Tbu is a AB×AB Hermitian two-fold Toeplitz matrix, ⋅H denotes the conjugate operator, and ⪰¯0 means a positive semidefinite matrix.The second postprocessing step of the two-dimensional multiple-snapshot grid-free compressive beamforming is to estimate the number and DOAs and quantify the strengths of sources. This can be realized by using the MaPP method to process theTbu^ and P^ obtained by equation (4). The detailed procedure can be seen in Ref. [18]. The array constructed by randomly choosing partial microphones from the standard uniform rectangular array is referred to as a non-uniform or sparse rectangular array, as shown in Figure 1(b). Employing the pressures measured by the partial microphones, the two-dimensional multiple-snapshot grid-free compressive beamforming also can obtain the Tbu^, reconstruct the full microphone pressure induced by sources, and eventually realize the DOA estimation and strength quantification of acoustic sources [18]. In this case, P★, P and N in equation (1) become PΩ★, PΩ and NΩ, and P★−P in equations (3) and (4) becomes PΩ★−PΩ, where Ω represents the set of the indices of the chosen microphones, Ω is the cardinality of Ω, PΩ★∈ℂΩ×L represents the matrix of the pressures measured by the chosen microphones, PΩ∈ℂΩ×L represents the matrix of the pressures induced by sources at the chosen microphones, and NΩ∈ℂΩ×L represents the matrix of the noises borne the chosen microphones.


## 2.2. Alternating Direction Method of Multipliers to Solve Positive Semidefinite Programming

In this section, we deduce the formulations of ADMM that can solve the positive semidefinite programming in equation (4). A detailed survey about ADMM can be seen in Ref. [23]. Because P★−P is a special case of PΩ★−PΩ with Ω including the indices of the full microphones, we conduct the derivation on PΩ★−PΩ. To apply ADMM, we reformulate equation (4) as(5)u^,P^,E^,Z^=argminu∈ℂNu,P∈ℂAB×L,E∈ℂL×L,Z∈ℂAB+L×AB+L12PΩ★−PΩF2+τ2ABtrTbu+trEsubject toZ=TbuPPHE⪰¯0,where Z is an auxiliary matrix and τ is a regularization parameter. The value of τ can be determined according to Ref. [24]. The augmented Lagrangian function of equation (5) is(6)ℒρE,u,P,Z,Λ=12PΩ★−PΩF2+τ2ABtrTbu+trE+Λ,Z−TbuPPHE+ρ2Z−TbuPPHEF2,where the Hermitian matrix Λ∈ℂAB+L×AB+L is the Lagrangian multiplier, ρ>0 is the penalty parameter and ⋅,⋅ represents the inner product. The ADMM solves equation (5) iteratively. Initializing Z0=Λ0=0, the updates in q+1-th iteration are as follows:(7)Eq+1,uq+1,Pq+1=argminE∈ℂL×L,u∈ℂNu,P∈ℂAB×LℒρE,u,P,Zq,Λq,(8)Zq+1=argminZ⪰¯0ℒρEq+1,uq+1,Pq+1,Z,Λq,(9)Λq+1=Λq+ρZq+1−Tbuq+1Pq+1Pq+1HEq+1.Introduce the partitions(10)Λq=Λ0q∈ℂAB×ABΛ1q∈ℂAB×LΛ1qH∈ℂL×ABΛ2q∈ℂL×L,Zq=Z0q∈ℂAB×ABZ1q∈ℂAB×LZ1qH∈ℂL×ABZ2q∈ℂL×L.Denote byΛ1Ωq∈ℂΩ×L and Z1Ωq∈ℂΩ×L, respectively, the matrices of the rows in Λ1q and Z1q corresponding to the chosen microphones, Ωc the set of the indices of the unchosen microphones, Ωc the cardinality of Ωc, PΩc∈ℂΩc×L the matrix of the pressures induced by sources at the unchosen microphones, Λ1Ωcq∈ℂΩc×L and Z1Ωcq∈ℂΩc×L, respectively, the matrices of the rows in Λ1q and Z1q corresponding to the unchosen microphones, and I1∈ℝL×L and I2∈ℝAB×AB, both, the identity matrices. It can be derived that the variable updates in equation (7) have the following closed forms:(11)Eq+1=Z2q+1ρΛ2q−τ2ABI1,(12)Tbuq+1=Z0q+1ρΛ0q−τ2ABI2,(13)PΩq+1=11+2ρPΩ★+2Λ1Ωq+2ρZ1Ωq,(14)PΩcq+1=Z1Ωcq+1ρΛ1Ωcq.The derivation can be seen in Appendix. LetM=diagAB,AB−A,…,A,A−1,A−2,…,1⊗1,2,…,B,B−1,B−2,…,1∈ℝNu×Nu, where diag⋅ forms a square matrix with off-diagonal elements being zeros and diagonal being the vector in the parentheses, ⊗ represents the Kronecker product and ℝ is the set of real numbers. Denote by Tb∗⋅ be the adjoint of Tb⋅. For a given matrix A∈ℂAB×AB, Tb∗A=trΘk1⊗Θk2Ak1,k2∈ℋ∈ℂNu. Here, Θk is an elementary Toeplitz matrix with ones on the k-th diagonal and zeros elsewhere, and ℋ is a halfspace [25] of A−1,B−1. k1,k2∈ℋ means k2∈0,1,…,B−1 when k1=0 and k2∈−B−1,−B−2,…,B−1 when k1∈1,2,…,A−1. Then,(15)uq+1=M−1Tb∗Tbuq+1.The update ofZ in equation (8) can be reformulated as(16)Zq+1=argminZ⪰¯0Z−Tbuq+1Pq+1Pq+1HEq+1+ΛqρF2,which can be performed by conducting the eigenvalue decomposition of the Hermitian matrix Tbuq+1Pq+1Pq+1HEq+1−Λq/ρ and setting all negative eigenvalues to zero.


## 3. Simulations

In this section, we compare the performance of the two-dimensional multiple-snapshot grid-free compressive beamforming using the IPM based SDPT3 solver and our ADMM based algorithm with simulations. In our ADMM based algorithm,ρ is set to 1 and the iteration is terminated if the relative changes of u and P at two consecutive iterations, i.e., uq−uq−12/uq−12 and Pq−Pq−1F/Pq−1F, both are less than 10−4 or the maximum number of iterations, set to 1000, is reached. Assume four sources. Their DOAs are (45°, 90°), (20°, 200°), (70°, 160°) and (45°, 270°), in turn. The frequency is 4000 Hz. Ten snapshots are adopted. The root mean square values of the source strength under each snapshot are 100 dB, 98 dB, 96 dB and 95 dB (referring to 2 × 10−5 Pa), in turn. Define an average Frobenius norm error θ^,ϕ^−θ,ϕF/2I and a normalized ℓ2-norm error s^rms−srms2/srms2 to measure the DOA estimation accuracy and the strength quantification accuracy. Thereinto, I is the number of sources, θ^∈ℝI and θ∈ℝI are the vectors of the estimated and the true elevation angles respectively, ϕ^∈ℝI and ϕ∈ℝI are the vectors of the estimated and the true azimuth angles respectively, and s^rms∈ℝI and srms∈ℝI are the vectors of the quantified and the true root mean square strengths respectively. Change the SNR to conduct simulations. Under each SNR, these errors, together with the consuming time of the IPM based SDPT3 solver and our ADMM based algorithm, are averaged over 100 Monte Carlo runs. In each run, the source strength and the noise are generated randomly. All the simulations are carried out in Matlab R2014a on a PC with a Windows 10 system and a 2.2 GHz Intel(R) Core(TM) i5-5200U CPU.Figure2 presents the curves of θ^,ϕ^−θ,ϕF/2I, s^rms−srms2/srms2 and consuming time vs. SNR when the standard uniform rectangular array with 64 microphones shown in Figure 1(a) is employed. Apparently, a low SNR brings relatively large DOA estimation and strength quantification errors. As shown in Figure 2(a), compared with the two-dimensional multiple-snapshot grid-free compressive beamforming using the IPM based SDPT3 solver, the one using our ADMM based algorithm has the smaller DOA estimation errors at low SNRs and almost the same DOA estimation errors at high SNRs. As shown in Figure 2(b), the two-dimensional multiple-snapshot grid-free compressive beamforming using our ADMM based algorithm has slightly larger strength quantification errors than the one using the IPM based SDPT3 solver. As shown in Figure 2(c), the consuming time of our ADMM based algorithm is evidently smaller than the one of the IPM based SDPT3 solver. Figure 3 presents the results when the non-uniform array with 30 microphones shown in Figure 1(b) is employed, which exhibit the same phenomena as in Figure 2. Changing the parameters, such as number and DOAs of sources, frequency and so on, to conduct simulations, similar phenomena can be obtained. These phenomena demonstrate that whether a standard uniform rectangular array or a non-uniform array constituted by a small number of microphones is employed, our ADMM based algorithm can bring evident efficiency improvement with no sacrificing or even ameliorating the DOA estimation accuracy and slightly sacrificing the strength quantification accuracy. The reason why our ADMM based algorithm is faster can be explained as follows. The per-iteration computational complexity of the IPM based SDPT3 solver is ONu+ABL+L22AB+L2.5 for the problem in equation (4). Hereinto, Nu+ABL+L2 is the number of variables and AB+L×AB+L is the dimension of the positive semideﬁnite matrix. The per-iteration computational complexity of our ADMM based algorithm is OAB+L3 because of the eigenvalue decomposition. The latter is smaller than the former.Figure 2
Curves of (a)θ^,ϕ^−θ,ϕF/2I, (b) s^rms−srms2/srms2 and (c) consuming time vs. SNR. The standard uniform rectangular array with 64 microphones is employed.
(a)
(b)
(c)Figure 3
Curves of (a)θ^,ϕ^−θ,ϕF/2I, (b) s^rms−srms2/srms2 and (c) consuming time vs. SNR. The non-uniform array with 30 microphones is employed.
(a)
(b)
(c)


## 4. Experiments

For purpose of validating correctness of the simulation conclusion and effectiveness of the two-dimensional multiple-snapshot grid-free compressive beamforming using our ADMM based algorithm in practical applications, we perform an experimental measurement on two small loudspeakers in a semi-anechoic room with a rectangular array. Figure4 presents the configuration. The array employs Brüel & Kjær Type 4958 microphones. The loudspeakers are excited by stationary white noises. From left to right, the Cartesian coordinates of the two loudspeakers are (2.24, 0, 5) m and (−2.24, 0, 5) m. Their DOAs are (24.13°, 0°) and (24.13°, 180°). Besides, there are two mirror sources because of the reflection effect of the ground. Their Cartesian coordinates are (2.24, −2.2, 5) m and (−2.24, −2.2, 5) m, and DOAs are (32.13°, 315.52°) and (32.13°, 224.48°). Pressure signals captured by microphones are acquired simultaneously by Brüel & Kjær PULSE Type 3560D Data Acquisition System and then transferred to Brüel & Kjær PULSE LABSHOP Software where their Fourier spectra are obtained. The sample frequency of 16384 Hz is utilized. Each snapshot has a length of 1 s and 214 samples. Ten snapshots are adopted. Eventually, the two-dimensional multiple-snapshot grid-free compressive beamforming using the IPM based SDPT3 solver and the one using our ADMM based algorithm are applied to map these sources. The parameter setting in our ADMM based algorithm keeps the same as in Section 3.Figure 4
Experimental configuration.Figure5 presents the loudspeaker source maps at 2000 Hz, 3000 Hz and 4000 Hz when the standard uniform rectangular array with 64 microphones shown in Figure 1(a) is employed. Obviously, whether the IPM based SDPT3 solver (Figures 5(a), 5(c), 5(e)) or our ADMM based algorithm (Figures 5(b), 5(d), 5(f)) is used, the two-dimensional multiple-snapshot grid-free compressive beamforming estimates the DOAs of these sources accurately. Table 1 lists the DOA estimation error corresponding to Figure 5 and the consuming time of the IPM based SDPT3 solver and our ADMM based algorithm. Apparently, the two-dimensional multiple-snapshot grid-free compressive beamforming using our ADMM based algorithm has almost the same DOA estimation error as the one using the IPM based SDPT3 solver. All these errors are very small. The consuming time of our ADMM based algorithm is only about 1/6 of the one of the IPM based SDPT3 solver. Figure 6 and Table 2 present the results when the non-uniform array with 30 microphones shown in Figure 1(b) is employed, which exhibit the same phenomena as in Figure 5 and Table 1. These phenomena demonstrate that in practical applications, the two-dimensional multiple-snapshot grid-free compressive beamforming using our ADMM based algorithm can reach the same DOA estimation accuracy as the one using the IPM based SDPT3 solver, and our ADMM based algorithm is distinctly faster. The experimental conclusion agrees with the simulated one, demonstrating that the conclusion is correct and the two-dimensional multiple-snapshot grid-free compressive beamforming using our ADMM based algorithm is effective in practical applications. It is worth mentioning that because we cannot obtain the strengths of the loudspeaker sources accurately, we do not compare the strength quantification accuracy here.Figure 5
Loudspeaker source maps at (a), (b) 2000 Hz, (c), (d) 3000 Hz and (e), (f) 4000 Hz obtained by the two-dimensional multiple-snapshot grid-free compressive beamforming using (a), (c), (e) the IPM based SDPT3 solver and (b), (d), (f) our ADMM based algorithm. The standard uniform rectangular array with 64 microphones is employed. In each map, the reconstructed output (∗) is scaled to dB by referring to its maximum, the reconstructed maximum referring to 2 × 10−5 Pa is labeled on the top, and the symbols ○ indicate the true DOAs but do not contain the strength information, so do in Figure 6.
(a)
(b)
(c)
(d)
(e)
(f)Table 1
DOA estimation error corresponding to Figure5 and consuming time of IPM based SDPT3 solver and ADMM based algorithm.
Approach to solve equation (4)
θ
^
,
ϕ
^
−
θ
,
ϕ
F
/
2
I × 100%
Consuming time
2000 Hz
3000 Hz
4000 Hz
2000 Hz
3000 Hz
4000 Hz
IPM based SDPT3 solver
1.93%
1.51%
0.88%
5.90 s
5.70 s
6.20 s
ADMM based algorithm
2.39%
1.22%
0.84%
1.01 s
0.90 s
1.00 sFigure 6
Loudspeaker source maps at (a), (b) 2000 Hz, (c), (d) 3000 Hz and (e), (f) 4000 Hz obtained by the two-dimensional multiple-snapshot grid-free compressive beamforming using (a), (c), (e) the IPM based SDPT3 solver and (b), (d), (f) our ADMM based algorithm. The non-uniform array with 30 microphones is employed.
(a)
(b)
(c)
(d)
(e)
(f)Table 2
DOA estimation error corresponding to Figure6 and consuming time of IPM based SDPT3 solver and ADMM based algorithm.
Approach to solve equation (4)
θ
^
,
ϕ
^
−
θ
,
ϕ
F
/
2
I × 100%
Consuming time
2000 Hz
3000 Hz
4000 Hz
2000 Hz
3000 Hz
4000 Hz
IPM based SDPT3 solver
2.11%
1.75%
1.03%
6.25 s
8.12 s
6.04 s
ADMM based algorithm
2.15%
2.47%
1.14%
0.98 s
1.00 s
1.00 s


## 5. Conclusions

In the existing atomic norm minimization based two-dimensional multiple-snapshot grid-free compressive beamforming, the positive semidefinite programming equivalent to the atomic norm minimization is solved by an off-the-peg IPM based solver. The solver trends to be time-consuming for large-dimensionality problems. In this paper, we present an alternative algorithm based on ADMM and compare it against the solver both with simulations and experimentally. Some interesting conclusions have been drawn. Firstly, as with the two-dimensional multiple-snapshot grid-free compressive beamforming using the IPM based solver, the one using our ADMM based algorithm also can estimate the DOAs and quantify the strengths of acoustic sources well. Compared with the former, the latter have the same and even higher DOA estimation accuracy, and slightly lower strength quantification accuracy. Secondly, compared with the IPM based solver, our ADMM based algorithm enjoys distinct efficiency advantage. Finally, the above conclusions hold up, whether a standard uniform rectangular array or a non-uniform array constituted by a small number of microphones is employed.



---

*Source: 1310805-2020-02-20.xml*