Applications of Compressive Sampling Technique to Radar and Localization

Abstract

During the last decade, the emerging technique of compressive sampling (CS) has become a popular subject in signal processing and sensor systems. In particular, CS breaks through the limits imposed by the Nyquist sampling theory and is able to substantially reduce the huge amount of data generated by different sources. The technique of CS has been successfully applied in signal acquisition, image compression, and data reduction. Although the theory of CS has been investigated for some radar and localization problems, several important questions have not been answered yet. For example, the performance of CS radar in a cluttered environment has not been comprehensively studied. Applying CS to passive radars and electronic warfare receivers is another concern that needs more attention. Also, it is well known that applying this strategy leads to extra computational costs which might be prohibitive in large-sized localization networks. In this chapter, we first discuss the practical issues in the process of implementing CS radars and localization systems. Then, we present some promising and efficient solutions to overcome the arising problems.

1. Introduction

The well-known Nyquist sampling theorem, which has served as a starting point for development of traditional analog-to-digital converters (ADCs), states that the sampling rate needs to be at least twice as high as the bandwidth of the input signal to achieve aliasing-free sampling. Moving to higher communication throughputs and carrier frequencies motivates the search of innovative ADCs, specifically when sampling rates reach several gigahertz. This is because employing traditional ADCs would result in very expensive architectures, particularly at high sampling rates; since they require a large die area and consume extremely high power even for resolutions as low as 7-bits [1, 2, 3, 4]

To overcome these issues, different methods, such as the time-interleaving structure and the multichannel filter-bank approach, have been proposed in the literature. Unfortunately, these techniques are only suitable for special scenarios or applications because of their high power consumption and their non-ideal characteristics. For further details, the interested reader can refer to [1, 2, 3, 4] and the references therein. More recently, a novel sampling strategy based on the emerging technique of compressive sensing (CS) [5, 6, 7], is able to reduce the sampling rates considerably. This strategy is also called compressive sampling since it breaks through the limits of the Nyquist sampling theory.

The technique of CS enables the reconstruction of a sparse (compressible) signal vector x $\in R^N$ from the measurement vector y $\in R^M$ generated by

$$\mathit{y}=\mathbf{\Phi x}$$E1

where $\mathbf{\Phi }\in R^{M\times N}$ is the measurement matrix with M < < N. It has been demonstrated that the proper selection of the measurement matrix $\mathbf{\Phi }$ is a key point for the success of CS [6].

During the last decade, CS has been successfully applied in many applications, such as image processing [8], wireless sensor networks and communication networks [9]. Although some recent works have studied the application of CS to radar and localization [10], several important questions have not yet been answered. For example, the application of CS in electronic warfare and passive radar scenarios has not been studied well. Furthermore, the effects of clutter and other structured noises on the performance of CS-based radar systems have not been comprehensively investigated to the knowledge of the authors. The extra computational burden caused by signal reconstruction methods is another practical challenge that should be carefully considered. While all previous works have improved our knowledge, the above shortcomings greatly motivate us to provide a more realistic analysis that addresses these important issues. The main aim of this chapter is to investigate some aspects of CS applied to radar concerning the reduction of ADCs’ sampling rates. Also, we present a novel CS-based strategy to decrease the traffic of large-scale localization networks with reduced computational complexity. It is not the aim of this chapter to investigate numerically efficient algorithms but to point out some problems, arising when designing and developing practical CS-based radars and localization systems, as well as possible solutions.

In the literature, the terms “compressive sensing” and “compressive sampling” are used interchangeably. Here, we make the distinction that compressive sensing means a dimension reduction of a data vector using a compressed sensing measurement matrix. Compressive sampling is the reduction of the sampling rate (from the Nyquist rate) in the digitization of an analog signal.

The organization of this chapter is as follows. In Section 2, we briefly review the basics of CS theory. In Section 3, we first present the radar main concepts. Then, we show how employing CS can reduce the sampling rate substantially. Next, we introduce two main scenarios where the standard CS radar formulation is not applicable. Finally, we propose an efficient technique that can be used to address the shortcomings of existing methods. In Section 4, we first briefly review the main concepts of localization. Then, we explain how the reconstruction step of the CS technique significantly increases the complexity of localization algorithms. Finally, we introduce a novel method which eliminates the complex recovery step of CS-based localizers and reduces the data traffic between the sensors and the fusion center.

2. Compressive sampling basics

Suppose a signal $\mathit{x}\in R^N$ can be represented as:

$$\mathit{x}=\mathit{\psi }\mathit{s},$$E2

