IEEE Signal Processing Magazine - January 2018 - 155

associated difference set contains all integers in [0, N ]. Intuitively, it may be viewed as a ruler with some marks erased but
still able to measure all integer distances between zero and
its length. For example, consider the minimal sparse ruler of
length N = 10. This ruler requires M = 6 marks, as shown in
Figure 17. All of the lags 0 # x # 10 on the integer grid are
identifiable. There is no closed-form expression for the maximum compression ratio M/N that is achievable using a sparse
ruler; however, the following bounds hold:
x (N - 1)

N

# M #
N

3 (N - 1)
,
N

(21)

where x . 2.4345 [79]. A circular or modular sparse ruler
extends this idea to include periodicity. Such designs that seek
minimal sparse rulers, i.e., rulers with a minimal number of
marks M, can achieve compression ratios M/N on the order
of N . As N increases, the compression ratio may become
arbitrarily low.
Two additional sampling techniques specifically designed
for autocorrelation recovery are nested arrays [74] and coprime
sampling [75], presented in the context of autocorrelation estimation as well as beamforming and DOA estimation applications. In nested and coprime structures, similar to multicosets,
the corresponding coarrays have more degrees of freedom
than those of the original arrays, leading to a finer grid for the
time lags with respect to the sampling times. We now quickly
review both sampling structures and their corresponding difference coarrays and show how the autocorrelation of an arbitrary stationary signal can be recovered on the Nyquist grid
from low-rate samples.
In its simplest form, the nested-array [74] structure has two
levels of sampling density. The first-level samples are at the
N 1 locations {,TNyq} 1 # , # N 1, and the second-level samples are
at the N 2 locations {(N 1 + 1) kTNyq} 1 # k # N 2 . This nonuniform
sampling is then repeated with the period (N 1 + 1) N 2 TNyq .
Because there are N 1 + N 2 samples in intervals of length
(N 1 + 1) N 2 TNyq, the average sampling rate of a nested-array
sampling set is given by

0

1

2

3

6

10

FIGURE 17. A minimal sparse ruler of order M = 6 and length N = 10.

-[(N 1 + 1) N 2 - 1] # n # [(N 1 + 1) N 2 - 1]. Going back to
our autocorrelation estimation problem, this result shows that,
by proper averaging, we can estimate R (x) at any lag x on
the Nyquist grid from nested-array samples with arbitrarily
low sampling rate as
Z Q -1
]1
u
u
u
*
] Q / x (N (k + q)) x (, + Nq), n = Nk - , ,
q
0
=
(24)
Rt [n] = [ Q -1
] 1 / x (Nu (k + q)) x * (Nu (, + q)), n = Nu (k - ,),
] Q q =0
\
where Q is the number of snapshots used for averaging and
Nu = N 1 + 1. Here, k and , are such that (23) holds.
Another sampling technique designed for autocorrelation
recovery is coprime sampling. It involves two uniform sampling sets with spacing N 1 TNyq and N 2 TNyq, respectively,
where N 1 and N 2 are coprime integers. The average sampling
rate of such a sampling set, given by
fs =

1
+ 1 ,
N 1 TNyq N 2 TNyq

(25)

can, again, be made arbitrarily small compared to the Nyquist
rate 1 TNyq by choosing arbitrarily large coprime numbers
N 1 and N 2 . The associated difference set, normalized by
TNyq, is composed of elements of the form n = N 1 k - N 2 ,.
Because N 1 and N 2 are coprime, there exist integers k and ,
such that the previous difference achieves any integer value n.
Therefore, the autocorrelation may be estimated by proper
averaging, as
Q -1

fs =

N1 + N2
1
+ 1 .
.
(N 1 + 1) N 2 TNyq
N 1 TNyq N 2 TNyq

(22)

This rate can be arbitrarily low because N 1 and N 2 may be as
large as we choose at the expense of latency.
Now, consider the difference coarray, which has a contribution from the cross differences and the self-differences. The
nonnegative cross differences, normalized by TNyq for clarity,
are given by
n = (N 1 + 1) k - ,, 1 # k # N 2, 1 # , # N 1.

Rt [n] = 1 / x (N 1 (k + N 2 q)) x * (N 2 (, + N 1 q)),
Q q =0

(23)

All differences in the range 1 # n # (N 1 + 1) N 2 - 1 are covered except for multiples of N 1 + 1. These are precisely the
self-differences among the second array. As a result, the difference coarray is a filled array composed of all integers

(26)

where k and , are such that n = N 1 k - N 2 ,.
The main drawback of both techniques, besides the practical issue of analog bandwidth that is similar to multicoset
sampling, is the added latency required for averaging. Furthermore, in practice, synchronizing ADCs with different sampling rates can be challenging. Finally, nested-array sampling
still requires one sampler operating at the Nyquist rate. Thus,
there is no saving in terms of hardware but only in memory
and computation.

Cyclostationary detection
Communication signals often exhibit statistical periodicity,
due to schemes like carrier modulation or periodic keying
[81]. Therefore, such signals are cyclostationary processes

IEEE SIGNAL PROCESSING MAGAZINE

|

January 2018

|

155
Table of Contents for the Digital Edition of IEEE Signal Processing Magazine - January 2018
