# An Active Sequential Xampling
Detector for Spectrum Sensing

Lorenzo Ferrari, and Anna Scaglione L. Ferrari and A. Scaglione
<EMAIL_ADDRESS>are with the School of Electrical,
Computer and Energy Engineering, Arizona State University, Tempe, AZ, 85281,
USA.This work was supported in part by the National Science Foundation
CCF-247896 grant.

###### Abstract

Nyquist sampling at very high carriers can be prohibitively costly for low
power wireless devices. In spectrum sensing, this limit calls for an analog
front-end that can sweep different bands quickly, in order to use the
available spectrum opportunistically. In this paper we propose a new sub-
Nyquist analog front-end and a sensing strategy formulated as a sequential
utility optimization problem. The sensing action maximizes a utility function
decreasing linearly with the number of measurements, and increasing as a
function of the active spectrum components that are correctly detected. The
optimization selects the best linear combinations of sub-bands to mix, in
order to accrue maximum utility. The structure of the utility represents the
trade-off between exploration, exploitation and risk of making an error, that
is characteristic of the spectrum sensing problem. We first present the analog
front-end architecture, and then map the measurement model into the abstract
optimization problem proposed, and analyzed, in the remainder of the paper. We
characterize the optimal policy, under constraints on the sensing matrix, and
derive the approximation factor of the greedy approach we introduce to solve
the problem. Numerical simulations showcase the benefits of combining active
spectrum sensing with sub-Nyquist sampling.

##  I Introduction

Mobile devices are increasingly being used for entertainment (gaming, video
streaming): the coexistence of these new services with the “Internet of
Things” (IoT) and Machine-to-Machine (M2M) communications means that wireless
applications may quickly become starved for bandwidth. Millimeter wave bands
can provide the much needed linear increase in throughput, but pose the
challenge of high speed sampling, required to sense the spectrum, for many
relatively low rate IoT applications, which are likely to benefit from
opportunistic decentralized spectrum access.In order to achieve efficient
usage of the spectrum, when a large portion is potentially available, we need
to overcome the bottleneck of Nyquist sampling, which can be prohibitive,
especially for low power wireless devices.

The literature offers two classes of solutions to eliminate this bottleneck: a
static sub-Nyquist sampling front-end or a tunable narrowband coupled with
active sensing strategies.

The static sub-Nyquist sampling approach is based on the representation of the
signal as a nonlinear Union of Subspaces (UoS) [1]. A common framework to
cover several acquisition and reconstruction approaches under the umbrella of
the UoS model was defined in [2], which named these analog to digital
conversion techniques Xampling architectures. Xampling architectures
preprocess the signal in the analog domain, and then sample at a lower rate
compared to what the Nyquist theorem dictates. The aim is to reduce the
complexity and energy cost for the Analog-to-Digital Converter (ADC) hardware.
The downside is the increased complexity in the reconstruction of the
underlying signal. Our work focuses on multiband signals, whose UoS
representation is a finite union of subspaces with infinite, but countable
dimensions, in the space spanned by orthogonal sinc functions. Examples of
Xampling architectures for multiband signals are in e.g. [3, 4, 5, 6]. There
are other Compressive Spectrum Sensing (CSS) algorithms in the literature that
are related. Typically, they start directly from a discrete time model (see
e.g. [7, 8]) where the receiver has a fixed number of measurements, forming an
underdetermined system of equations, whose solution is a sparse vector with
support equal to the spectrum occupancy.

The second set of approaches is fully adaptive and consists in selecting
opportunistically, and in a cognitive fashion, a small section of the spectrum
at a time, relying on an analog front-end able to swiftly switch between small
sub-bands. The problem choosing optimally the band to explore was studied by
several authors, see e.g. [14, 15, 16] and our previous work [17] that also
focuses on single band tests. Note that tests that alias the spectrum create
correlation in the resources, and this is why our formulation departs from the
Partially Observable Markov Decision Processes (POMDPs) models used in
previous works for single band tests. More recently, other authors have
proposed and studied sensing strategies that would reduce the required number
of CSS measurements to the sparsity of the signal. The work in [18] has a
predetermined sensing phase duration, while [19] introduces an analog
preprocessing which guarantees satisfactory detection performance,
irrespective of the sparsity of the signal, as long as the measurement phase
is proportional to the average occupancy. Our contribution and motivation is
discussed next.

###  I-A Contributions

Our main contribution is a new dynamic optimization framework married with the
design of the active sub-Nyquist spectrum sensing frontend.

We provide two arguments to study alternatives to Xampling (or to the
aforementioned CSS methods) previously studied. First, in the spectrum sensing
problem, the objective is the detection of the idle channels, not the signal
reconstruction: this suggests that the Xampling complexity may still exceed
what is really necessary for this task, as previously discussed in [9].
Additionally, most of the standard results in Compressive Sensing (CS), that
bound the $\ell_{2}$-norm of the estimation error, do not directly express the
detection performance. The architecture studied in this paper has the
advantage of being sequential, requiring incoherent observations and being
robust to time inaccuracies in the sampling hardware, as opposed to e.g. the
multi-coset approach in [6]. For the spectrum sensing detection problem, the
additive noise at the receiver plays an important role in the performance of
interest. Hence, rather than focusing on reconstruction in noiseless
scenarios, in this paper we directly tackle the so called noise folding
problem in the design [10]. Noise folding gives a Signal-to-Noise Ratio (SNR)
deterioration approximately linear in the number of bands that are aliased
prior to sampling [10]. This can cause poor performance for several Xampling
approaches at low SNR. As discussed in [11], low density measurement matrices
represent an effective countermeasure to noise folding. Additionally sparse
matrices enable belief propagation techniques (i.e. message passing) for
signal recovery (or detection in our context) that lead to state of the art
performance, in spite of the poor conditioning of the sensing matrices.

Second, to the best of our knowledge, receivers in the Xampling family that
are in the literature (see e.g. [3, 4, 5, 6, 12, 13, 9]) do not fall in an
active sensing framework, as they are not married to an online optimization of
the measurement strategy. Hence, that can have a limitation: if the spectrum
is not sufficiently sparse, neither the signal reconstruction, nor the
detection of its presence in a certain band, can be accurate, even in the
absence of noise. In fact, for general non-sparse signals, in a noiseless
setting, [9] proved that half the Nyquist rate is necessary (see also [12, 13]
for related discussions).

In contrast to Xampling architectures used for multi-band signals (e.g. the
Modulated Wideband Converter (MWC) in [5], the Multirate Asynchronous Sub-
Nyquist Sampler (MASS) in [25] and also [24]), our CSS sequential architecture
only needs a single mixer, with a programmable analog waveform and Low Pass
Filter (LPF). In our optimization framework, the Cognitive Receiver (CR) needs
to select what group of sub-bands (generally non-contiguous) to sense at each
test. A test corresponds to a sample, obtained after folding different sub-
bands of the wide-spectrum signal. Compared to other multi-band signals
receivers, the hardware in our architecture is simpler, since we use a single
non-coherent receiver and a single sampling device that collects energy
measurements sequentially, sampling at a fraction of the Nyquist rate.We use a
time-dependent utility function to optimize the trade-off between sensing and
exploitation.

It is important to remark that, similarly to [14, 15, 16, 17] and [24], the
optimum action will not generally attempt the full recovery of all the white
spaces. In fact, the optimum decision may be conservative and sense a very
limited portion of the spectrum. Furthermore, since scanning one sub-band at a
time is a possible action of our active spectrum sensing strategy, our method
subsumes previous techniques to scan the spectrum optimally, without mixing
it. We refer to this approach as that of Direct Inspection (DI) and discuss it
in Section IV-A.

Our work is more closely related with the stochastic optimization schemes that
extend the framework in [14, 15, 16], and optimize a CSS action based on
previous observations [20, 21, 22, 23, 24]. With the exception of [24], the
common goal in these papers is the recovery of the full support of a given
vector. Typically, the techniques proposed are shown to be able to cope with
lower SNR in the signal reconstruction with low complexity. What these
optimizations do not capture is the fact that, in cognitive spectrum sensing
applications, a timely decision is also desirable, to have enough time to
exploit the spectrum.  In fact, our method is also adaptive with respect to
the time horizon $K$, the number of resources $N$, the prior probabilities on
the states of each resources, and the parameters that characterize the utility
function (i.e. reward/penalty for good/bad decisions). Interestingly, from our
performance analysis, it is clear that sparse and adaptive sensing matrix
designs outperform dense sensing matrices, as well as those that are sparse,
but static. There are two main reasons for this: 1) through belief propagation
algorithms, they achieve near-optimum detection performance; 2) they mitigate
the aforementioned noise folding phenomena. We also emphasize in the paper
that our model is applicable not only when the utility comes from finding
empty entries (e.g. spectrum sensing), but also when one is interested in
finding the occupied ones (e.g. in a RADAR application).

More specifically, the paper is organized as follows: Section II is dedicated
to the signal model and the analog front-end of our detector, and in Section
III we formulate the optimization problem. Then, in Section IV we study the
optimal dynamic design, for the Direct Inspection (DI) case (IV-A), where
there is no mixing of sub-bands (also known as scanning receiver), and a Group
Testing (GT) case (IV-B), where we introduce the possibility of mixing
different bands. We will show that, even if finding the optimal policy is
exponentially complex in the number of resources, we can characterize the
approximation factor for a greedy procedure. Section V is dedicated to
alternative detection approaches: linearization of Maximum Likelihood (ML)
estimate and covariance estimation via LASSO relaxation. Numerical results to
sustain our claims are presented in Section VI.
Notation We use bold lower-case to represent vectors, bold upper-case for
matrices and calligraphic letters to indicate sets. With
$\mathbf{s}_{\mathcal{A}}$ we indicate the entries $i\in\mathcal{A}$ of vector
$\mathbf{s}$, and with $\|\mathbf{y}\|_{\mathbf{A}}^{2}$ we represent the
weighted $\ell_{2}$-norm $\mathbf{y}^{T}\mathbf{A}\mathbf{y}$. For any set
function $f(\mathcal{A})$ we define the marginal increment for adding element
$a$, as $\partial_{a}f(\mathcal{A})=f(\mathcal{A}+a)-f(\mathcal{A}).$

##  II Xampling Detector

In the context of spectrum sensing for cognitive radio, in addition to the
payload, each transmission includes large amounts of control signals overhead.
It is then natural to assume that the activity of the Primary Users (PUs), in
a certain spectrum, will persist for several sampling periods (see Fig.1).

Figure 1: Cognitive radio scenario

However, assuming this interval lasts $T=KT_{s}$, the sensing  mechanism
should provide the fastest decision it can. The goal of the proposed cognitive
receiver is to sequentially sense the spectrum for the first portion of the
interval and transmit the most it can during the remaining time,  over the
sub-channels found empty.

###  II-A Sensing Architecture and Observation Model

We assume that the complex envelope of the analog signal we are exploring is a
multicomponent signal, with overall bandwidth equal to $W=NR_{s}$. The
components are indexed by $i\in\mathcal{N}$, where
$\mathcal{N}\triangleq\\{1,2,\dots,N\\}$. The elements of the binary vector
$\mathbf{s}=\\{s_{i}:i\in\mathcal{N}\\}\in\\{0,1\\}^{N}$ indicate presence (1)
or absence (0) of a component (i.e. Primary User (PU) communication signal)
over the $i$-th sub-band. During the interval $0\leq t<T=KT_{s}$ the received
signal is:

