## 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.

### Keywords

- analog-to-digital converter (ADC)
- blind detection
- clutter
- compressive sampling (CS)
- compressive sensing (CS)
- localization
- radar
- time-difference of arrival (TDOA)

## 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** **y**

where *M* < < *N*. It has been demonstrated that the proper selection of the measurement matrix

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

where *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:

where *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 **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 **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 **s** has only non-zero elements at positions 3 and 5.

There are mathematical conditions on *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

### 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 **s** decreases.

To see this, suppose *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 *M,* for perfect reconstruction, to the coherency (a numerical number) of *M* is.

### 2.3. Restricted isometry property (RIP)

For

with

Notice that the isometry is the length of a vector. The inequality (4) limits the amount by which Euclidean distance **s** from **y**. Note that **s** is in the null space of *K*-sparse vector **s** and **s-***K*. To be able to distinguish **s** from

i.e., any 2 *K* columns of

The upper bound is necessary to keep the lower bound meaningful. Otherwise,

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

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

where **s** from **y** will yield additional errors due to

### 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

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 **x**(t) and PRBS, then resets and repeats. We have:

where

## 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

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

Then,

where *x*(t). For our purposes, it is more convenient to write (3) in matrix form as:or, equivalently, as (excluding noise):

where

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: **x** is sparse. Taking into account the noise (denoted by **e**),

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

### 3.4. Blind compressive sampling

In some radar scenarios, knowledge of the basis matrix

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

The above-mentioned scenarios motivated us to study the CS problem for the case where perfect knowledge of the basis matrix **s** from measurements **y** obtained from

### 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

where

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

### 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., **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

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.

### 4.3. TDOA estimation without reconstruction

Consider the estimation of the TDOA between two

and

where *D*, an integer, is the TDOA between

The circular cross-correlation of *D* samples. Now with CS, the measurements become

and

where *M* < *N*. In general, the transformations *D*. A common solution is to reconstruct

A novel way to obtain CS measurements that preserve the time-shift relationship uses a *M* = 4, *N* = 16, and

where

and for

Suppose *D* = 2, then, the circular cross correlation of *N* = 16 to *M* = 4, and TDOA estimation is obtained directly from

## 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.