Snapshot Deficit Beamforming for Direction of Arrival Estimation by Compressive Sensing

Snapshot Deficit Beamforming for Direction of Arrival Estimation by Compressive Sensing

Sikha K V

PG Scholar,

Dept. of Electronics Engineering

Govt. Model Engineering College, Thrikkakkara Ernakulam, India

Sheena K V

Assistant Professor, Dept. of Computer Science

Adi Shankara Institute of Engineering & Technology, Kalady, Ernakulam, India

Abstract Beamforming techniques for Direction of Arrival (DOA) estimation have been a very promising research area for decades. Compressive Beamforming Technique based solutions give better resolution and robustness, compared to the traditional methods of beamforming. The basic idea of Compressive Sensing (CS) is that, the underlying sparse signal can be reconstructed from fewer samples than the Nyquist- Shannon theorem requires. In this paper various beamforming approaches has been discussed and is compared with the compressive beamforming technique. Beam patterns of traditional beamforming techniques such as Conventional Beamformer (CBF), Minimum Variance Distortionless Response (MVDR) Beamformer and Multiple Signal Classification (MUSIC) beamformer has been simulated for angular estimation and compared with the 1-minimization (1- svd) algorithm under various scenarios such as noisy conditions and single snapshot cases. Simulation results show that the compressive beamforming technique is able to estimate even the closely spaced targets under snapshot deficient cases where in the traditional approaches fails.

Keywords Beamforming, Direction of Arrival Estimation, Compressive Sensing, CBF, MVDR, MUSIC.

1. INTRODUCTION

   Beamforming is a signal processing technique for directional signal transmission and reception, used in conjunction with an array of sensors [1]. This is achieved by combining elements in an array in such a way that signals at particular angles experience constructive interference while others experience destructive interference. DOA estimation using beamforming has got variety of applications in astronomy, radar, sonar and seismology. The problem of DOA estimation is to gather information about the location of the sources and the possible number of sources in the presence of noise. There have been many approaches in the literature for solving the same, but most of these traditional approaches cannot be applied during noisy conditions or when the number of snapshot is less.

   The simplest approach for DOA estimation is the Conventional Delay-Sum Beamforming (CB) [2]. Even though CB is simple to implement, it has got very low angular resolution and large number of side lobes. The resolution limit of CB beamformers cannot be improved beyond a certain limit by increasing the SNR. Adaptive beamforming techniques are introduced later to overcome the drawbacks of CB

   and the number of snapshots. Under noisy conditions and snapshot deficient cases, these methods fail to estimate the sources accurately.

   In recent years, a new approach of DOA estimation has been proposed based on the compressive sensing (CS) technique [5]. The area of compressed sensing was initiated in 2006 by two ground breaking papers, namely [6] by Donoho and [7] by Candès, Romberg, and Tao. The key idea of compressed sensing is to recover a sparse signal from very few non-adaptive, linear measurements by convex optimization. Performance of CS technique in DOA estimation under number of sources and noise conditions is presented by Malioutov et al.[8] Robustness of CS in sound source localization using sensor arrays has been demonstrated in [9] with coherent arrivals and snapshot deficient case.

   In this paper the performance of compressive sensing technique using 1-minimization algorithm is demonstrated under noisy conditions and with single and multiple snapshot scenarios. Also the efficiency and resolution capability of the CS technique for angular estimation has been analyzed with the traditional approaches for various source locations and Signal to Noise Ratios (SNR).

   The remainder of this paper is organized as follows. A brief description of the three traditional approaches of beamforming is provided in section II. Section III describes the compressive sensing approach for DOA estimation for a single snapshot case. In section IV, CS approach using 1-svd is compared with the CB, MVDR and MUSIC techniques and their performance is evaluated. Finally the conclusion is summarized in Section V.