$\displaystyle y(t)$ $\displaystyle=x(t)+w(t)$ (1) $\displaystyle x(t)$
$\displaystyle=\sum_{i=1}^{N}s_{i}x_{i}(t)e^{-j2\pi R_{s}(i-1)t}.$ (2)

with $w(t)\sim{\cal N}(0,N_{0}\delta(\tau))$ being Additive White Gaussian
Noise  (AWGN). The components of the received signals $x_{i}(t)$ correspond to
each PU source, modeled as band-limited random processes with bandwidth
$R_{s}$; they are equal in the mean square sense to the following process:

$x_{i}(t)=\sum_{k=1}^{K}x_{i}[k]sinc(\pi(R_{s}t-k+1)).$ (3)

Rather than having a filter bank architecture as in [24], to further reduce
the hardware complexity, we base our scheme on a sequential non-coherent
sampling architecture.

Figure 2: Sequential Xampling detector hardware architecture. The inputs of
the $L$ Voltage Controlled Oscillators (VCOs) are voltage levels proportional
to the position of the non-zero entries of the vector $\mathbf{b}_{k}$, to
switch and recenter their frequency at the corresponding multiple of $R_{s}$,
according to the prescribed sensing action.

As the diagram in Fig. 2 shows, the sequential receiver we propose first
modulates the received signal over the period $(k-1)T_{s}\leq t<kT_{s}$ with a
signal $g_{k}(t)$, synthesized by selecting an appropriate input to the $L$
VCOs. More specifically, if we denote by ${\cal A}_{k}\subset{\cal N}$ the
subset of $|{\cal A}_{k}|\leq L$ sub-band mixed in the sample for the $k$th
test, we have:

$\displaystyle g_{k}(t)$ $\displaystyle=\sum_{i=1}^{N}a_{ki}e^{j2\pi
R_{s}(i-1)t},$ (4) $\displaystyle a_{ki}$ $\displaystyle=\sum_{u\in{\cal
A}_{k}}\sqrt{b_{ku}}e^{j\phi_{ku}}\delta[i-u].$ (5)

where, as shown in (5), only $|{\cal A}_{k}|\leq L$ tones are activated, and
the phase $\phi_{ku}$ in (4)-(5) accounts for the delay in generating the tone
at the $u$-th frequency included in ${\cal A}_{k}$ plus the oscillator phase,
while $\sqrt{b_{ki}}$ is the amplitude. The optimal choice of the set ${\cal
A}_{k}$ is the subject of Section III. Correspondingly, for our incoherent
detector, the sensing vector coefficients $b_{ki}$ (that is, the $k$th row of
the sensing matrix ${\mathbf{B}}$), associated to the $k$th sample, are:

$b_{ki}=|a_{ki}|^{2}=\sum_{u\in{\cal A}_{k}}b_{ku}\delta[i-u]$ (6)

irrespective of the random phase $\phi_{ku}$ of the VCO tones activated.
Clearly, if $L\ll N$, ${\mathbf{B}}$ is a sparse matrix. Then, after
convolving the modulated signal with an ideal low-pass filter, with impulse
response $sinc(\pi R_{s}t)$, the receiver samples the output $c(t)$ at times
$kT_{s},~{}k=1,\ldots,\kappa$. This operation is equivalent111If the periodic
signals where not truncated in time the relationship would be exact, in
practice there will be some approximation error due to the windowing of the
signal over the prescribed interval $[(k-1)T_{s},kT_{s}]$. The effect of this
can be mitigated by using raised cosine filtering and a non rectangular window
to reduce the effect of side lobes.  to an orthogonal projection, as shown
below:

$\displaystyle c[k]$ $\displaystyle=\left.[y(t)g_{k}(t)]\star R_{s}sinc(\pi
R_{s}t)\right|_{t=kT_{s}}=\sum_{i=1}^{N}\sqrt{b_{ki}}e^{j\phi_{i}}Y_{ki}$ (7)

where $Y_{ki}$ represent the orthogonal projections over the period
$(k-1)T_{s}\leq t<kT_{s}$ of $y(t)$ over the following signals:

$Y_{ki}=\langle y(t),R_{s}e^{j2\pi
R_{s}(i-1)t}sinc\left(\pi\left(R_{s}t-k+1\right)\right)\rangle.$ (8)

Note that the signals

$\left\\{e^{j2\pi
R_{s}(i-1)t}sinc\left(\pi\left(R_{s}t-k+1\right)\right)\right\\}_{i,k\in\mathbb{Z}}$

form a orthogonal basis, and that (1) is equivalent to:

$\displaystyle x(t)$
$\displaystyle=\\!\\!\sum_{k=1}^{K}\sum_{i=1}^{N}s_{i}x_{i}[k]e^{j2\pi
R_{s}(i-1)t}sinc(\pi(R_{s}t-k+1))$ (9) $Y_{ki}=s_{i}x_{i}[k]+w_{i}[k]$ (10)

where $w_{i}[k]\sim{\cal CN}(0,n_{i})$. If we model $x_{i}[k]$ also as i.i.d.
$x_{i}[k]\sim{\cal CN}(0,\varphi_{i})$, we get that for a given state
$\mathbf{s}$:

$Y_{ki}\sim{\cal CN}(0,s_{i}\varphi_{i}+n_{i}).$ (11)

where $\boldsymbol{\varphi}$ is a vector collecting the average, unknown a
priori, received signal power from the existing communications. The receiver
samples for $k=1,\ldots,\kappa$ are:

$\displaystyle c[k]$
$\displaystyle=\sum_{i=1}^{N}\sqrt{b_{ki}}e^{j\phi_{i}}\left(s_{i}x_{i}[k]+w_{i}[k]\right)$
(12)

and therefore, assuming $\phi_{i}$’s are independent and uniformly distributed
in $[0,2\pi)$, they are also conditionally zero mean Gaussian random
variables:

$\displaystyle c[k]$ $\displaystyle\sim{\cal CN}\left(0,\theta[k]\right),$
(13) $\displaystyle\theta[k]$
$\displaystyle=\theta(\mathbf{b}_{k},\mathbf{s})\triangleq\mathbf{b}_{k}^{T}\left(\boldsymbol{\varphi}+\boldsymbol{n}\right).$
(14)

It follows that the information for the detection of the PU communications is
embedded in the variance of the sample (which is the energy received during
the $k$-th period). Sufficient statistics for our problem are:

$y[k]\triangleq|c[k]|^{2}$ (15)

which are exponentially distributed, i.e. $y[k]\sim Exp(\theta[k])$.
222Throughout the paper we will use, for convenience, the alternative
parameterization for the exponential distribution, e.g.
$f(k;\theta)=\frac{1}{\theta}e^{-\frac{x}{\theta}}u(x)$.

###### Remark 1

The signals are subject to linear distortion due to a multi-path channel. For
the case of Rayleigh narrowband fading and digital modulations, such as PSK
with constant amplitudes, the model is correct, but it is only an
approximation in other cases. Also, it  would be appropriate to include a
certain correlation among the samples $x_{i}[k]$ in the case of a frequency
selective channel. We do not consider it, given the generalization is
straightforward and the opportunistic strategy is a viable sub-optimum
solution for that case as well. Finally it is useful to remark that,
irrespective of the statistics of the received signal from the PUs, the
variance of the samples $c[k]$ will have the same expression, which makes the
energy detector a viable heuristic in general.

Our work will investigate the design of:

  1. 1.

the $\kappa\times N$ measurement matrix $\mathbf{B}$, whose rows are the
vectors $\mathbf{b}_{k}$ (exploration phase)

  2. 2.

a set of $N$ decision rules
$\mbox{\boldmath$\delta$}=\\{\delta_{i}\in\\{0,1\\}:i=1,2,\dots,N\\}$ over the
unknown states $s_{i}$ of the resources (at the end of the exploration phase).

Notice that the design of $\mathbf{B}$ includes:

  * •

the measurement vectors $\mathbf{b}_{k}$ for each test at time
$k=1,2,\dots,\kappa$ (matrix rows),

  * •

the sensing (exploration) time $\kappa$ to acquire information on the states
$s_{i}$ via the observations $y[k]$ (number of rows).

###  II-B Hardware Considerations

From the sufficient statistics $y[k]$ in (15), it follows that our incoherent
receiver can be implemented by combining different oscillators that do not
require to be synchronized or phase-locked (see Fig.2). Furthermore, the
switching frequency of the oscillator is also $R_{s}$, i.e. the single channel
bandwidth, which is much slower than the limit of state-of-the art hardware.
In the proposed receiver, the input is mixed with the signal $g_{k}(t)$, that
folds the spectrum present in specific sub-bands onto the center frequency of
the receiver, during what we can refer to as a sub-Nyquist carrier sensing
phase. The samples are spaced by intervals of duration $T_{s}=1/R_{s}$ which
is a factor $1/N$ smaller than the total spectrum.

Naturally, the mapping of the signal in general will be imperfect and, like in
any ADC, calibration is necessary [26, 27]. For most ADCs the assumption is
that this calibration is done during an initial training phase, in which a
known input signal can be used to estimate the equivalent matrix $\mathbf{B}$.

As far as the proposed architecture is concerned, the circuit diagram of Fig.2
assumes a settling time for the VCOs much smaller than $T_{s}$, i.e. the
sampling period for the single channel sub-band. If this assumption does not
hold, one should use a LPF with a smaller bandwidth and collect the samples
$c[k]$ at an even slower rate than $R_{s}$, to wait for the VCOs to settle.
This modification would not alter the statistical characterization of the
samples, derived in the previous subsection. The drawback of taking samples
less often is that (assuming the same occupancy coherence time) one would have
accrued less information than what is available in the received signal, and
would have less than $K$ slots to decide. Given that our strategy is derived
as a function of $K$, this would not invalidate our findings. Another
possibility would be to replace the $L$ tunable VCOs with $N$ oscillators at
constant frequencies, corresponding to the $N$ possible bands of the signal.
Using $N$ oscillators would increase the power consumption and cost of the
circuit but would significantly reduce the switching time between two
measurements. Hence, this would be the natural choice if one wants to exploit
a dense sensing matrix. Instead, the use of a bank of VCOs is preferable if
the matrices are sparse because a small number of VCOs can synthesize the
mixing signal. The switching would be in fact performed by a multiplexer, that
would take the sum of the up to $L$ tones selected by the vector
$\mathbf{b}_{k}$.

In general, since we focus on the detection of the signal, with reasonably
good device components we expect that calibration will either be far less
demanding or unnecessary, if one accepts loss in sensitivity. In fact, the
binary coefficients for the vector $\mathbf{b}$ can be set to ones and zeros,
as discussed in IV-B1. Controlling the gains is unnecessary for the system to
work, and it is preferable to not add tunable gains, as they can be another
possible source of uncertainty and complexity in the system. Finally,
imperfect tuning of the VCOs will reduce the SNR, either by spreading or
misplacing the center frequency of the components of interest, but not
fundamentally impair the detection.

##  III Optimization framework

