Combining Self-Organizing Map and Lipschitz Condition for Estimation in Direction of Arrival ()
1. Introduction
Array signal processing is an important branch in the field of modern signal processing, one of the important issues in array signal processing is the estimation of the direction of arrival (DOA). In recent years, many different DOA estimation algorithms have been proposed, including subspace decomposition, sparse decomposition, maximum likelihood parameter estimation, and mapping approximation, etc.
Subspace decomposition i.e. eigenspace spectral decomposition is an important method for estimation of DOA. It includes several algorithms represented by multiple signal classification algorithm (MUSIC) [1] and Estimation of Signal Parameters via Rotational Invariance Technique (ESPRIT) [2] . In the last few years, many algorithms based on these two algorithms have been proposed [3] [4] [5] [6] . Such as short-time fourier transform-based MUSIC (STFT-MUSIC) [7] , real-valued root-MUSIC (RV-root-MUSIC) [8] , time-frequency spatial spectral decom-position [9] , discrete fourier transform ESPRIT (DFT-ESPRIT) [10] , Time-Frequency Multi-Invariance ESPRIT (t-f MI-ESPRIT) [11] , neuro-evolution of augmenting topologies MUSIC (RNEAT-MUSIC) [12] , and combining ESPRIT with MUSIC [13] , etc. These algorithms mainly decompose the signal in observation space into signal subspace and noise subspace using the spectral decomposition of covariance array, and obtain the spectral function based on the property of orthogonality of the two, thus predicting the DOA. The spectral decomposition operation involves the covariance array, which makes this type of algorithm quite computationally intensive, thus is limited from the feasibility of real-time applications.
The sparse representation (SR) and compressive sensing (CS) have become hot spots of research on DOA estimation recently [14] [15] . The theory is originally proposed by Donoho [16] and Candes [17] in 2006. Following that, many DOA estimation algorithms based on sparse algorithms have been proposed, such as matching pursuit (MP) [18] , orchogonal matching pursuit (OMP) [19] , etc. The initial sparse decomposition method is limited by the density size of the grid, and to solve this limitation, many sparse decomposition methods on off-grid have been proposed [20] [21] [22] . However, this class of algorithms still suffers from practical problems such as large computational effort.
Maximum likelihood parameter estimation uses Gaussian white noise as the noise background, and the maximum value of the likelihood function as the goal for the optimal solution for DOA estimation. The maximum likelihood estimation method is classified into deterministic maximum likelihood (DML) [23] and stochastic maximum likelihood (SML) [24] . Many studies are still being focused on the maximum likelihood estimation algorithm [25] [26] . This method is superior to the subspace decomposition method in the case of low signal-to-noise ratio and small number of snapshots. While the solving process requires a nonlinear multidimensional search, so it suffers from practical problems of high computational effort.
Another type of DOA estimation method is the mapping approximation method. It aims to establish a mapping relationship between the signal observation space and the DOA space, and is typically represented by various neural networks [27] [28] , among them the Radial Basis Function Neural Network (RBFNN) [29] and Convolutional Neural Network (CNN) [30] [31] are the representatives. By establishing a nonlinear mapping between the received signal feature vector and the DOA space through a neural network, such methods avoid complex calculations with spectral decomposition. However, there are limitations to the training data. To get the exact mapping from the signal observation space to the DOA space is a difficult task, so a new solution idea is proposed and initially discussed in the issues of DOA estimation of communication signals [32] . Further, the method is applied to hydroacoustic DOA estimation under a uniform line array [33] . This method discretizes the continuous mapping by finding the mapping relationship between the topological ordering of the array signal time difference of arrival (TDOA) feature space and the topological ordering of the DOA space, so as to build a dictionary with look-up function for estimation of direction of arrival [33] . While it only investigates TDOA features under a specific uniform linear array and fails to provide further discussion on the topological ordering of TDOA features under other types of arrays as well as random arrays, the established mapping matching principles are rough and the estimation results are overly dependent on the density of the training grid.
According to Lipschitz condition, the topological order of the time difference of arrival (TDOA) or distance difference of arrival (DDOA) and the DOA of signals are similar, therefore we propose a discrete DOA estimation system by setting up a two-level SOM neural network. The SOM performs a nonlinear mapping between TDOA and the DOA of signals. It is shown that the system has the advantage of high accuracy, robustness, and implementations. The rest of this paper are organized as following. In section 2, we introduce the arbitrarily distributed sensor array data model, and then we introduce the structure of Kohonen self-organizing map, set up a two-level SOM neural network for the estimation of DOA, and analyze the topological order relationship between DDOA vectors and DOAs in Section 3. In section 4, a simulation study of the proposed system is implemented, the accuracy and feasibility of the proposed method is discussed. Finally, we discuss and conclude the paper in Section 4 and 5.
2. Background Material
Assume that there is a sensor array of M sensors in the 2-D plane as shown in Figure 1, the distance between each two adjacent sensors i and i + 1 is
, and
Figure 1. Sensor array and signal source.
,
. (1)
where
is the wave length of sound source, and
, where c is the speed of sound wave propagation in a medium, f is the frequency of sound source. Establish rectangular coordinate system, let sensor 1 and M placed on the x-axis, and sensor 1 located at the origin. Suppose that there is a single sound source located at point
in the plane, and the location of sensor i is
.
In this paper, the direction of arrival to estimated is the inclination angle of point
respect to
, write as
(2)
Let the observations of sensor i be
. (3)
where
is the signal radiating from the signal source,
is the time delay to sensor i, and
is the additive noise. We assume that the signal and noises are mutually independent and the noises distribution is Gaussian with zero means, variance of
. The distance from signal source
to sensor
is written as
. (4)
And the distance difference to sensor i and i + 1 is
(5)
Then the time difference between sensor i and i + 1 is
. (6)
Thus, TDOA vector noise free is
, (7)
where
is the distance difference vector, and the TDOA vector will be
. (8)
where
represents the noise, which is delay estimation error, and
,
,
. (9)
The central question is to set up a map
, from TDOA vector
to DOA
, i.e.
, (10)
And the estimated parameters
is to approximate the function
. (11)
where
denotes an estimation of F using neural network.
3. Data Preprocessing by Self-Organizing Map
3.1. Self-Organizing Map
In this paper, we set up a Kohonen self-organizing map, which is also called Kohonen feature map. SOM is a feed-forward neural network, which is an unsupervised and competitive learning algorithm [16] . SOM represent high-dimensional input data as low-dimensional (one- or two-dimensional) data, and keep the same topological order as original data do, thus the features of the input data will be visualizing in an order fashion. The other hand, SOM can be used for feature extraction and dimensionality reduction, too.
A SOM network is composed of two layers: input layer and output layer (competitive layer). As shown in Figure 2, there are identical numbers of input layer node to the input vector dimensions, the neurons of competitive layer are usually placed into a two-dimensional grid, which is usually arranged as rectangle or hexagonal. The variable weight connects the input nodes and output node i is written as
, where m is the dimension of the input vector.
Kohonen SOM’s training principle is as follows. When an input sample vector is put into the network, the Euclidean distance between neurons weights
and the input sample vector are calculated, the one who has the minimum distance will be the winning neuron. Then adjust the weights of the winning neuron and its neighboring neurons, to make them similar to the input sample vector. As a result, all neurons’ connected weights have a certain distribution by the training process.
The network training process consists of four steps:
Figure 2. Structure of Kohonen self-organizing map.
Step 1: Initialize the network. Assume that there are N sample vectors
, normalize as
. (12)
where
. And then give neuron weights
equal to part of the normalized input vector as the initial weights of the network:
. (13)
Step2: Calculate the Euclidean distance between the normalized input vector
and each neuron weight
, find the winning neuron
subject to
. (14)
where
. (15)
Step 3: Adjust the weights of winning neuron c. Adjust nodes i in neighborhood of winning node c, the adjustment is linear combination of input vector and current weight vector:
,
. (16)
where
is a decreasing learning rate function of training epoch t, and
is the neighborhood kernel with Gaussian function:
. (17)
where r is the location of neurons on the two-dimensional grids, and
is the smoothing factor.
Step 4: Repeat steps 2 and 3 until the convergence criterion is satisfied.
3.2. Lipschitz Condition
If function
satisfy the following conditions on interval
:
1) When
,
, i.e.,
;
2) For any
,
.
It is said that function
satisfies Lipschitz condition on
, and
is Lipschitz continuity, The least constant L for which the previous inequality holds, is called the Lipschitz constant of
. Lipschitz continuity is a more smoothness condition than uniform continuity. Intuitively, Lipschitz continuous function limits the speed of function change. The slope of a function that meets Lipschitz condition must be less than a real Lipschitz constant, which depends on function
.
3.3. DOA Estimation with SOM
In this paper, N points in the two-dimensional plane are used to generate training data. The N points represent the locations of N sound sources, each point corresponds to a distance difference vector
(which is given as Equation (7)) respect to the sensor array. Consider that there is only a constant factor c difference between the DOA vectors
and the distance difference vector
, we use
as an alternative input vector to
as training samples in this issue.
A two-level SOM neural network is set up. As shown in Figure 3, the first level of SOM is a mapping from
to
, the mapping makes the topological order of training samples visualized in the two-dimensional space. The input vectors are the normalized vectors
in the
space, they are mapped into the K (
) nodes on the two-dimensional space. The connection weights are adjusted continuously through automatic competition, and each activated node represents the center of one cluster, the sample vectors which is close enough on Euclidean distance are mapped onto one cluster. At the same time, the adjacent extent of neighboring nodes also reflects the degree of proximity between the input vectors
. It is shown that the two-dimensional map keeps the same topological order with the distance difference vector
.
The second level of SOM we set up is a 1-1 mapping process. It is from the trained two-dimensional space to another two-dimensional space, obviously, they have the same structure and number of nodes. Each node of the second map represents a cluster of angles of arrival, which is obtained according to the location of the signal source that activates the node. Assumed that node i in the first layer is activated by
(
) sample vectors, and the coordinates for the corresponding signal source are
, the direction of arrival corresponding to
is
. Consider that the node of the first level may be activated by one, several or none training vectors; the output of second level is constructed as the following rules (Figure 4):
1) If node i has been activated by one training input vector, the angle of the corresponding training signal source will be the output, and
.
2) If node i has been activated by not only one training input vector, then the average angles of the corresponding signal sources will be the output as this node stands for, then
. (18)
Figure 4. Flowchart of DOA estimation by the two-level SOM.
3) If node i has not been activated by any training input vector, the node will be considered as a null node. When it is activated by a new input vector, the output will be substituted with the value of the nearest one in Euclidean.
The process of DOA estimation we proposed is shown in Figure 4. The process is divided into two parts, the train part and test part. The network is trained by a large number of TDOA vectors from a large number of DOAs, through the Kohonen SOM the training vectors are grid up on an two dimensional level in theirs topological order. The DOAs level are arranged directly connected with level one, and keep the same topological order, thus the two level SOM are set up as an labelled network. When there is a new TDOA vector is put into the SOM, an optimal matching node will give the estimation of AOA.
3.4. Analysis of Reliability under Lipschitz Condition
The validity of the proposed method is based on whether the topological order of DOA is the same as (or similar to) vector of DDOA’s. In another word, if the Euclidean distance between vectors of DDOA of two signals is small, then the corresponding Euclidean distance between DOAs will be small as well. This is the theoretical basis of our estimation of DOA. Next, we will analysis the conditions it needs to meet.
Let
be the location of a signal source, another sound source’s coordinate is
, where
and
are small variations. Thus the distance difference vectors of the two signal sources are
and
, the DOAs of them are
and
respectively. According to Equation (4) and Equation (5), the increment is obtained,
. (19)
Obviously that function
is an elementary function and it is differentiable at point
, thus
. (20)
And the Euclidean distance between
and
is
. (21)
Since function
is an elementary function and it is differentiable at point
, then
. (22)
The ratio of the two distances is
. (23)
when point
is fixed,
is a constant, let
.
There are three kinds of conditions on R with the changes of
and
around zero:
1) R is a constant function; assume that
, where
is a constant. Equation 27 will be
, (24)
And then
. (25)
That is to say the Euclidean distance between DDOA vectors is in proportion to the corresponding Euclidean distance between DOA,
will change as
. In this condition, the SOM we set up is absolutely valid to DOA estimation.
2) R is a bounded function; there exists a positive constant L subject to
. (26)
where
is a positive constant, that is
. (27)
Then
. (28)
Take the SOM we set up as a function
, i.e.
, then
. (29)
It shows that function F satisfies Lipschitz conditions, F is uniformly continuous, then for
, there
, if only
, then
. When the Euclidean distance between DDOA vectors was small enough, the corresponding Euclidean distance between DOA must be very small, too. So, the SOM we set up is also valid to DOA estimation in this condition.
3) R is an unbounded function, in this condition, there are no definitive relationship between
and
, and the SOM we set up will be invalid in estimation of DOA.
In short, when
is bounded, TDOA vectors and DOAs will have a similar topological order and distribution, and the SOM we setup can be used in DOA estimation reliably.
4. Simulation Results
4.1. Without Noise
In this section, to verify the effectiveness of the two-level SOM network we setup, simulations are carried out as follow. In the simulations, we assume a sensor array with four sensors, the frequency of sound source is
, the speed of sound wave propagation in water is
, and the distance of each two adjacent sensors is set to be
, which is half of the wave length. The sensor positions are
,
,
,
. To get training vectors, 60 × 30 uniform distribution points are taken in rectangular region
as the positions of 1800 signal sources (Figure 6, black points), and then 1800 distance difference vectors
are got as training sample vectors. Calculate
value,
(30)
where
is definite as Equation (27). As shown in Figure 5, there are a common upper bound for most points (except a few points near
), belongs the second case, the method we propose is valid.
To test the trained network by signals in different distance and different angles, the locations of 180 test signals are chosen to be on the spiral of Archimedes:
. (31)
On which the DOA changes from 0˚ to 180˚, and the distance changes from 0 to 62.83 (Figure 6, green points). The nodes of feature map and DOA map are arranged as 50 × 50, which is a few more than the training data in number. Put the distance difference vectors of test signals into the trained network, and then get the estimation of DOAs. Figure 7 is the error of estimation; except several signals most of the error are within
.
Figure 7. Estimation errors with rectangular region training data.
To test the trained network by signals in different distance and different angles, the locations of 180 test signals are chosen to be on the spiral of Archimedes:
. (32)
On which the DOA changes from 0˚ to 180˚, and the distance changes from 0 to 62.83 (Figure 6, green points). The nodes of feature map and DOA map are arranged as 50 × 50, which is a few more than the training data in number. Put the distance difference vectors of test signals into the trained network, and then get the estimation of DOAs. Figure 7 is the error of estimation, except several signals most of the error are within
.
From the result above we can see that the results of DOA estimation are mainly associated to the angles of training signals, but little to the localizations. Thus, we chose another group of training data for contrast, a set of signals on circle
. (33)
1800 uniform distribution points are taken from the circle (Figure 6, red points). The test signals are the same with above.
At the same time, to study the factor of nodes arrangement, 8 kinds of nodes distributions are evaluated. The average absolute values of estimation error are shown as Table 1. It can be seen that the circle training data performs better than rectangular region, the network with 40 × 40 nodes get better accuracy in DOA estimation, which is a type of n × n and the number of nodes are a few less than training data, while the other structures performs poor relatively.
4.2. With Gaussian Noise
In practice, there are always additive noises with the signal received by sensor array; therefore, a practical method needs to be robust when noise exists. Take a simulate sinusoidal signal as a sound source, assume that the sound source are located in the direction of 30˚ for example, additive Gaussian noise are added to the signal from a ratio of signal to noise (SNR) of 20 dB to a SNR of 0 dB as Equation (3), then take the DDOA vectors of the 21 noisy signals as test data for the trained network (rectangular region trained). To test the performance of SOM network, we take MUSIC, Root-MUSIC, ESPRIT, and RBF for contrast,
Table 1. Results of DOA estimation by SOM neural network with different nodes arrangement and training data (degree).
Figure 8. Comparison of DOA estimation errors for SOM, MUSIC, Root-MUSIC, ESPRIT, and RBF.
where the RBF neural network take the rectangular region signals’ DDOA vectors as input data, and the corresponding DOAs as output to train the network. The DOA estimation errors are as shown in Figure 8. When the SNR is higher than 2 dB, the errors of SOM are within 1˚, and change little with the SNR decreases from 20 dB to 2 dB. Compared to MUSIC, Root-MUSIC, ESPRIT, and RBF, SOM performs better than RBF and slightly worse than MUSIC in anti-interference, and almost similar with Root-MUSIC and ESPRIT. Consider that the noises are added to features directly by SOM, in fact, usually the SNR of features should be much high after the process of de-noising, thus the performance of SOM will be much better than as shown in Figure 8. It indicates that the system of two-level SOM has the advantages of stability and accuracy and avoids the disadvantage of large calculation in addition.
5. Discussion
The proposed method in this study is an exploratory study of the relationship between characters of signals and DOA, there are many approaches designed for DOA estimation that try different methods of extracting features, and then validate the effectiveness of the accuracy of predicting DOA through different experimental solutions. The basis of this type of research is often supported by data results only, but lacks further deep theoretical discussion.
In this work, we attempt to discussion of the theoretical basis by using Lipschitz condition. When a mapping is Lipschitz continuous, the closer the original images of the mapping are to each other, the closer the images are to each other. For a variety of reasons, the analytic formula for the mapping between some features and DOA cannot be written directly, thus a variety of research methods for approximating the map based on a finite number of discrete data for fitting are proposed. In this study, we take a direct approach to estimate the Lipschitz coefficients from discrete features through Equation (30). When the maximum value of Lipschitz coefficients in a region is within an acceptable range, then the mapping between features and DOA is considered to be approximately Lipschitz continuous, and DOA estimation can be performed using the principle that similar features correspond to similar DOAs. The next problem comes to how to topologically sort the features, and it can be done by Kohonen self-organizing neural networks. In this work, we estimate DOA by building a two-layer Kohonen self-organizing neural network to perform the tasks used for approximate mapping and query dictionaries.
However, the Lipschitz coefficient estimated using equation 30 in this paper has two limitations. First, this estimation is limited to the sparsity of the sampled signal grid, which is closer to the true value when the grid is more dense and relatively rough when the grid is less dense. Second, the values of the Lipschitz coefficients in the local neighborhoods of different sampling points may vary widely, so the matching estimation DOA errors based on the Kohonen neural network will have a different. As shown in Figure 7, although the global error can be controlled within a certain range, the error range varies widely for different areas of the test points.
6. Conclusion
A two-level SOM system to estimate the DOA based on DDOA vectors was proposed and demonstrated experimentally. The system implements a classifier for DOA through the classification of DDOA vector, which is based on the theory of Lipchitz condition. The error on DOA varied within 1˚ for the noise free signals from 0˚ to 180˚. The system is robust to noise when the SNR decreased from 20 dB to 2 dB, compared to MUSIC Root-MUSIC, ESPRIT, and RBF, most error of SOM are lower than 1˚, and are stable relatively. The methodology avoids calculating the covariance matrix and decomposition, when estimating the DOA, the network can be trained in advance, which makes it feasible to carry out in real-time processing.
Acknowledgements
This work was financially Supported by National Natural Science Foundation of China (Grant No. 61774137, 51875535 and 61927807), Key Research and Development Foundation of Shanxi Province (Grant No. 201903D121156), and Shanxi Scholarship Council of China (Grant No. 2020-104 and 2021-108).