where $\mathit{\psi }=\left[{\mathit{\psi }}_1,\dots ,{\mathit{\psi }}_{\mathrm{N}}\right]\in R^{N\times N}$ is a full rank, orthonormal basis matrix, sometimes also known as the basis matrix [5], and the vector $\mathit{s}=\left[{\mathrm{s}}_1,\dots ,{\mathrm{s}}_{\mathrm{N}}\right]\in R^N$ has K non-zero elements. Then the signal x is K-sparse. In fact, the signal x is K-sparse if it is a linear combination of only K basis vectors; that is, only K elements of vector s in (2) are nonzero and the other (N-K) elements are zero. Also, we say that the signal x is compressible if the representation (2) has just a few large coefficients and many small coefficients in s. A sparse signal is compressible as described below. Putting (2) into (1) yields:

$$\mathit{y}=\mathit{\Phi \psi s}=\mathbf{\Theta }\mathit{s},$$E3

where $\mathbf{\Theta }=\mathbf{\Phi \psi }\in R^{M\times N}$ is called the sensing matrix. Since M < N, y is a compressed measurement of x. Such compression makes possible the storage and transmission of x at a lower dimension. Hence, CS is an important data compression technique.

This means that instead of measuring the N-point signal x directly, the CS framework acquires the information from far fewer measurements (M ≪ N) than traditional methods. Notice that since $\mathbf{\Theta }$ has far fewer rows than columns, (3) is non-invertible and underdetermined, rendering the CS problem ill-posed [11]. The main question therefore is: “how to recover x from y?”

In general, (3) has no unique solution since it has more unknowns (N) than equations (M). However, since x is K-sparse, we know that N-K unknown elements in s are zero. It is then possible to recover s from (3) using a technique known as $l_1$ minimization [6]. From s we recover x via (2).

The signal x is thus compressible and recoverable. It is well known that images and speech signals are compressible signals. Another example is a vector x whose elements are sums of samples of two sinusoids. Its ψ in (2) consists of columns of sinusoidal samples of frequencies $w_1,\dots ,w_N.$ If the sinusoids have frequencies $w_3$ and $w_5$, then s has only non-zero elements at positions 3 and 5.

There are mathematical conditions on $\mathbf{\Theta }$, and the numbers of measurements M, needed to ensure recovery of s. They are given in the next three subsections.

2.1. Number of measurements

Choosing the number of measurements M is a trade-off: While a small M is desirable for high compression, it must be sufficiently large to enable reconstruction. Generally M should be in the order of ${\text{log}}_2\frac{N}{K}$ . A rule of thumb is $M\cong 4K\left[6\right]$ provided that $\mathbf{\Theta }$ satisfies both the conditions of Incoherence (Subsection 2.2) and Restricted isometry property (Subsection 2.3).

2.2. Incoherence

From (3), it is seen that the elements of y are a linear combination (l.c.) of the elements of s, via the matrix $\mathbf{\Phi }\mathit{\psi }$. If $\mathbf{\Phi }$ is highly correlated to $\mathit{\psi }$, the probability of having independent l.c. (or measurements) of s decreases.

To see this, suppose $\mathbf{\Phi }\mathit{\psi }$ has a column, say the i-th column that contains all zeros. Then y is missing a measurement of the i-th element in s, and if this element is non-zero, we cannot recover s from y. This will happen if a row of $\mathbf{\Phi }$ is orthogonal to a column of $\mathit{\psi }$, i.e., there is a strong correlation between $\mathit{\Phi }$ and $\mathit{\psi }$. In CS theory, there is a theorem that relates the required number of measurements M, for perfect reconstruction, to the coherency (a numerical number) of $\mathit{\Phi }$ and $\mathit{\psi }$. The higher the coherency, the higher the required M is.

2.3. Restricted isometry property (RIP)

For $\mathbf{\Theta }=\mathit{\Phi \psi }\mathit{,}$ the RIP requires that for perfect reconstruction, $\mathbf{\Theta }$ must satisfy the inequality

$$\mathrm{\alpha }‖\mathit{s}‖\le ‖\mathbf{\Theta }\mathit{s}‖\le \mathrm{\beta }‖\mathit{s}‖,$$E4

with $0<\mathrm{\alpha }<1\text{and}1<\mathrm{\beta }<2.$

Notice that the isometry is the length of a vector. The inequality (4) limits the amount by which Euclidean distance $‖\mathbf{\Theta }\mathit{s}‖$ can differ from $‖\mathit{s}‖\mathit{.}$ The lower bound in (4) ensures a perfect recovery. Suppose $‖\mathit{s}‖\mathit{\ne }0$ but $‖\mathbf{\Theta }\mathit{s}‖=0$. This violates the lower bound of (4). Indeed, if $\mathit{y}=\mathit{\Phi \psi s}=0$, we cannot recover s from y. Note that $‖\mathbf{\Theta }\mathit{s}‖=0$ when $‖\mathit{s}‖\mathit{\ne }0$ implies that s is in the null space of $\mathbf{\Theta }$, meaning that at least two columns of $\mathbf{\Theta }$ are linearly dependent. Further to this point, consider two K-sparse vector s and $s^{\ast }$. The maximum sparsity of s-${\mathit{s}}^{\mathit{\ast }}$ is 2 K. To be able to distinguish $\mathbf{\Theta }$s from ${\mathbf{\Theta }s}^{\ast }$, we must have