During the times devoted to sensing $k=1,2,\dots,\kappa<K$ the player has the
possibility to dynamically and adaptively design each measurement, by
selecting a sensing vector $\mathbf{b}_{k}=[b_{k1},b_{k2},\dots,b_{kN}]$, that
indicates what subset of the entries of $\mathbf{s}$ to probe (that is, the
$b_{ki}$’s will be non-zero only on the channels that are actively sensed). To
capture the optimization between sensing (exploration) and exploitation of a
subset of the $\mathcal{N}$ sub-bands, we model a total utility proportional
to the time left for exploitation $(K-\kappa)$. The detector acquires
information about the entries $s_{i}$ via observations with a p.d.f.
parameterized by an unknown vector. Together with the optimal design of
$\mathbf{B}$, the detector also optimizes the binary decision vector $\delta$,
once the observations have been collected, on the state of the sub-bands. We
denote the type I (false alarm) and type II (miss) errors probability with
$\alpha_{i},\beta_{i}$ respectively, i.e. $\alpha_{i}=P(\delta_{i}=1|s_{i}=0)$
and $\beta_{i}=P(\delta_{i}=0|s_{i}=1)$. We assume the state entries $s_{i}$
are mutually independent Bernoulli random variables with known prior
probabilities, given by a vector
$\mbox{\boldmath$\omega$}=[\omega_{1},\omega_{2},\dots,\omega_{N}]$, where
$\omega_{i}=P(s_{i}=0)$.  A practical guideline to initialize the
$\omega_{i}$’s is to set them to be uniform, and equal to a conservative
estimate of the expected fraction of busy channels. In addition, past tests
results could potentially be used to update the beliefs. Let us consider a
reward $r_{i}>0$ for correctly detecting an empty sub-band and a penalty
$\rho_{i}<0$ for failing to detect a busy sub-band, the utility can be written
as

$\displaystyle
U(\mathbf{s},\mathcal{N},K,\mathbf{B},\mbox{\boldmath$\delta$})\triangleq(K-\kappa)\\!\sum_{i=1}^{N}\omega_{i}r_{i}\left(1-\alpha_{i}\right)+(1-\omega_{i})\rho_{i}\beta_{i}$
(16)

We anticipate however, that the framework proposed can be extended to cover
applications where the utility comes from an action on the entries detected as
busy, e.g. for a RADAR application, where the entries correspond to spatial
directions. Thus we use SS case (Spectrum Sensing) or R case (RADAR) to refer
to the case where utility is generated by detection of empty or busy entries
(also referred as resources), respectively. Extending the definition in (16)

$\displaystyle
U(\mathbf{s},\mathcal{N},K,\mathbf{B},\mbox{\boldmath$\delta$})$ (17)
$\displaystyle\triangleq\begin{cases}(K-\kappa)\\!\sum_{i=1}^{N}\omega_{i}r_{i}\left(1-\alpha_{i}\right)+(1-\omega_{i})\rho_{i}\beta_{i}&\mbox{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
SS case}}\\\
(K-\kappa)\sum_{i=1}^{N}(1-\omega_{i})(1-\beta_{i})r_{i}+\omega_{i}\alpha_{i}\rho_{i}&\mbox{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
R case}}\end{cases}$

###### Remark 2

In our framework there are two possible actions over a resource: the null
action that always brings zero utility, and the other one that brings a random
utility, which depends on the actual channel state. This is motivated by the
emphasis we place on the time-dependent utilization of the resources, which we
assume occurs only in one of the binary states (based on the application of
interest). Note that a more general formulation for (17) with $4$ different
rewards/penalties (for the possible cases $(s_{i},\delta_{i})$) would not
alter the structure of the problem, nor invalidate our results, i.e. there
exists a unique mapping from our model to such case.

Finding the optimal policy corresponds to solve the following optimization
problem

$\displaystyle\underset{\mathbf{B},\mbox{\boldmath$\delta$}}{\text{maximize}}$
$\displaystyle\mathds{E}\left[U(\mathbf{s},\mathcal{N},K,\mathbf{B},\mbox{\boldmath$\delta$})\right].$
(18)

##  IV Dynamic Design of Sensing Matrices

###  IV-A Direct Inspection (DI) case

In the DI case, we limit $\mathbf{b}_{k}$ to have only one non-zero entry $i$,
i.e. $b_{ki}\neq 0$, $b_{kj}=0~{}\forall j\neq i$. This means that there is an
underlying hypothesis testing:

$\displaystyle\mathcal{H}_{0}$ $\displaystyle:y[k]\sim Exp~{}(\theta_{0}[k])$
$\displaystyle\mathcal{H}_{1}$ $\displaystyle:y[k]\sim Exp~{}(\theta[k])$

with $\theta_{0}[k]=b_{ki}n_{i}$ and
$\theta[k]=b_{ki}(\varphi_{i}+n_{i})>\theta_{0}[k]$. In this context, it is
known that the signal energy is a sufficient statistic for the test and that
energy detection is optimal. Assuming no prior knowledge over the
$\varphi_{i}$’s in case of existing communication, we only need to design the
test threshold, which we set in order to maximize the utility defined in (17).
By defining
$\theta^{\star}[k]\triangleq\max\\{y[k],b_{ki}(\varphi_{\text{min}}+n_{i})\\}$
we get:

$y[k]\overset{\mathcal{H}_{1}}{\underset{\mathcal{H}_{0}}{\gtrless}}\frac{\ln\left(\gamma_{i}\frac{\theta^{\star}[k]}{\theta_{0}}\right)}{\frac{1}{\theta_{0}}-\frac{1}{\theta^{\star}[k]}}$
(19)
$\gamma_{i}\triangleq\begin{cases}\frac{r_{i}\omega_{i}}{|\rho_{i}|(1-\omega_{i})}&\mbox{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
SS case}}\\\
\frac{|\rho_{i}|\omega_{i}}{r_{i}(1-\omega_{i})}&\mbox{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}
R case}}\end{cases}$ (20)

Notice that, assuming a minimum average received signal power
$\varphi_{\text{min}}>0$ in case of existing transmission, makes the test
meaningful also for values of $\gamma_{i}<1$.

###### Assumption 1

To simplify the decision problem, we will assume every resource has to be
sensed before being declared empty/busy. This can be enforced as a
standard/protocol rule or numerically guaranteed by setting $\forall
i\in\mathcal{N},\omega_{i}<\frac{\rho_{i}}{\rho_{i}+r_{i}}$ ( SS case) /
$\omega_{i}>\frac{r_{i}}{|\rho_{i}|+r_{i}}$( R case).

It is clear that the optimality 333The threshold in (20) is the optimal
threshold that minimizes the Bayesian risk (maximize our utility) for the
binary case, when $\varphi_{i}$ is known. It is of common practice to replace
the MLE estimate for the unknown $\varphi_{i}$ (GLRT) and then reduce to the
binary case, using the same threshold. A local most powerful test exists for
$\theta\rightarrow\theta_{0}$ but GLRT is preferred for high SNR range. of the
test completely characterizes the set of decision rules $\delta$ for the
sensed resources, while Assumption 1 gives us the decision rules for the non-
sensed resources. This implies that for the DI case, the optimization in (18)
can be expressed solely in terms of $\mathbf{B}$. It is also known that for
this type of test, where there is uncertainty in a parameter of the
alternative hypothesis, one does not know the exact miss probability $\beta$;
thus we will use an upper-bound, which will reflect in a lower bound for the
achievable utility. Since this test is part of the DI strategy, we add the
superscript DI to the test error probabilities $\alpha_{i}$ and $\beta_{i}$
and have:

$\displaystyle\alpha^{DI}_{i}$
$\displaystyle=\min\left\\{\left(\frac{|\rho_{i}|(1-\omega_{i})}{r_{i}\omega_{i}\left(1+\frac{\varphi_{\text{min}}}{n_{i}}\right)}\right)^{\frac{1+\frac{\varphi_{\text{min}}}{n_{i}}}{\frac{\varphi_{\text{min}}}{n_{i}}}},1\right\\}$
(21) $\displaystyle\beta_{i}^{DI}$
$\displaystyle=1-\left(\alpha_{i}^{DI}\right)^{\frac{1}{1+\frac{\varphi_{i}}{n_{i}}}}.$
(22)

What we can guarantee, since $\varphi_{i}\geq\varphi_{\text{min}}$ is that

$\beta_{i}^{DI}\leq
1-\left(\frac{\rho_{i}(1-\omega_{i})}{r_{i}\omega_{i}\left(1+\frac{\varphi_{\text{min}}}{n_{i}}\right)}\right)^{\frac{n_{i}}{\varphi_{\text{min}}}}=\beta_{i,\text{max}}^{DI}$
(23)

###### Remark 3

The test performance for the DI case does not depend on $b_{ki}$, therefore,
for the DI case no further optimization is needed over the sensing matrix
$\mathbf{B}$, other than selecting the non-zero entries.

Under Assumption 1, we can rewrite the optimization problem in (18) for the DI
case as

$\displaystyle\underset{\mathcal{A}\subseteq\mathcal{N}}{\text{maximize}}$
$\displaystyle U^{DI}(\mathcal{A})$ (24) $\displaystyle
U^{DI}\left(\mathcal{A}\right)$
$\displaystyle\triangleq(K-|\mathcal{A}|)\sum_{i\in\mathcal{A}}u_{i}^{DI}$
(25) $\displaystyle u_{i}^{DI}$
$\displaystyle\triangleq\omega_{i}r_{i}(1-\alpha^{DI}_{i})-(1-\omega_{i})\rho_{i}\beta^{DI}_{i,\text{max}}$
(26)

We then introduce the following Lemma

###### Lemma 1

$U^{DI}({\mathcal{A}})$ is a normalized, non-monotone, non-negative sub-
modular function of $\mathcal{A}$.

###### Proof:

See Appendix -A

Lemma 1 implies that there are diminishing returns in augmenting sets by
adding a certain action to bigger and bigger sets. The maximization of a non-
monotonic sub-modular function is generally NP-hard, but the case of interest
is not as difficult. In fact, by sorting the resources $i$ so that:

$u_{1}^{DI}\geq u_{2}^{DI}\geq\ldots\geq u_{N}^{DI}$ (27)

the set of size $i$, $\mathcal{A}_{i}=\\{1,\ldots,i\\}$ will be such that for
any set ${\mathcal{X}}$ of size $|{\mathcal{X}}|=i$

$\sum_{k=1}^{i}u_{k}^{DI}\geq\sum_{k\in{\mathcal{X}}}u_{k}^{DI}$

Therefore, what remains is to find the best set size $i$ such that

$U^{DI}({\mathcal{A}})\leq
U^{DI}(\mathcal{A}_{i})\leq\max_{i}\left((K-i)\sum_{k=1}^{i}u_{k}^{DI}\right)$
(28)

The maximum in (28) is attained for

$i^{*}=\inf\limits_{i}\\{i:\partial_{i+1}U^{DI}({\mathcal{A}_{i}})<0\\}$ (29)

where
$\partial_{i+1}U^{DI}({\mathcal{A}_{i}})=(K-i)u_{i+1}^{DI}-\sum_{k=1}^{i+1}u_{k}^{DI}$.
In fact, given the function is sub-modular, as soon as this condition is
attained, it is maintained for $i+2,i+3$ etc., given that the marginal returns
continue to decrease. This maximization is greedy and stops when the marginal
reward becomes negative.

###  IV-B A Group Testing Approach

We now allow each test to mix different sub-bands, i.e. the vector
$\mathbf{b}_{k}$ to have more than one non-zero entry. As outlined in the
Introduction, aliasing of the spectrum comes with an associated noise folding
phenomenon. Its impact is particular severe in a non coherent scheme as ours.
In fact, the samples are collected sequentially and not in parallel, which
means that we do not have multiple observations of the same value but only
sequential observations tied to the same underlying random process.