2. CLASSICAL BEAMFORMING APPROACHES

   A uniform linear array (ULA) having M number of sensors is considered for discussion. Sensors are equally spaced at a distance d, which is half the wavelength () of the received signal. Assume that the sources are in the far field of the sensor arrays. Consider a plane wave transmitted by the ith source is arriving at an angle i in which ranges from -900 to +900 with respected to the array axis. Let s be the transmitted signal such that s cN. The array steering vector at each of the sensor array due to the source i can be written as in [9]:

   (2 )()

   beamformer. MVDR (Capon) [3] and MUSIC beamformers

   () =

   (1)

   [4] fall under the adaptive type which has got improved estimation performance which largely depends upon the SNR

   where p is the vector having the sensor locations. The observation (measurement) vector at the M sensors denoted as y cM such that M < N in most of the practical situations.

   Steering Matrix A formed using the steering vectors in (1) can be written as:

   = [(1) . ()] (2)

   Solving W using the method of Lagrange multipliers, the weight vector can be determined as:

   R-1 A()

   Let the zero mean additive noise received as n, the measurement vector y can be written as:

   W= YY

   YY

   A()HR-1 A()

   (8)

   y=As +n (3)

   Using (8), the MVDR spatial spectrum can be expressed

   as:

   The idea of beamforming is to steer the array so as to scan across the angular region and measure the output power in each direction. Maximum output power is obtained in

   () = = 1

   () 1 ()

   (9)

   those direction which coincides with the DOA of the signal and thus angular estimate is calculated.

   Beamformers are generally classified as either data independent or statistically optimum beamformers, depending on how the weights are chosen [1]. In data independent beamformer, the weights do not depend on the array data and are chosen to present a specified response for all signal and interference scenarios. Conventional Beamformer (CB) is a data independent beamformer having a fixed weight which is same as the steering matrix A. The weights in a statistically optimum beamformer are chosen based on the statistics of the

   The angle corresponding to the peak value in the

   spectrum is the DOA estimate.

   C. MUSIC Beamformer

   MUSIC is a high resolution DOA estimation algorithm based on the eigen decomposition of the cross spectral matrix . Eigen vectors obtained are then separated into signal subspace and noise subspace. The orthogonality between the signal subspace and noise subspace are exploited in MUSIC to estimate the DOA. Power spectrum of MUSIC can be expressed as:

   array data to optimize the array response and the weights are determined using adaptive algorithms. MVDR and MUSIC beamformer are some of the statistically optimum beamformers.

   ( ) 1

   =

   ()()

   where corresponds to the noise Eigen vector.

3. CS APPROACH FOR DOA ESTIMATION

   (10)

   1. Conventional Beamformer

      CB is the simplest DOA estimation technique which is also known as the Delay-Sum Method. CB linearly combines the sensor output to enhance the signal at a particular look direction and attenuating the signal from undesired directions.

      The output power of CB can be expressed as:

      PCB ()=WHRYYW (4)

      where is the cross spectral matrix given as:

      Compressive Sensing (CS) is an innovative process in which sparse or compressible signals are captured and represented at a rate considerably below the Nyquist rate. Traditional approaches to data acquisition follow Shannon's Sampling theorem which states that a band limited signal can be perfectly reconstructed if and only if it is sampled at a rate at least twice its bandwidth. A signal is said to be sparse or compressible if it contains only very few non-zero coefficients or if it can be transformed into some other domain where the signal has only a fewer number of significant samples. In compressive sensing approach, the sparse signal is reconstructed using convex optimization

      = 1

      (5)

      process [10].

      =1

      and W is the weight vector which is same as A in case of CB. Hence can be rewritten as:

      () = ()() (6)

      CB is efficient even for single snapshot scenario, but it suffers from low resolution and large number of secondary lobes.

   2. MVDR Beamformer

   The MVDR is an adaptive beamforming algorithm also known as Capon Beamformer. The basic principle of MVDR

   Compressive Sensing is possible because of two principles say sparsity and incoherence [11]. Compressive Sensing exploits the fact that many natural signals are sparse or compressible which implies that they have short representations when expressed in the proper basis . If a signal can be expressed as a linear combination of only K basis vectors, then the signal is said to be K-sparse (K nonzero coefficients). Incoherence deals with the idea that objects having a sparse representation in must be spread out in the domain in its acquired domain. Consider two bases and . The coherence between the two bases is given by [12]:

   is to minimize the output power in such a way that the gain should be unity along the look direction. Cost function can be denoted as:

   (, ) = 1,

   |

   (11)

   min

   = 1 (7)

   where N is the length of the original signal, k and j are the kth column and jth column of and respectively. The coherence is a measure of the largest correlation between the

   basis vectors of and and it always lies in the interval (1, ).

   In Compressed Sensing, the original N x 1 signal x is multiplied by a M x N measurement matrix , to obtain the M (M<N) compressed measurements. This can be expressed mathematically as:

   = = = (12)

   The measurement matrix should be incoherent with the sparsifying basis for achieving compressed sensing and reconstruction. The value of M required is considerably smaller than N, hence the name compressed sensing.

   1. Reconstruction Process

      The reconstruction process considers the problem of recovering an object x from its linear measurements = . The signal reconstruction algorithm must take the M measurements in the vector y, the measurement matrix and the basis and reconstruct the N length signal x or equivalently its sparse coefficient vector s. The M linear measurements can be written as (12)

      = (13)

      where = .

      The transform matrix has fewer rows than columns i.e. M

      < N which implies that the number of equations is less than the number of unknowns. Hence there are infinitely many solutions () that satisfy = which is an ill-posed problem. This it turns out to be an optimization problem and the solution can be found by applying constraints.

      1. Minimum 2 norm reconstruction: The classical approach to find the ill-posed inverse problems is to find the with the smallest 2 (energy) by solving

         s = arg min s 2 subject to y = s (14)

         The solution to (14) is the least squares solution which has a tendency to spread the energy among a large number of entries of s, resulting in a non-sparse solution.

      2. Minimum 0 norm reconstruction: The 0 norm counts the number of non-zero entries in s. The optimization problem can be written as

         s = arg min s 0 subject to y = s (15)

         Solving (15) is numerically unstable and NP complete, and hence not used commonly.

      3. Minimum 1 norm reconstruction: The optimization problem can be written as

         s = arg min s 1 subject to y = s (16)

         This problem can exactly recover K sparse signals and closely approximate compressible signals with high probability [12]. 1 norm minimization is a convex

         optimization problem that conveniently reduces to a linear program known as basis pursuit whose computational complexity is about O(N3) which makes the optimization problem computationally tractable.

   2. Formulation of DOA Estimation Problem using CS Approach

   Consider single snapshot case with T=1. In DOA estimation problem, the goal is to find . To cast this problem as a sparse representation problem, an over-complete representation A in terms of all possible source locations is introduced. Let {1, 2 N} be the sampling grid of all source locations of interest. The number of potential source locations N will be much greater than the number of sources K or even the number of sensors M. Steering Matrix A can be constructed using the steering vectors at each source locations as its columns

   = [(1) (2) . ()] (17)

   As explained in (3), the measurement vector y can be written as y = As + n. Now the signal model in (3) can be rewritten as a CS problem [13]

   = = A + n (18)

   where of size M x N is constructed by randomly selecting M rows from an identity matrix of size N x N. As a result, the compression procedure is performing a random sub- sampling/selection of the antenna elements of the array. Now the number of sensor elements needed is greatly reduced when compared to the traditional DOA estimation methods and therefore (18) can be written as y = As + n.

   As in numerous nonparametric source localization techniques, the approach forms an estimate of the signal energy as a function of hypothesized source location, which ideally contains dominant peaks at the true source locations. The central assumption is that the sources can be viewed as point sources, and their number is small. With this assumption, the underlying spatial spectrum is sparse (i.e., s has only a few nonzero elements), and we can solve this inverse problem via regularizing it to favor sparse signal fields using the 1-methodology. The appropriate objective function for the problem is

   2

   s = min y As 2 + s 1 (19)

   where is the regularization parameter. 1-minimization problem (1-SVD) is solved using cvx toolbox [14] which uses interior point method to solve the convex optimization problem.