$$\mathbf{\Theta }\left(\mathit{s}-{\mathit{s}}^{\ast }\right)\ne 0.$$E5

i.e., any 2 K columns of $\mathbf{\Theta }$ must be linearly independent. This ensures that $\mathbf{\Theta }$ satisfy the lower bound of (4).

The upper bound is necessary to keep the lower bound meaningful. Otherwise, $\mathbf{\Theta }$ can be arbitrary scaled to satisfy the lower bound.

Note that incoherency and RIP both give conditions for perfect reconstruction. But the incoherency condition is valid only for a K-sparse vector. In contrast, RIP applies even when s is a non-sparse vector; in this case, the recovered vector will consist of the K most significant elements.

Checking if a chosen $\mathbf{\Theta }$ satisfies the RIP criteria is computationally expensive and cannot be realized in practice. It has been shown in [6] that with high probability, random Gaussian, Bernoulli, and partial Fourier matrices do satisfy the RIP condition.

Finally, in practice, noise is commonly present in the measurement. Therefore, (3) becomes

$$\mathit{y}=\mathit{\Phi \psi s}+\mathit{e}=\mathbf{\Theta }\mathit{s}+\mathit{e},$$E6

where $\mathit{e}\in R^M$ represents an unknown noise vector. Recovering s from y will yield additional errors due to $\mathit{e}$. A bound on this error, as a function of the power of $\mathit{e}$, can be obtained [7].

2.4. Sampling rate reduction by CS

In some applications, for example in an electronic warfare (EW) receiver, a high sampling rate is required because the receiver must scan for signals with high bandwidths. High rate ADCs have low accuracy and consume high power. In addition, the high number of samples can fill up the available memory quickly. As we will show, compressive sampling can essentially reduce the sampling rate and number of samples via a system known as the random-modulation pre-integrator (RMPI) [12].

A simplified block diagram of the sampling scheme given in [12] is shown in Figure 1. An RMPI with four output channels generates a CS vector $\mathit{y}\in R^{80}.$

Figure 1.

Block diagram of RMPI with four channels.

Here, x(t) represents the input signal with bandwidth B Hz. Also, note that the Nyquist sampling rate is 2B Hz, and one-bit duration is equal to $\frac{1}{2B}$ second. Since the duration of 52 bits is $\frac{52}{2B}$, an ADC samples at $\frac{2B}{4\times 52}\mathit{Hz}.$ So, the actual sampling rate is $\frac{2B}{52}\mathit{Hz}$ and each integrator sums $\frac{52}{2B}$ seconds of the product of x(t) and PRBS, then resets and repeats. We have:

$$\mathit{x}={\left[x\left(1\right),\dots ,\mathrm{x}\left(1040\right)\right]}^T$$E7

$$\mathit{y}={\left[y\left(1\right),\dots ,\mathrm{y}\left(80\right)\right]}^T$$E8

$$\mathbf{\Phi }=\left[\begin{array}{cc}{\mathit{A}}_{1}0\dots & 0\\ \begin{array}{c}\begin{array}{ccc}0& {\mathbf{A}}_2& \dots \end{array}\\ \begin{array}{ccc}⋮& ⋮& \ddots \end{array}\\ \begin{array}{ccc}0& 0& \dots \end{array}\end{array}& \begin{array}{c}0\\ ⋮\\ {\mathbf{A}}_{20}\end{array}\end{array}\right]$$E9

where $A_i\in R^{4\times 52}$ contains elements of $\pm 1$. Hence, the sampling rate is reduced by a factor of 13, as is the number of samples, i.e., $\frac{N}{M}=13.$

3. Application of CS to radar

In this section, we seek to provide a more realistic analysis of the application of CS in practical radar systems. We follow an alternative approach instead of that used in previous published works in the context of CS radar, which is a generalization of a canonical CS formulation. Although our approach is designed for the radar scenario, it is also capable of accommodating other practical scenarios in which the basis matrix is (partially) unknown and/or the observed data is contaminated by structured noises (interference).

3.1. Introduction

Radar (radio detection and ranging) systems are present in many different civilian, military, and biomedical applications [13]. Radar systems are used to detect and determine the range, angle, and velocity of different objects, such as aircraft, missiles, ships, tanks, helicopters, and ground stations. Air traffic control, mapping of ground contours, detecting weather formations, and automotive traffic enforcement are some civilian applications of Radar systems.

Traditional radar systems consist of a transmitter, a transmitting antenna, a receiving antenna, and a receiver (powerful processor). The transmitter sends probing pulses of electromagnetic waves toward the areas of interest. The properties of the transmitted waves change when they are reflected by the potential targets. This enables the radar to locate the unknown targets (threats). This kind of detection is usually called active detection. Passive radars, which are essentially receive-only radars, do not transmit any probing signal. Instead, passive radars perform detection and estimation from signals that come from sources such as radar, radio and television (TV) stations [14].