To mitigate the noise folding effects, and reduce the hardware complexity, our
focus is on low density measurement matrices. Our goal is to develop a
relatively simple dynamic strategy for choosing a sensing matrix, whose
utility can be expressed in closed form, and can potentially outperform the DI
alternative. A common approach for recovery with low density measurement
matrices is to use belief propagation via message passing444In our model, an
uninformative prior can be assigned to the $\varphi_{i}$’s to run the belief
propagation message-passing algorithm on the obtained measurements, whose most
well known application is Low Density Parity Check (LDPC) optimum error
correction decoding. For LDPC (and CS methods), performance guarantees come as
asymptotic bounds on the $\ell_{2}$-norm, but little is known for optimal
design in the finite regime. A difficulty in the design arises from the
inherent multi-hypothesis testing problem associated with sensing several
resources at the same time. This is why, to develop our dynamic design, we
look at a Group Testing (GT) approach, which allows us to consider a binary
hypothesis test for each measurement. In this way, the complexity of the
analysis is relatively low, and we can derive the expected performance for any
sensing matrix, under mild assumptions. Prior to providing more details, a
remark regarding related group-testing approaches is in order:

###### Remark 4

In the context of group testing, little is known in presence of measurement
errors that depend on the group size, which is the scenario this work
considers, as the remainder of the paper will detail. Asymptotic results on
the target rate for measurement-dependent noise, using an information-
theoretic approach, are given in [28], where the noise is modeled as
independent additive Bernoulli with bias dependent on the test size. Hence,
the false-alarm and missed-detection probabilities of each single test, are
symmetric. An additional noise, called dilution effect was considered in [29],
where each resource could independently flip from $1$ to $0$ before the
grouped test, and information-theoretic bounds were provided. In our model the
false alarm and miss-detection probabilities are dependent on the optimization
of the test threshold, therefore the noise is not independently added (nor an
independent dilution can be considered). Furthermore, the strategy derived
depends on the finite horizon for $K$, i.e. our results are not asymptotic.
The same considerations apply to similar information-theoretic approaches in
[30, 31, 32].

From the sensing matrix $\mathbf{B}$, let us define the sets
$\mathcal{A}_{k}=\\{i\in\mathcal{N}:b_{ki}\neq 0\\}$ and
$\mathcal{B}_{i}=\\{1\leq k\leq\kappa:b_{ki}\neq 0\\}$. Note that at times we
use $\mathbf{B}$ as an argument in functions that, strictly speaking, are just
functions of the sets $\mathcal{A}_{k}$ just defined. For each test we define
a binary group test as follows555 We envision that such test would be useful
for a downlink transmission in which the Access Point (AP) may want to allow
multiple communications at the same time and can alert the SUs over a
narrowband signaling channel to access the spectrum.:

$\begin{cases}\mathcal{H}_{0}:&\forall i\in\mathcal{A}_{k}~{}~{}s_{i}=0\\\
&\Rightarrow\theta_{0}[k]=\mathbf{b}_{k}^{T}\boldsymbol{n}\\\
\mathcal{H}_{1}:&\exists i\in\mathcal{A}_{k}~{}~{}s.t.~{}~{}s_{i}=1\\\
&\Rightarrow\theta[k]\geq\\!\left(\\!\min\limits_{i}b_{ki}\\!\right)\\!\varphi_{\text{min}}\\!+\\!\mathbf{b}_{k}^{T}\boldsymbol{n}=\theta_{\text{min}}[k]\end{cases}$
(30)

###### Remark 5

It is important to highlight that the two hypotheses pertain exclusively the
group of sub-bands explored in test (i.e. $\mathcal{A}_{k}$), not the whole
spectrum. Also note that this group-testing approach pertains the design of
the sensing matrix and detection algorithm and not the underlying observation
model. The different approaches we compare ourselves against later, use
detection strategies that are multi-hypothesis tests.

The test can be written as:

$\frac{\max\limits_{\theta[k]\geq\theta_{\text{min}}[k]}f_{\theta[k]}(y[k])}{f_{\theta_{0}[k]}\left(y[k]\right)}\overset{\mathcal{H}_{1}}{\underset{\mathcal{H}_{0}}{\gtrless}}\gamma_{k}.$
(31)

for which we can derive:

$\displaystyle\upalpha(\mathbf{b}_{k},\gamma_{k})$
$\displaystyle=\left(\frac{1}{\gamma_{k}\frac{\theta_{\text{min}}}{\theta_{0}}}\right)^{\frac{\frac{\theta_{\text{min}}}{\theta_{0}}}{\frac{\theta_{\text{min}}}{\theta_{0}}-1}}$
(32) $\displaystyle\upbeta(\mathbf{b}_{k},\gamma_{k})$
$\displaystyle=1-\left(\upalpha(\mathbf{b}_{k},\gamma_{k})\right)^{\frac{\theta_{0}}{\theta_{\text{min}}}}$
(33)

The decision declares that resource $i$ is busy ($\mathcal{H}_{1}$ is true) if
the majority of the tests, where resource $i$ is involved, is positive, else
it accepts the null hypothesis $\mathcal{H}_{0}$ for resource $i$. Thus:

$\displaystyle\pi_{0}(i,\mathbf{b},\gamma)=\\!\\!\left(\\!1\\!-\\!\\!\\!\\!\\!\prod_{j\in\mathcal{A}_{k}\setminus
i}\\!\\!\\!\\!\omega_{j}\\!\right)\\!\left(1\\!-\\!\upbeta_{i}(\mathbf{b},\gamma;0)\right)+\\!\upalpha(\mathbf{b},\gamma)\\!\\!\\!\\!\\!\prod\limits_{j\in\mathcal{A}_{k}\setminus
i}\\!\\!\\!\\!\omega_{j}$ (34)
$\displaystyle\pi_{1}(i,\mathbf{b},\gamma)=1-\upbeta_{i}(\mathbf{b},\gamma;1)$
(35)

where the functions $\pi_{j}(i,\mathbf{b},\gamma),~{}j=0,1$ are only defined
when $b_{i}\neq 0$. These functions represent the probabilities of declaring
$\mathcal{H}_{1}$ in a group-test defined by $\mathbf{b}$ with threshold
$\gamma$ and given $s_{i}=j,~{}j=0,1$. Notice that the error probabilities
$\upalpha,\upbeta$ refer to each binary hypothesis testing defined in (30).
The notation for $\upbeta_{i}(\mathbf{b},\gamma;s_{i})$ indicates the
probability of having a missed-detection conditioned on the state $s_{i}$ of
one of the resources. It then follows that

$\displaystyle\alpha^{GT}_{i}(\mathbf{B},\boldsymbol{\gamma})$ (36)
$\displaystyle\triangleq\\!1\\!-\\!F_{PBD}\\!\left(\left\lceil\frac{|\mathcal{B}_{i}|}{2}\right\rceil-1;|\mathcal{B}_{i}|,\\{\pi_{0}(i,\mathbf{b}_{k},\gamma_{k})\\!:\\!k\in\mathcal{B}_{i}\\}\right)$
$\displaystyle\beta^{GT}_{i}(\mathbf{B},\boldsymbol{\gamma})$ (37)
$\displaystyle\triangleq
F_{PBD}\\!\left(\left\lceil\frac{|\mathcal{B}_{i}|}{2}\right\rceil-1;|\mathcal{B}_{i}|,\\{\pi_{1}(i,\mathbf{b}_{k},\gamma_{k})\\!:\\!k\in\mathcal{B}_{i}\\}\right)$

where $F_{PBD}(k;n,\mathbf{p})$ indicates the CDF of a Poisson Binomial
Distribution parameterized by $\mathbf{p}\in[0,1]^{n}$. At this point, one can
replace (36)-(37) in (17), to then solve the optimization in (18), where the
equivalence between the decision rules $\delta$ and the selection of the
thresholds $\gamma$ is essentially the same as for the DI case.

Notice that, in order for (36)-(37) to hold, each of the tests must be
independent, conditioned on the state of the resource $i$. This is true if the
sensing matrix (in the language used for LDPC codes) does not have length-4
cycles (i.e. two different measurements do not mix more than one sub-band in
common)666Such condition is typically required for belief propagation
algorithms, e.g. message passing, which suffer from loopy networks with short
cycles..

The optimization remains extremely complex due to the complexity of the
decision space for $\mathbf{B}$ and the sum of an exponentially growing number
of terms for the probabilities defined in (36)-(37). Nevertheless, it gives a
method to evaluate the objective of our optimization for any sensing matrix
$\mathbf{B}$, where the optimization over $\gamma$ can be numerically solved.
In fact, (36)-(37) are monotonic functions of the probabilities
$\pi_{0},\pi_{1}$ defined in (34)-(35), which are monotonic in the
$\gamma_{k}$’s, and therefore a unique solution for $\gamma$ exists. Next, we
introduce additional constraints to (18), in particular on the structure of
$\mathbf{B}$, in order to evaluate whether a GT strategy could be superior to
the DI approach.

###### Remark 6

Note that an ML or a MAP estimator, for a rank-deficient sensing matrix, do
not provide optimality guarantees in terms of minimum error probability or
minimum Bayesian risk. Nevertheless, for the same sensing matrix, we expect
the MAP estimator to outperform the binary group-testing hypothesis in (30) by
simply adding more degrees of freedom to the decision $\delta$ in the
$\kappa$-th dimensional space of the observations. Therefore, the evaluation
of the objective in (18) via (36)-(37) provides a benchmark for the utility
obtainable with a more refined detection method.

####  IV-B1 The pairwise tests case

We start by considering matrices $\mathbf{B}$ that have the following
property: each resource is sensed only one time, either directly inspected or
mixed with another resource, and no test mixes more than 2 resources, i.e.
$|\mathcal{A}_{k}|\leq L=2,|\mathcal{B}_{i}|\leq 1~{}~{}\forall
k=1,\dots,\kappa,~{}i=1,\dots,N$. Let us discuss the test that mixes entries
$i$ and $j$. According to the strategy derived at the beginning of the
section, one can use (34)-(35)-(36)-(37) to write out the per-time instant
utility obtainable after the decision. First, from (30), we note that, without
prior knowledge over $\varphi_{i},\varphi_{j}$ other than the threshold
$\varphi_{min}$, the best choice to minimize $\alpha$ is to set $b_{i}=b_{j}$
(we refer to this false alarm probability as $\alpha_{ij}$). Therefore,
similar to the DI case, one can consider binary coefficients for
$\mathbf{b}_{k}$, i.e. $b_{ki}\neq 0\rightarrow b_{ki}=1$. This will hold true
also for the extension of $L>2$ and will give implementation advantages as
discussed in II-B.

A missed detection event in (30) can occur for three different states of the
resources $i,j$; we upper-bound the corresponding missed detection
probabilities by always considering $\theta=\theta_{\text{min}}$ and refer to
this bound as $\beta_{ij,\text{max}}$. We then obtain:

$\displaystyle
u_{ij}^{GT}\triangleq\omega_{i}\omega_{j}(r_{i}+r_{j})(1-\alpha_{ij})+\left[(\omega_{i}(1-\omega_{j})(r_{i}+\rho_{j})+\right.$
$\displaystyle\left.\omega_{j}(1-\omega_{i})(r_{j}+\rho_{i})+(1-\omega_{i})(1-\omega_{j})(\rho_{i}+\rho_{j}))\right]\beta_{ij,\text{max}}$
(38)

where the threshold for this test $\gamma_{ij}$ has been set to maximize (38),
i.e.

