Identifying Unused RF Channels
Using Least Matching Pursuit

In this paper, we improve upon the results of [13] in two ways: First, we develop a sufficient condition for which ZD-GroTH is guaranteed to identify zero (or unused) components; the condition depends on the dynamic range of the sparse signal, coherence properties of the sampling operator, and the noise power. Second, by inspecting our whitespace identification condition, we develop a refined “anti-CS” algorithm we call least matching pursuit (LMP). Our method improves upon ZD-GroTH by including a block orthogonal matching pursuit (BOMP) stage [14, 15], which reduces the dynamic range between non-zero signal components, and a refined correlation criterion, which improves sensitivity. To demonstrate the efficacy of LMP, we simulate a whitespace detection task in a realistic RF system that measures spectral features using nonuniform wavelet sampling (NUWS) [16], and we compare the performance of LMP to that of BOMP, ZF-GroTH, and a deep-learning based whitespace detector.

Uppercase boldface letters stand for matrices; lowercase boldface letters denote column vectors. For a matrix $\mathbf{A}$, we denote its Hermitian transpose by $\mathbf{A}^{H}$, its pseudo-inverse by $\mathbf{A}^{\dagger}$, and its $i$th block by $\mathbf{A}_{i}$, which is a collection of contiguous columns in $\mathbf{A}$. The $\ell_{2}$-norm (spectral norm) of a matrix $\mathbf{A}$ is $\|\mathbf{A}\|_{2}=\sigma_{\max}$, where $\sigma_{\max}$ is the largest singular value of $\mathbf{A}$. The $\ell_{2}$-norm of a vector $\mathbf{a}$ is $\|\mathbf{a}\|_{2}=\sqrt{\sum_{k}|a_{k}|^{2}}$.

To minimize the costs of sampling, we focus on CS-based acquisition schemes that acquire fewer measurements than the Nyquist rates dictates while exploiting signal sparsity in a given transform domain [17]. To model the fact that typical RF signals occupy frequency bands, we use a block-sparse signal model for which the signal components that are active or inactive appear in contiguous groups [14, 15].

Mathematically, we assume a discretized signal $\mathbf{x}\in\mathbb{C}^{N}$ that consists of $B$ blocks $\mathbf{x}_{i}\in\mathbb{C}^{N_{i}}$, where $i=1,\ldots,B$, $\sum_{i=1}^{B}N_{i}=N$, and $\mathbf{x}=[\mathbf{x}_{1}^{H},\ldots,\mathbf{x}_{B}^{H}]^{H}$. For RF whitespace detection, each block $\mathbf{x}_{i}$, $i=1,\ldots,B$, represents a contiguous band of discrete frequencies. In what follows, we assume that the signal $\mathbf{x}$ is $K$-block-sparse, meaning that exactly $K$ blocks are nonzero. CS-based signal acquisition is modeled by the input-output relation $\mathbf{y}=\mathbf{A}\mathbf{x}+\mathbf{n}$, where $\mathbf{y}\in\mathbb{C}^{M}$ contains the compressive measurements with $M\ll N$, $\mathbf{A}\in\mathbb{C}^{M\times N}$ is the effective sensing matrix (which combines the effect of the sensing matrix and the sparsifying transform), and $\mathbf{n}\in\mathbb{C}^{M}$ models measurement noise. To simplify notation, we can write an equivalent system model $\mathbf{y}=\sum_{i\in\mathcal{U}}\mathbf{A}_{i}\mathbf{x}_{i}+\mathbf{n}$, where $\mathbf{A}_{i}\in\mathbb{C}^{M\times N_{i}}$ is the $i$th block matrix of the effective sensing matrix $\mathbf{A}=[\mathbf{A}_{1},\ldots,\mathbf{A}_{B}]$ and $\mathcal{U}$ denotes the set of indices corresponding to the non-zero blocks in the vector $\mathbf{x}$.