A single-input single-output (SISO) radar consists of a single transmitter and a single receiver. A few decades ago, multiple-input multiple-output (MIMO) radar systems have been proposed as an extension of SISO radar systems. MIMO radar systems employ multiple elements on the transmitting and receiving sides, while SISO radars employ one element on each side. It is demonstrated that employing multiple transmit and receive elements significantly improves the performance. Since an SISO radar can be considered as a special case of MIMO radars, most recent works have focused on the MIMO scenario.

Broadly speaking, there are two main groups of MIMO radars: Co-located MIMO radars and distributed MIMO radars [15]. In the co-located MIMO radar all the antennas are closely spaced, while in the distributed MIMO radar, the antennas are widely separated. To be more precise, a distributed MIMO radar views the potential target from different angles. Hence, if the received signal from any specific path is weak, it can be compensated by signals received from other paths. Although all transmit-receive antenna pairs in a co-located MIMO radar see the potential target from the same view, transmitters use different probing waveforms. In summary, a distributed MIMO radar exploits the spatial diversity, while a co-located MIMO radar exploits the waveform diversity.

3.2. CS for radar

Usually, radar detection and classification tasks require the transmission of wide-bandwidth probing signals during short observation times. Employing wideband probing pulses necessitates using fast ADCs with high sampling rates, which in turn leads to the generation of a huge amount of data. In most cases, data processing becomes one of the most important design issues. Recently, the emerging technique of compressive sampling has been proposed to alleviate the identified practical problems [16]. As mentioned previously, CS exploits the sparsity (compressibility) of received signals in different spaces to reduce the sampling rate as well as the volume of generated data and hence, is a promising technique for sophisticated radar systems.

The idea of using the CS technique in the context of radar systems was initially proposed by Herman and Strohmer in [17]. They showed that since the number of targets is typically much smaller than the number of range-Doppler cells, the prerequisite on the signal sparsity is often met in most radar scenarios, and hence CS can be efficiently used in radar systems. It is worth mentioning that [17] just focused on the simple SISO radar scenario. Then, Chen and Vaidyanathan in [18] extended the work in [17] to the MIMO radar case. During the last decade, different aspects of employing CS in both SISO and MIMO radars have been investigated; please see [15, 19] and the references therein.

Although CS has been applied in radar problems, it has not been comprehensively studied with respect to clutter and other structured noises. To be more precise, all related works modeled the observed signal by radar as a signal contaminated by additive noise. However, it is more realistic to add another term into the model to account for the clutter. Also, the proposed methods in the literature are suitable only for the case where radar transmitting waveforms are completely known, and hence, are not applicable to some important practical cases, such as electronic surveillance and threat recognition cases. To the best of our knowledge, none of the published works, on application of CS to radar, studied the general case where the signal is contaminated by clutter and the basis matrix is (partially) unknown.

The above shortcomings motivate us to provide a more realistic model that addresses these important issues. To this end, in the next subsection, we first present a high-level block diagram of CS-based radar architecture to show how CS can be employed to reduce the sampling rate of traditional radar systems. Then, in the next subsections, we study the case where perfect knowledge of the transmitted waveforms is not available, and when the received signals are contaminated by clutter and other structured noises. Finally, we introduce our solution for such a complex problem.

3.3. Sub-Nyquist radar system

We now explain how CS is able to relax the required Nyquist-sampling rate of traditional radar systems. Let x(t) represent the signal received by a radar system with bandwidth B. As depicted in Figure 2, x(t) is first multiplied by the sensing matrix $\mathbf{\Phi }\left(\mathrm{t}\right)$ in the time domain at Nyquist frequency $f_{\mathrm{S}}$. The modulated signal is then integrated for a duration of $\frac{N}{f_{\mathrm{S}}}.$ The output is sampled at sub-Nyquist rate $\frac{f_{\mathrm{S}}}{N}$. One can easily show that

$$y_i={\int }_{\mathrm{t}}^{\mathrm{t}+\frac{\mathrm{N}}{{\mathrm{f}}_{\mathrm{S}}}}{\mathrm{\Phi }}_i\left(t\right)\mathbf{x}\left(t\right)\mathit{dt},i=1,\dots ,M,$$E10

where N is the number of integration samples per compression block. The selection of the sensing matrix that multiplies the input vector is a key point for the success of every CS approach. It has been shown that in most applications, the use of random sensing matrices provides a good performance. Let us assume that

$${\left.{\mathrm{\Phi }}_i\left(t\right)\right|}_{t=\frac{j-1}{f_S}}^{t=\frac{j}{f_S}}={\mathrm{\Phi }}_{i,j}\mathbf{\in }\left\{+1,-1\right\},i=1,\dots ,M,j=1,\dots ,N.$$E11

Figure 2.

Block diagram of compressive sampling architecture for radar systems.

Then, $y_i$ in (10) can be represented as