$\gamma_{ij}=\frac{\omega_{i}\omega_{j}(r_{i}+r_{j})}{(1-\omega_{i})(|\rho_{i}|-\omega_{j}r_{j})+(1-\omega_{j})(|\rho_{j}|-\omega_{i}r_{i})}.$
(39)

Let us then consider a graph where each resource is a vertex and the edge
weight $u_{ij}$ between two vertices $ij$ is the utility (per time instant)
$u^{GT}_{ij}$ just defined (the weight of the loops $u_{ii}^{GT}$ are given by
$u^{DI}_{i}$ in (26)). We can then translate our problem into a particular
instance of a max-cut problem: picking a subset of the edges and form a
subgraph, where each edge represents a test, to maximize the objective in
(18). Formally, we can write

$\displaystyle\underset{\mathcal{E}}{\text{maximize}}$ $\displaystyle
U^{GT}(\mathcal{E})$ (40) subject to $\displaystyle\deg_{\mathcal{E}}(i)\leq
1~{}~{}\forall i\in\mathcal{N}$

where

$U^{GT}(\mathcal{E})\triangleq\\!\left(K\\!-|\mathcal{E}|\right)\\!\\!\left(\sum_{ij\in\mathcal{E}}u_{ij}^{GT}\right)\\\
$ (41)

and $\deg_{\mathcal{E}}(i)$ is the nodal degree of node $i$ induced by the
undirected graph $\mathcal{G}=\left(\mathcal{N},\mathcal{E}\right)$. It is
possible to map the constraint on the nodal degree in the objective of (40),
by adding a penalty for the violation of such constraint. This guarantees the
optimal solution will be equivalent to (40), i.e. no set of edges that
violates the constraint can improve the objective, and any feasible set of
edges would have the same objective in the two problems. We rewrite our
optimization as

$\displaystyle\underset{\mathcal{E}}{\text{maximize}}$ $\displaystyle
U^{GT}(\mathcal{E})-M\sum_{i\in\mathcal{N}}\Upsilon(\deg_{\mathcal{E}}(i))$
(42)

where

$\Upsilon(n)\triangleq\begin{cases}0&\mbox{for}~{}n\leq 1\\\
n-1&\mbox{for}~{}n\geq 2\end{cases}$ (43)

and $M$ is a positive constant.

###### Lemma 2

For $M>0$ the objective in (42) is a non-monotone sub-modular function of
$\mathcal{E}$ and it is possible to find $M^{*}>0$ such that for any $M>M^{*}$
the two optimizations (40)-(42) are equivalent.

###### Proof:

See Appendix -B

We now discuss the extension of this result for $L>2$, to develop a general
algorithm that leverages the sub-modularity of the optimum design problem in
(40).

####  IV-B2 Extension to $L>2$

If we mix more than 2 channels, instead of just edges or self loops to
indicate the tests, we could have cycles of length up to $L$. The nodal degree
in (42) will then be interpreted as the number of cycles a node belongs to,
and the set of edges will be replaced with the set of cycles. We then replace
the set $\mathcal{E}$ of edges with the set $\mathcal{C}$ of possible cycles,
and use $c$ to indicate the generic cycle (which could be a self-loop, an edge
or a cycle with length $3$ or greater). With these substitutions, the proof of
sub-modularity in Lemma 2 naturally extends to this case as well. In light of
the constraint $|\mathcal{B}_{i}|\leq 1$ we will have that no node can be in
two cycles.

To visualize this concept, in Fig.3 we show two possible sets of cycles of
length up to $4$. On the right, we have a set of tests that respect our
constraint: there is a test that only considers one resource and three tests
that combine 2, 3, and 4 resources respectively, but no resource is considered
in two different tests. On the left, instead, a resource is considered in two
tests: one where it is combined with other $3$ resources, and one where it is
inspected directly; such configuration is therefore not acceptable.

Figure 3: Example of two sets of tests. The right configuration has $4$ tests
and no resource is considered in two different tests, therefore it respect our
constraints, whereas the left configuration has a resource included in two
tests, and is not a feasible solution.

####  IV-B3 The factor approximation of the greedy algorithm

Having proven the sub-modularity of (42) in Lemma 2, it is natural to resort
to a greedy procedure, however it is important to highlight that the objective
in (42) does not respect the non-negativity property. To the best of our
knowledge, there is no known procedure in the literature on approaching the
maximization of a general sub-modular non monotone function, if the minimum
value is not known: no constant approximation factor guarantee can therefore
be given in general. Nevertheless, due to the particular structure of our
problem, it is possible to find a factor approximation for the output of the
greedy procedure, described in Algorithm 1.

###### Lemma 3

Algorithm 1 guarantees a $\alpha$-constant factor approximation of the optimal
solution for (42), where:

$\alpha=\frac{1}{\min\\{L_{\text{eff}},\frac{K}{2}\\}}\frac{K-1}{K-\min\\{L_{\text{eff}},\frac{K}{2}\\}}.$
(44)

###### Proof:

See Appendix -C.

1: Initialize: $\mathscr{C}=\emptyset$.

2: While $\exists~{}\mathcal{C}\in\bar{\mathscr{C}}$ such that
$\partial_{\mathcal{C}}U^{GT}(\mathscr{C})>0$

3: Find
$\mathcal{C}^{*}=\operatorname*{arg\,max}_{\mathcal{C}\in\bar{\mathscr{C}}}\partial_{\mathcal{C}}U^{GT}(\mathscr{C})$

4: $\mathscr{C}\leftarrow\mathscr{C}\cup\mathcal{C}^{*}$

5: End

Algorithm 1 Greedy Maximization of $U^{GT}(\mathscr{C})$

The set $\bar{\mathscr{C}}$ indicates the set of cycles that are not adjacent
(share a node) with any of the cycle in $\mathscr{C}$. Note that

$\partial_{\mathcal{C}^{\prime}}U^{GT}(\mathscr{C})=-\sum_{\mathcal{C}\in\mathscr{C}}u_{\mathcal{C}}+(K-|\mathscr{C}|-1)u_{\mathcal{C}^{\prime}}$
(45)

so, as long as the number of tests $|\mathscr{C}|$, added in the greedy
maximization, is less than the time horizon $K$, we have

$\operatorname*{arg\,max}_{\mathcal{C}\in\mathscr{C}^{c}}\partial_{\mathcal{C}}U^{GT}(\mathscr{C})=\operatorname*{arg\,max}_{\mathcal{C}\in\mathscr{C}^{c}}u_{\mathcal{C}}.$
(46)

This relation indicates that, in the greedy procedure, edges are added in
decreasing order of utility, respecting the constraint on the nodal degree.
Also, from (45) it is easy to find that the optimal $|\mathscr{C}|$ will never
exceed $\left\lceil\frac{K-1}{2}\right\rceil$. In the greedy procedure in
Algorithm 1, there is a constant number of operations per query, which
indicates the overall complexity of the algorithm is dominated by the sorting
of all possible cycles’ utilities. In the worst case, sorting $n$ values
require $O(n^{2})$ operations, thus the complexity will be given by
$O\left(\left(\sum_{\ell=1}^{L}\binom{N}{\ell}\right)^{2}\right)=O\left(N^{2L}\right)$,
i.e. polynomial in $N$ and exponential in $L$.

###  IV-C Additional applications of the stochastic optimization

We would like to highlight the analysis for the factor approximation of the
greedy strategy transcends the spectrum sensing application discussed in
detail in this paper. In fact, group-testing has been applied to a number of
disparate contexts to model the outcome of sequential tests. As long as one
has a way to define the per-time utility derived from each test as in (38),
and an overall utility as in (41), then our results can be applied. Classes of
problems that could be formulated in a similar way include job scheduling for
data centers, design of parity checks for rateless coding, dynamic
advertisement (promoting an offer that bundles two products/services together)
etc.. Obviously, in all these cases, the statistics of the observations would
be radically different.

##  V Alternative approaches

In the previous sections, we have provided methods that find a low density
measurement matrix. As will be apparent in our numerical results, the noise
folding phenomenon justifies the use of sparse sensing matrices. They are also
ideal when one wants to use belief propagation to the decision problem.
However, for the sake of comparison here we look at alternative support
recovery methods, which can be applied to any measurement matrix $\mathbf{B}$,
and that can be mapped into previous solutions, as the MWC in [5, 9].

###  V-A ML estimate

Let us assume that $\kappa$ measurements have been collected, by mixing a set
$\mathcal{A}\subseteq\mathcal{N}$ of sub-bands. One could ignore the prior
$\omega_{i}$ and derive the ML estimate for $\varphi$. The log-likelihood
function is:

$\displaystyle\log\left(f\left(\boldsymbol{y}|\boldsymbol{\varphi}_{\mathcal{A}}\right)\right)=-\sum_{k=1}^{\kappa}\log\theta[k]+\frac{y[k]}{\theta[k]}$
$\displaystyle\overset{\theta[k]\rightarrow
y[k]}{\approx}-\sum_{k=1}^{\kappa}1+\log
y[k]+\frac{1}{2}\left(\frac{y[k]-\theta[k]}{y[k]}\right)^{2}$ (47)

where the linearization corresponds to the Taylor expansion of the likelihood
function around the observations mean (recall (14)-(15)). A possible approach
consists in solving the following LASSO problem:

$\hat{\boldsymbol{\varphi}}_{\mathcal{A}}=\operatorname*{arg\,min}_{\boldsymbol{\varphi}_{\mathcal{A}}}\|\boldsymbol{\lambda}_{\mathcal{A}}\boldsymbol{\varphi}^{T}_{\mathcal{A}}\|_{1}+\frac{1}{2}\|\left(\mathbf{y}-\mathbf{B}(\boldsymbol{\varphi}^{T}_{\mathcal{A}}+\boldsymbol{n}_{\mathcal{A}}^{T})\right)\|_{\mathbf{C}^{-1}}^{2}$
(48)

with $\mathbf{C}=\text{diag}(\mathbf{y})$ denoting the covariance of the
observations, and $\boldsymbol{\lambda}_{\mathcal{A}}$ the vector of weights
for the weighted $\ell_{1}$-norm. The first penalty term in the objective
enhances sparsity, while the second term comes from the ML estimate in (47).
To incorporate the information of the prior beliefs $\omega_{i}$, one can set
$\lambda_{i}=\gamma_{i}$ from (20), $\forall i\in\mathcal{A}$, to favor the
estimates $\varphi_{i}>0$ for entries with lower thresholds $\gamma_{i}$.
Alternatively, one can also set $\lambda_{i}=\lambda~{}\forall
i\in\mathcal{A}$. Note that, compared to the non-sequential sampling models
(i.e. those using a filterbank), the application of the LASSO (see Section V)
in this context is an approximation. The random demodulator in [33] (similar
to our scheme in terms of architecture) is an Xampling ADC converter for
signals that are sum of harmonics with constant amplitude, i.e. each subspace,
in the UoS representation, has finite dimension.  This is not the case we are
interested in, and approximating our signal as a sum of harmonics would
require sampling at a much higher rate than $R_{s}$. For our multiband signal
model, instead, rather than having observations that are noisy linear
combination of a sparse input, the p.d.f. of the samples depends on those same
linear combinations.

###  V-B Covariance estimate

A similar approach is to estimate the covariance of the samples, and write the
correspondent linear equations system, as derived in [9], using the analog
front-end of the MWC, introduced in [5]. This leads to write a system

$\boldsymbol{z}=\mathbf{B}\left(\boldsymbol{\varphi}+\boldsymbol{n}\right)+\boldsymbol{\epsilon}$
(49)