In practice, CS measurements are acquired by computing inner products between the uncompressed signal, written by $\mathbf{z}=\mathbf{\Psi}^{-1}\mathbf{x}$ where $\mathbf{\Psi}\in\mathbb{C}^{N\times N}$ is a sparsifying transform, and rows of the sensing matrix $\mathbf{\Uptheta}\in\mathbb{C}^{M\times N}$ using analog circuitry. The effective sensing matrix is $\mathbf{A}=\mathbf{\Uptheta}\mathbf{\Psi}^{-1}$ and each block matrix is given by $\mathbf{A}_{i}=\mathbf{\Uptheta}\mathbf{\Psi}^{-1}_{i}$, where $\mathbf{\Psi}^{-1}_{i}\in\mathbb{C}^{N\times N_{i}}$ is the $i$th block of the inverse sparsifying transform so that $\mathbf{\Psi}^{-1}=[\mathbf{\Psi}^{-1}_{1},\ldots,\mathbf{\Psi}^{-1}_{B}]$. For RF whitespace detection, $\mathbf{z}$ is the Nyquist-sampled time-domain signal, $\mathbf{\Psi}$ is the discrete Fourier transform (DFT) matrix (as we assume block-sparsity in the frequency domain), $\mathbf{\Uptheta}$ is a suitably-chosen sensing matrix (see \frefsec:nuws for the sensing matrix used in our experiments), and $\mathbf{y}$ contains the $M$ compressive measurements

A prime goal of CS is to recover the nonzero (or used) blocks $\mathbf{x}_{i}$, $i\in\mathcal{U}$, in the vector $\mathbf{x}$ from the CS measurements in $\mathbf{y}$ using block-sparse signal recovery algorithms [14]. In contrast, whitespace detection aims at detecting unused blocks, i.e., the blocks indexed by the set $\mathcal{N}=\{i=1,\ldots,N\mid\|\mathbf{x}_{i}\|_{2}=0\}$. For noiseless measurements, one could first run a block-sparse signal recovery algorithm to identify the used blocks and then label all other blocks as unused. The presence of noise, however, renders it extremely challenging to distinguish noise from weak signal components—the situation is further aggravated by the fact that most (block) sparse signal recovery algorithms shrink weak signals to zero. Even though our goal is not to detect strong signals, we now briefly summarize BOMP, a prominent block-sparse signal recovery method. As shown in \frefsec:LMPsec, we will use BOMP as a preprocessing step to improve CS-based whitespace detection.

BOMP is an iterative block-sparse signal recovery algorithm put forward in [15]. The algorithm starts by initializing the so-called residual by $\mathbf{r}^{0}=\mathbf{y}$. At each iteration $t=1,\ldots,K$, BOMP first calculates a normalized correlation between the residual $\mathbf{r}^{t}$ and each block $\mathbf{A}_{i},\,\forall i\in\mathcal{B}$ according to

Note that, compared to [15], we use a modified correlation criterion that uses the term $(\mathbf{A}_{i}^{H}\mathbf{A}_{i})^{-0.5}$, which does not require the blocks to have orthonormal columns. Next, BOMP selects the index of the block with the highest correlation according to $c^{t+1}=\operatorname*{arg\;max}_{i}\lambda_{i}^{t+1}$ and adds the selected block to the support set ${\Omega}^{t+1}={\Omega}^{t}\,\cup\,{c^{t+1}}$. BOMP then computes an estimate $\hat{}\mathbf{x}_{\Omega^{t+1}}$ of the non-zero blocks $\hat{\mathbf{x}}=\mathbf{A}_{\Omega^{t+1}}^{\dagger}\mathbf{y}$, where $\mathbf{A}_{\Omega^{t+1}}$ contains the blocks indexed by the support set estimate $\Omega^{t+1}$. Finally, BOMP updates the residual according to $\mathbf{r}^{t+1}=\mathbf{y}-\mathbf{A}_{\Omega^{t+1}}\hat{\mathbf{x}}_{\Omega^{t+1}}$. See Algorithm 1 for the pseudocode of BOMP.

The ZD-GroTh algorithm [13] identifies the block $\mathbf{A}_{i}$ that minimizes the correlation with the received signal as