$$y_i=\sum _{\mathit{j}=\mathbf{1}}^{\mathit{N}}{\mathrm{\Phi }}_{i,j}{x}_j,i=1,\dots ,M,$$E12

$$\left[\begin{array}{c}\begin{array}{c}{y}_1\\ y_2\end{array}\\ ⋮\\ y_M\end{array}\right]=\left[\begin{array}{cc}\begin{array}{ccc}{\mathrm{\Phi }}_{1,1}& {\mathrm{\Phi }}_{1,2}& \dots \end{array}& {\mathrm{\Phi }}_{1,N}\\ \begin{array}{c}\begin{array}{ccc}{\mathrm{\Phi }}_{2,1}& {\mathrm{\Phi }}_{2,2}& \dots \end{array}\\ \begin{array}{ccc}\mathbf{⋮}& \mathbf{⋮}& \mathbf{\ddots }\end{array}\\ \begin{array}{ccc}{\mathrm{\Phi }}_{M,1}& {\mathrm{\Phi }}_{M,2}& \dots \end{array}\end{array}& \begin{array}{c}{\mathrm{\Phi }}_{2,N}\\ \mathbf{⋮}\\ {\mathrm{\Phi }}_{M,N}\end{array}\end{array}\right]\left[\begin{array}{c}\begin{array}{c}{x}_1\\ x_2\end{array}\\ ⋮\\ x_N\end{array}\right]$$E13

where $x_j={\int }_{t+\frac{\left(j-1\right)}{f_S}}^{t+\frac{j}{f_S}}{\Phi }_i\left(t\right)x\left(t\right)\mathit{dt}$ and $x_j$ are simply the Nyquist samples of the input signal x(t). For our purposes, it is more convenient to write (3) in matrix form as:or, equivalently, as (excluding noise):

$$\mathit{y}=\mathbf{\Phi }\mathit{x},$$E14

where $\mathit{y}={\left[y_1,\dots ,y_M\right]}^T$, $\mathit{x}={\left[x_1,\dots ,x_N\right]}^T$, and $\mathbf{\Phi }=\left[\begin{array}{cc}\begin{array}{ccc}{\mathrm{\Phi }}_{1,1}& {\mathrm{\Phi }}_{1,2}& \dots \end{array}& {\mathrm{\Phi }}_{1,N}\\ \begin{array}{c}\begin{array}{ccc}{\mathrm{\Phi }}_{2,1}& {\mathrm{\Phi }}_{2,2}& \dots \end{array}\\ \begin{array}{ccc}\mathbf{⋮}& \mathbf{⋮}& \mathbf{\ddots }\end{array}\\ \begin{array}{ccc}{\mathrm{\Phi }}_{M,1}& {\mathrm{\Phi }}_{M,2}& \dots \end{array}\end{array}& \begin{array}{c}{\mathrm{\Phi }}_{2,N}\\ \mathbf{⋮}\\ {\mathrm{\Phi }}_{M,N}\end{array}\end{array}\right]$. Thus, CS reduces the sampling rate to $\frac{M{f}_{\mathrm{S}}}{N}$, which is much lower than the Nyquist rate $f_{\mathrm{S}}$.

The architecture presented in Figure 2 can be adapted to any application. The main idea is that the input signal is first compressed in the analog domain and then, traditional ADCs are used for sampling.

Remark: Exploiting the sparsity of the received signal x in different spaces, we have: $\mathit{x}=\mathit{\psi s}$, where $\mathbf{\psi }$ represents the basis matrix in which signal x is sparse. Taking into account the noise (denoted by e), $\mathit{y}$ can be expressed as:

$$\mathit{y}=\mathbf{\Phi }\mathit{\psi s}+\mathit{e}.$$E15

The standard equation (15) is the starting point of existing literature in the context of CS-based radars. To be more precise, exploiting the sparsity of radar signals in various spaces, radar problems are first transformed into the CS context (radar problems are reformulated as a recovery of sparse vectors). Then the CS problems are solved by conventional sparse recovery methods. All conventional recovery methods assume that both sensing $\left(\mathbf{\Phi }\right)$ and basis $\left(\mathit{\psi }\right)$ matrices are known and available. As we will discuss in Subsection 3.4, this fundamental assumption is not valid in some important radar applications.

3.4. Blind compressive sampling

In some radar scenarios, knowledge of the basis matrix $\left(\mathit{\psi }\right)$ is available. For example, in MIMO radar scenario, the transmitted waveforms are known a priori. Therefore, a receiver can use this knowledge to construct the basis matrix locally. However, in some practical cases like passive radars, the transmitters are not part of the radar system, and hence, perfect knowledge of the transmitted waveforms is not available. Therefore, a receiver is only able to reconstruct from a noisy version of the basis matrix $\left(\mathit{\psi }\right)\mathit{.}$ As discussed in the related literature, erroneous basis matrices can lead to a significant performance loss (huge decrease in probability of detection), which is not acceptable in practice.