4. SIMULATION RESULTS

   A uniform linear array of M=10 sensors separated by half a wavelength of the narrowband source signals is considered for the experiment. Three narrowband sources (K=3) impinge on this array from distinct DOAs. Performance of CB, MVDR and MUISC beamformers is compared with L1- SVD for three sources kept at various angles for snapshots T=30 and T=1(Singe-Snapshot) with a uniform sampling grid of 10(N=181).

   Fig. 1 shows the beam pattern for CB, MVDR, MUSIC and L1-SVD for three equal strength sources which are located at farther apart (-300, 200and 600) with a uniform linear array of M=10 sensors, SNR=15dB and T=30. As seen from the plot, all the beamforming techniques are able to resolve the three sources, but the 3dB beam width is lesser for L1-SVD compared to the other approaches. MVDR and MUSIC gives better performance compared t CB. When the number of snapshots and SNR is high, all the beamforming approaches mentioned here are performing well.

   Fig. 1 DOA estimation of three equal strength sources located at -300, 200and 600 with a ULA of M=10 sensors, SNR=15dB and T=30

   Fig. 2 compares the performance of CB, MVDR, MUSIC and L1-SVD when the three sources are located at 230, 330 and 430 and SNR = 15dB. The CB beamformer is unable to resolve the three sources whereas Capon, MUSIC and L1- SVD resolve the three sources. Conventional beamformers can resolve the sources only when the source locations are sufficiently apart.

   Fig. 2 DOA estimation of three equal strength sources located at 230, 330 and 430 with a ULA of M=10 sensors, SNR=15dB and T=30

   Performance of DOA estimation algorithm largely depends on the resolution capability of the sources when they are placed at close proximity. Fig. 3 compares the performance of the above mentioned beamformers when the sources are located with DOAs 230, 280, 330 and SNR = 15dB. L1-SVD can resolve the two sources whereas CB, MVDR and MUSIC

   is unable to resolve the three closely spaced sources as evident from the figure, which shows the superior resolution of compressive sensing based beamformers.

   .

   Fig. 3 DOA estimation of three equal strength sources located at 230, 280and 330 with a ULA of M=10 sensors, SNR=15dB and T=30

   Fig. 4 shows the performance of the four beamformers when the three sources with DOAs 330, 430 and 530, T=30 and SNR= -5dB. It is clear from the figure that only L1-SVD is able to resolve the two sources at this SNR. The other three methods are unable to resolve the sources during noisy conditions.

   Fig. 4 DOA estimation of three equal strength sources located at 230, 330 and 430 with a ULA of M=10 sensors, SNR=-5dB and T=30

   Now consider the case for single snapshot (T=1). MVDR and MUSIC beamformers performance degrades when the snapshots are less as the cross spectral matrix becomes rank deficient. Hence for single snapshot scenario, CB beamformer is compared with L1-SVD when the three sources are located at 230, 280, 330 and SNR = 25dB. Even for a single snapshot case, L1-SVD is able to resolve the closely spaced sources with much accuracy as seen from the fig. 5.

   Fig. 5 DOA estimation of three equal strength sources located at 230, 280 and 330 with a ULA of M=10 sensors, SNR=25dB and T=1

   From the above simulation results, it is evident that L1-SVD based on compressive sensing approach outperforms the traditional methods of beamforming. Conventional Beamformer fails to resolve the closely spaced target under any conditions. MVDR and MUSIC beamformer has shown better performance compared to conventional beamformers under high SNR, and when the number of snapshots is large. But the performance of these two algorithms degrades during noisy conditions or when the snapshots are less. In all the scenarios mentioned above, L1-SVD has shown superior resolution even for closely spaced sources.