where the sensing matrix $\mathbf{B}$ ($\mathbf{A}$ in their work) is a
$M\times N$ matrix, with $M$ being the number of analog channels and $N$ the
number of spectral bands, whose occupancy is desired to be detected. The
authors estimate the covariance vector (diagonal of the covariance matrix)
$z_{i}=\mathds{E}\left[x_{i}^{2}[k]\right]$ (where the $x_{i}$ have been
introduced in (9)) by taking multiple samples in multiple frames (in their
work $K$ samples per frame in $P$ frames). Note, however, than in their work
the sampling frequency per branch, called $f_{s}$, needs to be larger than the
single component bandwidth $R_{s}$, to justify the approximation of a multi-
band signals as sum of harmonics with constant amplitudes over a single frame.
Also, in light of this, the different frames considered for the estimate of
$\boldsymbol{z}$, cannot be consecutive in time, since the $x_{i}$’s would be
correlated. However, for the sake of comparison, to calculate the utility of
the scheme in [9], we will ignore this limitation in our numerical tests (c.f.
Section VI) as well as their need of sampling at a faster rate than our
method, pretending their scheme can take $\kappa$ (using their notation
$\kappa=KP$) independent consecutive measurements, and can do so at the lower
rate $R_{s}$. One can then use (48) for the recovery of the sparse vector
$\boldsymbol{\varphi}$ from the linear system in (49), replacing $\mathbf{C}$
with $\mathbf{I}$, and $\mathcal{A}$ with $\mathcal{N}$, since their scheme
mixes the whole spectrum.

##  VI Simulation Results

In this section, we showcase the ability of our approach to dynamically switch
between a DI receiver (scanning receiver) and a GT approach, based on the
expected occupancy (the vector of priors $\omega$), the time available $K$,
the minimum SNR threshold $SNR_{\text{min}}=\frac{\varphi_{\text{min}}}{w}$
and the number of resources $N$. In the context of spectrum sensing (SS case),
the parameters $r_{i}$ and $\rho_{i}$ can be mapped into a maximization of the
overall weighted network throughput (see [17]): the reward $r_{i}$ can be
proportional to the achievable rate over the channel $i$ in the absence of PU
communications, i.e. $r_{i}\propto\log(1+SNR_{i,S})$ (where the suffix $S$
indicates the secondary communication), whereas the penalty $\rho_{i}$ can be
made proportional to the loss in rate caused to the primary communication, due
to the interference added by the secondary. For the cognitive radio
application, the concept of exploitation of the resource is tied to the
definition of utility function chosen in (17), which is expressed in
$bits/s/Hz$777From (17)-(18), $r_{i}$’s and $\rho_{i}$’s can be normalized
over the communication bandwidth without altering the optimization.. The
longer the time available to transmit, the larger is the number of bits that
can be transmitted over that band. For the other case, i.e. when the reward
comes from detecting correctly resources that are busy (for example a RADAR
application), it is not immediately clear why the utility would be
proportional to the number of remaining time instants. To interpret this, we
model the action upon declaration of $s_{i}=1$ as a Bernoulli trial which
accrues a reward $r_{i}$ if such action is successful (i.e. the target is
actually hit) and this happens with a certain probability $p_{i}$ for each
attempt. The number of attempts $T_{i}$ necessary to hit the target will then
be geometrically distributed. One can then find that the expected reward is
equal to
$r_{i}P(T_{i}\leq(K-\kappa))=r_{i}\sum_{k=1}^{K-\kappa}p_{i}(1-p_{i})^{k-1}=r_{i}(1-(1-p_{i})^{K-\kappa})\approx(K-\kappa)r_{i}p_{i}$
for small $p_{i}$, which would motivate having an expected utility that
increases linearly with time. The $\rho_{i}$ associated with this case would
model an intervention cost, whose main purpose would be to limit the false
alarm rate. It is important to highlight, however, that the time dependency in
the optimization objective prevents our formulation to return a standard
Constant False Alarm Rate (CFAR) detection method. Nevertheless, our model can
apply to electronic warfare (tentatives of create jamming), wake-up radio, and
other problems where the action (and the associated utility) is on the
channels that are declared busy. For all the figures we refer to $L=2,3$ as
the maximum number of resources per test allowed in our greedy procedure in
Algorithm 1. Theoretically, the optimal value for $U^{GT}$ monotonically
increases with $L$, since increasing $L$ introduces additional degrees of
freedom. However, in our simulations we used the greedy solution and, as
proved in our Lemma 3, the approximation factor of the greedy maximization is
potentially worse for higher values of $L$, as the following numerical results
will show.

We indicate with “Group Testing” the utility obtained with our GT approach.
The “MAP Estimator” is the estimator that knows the true values $\varphi_{i}$,
uses the same matrix $\mathbf{B}$ of the GT approach, but then decides on each
resource, based on the posterior for $\omega_{i}$, using belief-propagation.

####  VI-1 SS case vs RADAR

Even though, in light of the symmetry in the definition of the threshold
$\gamma_{i}$, one can switch the $r_{i}$’s and $\rho_{i}$’s to go from  SS
case to  R case and find the same trends, even for the combined tests, to
avoid confusion, we highlight the difference in the two scenarios, in the
first simulation we present in Fig.4.

For the experiment in Fig. 4, we set $K=30,N=60$ and
$r_{i}=r,\rho_{i}=\rho~{}\text{and}~{}\omega_{i}=\omega,SNR_{i}=SNR_{\text{min}}(10dB)~{}\forall
i\in\mathcal{N}$ we have that for $\omega$ equal to $\frac{\rho}{\rho+r}$ or
$\frac{r}{\rho+r}$ for SS case or R case, respectively. These are the
threshold values given in Assumption 1, to guarantee no resource can give
positive utility if not tested. As we can see, in both scenarios the utility
increases with the ratio $\frac{\rho}{r}$, since the prior probability, that
favors a positive utility, increases as well. However, the gain for the GT
approach over the DI, happens in complementary ranges: when $\frac{\rho}{r}>1$
for spectrum sensing application, and when $\frac{\rho}{r}<1$ in the RADAR
problem. When the penalty increases with respect to the reward, the GT
approach for spectrum sensing will be conservative and not transmit in any of
the channels in a group that tested positively; nevertheless, as the priors
$\omega_{i}$ increase, it is possible to find multiple empty sub-bands with
just one test and gain in utility compared to the DI. For the RADAR
application, when the penalty increases with respect to the reward, there is a
disadvantage in declaring as busy all the elements in the test, even if the
prior $\omega$ decreases. Clearly this limits the benefit of combined tests,
whereas when $\frac{\rho}{r}$ decreases, there is a gain since one element,
found busy in the pool, guarantees higher reward. Apart from this asymmetry,
both cases show the same trends in utility over number of available resources
$N$, and the value of $SNR_{\text{min}}$. Hence, we will only consider the SS
case in the next simulations.

(a) Spectrum sensing application
$\left(\text{prior}~{}~{}\omega={\rho}/({\rho+r})\right)$

(b) RADAR application $\left(\text{prior}~{}~{}\omega={r}/({\rho+r})\right)$

Figure 4: Comparing utility for different approaches vs the ratio
$\frac{\rho}{r}$ (horizon $K=30$, number of resources $N=60$,
$SNR_{\text{min}}=10dB$). The utility for the RADAR application ( R case) is
normalized over the unit measure of $r_{i}$ and $\rho_{i}$.

####  VI-2 Utility for different $N$

In Fig.5 we plot the utility (normalized over $K^{2}$) over the ratio
$\frac{K}{N}$ for two different horizons, i.e. $K=10$ and $K=30$ and
$SNR_{\text{min}}=10dB$. We can see that, only for $\frac{K}{N}\lessapprox
0.75$, the GT approach outperforms all competing options whereas, when the
horizon increases, almost no benefit comes from mixing resources. This
suggests that there is enough time to test them independently with high
accuracy. For this experiment, we set
$\omega_{i}\sim\left(0.7,\frac{\rho_{i}}{\rho_{i}+r_{i}}\right)$, where
$r_{i}=\log(1+SNR_{i,S})$ and $\rho_{i}=5r_{i}$ with
$SNR_{{i,S}_{dB}}\sim\mathcal{U}([10,20])$. The $SNR$ for the test,
$\frac{\varphi_{i}}{n_{i}}$, is generated uniformly between $10$ and $20$ dB;
recall that the only information used in our algorithm is the minimum $SNR$
value, i.e. in this case $10dB$. In the regime considered, the DI is
approximately constant since it is easy to show
$U^{DI,OPT}\leq\frac{K^{2}}{4}u_{\text{max}}$ irrespective of $N$.

####  VI-3 Utility for different $SNR_{\text{min}}$

In this set of experiments we studied how the utility behaves versus the
minimum $SNR$ in each active sub-band. In this case the $SNR$ was drawn
uniformly between $SNR_{\text{min}_{dB}}$ and $SNR_{\text{min}_{dB}}+10$, and
once again only the value of $SNR_{\text{min}}$ was used in the optimization,
which is shown in the abscissa of the figures. Matching our intuition, we can
see how the GT approach outperforms the DI only when $SNR_{\text{min}}$ is
sufficiently high, and also that the gain in utility is larger for $K=10$ than
for $K=30$. In fact, for this experiment the number of resources has been
fixed to $N=20$ and, as previously highlighted, increasing $K$ for fixed $N$
diminishes the benefit of combining resources in a test. We also plotted the
utility obtainable with the approximate ML estimate obtained via Compressive
Sensing, described in Section V. For this case, to illustrate the noise-
folding issue, we used a dense matrix that has the same aspect ratio of the
one found via $GT$ approach (i.e. that scans the same set of resources for the
same number of tests). To show reasonable results, only for the ML estimate
via CS, we actually took the mean of $y[k]$ over $10$ samples. We can see
that, despite having more measurements, such approach gives a much lower
utility than DI as well as the proposed GT, due to the negative effect of
noise folding. For $K=30$, we also compared our approach with the performance
obtained using belief propagation in a loopy network and an LDPC matrix (see
[11] for details). Considering $N=20$ resources, and an expected sparsity
approximately equal to $4$, we chose a regular LDPC matrix with a row weight
of $5$ ($20/4$ as suggested in [11]) and a column weight of $3$, resulting in
$12$ tests. The LDPC has not been implemented for $K=10$, since the regularity
constraints would have given either a diagonal matrix (same as DI), or a
relatively dense matrix. The absence of any optimization in the choice of
which and how many resources to test produces a utility which, for low $SNR$,
is lower than the DI approach proposed. For high enough $SNR$, the LDPC design
can outperform the DI approach, but still gives a utility lower than our GT
strategy with $L=2$. This highlights the benefit of having an active sub-
Nyquist receiver compared to a static offline selection of the parameters.

(a) Horizon $K=10$

(b) Horizon $K=30$

Figure 5: Comparing utility for different approaches vs the ratio horizon $K$
over the number of resources $N$ for different horizons $K$ and the prior
$\omega_{i}\sim\mathcal{U}\left(0.7,\frac{\rho_{i}}{r_{i}+\rho_{i}}\right)$.
The utility on the $y$ axis is normalized by $K^{2}$ ($SNR_{\text{min}}=10dB$)

(a) Horizon $K=30$

(b) Horizon $K=10$

Figure 6: Comparing utility for different approaches vs $SNR_{\text{min}}$ for
different horizons $K$ and the prior
$\omega_{i}\sim\mathcal{U}\left(0.7,\frac{\rho_{i}}{\rho_{i}+r_{i}}\right)$
(number of resources $N=20$)