Also, in some other applications such as electronic surveillance and threat recognition, electronic warfare (EW) [14] receivers are preferred to both passive and active radars. Particularly, EW receivers need neither probing pulses nor illuminator signals, since they listen to the electromagnetic radiations of the potential threats instead of weak reflected radar (illuminator) signals. More specifically, EW receivers detect potential targets through sensing the electro-magnetic spectrum, and extracting (and/or analyzing) the characteristics of their transmissions. Therefore, their detection range is much higher than that of radars, while they remain electronically silent and undetectable. However, applying standard CS techniques in the context of EW receivers is not possible. This is because a priori knowledge about the transmitted signal by unknown source is not available at all, which means a receiver is not able to build the basis matrix $\left(\mathit{\psi }\right)$.

The above-mentioned scenarios motivated us to study the CS problem for the case where perfect knowledge of the basis matrix $\left(\mathit{\psi }\right)$ is not available ($\mathit{\psi }$ is completely unknown or noisy). This interesting scenario can be referred to as the blind CS problem [11]. In summary, the blind CS problem aims to recover the sparse vector s from measurements y obtained from $\mathit{y}=\mathbf{\Phi }\mathit{\psi s}\mathit{+}\mathit{e}$, while the basis matrix $\mathit{\psi }$ is unknown. This is in sharp contrast to the existing CS literature which is based on a perfect knowledge of the basis matrix. In general, solving such a problem is very hard since we have three unknowns: sparse vector $\mathit{s}$, basis matrix $\mathit{\psi }$, and noise vector $\mathit{e}$. An efficient CS-based method which iteratively solves this problem has been proposed in [14].

3.5. CS-based radars in cluttered environments

Clutter, a term used for unwanted echoes, can cause serious performance issues with radar systems. Although CS has been applied to different radar problems, it has not yet been studied with respect to clutter and other structured noises. It is not possible to neglect the effects of clutter since clutter is produced from nearly all surfaces when illuminated by a radar, such as ground, sea, rain, animals/insects, chaff and atmospheric turbulences. In order to build reliable practical CS-based radars, it is necessary to investigate the harmful effects of clutter and other environmental factors on the CS performance. Up to now, all existing works in the field of CS radar limited their studies to the ideal clutter-free scenario.

The definition of clutter depends on the mission and function of the intended radar system. Usually, in the context of radar, clutter is modeled as the superposition of echoes from all unwanted objects. Therefore, it is realistic to introduce a third term in the CS model (15) to account for clutter and other interfering signals. In the presence of clutter, the signal measured by the radar receiver can be written as

$$\mathit{y}=\mathbf{\Phi }\mathit{\psi s}+\mathit{e}+\mathit{c},$$E16

where $\mathit{c}$ represents the clutter. As stated in [20], merging the clutter $\left(\mathit{c}\right)$ and the additive (unstructured) noise $\left(\mathit{e}\right)$ components allows us to address this kind of problems. However, it is important to highlight that merging the noise $\left(\mathit{e}\right)$ and the clutter components $\left(\mathit{c}\right)$ or ignoring the weaker component (usually additive noise) leads to poor performance in most practical cluttered environments. Therefore, it is important to derive a novel framework for recovering the sparse signals from corrupted measurements by noise and clutter. The developed method should be able to obtain knowledge on the structure of clutter. This knowledge can be used to discriminate the intended signal from the contaminating sources.

However, adding clutter as in (16) makes the sparse recovery problem much more challenging since, as stated in [21], the clutter covariance matrix is usually unknown in radar applications and has to be estimated from the observed data. This means that in addition to the sparse vector s, the noise and the clutter covariance are other unknowns that should be estimated from measurements y.

To be more precise, the ultimate goal is to determine the non-zero elements of vector s from far fewer measured samples y generated by (16), while the covariance matrix of the clutter $\mathit{c}$ and the variance of the noise $\mathit{e}$ are both unknown. Similar to the Blind CS problem, reconstruction of sparse radar signals in the presence of clutter is a complicated problem.

3.6. Proposed solution

As we discussed in previous subsections, reconstruction of sparse radar signals under the scenario where the received vector is contaminated by clutter and/or perfect knowledge of the basis (dictionary) matrix is not available, is very complicated. In the canonical CS formulation, i.e., $\mathit{y}=\mathbf{\Phi }\mathit{\psi s}\mathit{+}\mathit{e}$, only two unknowns exist: sparse vector $\mathit{s}$ and e and its variance. However, in both Blind CS and cluttered environment cases, in addition to the sparse vector s and variance of the noise, the basis matrix (covariance matrix of the clutter) is another unknown that should be estimated from the measurement vector $\mathit{y}\mathit{.}\text{Unfortunately},$ none of the proposed approaches for conventional CS formulation is applicable to these complex scenarios.