5. CONCLUSION

In this paper DOA estimation using L1-SVD based on compressive sensing approach has been analyzed and its performance is compared with the traditional beamforming approaches for single snapshot and multiple snapshot scenarios. Simulation results indicate that the Compressive beamformers have superior resolution even for a single snapshot data in comparison with the CBF, MVDR and

MUSIC beamformers. Also MVDR and MUSIC need multiple snapshots whereas the L1-SVD algorithm is able to resolve closely spaced sources for both multiple and single snapshot scenarios. It is found to have good resolving capability even at low SNR.

REFERENCES

1. Barry D. Van and Kevin M. Buckley, Beamforming: A versatile approach to spatial filtering, IEEE ASSP Magazine, vol. 5, no. 2, pp. 4-24, Apr. 1988.

2. H. Van Trees, Optimum Array Processing (Detection, Estimation and Modulation Theory, Part IV), New York: Wiley-Interscience, 2002.

3. J. Capon, High-resolution frequency-wavenumber spectrum analysis, Proc. IEEE, vol. 57, pp. 1408-1418, Aug 1969.

4. RO. Schmidt, Multiple emitter location and signal parameter estimation, IEEE Trans. Antennas Propagation, vol. 34, pp. 276-280 Mar 1986.

5. R. Baraniuk, Compressive sensing, IEEE Signal Processing Magazine, vol. 24(4), pp. 118-120, 2007.

6. D. L. Donoho Compressed sensing, IEEE Trans. Inform. Theory, vol. 52, pp. 1289-1306, Apr. 2006.

7. E. J Candès, J. Romberg, and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete Fourier information, IEEE Trans. Inform. Theory, vol. 52, pp. 489-509, Apr. 2006.

8. D. Malioutov, M. Cetin, and A. S. Willsky, A sparse signal reconstruction perspective for source localization with sensor arrays," IEEE Trans. Signal Process, vol. 53, no. 8, pp. 3010-3022, Aug. 2005.

9. A. Xenaki and K. Mosegaard, Compressive beamforming, J. Acoust.

   Soc. Am., vol. 136, no. 1, pp. 4-24, July 2014

10. S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, New York, 2004.

11. E. J. Candès and M. B. Wakin, An Introduction To Compressive Sampling, IEEE SP Magazine, vol. 5, no. 2, pp. 21-30, Mar. 2008.

12. Wu Sheng Lu, Compressed Sensing and sparse Signal Processing, University of Victoria, Canada via Convex Programming, Oct. 2005.

13. Ying Wang, Geert Leus, Ashish Pandharipande , "Direction Estimation Using Compressive Sampling Array Processing", in IEEE/SP 15th work-shop on SSP, pp 626-629 , 2009

14. M. Grant and S. Boyd, CVX: MATLAB software for disciplined convex programming, version 2.0 beta, http://cvxr.com/cvx.