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.
- analog-to-digital converter (ADC)
- blind detection
- compressive sampling (CS)
- compressive sensing (CS)
- time-difference of arrival (TDOA)
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
where is the measurement matrix with
During the last decade, CS has been successfully applied in many applications, such as image processing , wireless sensor networks and communication networks . Although some recent works have studied the application of CS to radar and localization , 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 can be represented as:
where is a full rank, orthonormal basis matrix, sometimes also known as the basis matrix , and the vector has
where is called the sensing matrix. Since
This means that instead of measuring the
In general, (3) has no unique solution since it has more unknowns (
There are mathematical conditions on , and the numbers of measurements
2.1. Number of measurements
Choosing the number of measurements
From (3), it is seen that the elements of
To see this, suppose has a column, say the
2.3. Restricted isometry property (RIP)
For the RIP requires that for perfect reconstruction, must satisfy the inequality
Notice that the isometry is the length of a vector. The inequality (4) limits the amount by which Euclidean distance can differ from The lower bound in (4) ensures a perfect recovery. Suppose but . This violates the lower bound of (4). Indeed, if , we cannot recover
i.e., any 2
The upper bound is necessary to keep the lower bound meaningful. Otherwise, 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
Checking if a chosen satisfies the RIP criteria is computationally expensive and cannot be realized in practice. It has been shown in  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
where represents an unknown noise vector. Recovering
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) .
where contains elements of . Hence, the sampling rate is reduced by a factor of 13, as is the number of samples, i.e.,
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).
Radar (radio detection and ranging) systems are present in many different civilian, military, and biomedical applications . 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 .
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 . 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 . 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 . 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  just focused on the simple SISO radar scenario. Then, Chen and Vaidyanathan in  extended the work in  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
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, in (10) can be represented as
where and are simply the Nyquist samples of the input signal
where , , and . Thus, CS reduces the sampling rate to , which is much lower than the Nyquist rate .
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.
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 and basis 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 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 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)  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 is not available (is completely unknown or noisy). This interesting scenario can be referred to as the blind CS problem . In summary, the blind CS problem aims to recover the sparse vector
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 represents the clutter. As stated in , merging the clutter and the additive (unstructured) noise components allows us to address this kind of problems. However, it is important to highlight that merging the noise and the clutter components 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 , 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
To be more precise, the ultimate goal is to determine the non-zero elements of vector
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., , only two unknowns exist: sparse vector and
Applying a probabilistic approach seems to be the best method to efficiently handle these complex problems. As mentioned in , 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 .
Sparse Bayesian Learning (SBL), which was first proposed by Tipping , 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  and the references therein. Having noticed the benefits of SBL,  has recently applied SBL to EW receiver design. Also,  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 . 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,  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
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 . As stated in , 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 , 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 , 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 . 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 vectors
The circular cross-correlation of and will yield a peak at a correlation shift of
where , and
A novel way to obtain CS measurements that preserve the time-shift relationship uses a that sums the elements of a vector. As an example, let
where is an identity matrix. Then, the elements of are
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