In contrast to the original method in [13], we use the selection criterion in \frefeq:antiomp that enables the use of unnormalized blocks. While [13] provides statistical guarantees for the success of ZD-GroTh, we next propose a sufficient condition for the success of ZD-GroTh that depends on the dynamic range of the block-sparse signal, the effective sensing matrix, and the power of the measurement noise. In what follows, we will make use of the following definitions:

We can now formulate the following sufficient condition for the success of ZD-GroTh. The proof is given in \frefapp:bomp.

Proposition 1 is useful to understand conditions for which we can identify an unused block via ZD-GroTh. For the special case where (i) the blocks $\mathbf{A}_{i}$, $i=1,\ldots,B$ have orthonormal columns, (ii) all the used signal blocks have equal power, i.e., $\|\mathbf{x}_{i}\|=\|\mathbf{x}_{j}\|$ for $i\neq j$ and $i,j\in\mathcal{U}$, (iii) and for noiseless measurements, we recover the standard BOMP condition $K<\frac{1}{2}\left(\mu_{B}^{-1}+1\right)$ from [15]. For the general case, it is clear that the dynamic range between strong signal components and the weakest one $\mathbf{x}_{\min}$ plays a critical role in the success of this method, i.e., the ratio $\delta=\frac{\sum_{j\in\mathcal{U}}\|\mathbf{x}_{j}\|_{2}}{\|\mathbf{x}_{\min}\|_{2}}$ on the LHS of \frefeq:prop1 should be as small as possible¹¹1This ratio is lower-bounded by the block-sparsity $K$, which is achieved with equality if all active signal components have equal power.. This observation enables us to design the following improved algorithm for detecting unused blocks from CS measurements.

Inspired by the above observation, we minimize the detrimental effect of high dynamic range $\delta$ of active signal components by first eliminating the strongest active sparse blocks and then invoke a variant of the minimum correlation condition in \frefeq:antiomp; this can be accomplished by first running BOMP for $P$ iterations (typically $P\leq K$) followed by selecting the least correlated block from the resulting residual $\mathbf{r}^{P+1}$. However, by directly using \frefeq:antiomp on the residual, we ignore correlation information that has been acquired during all BOMP iterations. To this end, we also refine the selection criterion by considering the sum of all correlation coefficients over the $P$ BOMP iterations and select the block with the smallest sum. This approach effectively avoids the selection of blocks that had small correlation only in the last iteration of BOMP but had consistently low correlation before. Concretely, we propose to use the following refined selection criterion:

Here, the correlation results $\{\lambda^{t+1}_{i},i=1,\ldots,B\}_{t=1}^{P}$ have been collected while running BOMP as detailed in Algorithm 1. The resulting whitespace detection method, called least matching pursuit (LMP), is summarized in Algorithm 2.

Non-uniform wavelet sampling (NUWS) has been proposed in [16] as a flexible and hardware-friendly compressive sensing strategy for RF sensing [18] and feature extraction tasks [19]. In short, NUWS combines the advantages of nonuniform sampling [9] and random modulation [20]. Mathematically, NUWS takes inner products between the analog signal and wavelet-like pulses $\mathbf{w}(\tau,\rho,f)\in\mathbb{C}^{N}$, which can be tuned in terms of the time instant $\tau$, pulse width $\rho$, and frequency $f$. The tunability of NUWS enables one to adapt the sequence of wavelets to the task at hand. For our RF sensing application, we consider Haar-like wavelets [19] with entries in $\{+1,0,-1\}$ that can easily be generated with mixed-signal circuitry [18].