####  VI-4 Detection performance vs MWC

In this last section, we compare our approach to the performances of another
incoherent power spectrum sensing approach proposed in [9], which was
mentioned in Section V-B. We considered $150$ independent bands with an
expected $5\%$ occupancy, e.g. $\omega_{i}=0.95~{}~{}\forall i\in\mathcal{N}$.
For the MWC scheme there are $M=30$ analog channels (in expectation twice the
support of the double-sided bandwidth occupancy). We recall that our
definition of SNR is the worst case per sub-band when the signal is present,
e.g. $SNR=\frac{\varphi_{\text{min}}}{n}$, where we considered for simplicity
$n_{i}=n~{}\forall i\in\mathcal{N}$, whereas the SNR considered in [9] is
$\frac{\sum_{i\in\mathcal{N}}s_{i}\varphi_{i}}{Nn}$. As indicated in [9], for
a fixed sensing time it is preferable to choose approximately the same number
of frames and samples per frame. This is the case in the simulations in Fig.
7, where $\kappa$ indicates the product of the two quantities $KP$. For the
utility parameters, in light of Assumption 1, we considered $r_{i}=1$ and
$\rho_{i}=19,~{}\forall i\in\mathcal{N}$. We remark however, that the ROC
curves in Fig.7 for the MWC power spectrum sensing, do not depend on these
parameters: the different points in the curve are obtained by changing
$\lambda$ ($\lambda_{i}=\lambda~{}\forall i\in\mathcal{N}$) in (48). Notice
that, for the same sampling frequency in each branch, the scheme in [9]
collects $M$ times the observations we collect per unit of time, hence the two
points for the optimized strategy correspond to: 1) an unfair comparison with
our scheme, where we keep $\frac{1}{M}$ observations (indicated with $R_{s}$),
and 2) a fair comparison where we assume our scheme can collect the same
number of observations, sampling at $M\cdot{R_{s}}$, hence obtaining a factor
of $M$ SNR gain per test888We remind the reader that the sampling rate in [9]
should actually be higher than $R_{s}$, as discussed in Section V-B. . We note
that at $10~{}dB$ (Fig.7(a)), the MWC scheme needs approximately $8\cdot
M=240$ times more observations to outperform our proposed approach in the
unfair comparison, while at $20~{}dB$ our approach offers better detection
performances, even when we let MWC collecting $200\cdot M$ more observations.
What is remarkable is how much higher is the gain of our approach at higher
SNR. This is due to the effect of the $SNR$ on the covariance estimate, which
is required in the power spectrum sensing algorithm in [9]. In fact, while
extending the number of samples per frame $K$ can mitigate the noise-folding
problem, improving the accuracy of the covariance estimate requires a larger
number of frames $P$, despite good $SNR$. For instance, for a Gaussian random
variable with zero mean and variance $\sigma^{2}$, it is relatively
straightforward to find that the ML estimate for the variance, has itself
variance equal to $\frac{2\sigma^{4}}{P}$ (for $P$ observations). This implies
that the LASSO-recovery step does not keep to improve for higher $SNR$, but
rather by averaging more, i.e., for higher $P$.

(a) $SNR=10dB$

(b) $SNR=20dB$

Figure 7:  ROC curve for the power spectrum sensing algorithm in [9] with MWC
front-end, and comparison with the detection performances of our optimized
sensing strategy

##  VII Conclusions

In this work, we proposed a new framework to optimize the performances of an
opportunistic spectrum access strategy with sub-Nyquist sampling, and
described the connection between such strategy and the design of the front-end
sampling architecture. For the problem proposed, we characterized the factor
approximation of the greedy strategy and showed, via numerical results, how
our dynamic design for the sensing matrix guarantees better performances than
other static approaches, namely: the linearization of an ML estimate using a
dense CS-sensing matrix, Belief Propagation using a regular Low-Density
Parity-Check sensing matrix, and the Xampling power spectrum sensing strategy
proposed in [9].

Figure 8: Representation of the iterative procedure to obtain the factor
approximation of the greedy algorithm

###  -A Proof of Lemma 1

To prove the submodularity of $U^{DI}(\mathcal{A})$ we show that, to prove the
submodularity property:

$U^{DI}(\mathcal{A}+a)+U^{DI}(\mathcal{A}+b)\geq
U^{DI}(\mathcal{A}+a+b)+U^{DI}(\mathcal{A}).$ (50)

is equivalent to prove

$u_{a}^{DI}+u_{b}^{DI}\geq 0$ (51)

which is true by assumption on the function $u_{i}^{DI}$ defined in (26).
Since $u_{i}^{DI}=0$ for $\alpha_{i}=1,\beta_{i}=0$, we have $u_{i}^{DI}\geq
0~{}~{}\forall i\in\mathcal{N}$ for the optimized
$\alpha_{i}^{DI},\beta_{i,\text{max}}^{DI}$.

###  -B Proof of Lemma 2

The function is the sum of two terms, to prove the first one is sub-modular
one can follow the same steps in Appendix -A. For the second term, it is
enough to show that, for any $i$, $-\Upsilon(\deg_{\mathcal{E}}(i))$ is a sub-
modular function of $\mathcal{E}$. The function is clearly sub-modular since
is a concave function of the nodal degree, and from this we can conclude the
second term is a positive sum of sub-modular functions, hence sub-modular. To
prove the equivalence of the two optimizations in (40)-(42), we first note
that for any $\mathcal{E}$ that satisfies the constraints in (40), the second
term of the objective in (42) is equal to 0 and the two objectives are equal.
It follows that we simply need to verify that no set of edges, that violate
the constraint on the nodal degree, would be the optimal solution for (42). To
show this, we note that any infeasible set of edges (according to (40)) can be
made feasible by removing some edges. For $M$ large enough, i.e.
$M>K\max_{ij}u_{ij}$ it is relatively straightforward to verify that such
removal of edges would improve the objective, preventing an infeasible
solution for (40) to be optimal for (42), and this concludes the proof.

###  -C Proof of Lemma 3

We want to prove

$U^{GT}\left(\mathscr{C}^{G}\right)\geq\alpha U^{GT}(\mathscr{C}^{OPT})$ (52)

where
$\alpha=\frac{1}{\min\\{L_{\text{eff}},\frac{K}{2}\\}}\frac{K-1}{K-\min\\{L_{\text{eff}},\frac{K}{2}\\}}$
and $L_{\text{eff}}\leq L$ is the largest test size returned by the greedy
algorithm. We also rewrite

$\displaystyle U^{GT}\left(\mathscr{C}^{G}\right)$
$\displaystyle=(K-|\mathscr{C}^{G}|)U_{\mathscr{C}^{G}}$ $\displaystyle
U^{GT}(\mathscr{C}^{OPT})$
$\displaystyle=(K-|\mathscr{C}^{OPT}|)U_{\mathscr{C}^{OPT}}$

To prove the claim we look at the graph obtained by the union of the cycles in
the optimal and the greedy solution. Since in each of the solutions, no node
can be in two cycles, it follows that in the obtained graph, no node can be in
more than two cycles. Let us start by assuming there is a cycle $\mathcal{C}$
with associated utility $u_{\mathcal{C}}$ in the optimal solution that does
not share any node with the greedy solution. This means

$\displaystyle\frac{U_{\mathscr{C}^{OPT}}-u_{\mathcal{C}}}{K-|\mathscr{C}^{OPT}|}\leq
u_{\mathcal{C}}\leq\frac{U_{\mathscr{C}^{G}}}{K-|\mathscr{C}^{G}|-1}$ (53)
$\displaystyle\rightarrow
U_{\mathscr{C}^{OPT}}\leq(K-|\mathscr{C}^{OPT}|+1)u_{\mathcal{C}}\leq
U_{\mathscr{C}^{G}}\frac{K-|\mathscr{C}^{OPT}|}{K-|\mathscr{C}^{G}|}$ (54)

where (53) follows from the fact that adding $\mathcal{C}$ to
$\mathscr{C}^{OPT}\setminus\\{\mathcal{C}\\}$ improves the objective, but
would not improve the objective for the greedy solution. From (54) we could
then conclude $|\mathscr{C}^{G}|>|\mathscr{C}^{OPT}|$, since for
$|\mathscr{C}^{G}|\leq|\mathscr{C}^{OPT}|$ we would find from (54) that
$U^{GT}\left(\mathscr{C}^{G}\right)\geq U^{GT}(\mathscr{C}^{OPT})$. This means
we can replace a cycle in $\mathscr{C}^{G}$ with this isolated cycle, to form
a set of cycle $\tilde{\mathscr{C}}^{G}$ whose objective is lower than
$\mathscr{C}^{G}$ by greedy search. In light of (54), we can iterate this
process by always picking the cycle to be replaced, in such a way that all the
cycles in the optimal solution share at least one node with the set of cycles
in $\tilde{\mathscr{C}}^{G}$. Now we have that all the cycles in the optimal
solution share at least one node with a cycle in $\tilde{\mathscr{C}}^{G}$.
If, instead, one has that no cycle $\mathcal{C}$ in the optimal solution is
isolated, and that there are isolated cycles in the greedy solution, then the
set $\tilde{\mathscr{C}}^{G}$ is formed by removing these cycles from
$\mathscr{C}^{G}$, lowering the objective (by submodularity and greedy
search). One would then again obtain that all the cycles in the optimal
solution share at least one node with the set of cycles in
$\tilde{\mathscr{C}}^{G}$. We now iteratively remove cycles from
$\tilde{\mathscr{C}}^{G}$ and $\mathscr{C}^{OPT}$, while bounding the loss in
performance and therefore obtain the factor approximation we want to prove. We
can remove cycles from $\tilde{\mathscr{C}}^{G}$ in decreasing order of
utility and since we know that for each cycle $\mathcal{C}^{\prime}$ of length
$L$ in $\tilde{\mathscr{C}}^{G}$ there are at most $L$ different cycles in the
optimal solution that share a node with $\mathcal{C}^{\prime}$, by greedy
search we have that $L\cdot u_{\mathcal{C}^{\prime}}$ is greater than the
utility given by the cycles in the optimal solution that are adjacent to cycle
$\mathcal{C}^{\prime}$. Let us then define $\hat{\mathscr{C}}^{G}$ as the
minimal subset of $\tilde{\mathscr{C}}^{G}$ that can cause the removal of all
the cycles in the optimal solution when iterating the procedure just
described, i.e. the set containing the first $|\hat{\mathscr{C}}^{G}|$ in
decreasing order of utility contained in $\tilde{\mathscr{C}}^{G}$. Again, by
sub-modularity and greedy search, one can easily find that the objective for
$\hat{\mathscr{C}}^{G}$ is lower than $\tilde{\mathscr{C}}^{G}$, since if the
objective could not be improved by removing a cycle from $\mathscr{C}^{G}$,
then it also cannot improve the objective for $\tilde{\mathscr{C}^{G}}$, which
has utility strictly greater than $\mathscr{C}^{G}$. At this point we can
prove (52) for $\hat{\mathscr{C}}^{G}$and this will prove it for
$\mathscr{C}^{G}$. We use $d_{\mathcal{C}}$ to define the number of cycles in
$\mathscr{C}^{OPT}$ that can be removed by removing the cycle $\mathcal{C}$ in
$\hat{\mathscr{C}}^{G}$ and
$d\triangleq\max\limits_{\mathcal{C}\in\hat{\mathscr{C}}^{G}}d_{\mathcal{C}}$.
By iterating our procedure described above, we end up having