Applying a probabilistic approach seems to be the best method to efficiently handle these complex problems. As mentioned in [20], most probabilistic approaches for sparse signal recovery are Bayesian. It is well known that the Bayesian methods regularize the under-determined problem by employing priors on the regression coefficients. In fact, since Bayesian methods estimate the posterior distribution of the unknown coefficients instead of their point estimates, they gain more information than other methods. Also, it is worth mentioning that the performance of Bayesian approaches is better than that of other techniques, especially when a probabilistic model is a reasonable representation of the physical process that generates the observations [20].

Sparse Bayesian Learning (SBL), which was first proposed by Tipping [22], is one of the most important families of Bayesian algorithms. In the last decade, this method was the focus of numerous studies and it was greatly extended by many other researchers; for more details please see [23] and the references therein. Having noticed the benefits of SBL, [14] has recently applied SBL to EW receiver design. Also, [20] applied SBL to the scenario where the observed data is represented as the superposition of signal plus noise plus interference. These works can be considered as a good start for the most general scenario where data measured by a radar are contaminated by clutter and perfect knowledge of the basis matrix is not available.

3.7. Complexity analysis

Applying CS to radar and other systems, on one hand, reduces the volume of generated data and Nyquist sampling rate, but on the other hand, results in additional computational cost [24]. In some practical scenarios, the extra computational burden caused by CS reconstruction methods appears as a new design challenge. For example, when the number of sensors (network size) increases, this extra computational cost becomes prohibitive. Hence, finding low-complexity CS recovery methods has become one of the most popular topics in CS theory.

More recently, [25] introduced a general framework, called compressive signal processing, in which signal processing problems are solved directly in the compressive measurement domain. This methodology is in sharp contrast to the standard CS problem where full signals are first recovered from compressed measurements and then signal processing approaches are performed on the reconstructed signals. Applying such an interesting strategy enables us to take advantage of CS benefits without any extra cost. In the next Section, we will provide a similar compressive signal processing-based foundation for the localization of unknown sources.

4. Application of CS to localization

4.1. Introduction

Determining the location of unknown sources, often called localization, is an important problem in many different applications, sometimes as the first step toward solving more complicated tasks [26]. As stated in [27], a common approach to localize unknown sources in wireless systems is to collect the ranging information from radio signals traveling between the unknown source and a number of reference nodes. Usually, ranging information is measured based on one or more physical parameters of the radio signal, such as the time of arrival (TOA), time-difference-of-arrival (TDOA), received signal strength (RSS), and angle of arrival (AOA). Among these techniques, TOA-based range estimates are inherently more accurate than others, while the RSS-based is low-cost and easily implementable.

Localization of unknown sources is not possible unless the required number of reference nodes exist in the neighborhood of the unknown source. For example, in the 2-D case, at least three reference nodes are required for localization. Therefore, usually a network of reference nodes is utilized for the positioning of unknown sources in the area of interest. In such an architecture, all reference points send their ranging measurements to a special reference point, called Fusion Centre, which performs the localization.

In most practical cases, due to limitations such as low data-rate links between reference points and high network traffic, it is not possible to send all measurements to the Fusion Centre. This significantly affects the localization accuracy. To address these issues, some recent works have applied CS to localization; for example, see [28], and the references therein. Applying CS is a promising approach to handle the aforementioned problems since it significantly reduces the amount of data generated by reference nodes. However, the extra computational burden caused by CS reconstruction methods becomes prohibitive as the number of sensors (network size) and/or sampling rate (bandwidth) increases. Hence, the challenge is to find a low-complexity CS based framework for practical localization networks.

In the following, we focus on the TDOA-based localization scenario and develop a novel CS-based localization framework that estimates the TDOAs directly from CS measurements without reconstructing the full-scale signals. It is worth mentioning that the developed method solves the computational cost issue since it eliminates the reconstruction step. Although this approach is specially designed for TDOA-based localization, it can be developed for other applications.

4.2. TDOA-based localization

Typically, TDOA-based localization consists of three main steps:

• Step 1: All reference points (also known as observing receivers) send their collected samples to the Fusion Centre.

• Step 2: Fusion Centre estimates TDOAs between different reference points involved in the positioning of unknown sources.

• Step 3: Fusion Centre solves the equations that relate the unknown source position to the estimated TDOAs.

Therefore, estimating TDOAs is an essential first step for localization of unknown sources [29], and affects the accuracy of the positioning. Most practical localizers obtain TDOA estimates by cross-correlating the received signals from different reference points. This method is usually called generalized cross-correlation (GCC). However, large distances between reference points and Fusion Centre impose limitations on the data rate between the nodes [28]. Therefore, it is not possible to estimate TDOAs of all sensor pair combinations. This limitation reduces the accuracy substantially.