In order to adapt the sensing matrix to our application, we first construct an overcomplete dictionary $\mathbf{W}\in\mathbb{C}^{L\times N}$ whose rows consists of a large number of different wavelet sequences $\{\mathbf{w}(\tau_{l},\rho_{l},f_{l})\}_{l=1}^{L}$ with $L\gg N$. We then select a subset of $M$ wavelets so that the effective sensing matrix $\mathbf{A}=\mathbf{R}_{\Omega}\mathbf{W}$ has desirable properties. Here, $\mathbf{R}_{\Omega}$ is a restriction operator that selects a subset of $M$ sequences from the dictionary $\mathbf{W}$. Subset selection is carried out so that the resulting block mutual coherence $\mu_{B}$ in \frefeq:mu_block is minimized. Since this subset selection problem is of combinatorial nature, we use a greedy approach. We start with an empty set of wavelet sequences. We then calculate the block mutual coherence $\mu_{B}$ for each of the $l=1,\ldots,L$ wavelet sequences in $\mathbf{W}$ and keep the sequence associated with the lowest $\mu_{B}$. We repeat this greedy procedure until $M$ wavelets have been collected.

To demonstrate the efficacy of LMP in a realistic scenario, we model a complete RF transmitter and receiver chain in MATLAB; see \freffig:model for an overview. We generate $20$ frequency bands between $2.4$ GHz and $2.5$ GHz and assume that at most five transmitters in five bands are active at a time. We randomly place the transmitters within a distance of $1$ m and $280$ m from the receiver and use the path-loss model from [21]. At the transmitter, we generate a $5$ MHz QPSK signal that is mixed with a carrier that is randomly selected among the 20 uniformly spaced channels. The $20$ dBm signal is then transmitted over an antenna at height $1.65$ m.

At the receiver side, we collect the signals at an antenna at height $15$ m with an antenna gain of $10$ dBi. The signal is then passed through a low-noise amplifier (LNA) followed by a intermediate frequency mixer operating at $2.45$ GHz. We model LNA and mixed non-linearities using first, third, and fifth harmonics at $50$ Ohm impedance, $-1$ dB gain compression, and a third-order intercept point of $10$ dBm. Phase noise at the mixers is simulated using Leeson’s model [22] with $1$ MHz carrier frequency offset at $-110$ dBc. For the voltage gains of mixers and the LNA, we use $8$ dB and $20$ dB respectively, and we use a noise figure of $5$ dB for both the mixer and LNA. We add thermal noise to the signal both at the transmitter before the mixer and at the receiver before LNA operating at $290$ K. We then perform NUWS on the output signal of the RF receiver using the wavelet dictionary described in \frefsec:nuws by taking a maximum of $N=200$ Nyquist samples.

We show simulation results for $M=50$, $M=100$, and $M=150$ NUWS measurements (corresponding to compression ratios of $1/4$, $1/2$, and $3/4$) that are obtained by performing $50,000$ Monte-Carlo trials, which randomize transmitter location, spectrum occupancy, transmit signals, and noise. Figures 2a, 2b, and 2c show the resulting error rates vs. average signal-to-noise ratio (SNR) over all active transmitters. Errors are declared whenever we decide a channel was unused but the channel was occupied by a transmitter. Black dashed lines show the baseline error rate for randomly selecting an unused channel; blue dashed lines show the error rate of using all the $N=200$ Nyquist samples and analyzing the signal power in the discrete Fourier domain. Green dashed lines show the error rate of a feedforward neural network (NN) with four hidden layers, each having $1024$, $512$, $256$, and $128$ neurons with rectified linear unit (ReLU) activation functions. We train the NN from 200,000 examples. Purple dashed lines show the error-rate of BOMP with $K=19$ iterations which leaves one channel left that we declare as unused and red solid lines show the error rate of ZD-GroTh as in (2). Orange solid lines show the error rate of the proposed LMP algorithm with $P=4$.

We observe that both ZD-GroTh and LMP consistently achieve lower error rate than BOMP and the NN-based whitespace detector, even though the neural network has been retrained for each SNR. Furthermore, we see that at moderate SNR values ($\textit{SNR}\geq 5$ dB), LMP outperforms ZD-GroTh. At low SNR ($\textit{SNR}<5$ dB), performing NUWS on 200 time samples is insufficient to achieve low error rates. If lower error rates are desirable, more samples have to be acquired—the same observation applies to the Nyquist-based approach.