$\displaystyle(K-|\hat{\mathscr{C}}^{G}|)U_{\hat{\mathscr{C}}^{G}}=\frac{1}{d}\frac{K-|\hat{\mathscr{C}}^{G}|}{K-|\mathscr{C}^{OPT}|}(K-|\mathscr{C}^{OPT}|)d\cdot
U_{\hat{\mathscr{C}}^{G}}$
$\displaystyle\geq\frac{1}{d}\frac{K-|\hat{\mathscr{C}}^{G}|}{K-|\hat{\mathscr{C}}^{G}|-d+1}(K-|\mathscr{C}^{OPT}|)d\cdot
U_{\hat{\mathscr{C}}^{G}}$
$\displaystyle\geq\frac{1}{d}\frac{K-|\hat{\mathscr{C}}^{G}|}{K-|\hat{\mathscr{C}}^{G}|-d+1}(K-|\mathscr{C}^{OPT}|)U_{\mathscr{C}^{OPT}}$
$\displaystyle\geq\frac{1}{\min\\{L_{\text{eff}},\frac{K}{2}\\}}\frac{K-1}{K-\min\\{L_{\text{eff}},\frac{K}{2}\\}}(K-|\mathscr{C}^{OPT}|)U_{\mathscr{C}^{OPT}}$

and since
$(K-|{\mathscr{C}}^{G}|)U_{{\mathscr{C}}^{G}}\geq(K-|\hat{\mathscr{C}}^{G}|)U_{\hat{\mathscr{C}}^{G}}$,
this concludes the proof. We have used the fact that $d\leq L_{\text{eff}}$
and that the function $d(K-d)$ has its maximum in $d=\frac{K}{2}$. Fig.8 shows
an example of the iterative procedure to obtain the bound just derived.

## References

  * [1] Y. M. Lu and M. N. Do, “A theory for sampling signals from a union of subspaces,” _IEEE Trans. Signal Process._ , vol. 56, no. 6, pp. 2334–2345, 2008.
  * [2] M. Mishali, Y. C. Eldar, and A. J. Elron, “Xampling: Signal acquisition and processing in union of subspaces,” _IEEE Trans. Signal Process._ , vol. 59, no. 10, pp. 4719–4734, 2011.
  * [3] G. L. Fudge, R. E. Bland, M. A. Chivers, S. Ravindran, J. Haupt, and P. Pace, “A Nyquist folding analog-to-information receiver,” in _Signals, Systems and Computers, 2008 42nd Asilomar Conference on_. IEEE, 2008, pp. 541–545.
  * [4] M. Mishali and Y. C. Eldar, “Blind multiband signal reconstruction: Compressed sensing for analog signals,” _IEEE Trans. Signal Process._ , vol. 57, no. 3, pp. 993–1009, 2009.
  * [5] ——, “From theory to practice: Sub-Nyquist sampling of sparse wideband analog signals,” _IEEE J. Sel. Topics Signal Process._ , vol. 4, no. 2, pp. 375–391, 2010.
  * [6] R. Venkataramani and Y. Bresler, “Perfect reconstruction formulas and bounds on aliasing error in sub-Nyquist nonuniform sampling of multiband signals,” _IEEE Trans. Inf. Theory_ , vol. 46, no. 6, pp. 2173–2183, 2000.
  * [7] F. Zeng, C. Li, and Z. Tian, “Distributed compressive spectrum sensing in cooperative multihop cognitive networks,” _IEEE J. Sel. Topics Signal Process._ , vol. 5, no. 1, pp. 37–48, 2011.
  * [8] Z. Zeinalkhani and A. H. Banihashemi, “Iterative recovery algorithms for compressed sensing of wideband block sparse spectrums,” in _Communications (ICC), 2012 IEEE International Conference on_. IEEE, 2012, pp. 1630–1634.
  * [9] D. Cohen and Y. C. Eldar, “Sub-Nyquist sampling for power spectrum sensing in cognitive radios: A unified approach,” _IEEE Trans. Signal Process._ , vol. 62, no. 15, pp. 3897–3910, 2014.
  * [10] E. Arias-Castro and Y. C. Eldar, “Noise folding in compressed sensing,” _IEEE Signal Processing Letters_ , vol. 18, no. 8, pp. 478–481, 2011.
  * [11] D. Baron, S. Sarvotham, and R. G. Baraniuk, “Bayesian compressive sensing via belief propagation,” _IEEE Trans. Signal Process._ , vol. 58, no. 1, pp. 269–280, 2010.
  * [12] M. A. Lexa, M. E. Davies, and J. S. Thompson, “Compressive and noncompressive power spectral density estimation from periodic nonuniform samples,” _arXiv preprint arXiv:1110.2722_ , 2011.
  * [13] D. D. Ariananda and G. Leus, “Compressive wideband power spectrum estimation,” _IEEE Trans. Signal Process._ , vol. 60, no. 9, pp. 4775–4789, 2012.
  * [14] Q. Zhao, B. Krishnamachari, and K. Liu, “On myopic sensing for multi-channel opportunistic access: structure, optimality, and performance,” _IEEE Trans. Wireless Commun_ , vol. 7, no. 12, 2008.
  * [15] J. Unnikrishnan and V. V. Veeravalli, “Algorithms for dynamic spectrum access with learning for cognitive radio,” _IEEE Trans. Signal Process._ , vol. 58, no. 2, pp. 750–760, 2010.
  * [16] K. Wang and L. Chen, “On optimality of myopic policy for restless multi-armed bandit problem: An axiomatic approach,” _IEEE Trans. Signal Process._ , vol. 60, no. 1, pp. 300–309, 2012.
  * [17] L. Ferrari, Q. Zhao, and A. Scaglione, “Utility maximizing sequential sensing over a finite horizon,” _IEEE Trans. Signal Process._ , vol. 65, no. 13, pp. 3430–3445, 2017.
  * [18] N. Michelusi and U. Mitra, “Cross-layer estimation and control for cognitive radio: Exploiting sparse network dynamics,” _IEEE Transactions on Cognitive Communications and Networking_ , vol. 1, no. 1, pp. 128–145, 2015.
  * [19] Y. Ma, Y. Gao, A. Cavallaro, C. Parini, W. Zhang, and Y.-C. Liang, “Sparsity independent sub-Nyquist rate wideband spectrum sensing on real-time tv white space,” _IEEE Trans. Veh. Technol._ , 2017.
  * [20] J. Hao, F. Tosato, and R. J. Piechocki, “Sequential compressive sensing in wireless sensor networks,” in _Vehicular Technology Conference (VTC Spring), 2012 IEEE 75th_. IEEE, 2012, pp. 1–5.
  * [21] D. M. Malioutov, S. R. Sanghavi, and A. S. Willsky, “Sequential compressed sensing,” _IEEE J. Sel. Topics Signal Process._ , vol. 4, no. 2, pp. 435–444, 2010.
  * [22] J. Zhao, X. Wang, and Q. Liu, “Cooperative sequential compressed spectrum sensing over wide spectrum band,” in _Sensing, Communication, and Networking (SECON), 2015 12th Annual IEEE International Conference on_. IEEE, 2015, pp. 1–9.
  * [23] G. Braun, S. Pokutta, and Y. Xie, “Info-greedy sequential adaptive compressed sensing,” _IEEE J. Sel. Topics Signal Process._ , vol. 9, no. 4, pp. 601–611, 2015.
  * [24] S. Bagheri and A. Scaglione, “The restless multi-armed bandit formulation of the cognitive compressive sensing problem,” _IEEE Trans. Signal Process._ , vol. 63, no. 5, pp. 1183–1198, March 2015.
  * [25] H. Sun, W.-Y. Chiu, J. Jiang, A. Nallanathan, and H. V. Poor, “Wideband spectrum sensing with sub-Nyquist sampling in cognitive radios,” _IEEE Trans. Signal Process._ , vol. 60, no. 11, pp. 6068–6073, 2012.
  * [26] L. Chen, J. Jin, and Y. Gu, “A calibration system and perturbation analysis for the modulated wideband converter,” in _Signal Processing (ICSP), 2010 IEEE 10th International Conference on_. IEEE, 2010, pp. 78–81.
  * [27] E. Israeli, S. Tsiper, D. Cohen, E. Shoshan, R. Hilgendorf, A. Reysenson, and Y. C. Eldar, “Hardware calibration of the modulated wideband converter,” in _Global Communications Conference (GLOBECOM), 2014 IEEE_. IEEE, 2014, pp. 948–953.
  * [28] Y. Kaspi, O. Shayevitz, and T. Javidi, “Searching for multiple targets with measurement dependent noise,” in _Information Theory (ISIT), 2015 IEEE International Symposium on_. IEEE, 2015, pp. 969–973.
  * [29] G. K. Atia and V. Saligrama, “Boolean compressed sensing and noisy group testing,” _IEEE Trans. Inf. Theory_ , vol. 58, no. 3, pp. 1880–1901, 2012.
  * [30] J. Scarlett and V. Cevher, “Converse bounds for noisy group testing with arbitrary measurement matrices,” in _Information Theory (ISIT), 2016 IEEE International Symposium on_. IEEE, 2016, pp. 2868–2872.
  * [31] C. L. Chan, P. H. Che, S. Jaggi, and V. Saligrama, “Non-adaptive probabilistic group testing with noisy measurements: Near-optimal bounds with efficient algorithms,” in _Communication, Control, and Computing (Allerton), 2011 49th Annual Allerton Conference on_. IEEE, 2011, pp. 1832–1839.
  * [32] A. Sharma and C. R. Murthy, “On finding a subset of non-defective items from a large population using group tests: Recovery algorithms and bounds,” in _Acoustics, Speech and Signal Processing (ICASSP), 2015 IEEE International Conference on_. IEEE, 2015, pp. 4150–4154.
  * [33] J. A. Tropp, J. N. Laska, M. F. Duarte, J. K. Romberg, and R. G. Baraniuk, “Beyond Nyquist: Efficient sampling of sparse bandlimited signals,” _IEEE Trans. Inf. Theory_ , vol. 56, no. 1, pp. 520–544, Jan 2010.

|  Lorenzo Ferrari (S ’14) received his PhD in Electrical Engineering at
Arizona State University and is now a Senior Engineer at Qualcomm Research.
Prior to that, he received his B.Sc. and M.Sc degree in Electrical Engineering
from University of Modena, Italy in 2012 and 2014 respectively. His research
interests lie in the broad area of wireless communications and signal
processing. He has received the IEEE SmartGridComm 2014 Best Student Paper
Award for the paper “The Pulse Coupled Phasor Measurement Unit”.
---|---
|  Anna Scaglione (F ’11) is currently a professor in electrical and computer
engineering at Arizona State University. She was previously at the University
of California at Davis, Cornell University and University of New Mexico. Her
research focuses on various applications of signal processing in network and
data science that include intelligent infrastructure for energy delivery and
information systems. Dr. Scaglione was elected an IEEE fellow in 2011\. She
received the 2000 IEEE Signal Processing Transactions Best Paper Award and
more recently was honored for the 2013, IEEE Donald G. Fink Prize Paper Award
for the best review paper in that year in the IEEE publications, her work with
her student earned 2013 IEEE Signal Processing Society Young Author Best Paper
Award (Lin Li). She was EIC of the IEEE Signal Processing Letters and served
in many other capacities the IEEE Signal Processing, IEEE Communication
societies and is currently Associate Editor for the IEEE Transactions on
Control over Networked Systems.
---|---