Some recent works employ CS to overcome the identified issues. The block diagram of this strategy is shown in Figure 3. In particular, reference points first apply the technique of CS on their observed samples and then transmit CS-based version of their collected samples to the Fusion Centre. Fusion Centre then applies one of the CS recovery methods on the received CS measurements to reconstruct the Nyquist samples from CS measurements sent by the reference points. Next, it estimates TDOAs by cross-correlating all reconstructed signal pairs. Although applying such a strategy significantly reduces the traffic of localization networks (the amount of data that need to be sent from the reference receivers to Fusion Centre), the reconstruction step introduces a prohibitive extra computational burden on the Fusion Centre. Also, it should be highlighted that all the existing recovery algorithms are subject to errors, especially in the presence of noise, interference, and clutter, which affect the accuracy of positioning. The above shortcomings motivate us to provide a new framework that addresses these important issues.

Figure 3.

Block diagram of CS-based TDOA localizer.

4.3. TDOA estimation without reconstruction

Consider the estimation of the TDOA between two $N\times 1$ vectors

$${\mathit{x}}_1={\left[x\left(0\right),\dots ,\mathrm{x}\left(\mathrm{N}-1\right)\right]}^T$$E17

and

$${\mathit{x}}_2={\left[x\left(D\right),\dots ,\mathrm{x}\left(\mathrm{D}+\mathrm{N}-1\right)\right]}^T$$E18

where D, an integer, is the TDOA between ${\mathit{x}}_1$ and ${\mathit{x}}_2\mathit{.}$

The circular cross-correlation of ${\mathit{x}}_1$ and ${\mathit{x}}_2$ will yield a peak at a correlation shift of D samples. Now with CS, the measurements become

$${\mathit{y}}_1=\mathbf{\Phi }{\mathit{x}}_1$$E19

and

$${\mathit{y}}_2=\mathbf{\Phi }{\mathit{x}}_2,$$E20

where ${\mathit{y}}_1\in R^M,{\mathit{y}}_2\in R^M,\mathbf{\Phi }\in R^{M\times N}$, and M < N. In general, the transformations $\mathbf{\Phi }{\mathit{x}}_1$ and $\mathbf{\Phi }{\mathit{x}}_2$ will break up the time-shift relationship between ${\mathit{x}}_1$ and ${\mathit{x}}_2$. A cross correlation of ${\mathit{y}}_1$ and ${\mathit{y}}_2$ will not give a peak at a shift of D. A common solution is to reconstruct ${\mathit{x}}_1$ and ${\mathit{x}}_2$ from (19) and (20), via CS reconstruction techniques. But the computations could be time-consuming and the reconstruction will have errors if noise is present.

A novel way to obtain CS measurements that preserve the time-shift relationship uses a $\mathbf{\Phi }$ that sums the elements of a vector. As an example, let M = 4, N = 16, and

$$\mathbf{\Phi }=\left[\mathbf{I}\right|\mathbf{I}\left|\mathbf{I}\right|\mathbf{I}]\mathbf{I}\in R^{M\times M}$$E21

where $\mathbf{I}\in R^{M\times M}$ is an identity matrix. Then, the elements of ${\mathit{y}}_1$ are

$$\begin{array}{l}{y}_1(0)=x(0)+x(4)+x(8)+x(12)\\ y_1(1)=x(1)+x(5)+x(9)+x(13)\\ y_1(2)=x(2)+x(6)+x(10)+x(14)\\ y_1(3)=x(3)+x(7)+x(11)+x(15)\end{array}$$E22

and for ${\mathit{y}}_2$

$$\begin{array}{l}{y}_2(0)=x(\text{D})+x(\text{D}+4)+x(\text{D}+8)+x(\text{D}+12)\\ y_2(1)=x(\text{D}+1)+x(\text{D}+5)+x(\text{D}+9)+x(\text{D}+13)\\ y_2(2)=x(\text{D}+2)+x(\text{D}+6)+x(\text{D}+10)+x(\text{D}+14)\\ y_2(3)=x(\text{D}+3)+x(\text{D}+7)+x(\text{D}+11)+x(\text{D}+15)\end{array}$$E23

Suppose D = 2, then, the circular cross correlation of ${\mathit{y}}_1$ and ${\mathit{y}}_2$ will peak at a shift of 2. In this example, $\mathbf{\Phi }$ has compressed the measurements from N = 16 to M = 4, and TDOA estimation is obtained directly from ${\mathit{y}}_1$ and ${\mathit{y}}_2$, without the need for reconstruction.

5. Conclusion

This chapter has introduced the concept and advantages of compressive sampling (CS). Applying CS to radar signals with a high bandwidth can significantly reduce the sampling rate and the power required by the Analog-to-Digital converter. It has also been shown that even when the transmitted signal and the basis matrix ψ are unknown, such as in passive radars and Electronic Warfare receivers, or when clutter with an unknown covariance matrix is present, CS can be used with Sparse Bayesian Learning to reduce the sampling rate and the amount of data generated. Finally, another application of CS to localization of unknown sources has been described. When estimating the TDOA between signals, using CS can reduce the data traffic between the reference points and Fusion Centre. Furthermore, a method to estimate the TDOA without reconstructing the signals at Fusion Centre has been developed to avoid the huge computational cost and possible errors that other CS-based techniques using reconstruction require.