{'fraction_non_alphanumeric': 0.03892335401240744, 'fraction_numerical': 0.00825495297178307, 'mean_word_length': 4.608585858585859, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Fault Tolerant Matrix Pencil Method for Direction of Arrival Estimation

Continuing to estimate the Direction-of-arrival (DOA) of the signals impinging on the antenna array, even when a few elements of the underlying Uniform Linear Antenna Array (ULA) fail to work will be of practical interest in RADAR, SONAR and Wireless Radio Communication Systems. This paper proposes a new technique to estimate the DOAs when a few elements are malfunctioning. The technique combines Singular Value Thresholding (SVT) based Matrix Completion (MC) procedure with the Direct Data Domain (D^3) based Matrix Pencil (MP) Method. When the element failure is observed, first, the MC is performed to recover the missing data from failed elements, and then the MP method is used to estimate the DOAs. We also, propose a very simple technique to detect the location of elements failed, which is required to perform MC procedure. We provide simulation studies to demonstrate the performance and usefulness of the proposed technique. The results indicate a better performance, of the proposed DOA estimation scheme under different antenna failure scenarios.


INTRODUCTION
Antenna Array signal processing and estimation of Direction-of-Arrival (DOA) parameter of the received signal of interest, is of practical interest in RADAR, SONAR and wireless radio communication systems. There are many DOA estimation algorithms, these algorithms can be classified into three broad categories; Maximum Likelihood approach, subspace based approach and Direct Data Domain (D 3 ) approach [1] [2]. The Maximum likelihood (ML) method is optimal in the maximum likelihood sense [1], but requires accurate initializations to ensure global minimum and moreover, the method is highly computationally intensive. Expectation Maximization (EM) methods [3] [4] for ML approach reduces the computational requirements. However, the accurate initializations are still needed.
The subspace based algorithms like Multiple Signal Classification (MUSIC) [5] and Estimation of Signal Parameters via Rotational Invariance Technique (ESPRIT) [6], overcome the high computational requirement by exploiting the low rank structure of the noise free signal. These methods rely on the statistical properties of the data, and thus, need a sufficient large number of samples for accurate estimation. Furthermore, when the signal sources are highly correlated, the correlation matrix of the data tends to lose rank. This leads to the performance degradation of the DOA estimation algorithms based on the subspace approach. However, preprocessing scheme called spatial smoothing [7] is used to estimate the DOAs of the received highly correlated signal sources. Furthermore, there are recent algorithms derived for Nonuniform Antenna Arrays based on the above approaches [8] [9] and Ubiquitous Positioning [10].
Direct Data Domain (D 3 ) based algorithm namely, the Matrix Pencil (MP) Method [11] [12] is a practically attractive algorithm. The algorithm needs only one snapshot to estimate the DOAs and further, there is no need to form the correlation matrix. Correlated signal sources have no significant impact on the performance. The technique can also be applied to Nonuniform Antenna Array (NUA) without much modification [13]. However, the algorithm is sensitive to perturbation and measurement errors, resulting in a low Signal-to-Noise (SNR) threshold.
It is a common practice to use large number of elements in an antenna array, and hence, failure of a few elements will be disastrous in critical applications. Replacing the malfunctioning antenna array elements will be time consuming and costly. To deal with such problems, redundant antenna array is employed, which is wastage of the hardware and is a costly affair. The failure of elements results in incomplete data observations or sparse data observations. In such cases, conventional DOA estimation algorithms will have a problem to estimate the DOAs, because the structure and the statistical properties of the data cannot be found directly. If it is possible to reconstruct the complete data from the observed incomplete data, we can continue to estimate the DOA, from the ULA, where a few elements have failed to work, this will avoid redundant hardware.
For handling sensor failures, many modifications for conventional methods are proposed [14] [15]. Larson and Stoica [14], proposed a technique for estimating the correlation matrix of the incomplete data using the ML approach and has shown improvement in MUSIC for handling sensor failure. However, it increases the complexity. A method for DOA estimator to handle sensor failure based on neural network approach is proposed by Vigneshwaran et al [15]. The technique can handle correlated signal sources, avoids the Eigen decomposition. The drawback with these techniques is initialization of the network, and is performed by trial and error method. The authors in [16] proposed a DOA estimation technique by combining the EM algorithm with the MP method. The EM algorithm expects the missing data and maximizes the performance using the MP method. However, the method suffers from the drawback of increased complexity and requires good initialization.
Matrix Completion (MC) [17] is a process of completing the data matrix from incomplete data matrix. This problem arises in a variety of situations like system identification [18], collaborative filtering [19], DOA estimation [20], etc. The singular Value Threshold (SVT) algorithm proposed by Candes [21], can exactly recover the missing data from the knowledge of the location of the data elements in the matrix by solving a simple convex optimization problem [22], i.e., minimizing the nuclear norm, which is the sum of singular values of the data matrix.
This paper proposes a technique to deal with problem of DOA estimation when a few elements of the antenna array fail. The technique uses two procedures when the element failure is observed at time instance ‫.'ݐ'‬ The first procedure, is to form the complete data matrix from the incomplete data matrix generated by the faulty ULA, using the SVT based MC algorithm. Later in the second procedure, DOAs are estimated directly from the obtained complete data using the MP method. The MC procedure first forms the location matrix. The location matrix describes the location of the elements that are functioning. The location matrix is formed by finding the distance between the samples at time instance ‫ݐ'‬ − 1' and at time instance ‫.'ݐ'‬ At ‫ݐ'‬ − 1' all the elements are assumed to be working. The information from the location matrix, forms one of the input to the MC procedure using SVT.
The novelty in our algorithm is therefore present only when element malfunctioning is observed. The SNR and RMSE performance of the algorithm is evaluated in terms of varying percentage of element failures. The algorithm is compared with the standard MP Method. For the proposed technique, we consider the faulty ULA, whereas for the latter all the elements are assumed to be functioning.
The rest of the paper is organized as follows. The following section discusses the signal model for DOA estimation. In section 3, proposed technique is discussed followed by simulation results in section 4. Finally, conclusions are drawn in section 5. The DOA estimation problem is to estimate the directions of plane wave incident on the antenna array in presence of errors. The problem can be looked as parameter estimation. We here, mainly introduce the model of a DOA estimator. Consider a Uniform Linear Antenna Array (ULA) of ‫'ܯ'‬ elements as shown in Figure 1. The elements are spaced equidistant '݀' equal to 'ߣ 2 ⁄ ' from each other, where, 'ߣ' is the wavelength of the signal received. The plane waves arrive at the array from direction 'ߠ ' off the array broadside. The angle ߠ is called direction-of-arrival (DOA) of the received signal. Let ܰ, narrowband signals ‫ݏ‬ ଵ ሺ‫ݐ‬ሻ, ‫ݏ‬ ଶ ሺ‫ݐ‬ሻ, ⋯ , ‫ݏ‬ ே ሺ‫ݐ‬ሻ impinge on the array with DOAs ߠ , ݅ = 0,1,2, ⋯ ܰ − 1. Therefore, the signal x m received at the m th element at time instance 't' is

SIGNAL MODEL
Eq. (1) can be written in a compact form as Where ܶ is the number of snapshots, considering only one snapshot i.e. T=1, ‫ܛ‬ሺ‫ݐ‬ሻ is ‫ܯ‬ × 1 vector of signal sources, ‫ܟ‬ሺ‫ݐ‬ሻ is ‫ܯ‬ × 1 noise matrix which is assumed to be Additive White Gaussian noise (AWGN), ‫ۯ‬ሺߠሻ is the ‫ܯ‬ × ܰ array steering matrix and ‫ܠ‬ሺ‫ݐ‬ሻ is the ‫ܯ‬ × 1 received signal vector. Assume that at random locations a few elements are malfunctioning. In such case, the outputs from these elements are not available, resulting in the incomplete data vector ‫ܠ‬ ᇱ ሺ‫ݐ‬ሻ of size ‫ܯ‬ ᇱ × 1, where ‫ܯ‬ ᇱ is the number of elements functioning.
The objective in this paper is to continue the DOA estimation of ܰ source signals even when a few elements of a given ULA are malfunctioning.

PROPOSED DOA ESTIMATION ALGORITHM
The various steps of the proposed algorithm is described in Table 1 and illustrated in Figure 2. If there are element failures, we follow three important steps. First, we form the location matrix of the elements that are functioning. In second step, the information from the location matrix is  Apply MP method to estimate the DOA used to form the complete data matrix using the SVT algorithm [21] (MC Procedure) and once the complete data is recovered, in the third step, the MP method is used to estimate the DOA. In the following section, the details of these steps are discussed.

Array element location matrix
The matrix completion using the SVT algorithm requires the knowledge of the indices of the observed entries in the data matrix, which are the location of the functioning elements in the ULA. We propose a simple technique to locate the location of the working elements using previous sample and the present sample and comparing them to detect whether the particular element has failed or not. The algorithm to form a location matrix Ω is described in Table 2. and is based on finding the distance between the respective samples.

Algorithm for DOA estimation
At time instance ‫,ݐ‬ a few of the elements will fail to work, resulting in incomplete data. To recover the complete data from the observed incomplete data which resulted from failure of a few elements, we apply the SVT matrix completion algorithm given in Table 3.
Recovering a matrix from a sample of its entries is known as the matrix completion problem. In [16] [20], Candes and Recht, proved that the most of the low rank 'r' matrices can be recovered from its partial set by solving a simple convex optimization problem.
Where, ‫‖ܠ‖‬ * is called the nuclear norm and is defined as the sum of its singular values, ‫ܠ‬ is the matrix to recovered, Ω is the set of indices's of the sampled entries, P ஐ ሺ. ሻ is a masking operator which selects the entries of ‫ܠ‬ that are within Ω and ‫ܠ‬ ᇱ is the collected partial samples. Provided that the number of samples obey ‫ܯ‬ ≥ ‫ܯܥ‬ ଵ.ଶ ‫ܯ݈݃ݎ‬ for some positive numerical constant ‫.ܥ‬ The SVT algorithm developed by Cai, Candes and Shen in [21] is used to solve the norm minimization problem in (3). However, the entries must be selected randomly and we cannot hope to complete the matrix if some of the singular vectors of the matrix are extremely sparse.
If the singular vectors of ‫ܠ‬ ᇱ are sufficiently spread, then there is a unique low rank matrix which is consistent with the observed entries. In such cases, one could, in principle, recover the unknown matrix by solving Unfortunately this is NP-hard. A popular alternative to the NP hard problem is the convex relation [17] given in (3) where, nuclear norm is the tightest convex relation of the NP-hard rank minimization problem.
The inputs to the SVT algorithm are, a parameter ߬, step size ߜ, sampled set Ω, sampled entries ‫ܠ‬ሺΩሻ and initializing vector ‫܇‬ = 0. The algorithm is Repeat steps in (5) until convergence. shrink(.) is a nonlinear function which applies soft thresholding rule at level τ, to the singular values of the input matrix. The key property here is that for large values of τ, the sequence ሼ‫ܠ‬ ሽ converges to a solution which very nearly minimizes (3). Hence, at each step, one needs to compute only atmost one singular value decomposition and perform a few elementary matrix additions.
For shrinkage operator, consider the SVD of ‫ܠ‬ of rank r, ‫ܠ‬ = ‫܄܁܃‬ ு , ‫܁‬ = ݀݅ܽ݃ሺሼߪ ሽ, 1 < ݅ < ‫ݎ‬ሻ Where ‫܃‬ and ‫܄‬ are the right and the left singular vectors and ‫܁‬ is the singular value matrix. For each ߬ ≥ 0, a soft thresholding operator ‫ܦ‬ ఛ defined as follows Where ሺ * ሻ ା , is the positive part of the *. In other words, this operator simply applies the soft thresholding rule to the singular values of ‫,ܠ‬ effectively shrinking these towards zero.
The problem of estimating the DOA from incomplete observations in our case can be written as ‫ܠ‬ ᇱ , is the data collected from the working elements and Ω is the location matrix whose entries are the location of the elements that are working in a ULA. The operator ‫ܠ‬ሺΩሻ represents the data collected from only the working elements. Once the complete data is recovered, MP method is followed to estimate the DOAs [11] [12]. The SVT algorithm for recovering the missing data is shown in Table 3.
For MP method, the signal model given in (1) is rewritten as, Where, For simplicity the index t is eliminated. The MP method for noiseless data the algorithm begins by choosing a parameter ‫,ܮ‬ known as pencil parameter. A good choice of this parameter is in between M/3 and 2M/3 [12].
Now we construct a matrix ‫܆‬ from the data samples of (9) The two matrices ‫܆‬ and ‫܆‬ are defined as The matrix pencil for two matrices ‫܆‬ and ‫܆‬ are defined as the linear combination of the two matrices with scalar β described by In the absence of noise, it is easy to verify that ‫܆‬ and ‫܆‬ can be decomposed in to ‫܆‬ = ‫۰܈ۯ‬ and ‫܆‬ = ‫۰ۯ‬ such that provided that the pencil is of rank ܰ. Under this condition each value of ߚ = ‫ݖ‬ is a rank reducing number of the pencil. However if ‫ܮ‬ is not within the above range, then none of ‫ݖ‬ 's are a rank reducing number of a matrix pencil. This implies that the values of ‫ݖ‬ 's are the generalized eigenvalues of the matrix pair ‫܆[‬ ‫܆‬ ]. Furthermore, it can be shown that the generalized eigenvalues of ‫܆‬ − β‫܆‬ can be found from the non-zero eigenvalue of ‫܆‬ ற ‫܆‬ where † is the Moore-Penrose pseudoinverse. Finally the DOAs are estimated by using equation.
Where, c is the propagation velocity. In the absence of noise, the pencil will have rank ܰ, which is not satisfied when the signal is corrupted by noise. To mitigate the effect of noise Total Least Squares (TLS) [23] approach is applied by taking Singular Value Decomposition (SVD) of ‫܆‬ in (11). This method is known as Total Least Squares -Matrix pencil (TLS-MP) method.
We start with taking the SVD of ‫܆‬ in (11). Only ܰ of singular values of this matrix corresponds to signals, while the rest corresponds to the noise. We generate a new filtered version of the data matrix.
Where, ൣ‫܃‬ ሖ ൧ are the first ܰ left singular vectors, ൣ‫܄‬ ሖ ൧ are the first ܰ right singular vectors and ൣ ሖ ൧ are the first ܰ singular values. Now ‫܆‬ is replaced by ‫܆‬ ሖ in (11). The above steps are followed to estimate the DOA of the received signals.

SIMULATION RESULTS
In this section, we examine the performance of the proposed DOA estimation technique using several simulations and compare with the standard TLS-MP method for various noisy conditions and elements failure scenario. The simulation is carried on Intel Core 2 Duo, 2.8 GHz processor, 2 Mb RAM, running on Windows XP SP2 16 bit operating system. We consider a ULA of 100 elements, the spacing between the elements is ߣ 2 ⁄ , where, ߣ is the wavelength of the signal of interest. The signals are assumed to be impinging from the direction ߠ off the broadside of the array.
The signals are assumed to be complex exponential sequence given by Where ߶ is the random phase uniformly varying between ൣ-ߨ, ߨ൧. The SNR in dB at each element is defined as Where ߪ ௦ , is the signal power and ߪ ௪ , is the noise power. The Root Mean Square Error is defined as Where, ߠ is actual DOA and ߠ is the estimated values. The failure of elements is considered to be at random locations. Six signals of equal magnitude are assumed to be impinging on the array from the directions ߠ = ሼ0 , 5 , 10 , 15 , 20 , 30 ሽ.
In our first example, we compare the TLS-MP method and the proposed modified MP method for functioning ULA. The SNR in this case is taken as 24 dB, the array size is 100 elements. It can be observed form Table 4, the proposed technique performs better than the TLS-MP method. The improvement is due to iteratively using the SVD. However, the improvement is obtained at the cost of slightly increased complexity.  Figure 3, we observe that the performance of the proposed technique with 5 faulty elements is comparable with the actual MP method, where all the elements are functioning. The results are also tabulated in Table 5, for the SNR of 24 dB.
In our third example, we consider the performance of the algorithm for varying number of working elements. The numbers of elements that are working in each experiment are 95, 90, 85, 80 and 70 elements respectively and the results are plotted in RMSE plot, shown in Figure 4. It is observed that the algorithm is consistent in its performance until 80 elements are functioning. Furthermore, when only 70 elements are functioning the performance degrades. The time taken to perform the matrix completion is observed to be 0.48 seconds and the error in reconstruction is 10 -2 , using 50 iterations for the matrix completion

Computational complexity
The computational complexity of the algorithms is shown in Table 6. It is observed that even though the proposed technique has more complexity, the tradeoff is that on the cost of computations, we can save the use of redundant hardware when there is a failure of elements. The increase in the complexity when compared with the TLS-MP method is only due to the iterative application of SVD in MC procedure. The computational complexity in SVT is just the number of iterations multiplied by the complexity of finding the largest singular vectors.

CONCLUSION
Failure of a few elements in the antenna array is not tolerated in DOA estimation applications. This paper discusses a technique to estimate the DOAs, when a few elements in the ULA fail to work. The technique uses a preprocessing scheme namely, singular value thresholding based matrix completion procedure for recovering the missing data from the failed elements. Later the MP method is employed to estimate the DOA from the recovered complete data matrix. We have also proposed a very simple technique to know the location of the elements that are working, which is required for matrix completion procedure. We evaluated the performance of the proposed modified MP method under various noisy conditions and element failure scenarios. Before considering the performance evaluation for the faulty ULA, from the simulation results, the algorithm is observed to perform better than the conventional TLS-MP method. When the elements are failed the proposed algorithms continue to estimate the DOAs until certain number of elements malfunctioning. When a large number of elements have failed the performance of the algorithm degrades. The advantage of the proposed modified MP method is usage of redundant hardware is avoided with increase in the complexity of the algorithm due to the repetitive usage of SVD. Further work has to be done to build more robust DOA estimation algorithms to tolerate the element failure, as in many applications, all the elements in the underlying ULA can rarely be expected to function properly. Direct data domain methods like Matrix Pencil method and matrix completion from the convex optimization theory offer elegant possibilities for developing robust DOA estimation algorithms.