1

Deterministic coding theorems for blind sensing:
optimal measurement rate and fractal dimension

arXiv:1708.05769v1 [cs.IT] 18 Aug 2017

Taehyung J. Lim and Massimo Franceschetti, Senior Member, IEEE

Abstract—Completely blind sensing is the problem of recovering bandlimited signals from measurements, without any spectral
information beside an upper bound on the measure of the whole
support set in the frequency domain. Determining the number
of measurements necessary and sufficient for reconstruction has
been an open problem, and usually partially blind sensing is
performed, assuming to have some partial spectral information
available a priori. In this paper, the minimum number of
measurements that guarantees perfect recovery in the absence
of measurement error, and robust recovery in the presence of
measurement error, is determined in a completely blind setting.
Results show that a factor of two in the measurement rate is
the price pay for blindness, compared to reconstruction with full
spectral knowledge. The minimum number of measurements is
also related to the fractal (Minkowski-Bouligand) dimension of a
discrete approximating set, defined in terms of the Kolmogorov
ǫ-entropy. These results are analogous to a deterministic coding
theorem, where an operational quantity defined in terms of minimum measurement rate is shown to be equal to an informationtheoretic one. A comparison with parallel results in compressed
sensing is illustrated, where the relevant dimensionality notion in
a stochastic setting is the information (Rényi) dimension, defined
in terms of the Shannon entropy.

A. Problem set-up
Let f : R → R be square-integrable and such that

[−Ω,Ω]

m( ) ≤ 2Ω’

Ω

−Ω

2Ω

ω

f(t)

-T/2

-T/2

t

Fig. 1. Illustration of a sparse multi-band signal observed over a single time
interval.

where M is an operator from multi-band signals to M dimensional vectors and e ∈ RM is the measurement error.
We assume each measurement yn ∈ y results from observing the signal over the interval [−T /2, T /2] through the inner
product with a bandlimited kernel, plus an error term.

−T /2

(1)

where F indicates Fourier transform, ω indicates angular
frequency, and Q is a subset of the interval [−Ω, Ω] of measure
m(Q) ≤ 2Ω′ .

f(ω)|

Definition 1. (Measurements) For all n ∈ {1, . . . , M }, we
have
Z T /2
f (t)ϕn (t)dt + en ,
(4)
yn =

I. I NTRODUCTION

Ff (ω) = 0, for ω 6∈ Q,

|

(2)

A typical example occurs when Q is the union of a finite
number of disjoint sub-intervals of [−Ω, Ω] and Ω′ ≪ Ω, see
Figure 1. These kind of signals arise in many applications,
ranging from radio, to audio, and biological communication
and sensing systems. A natural question is what is the minimum number of measurements that can be performed over a
given time interval and that guarantees reconstruction with a
minimum amount of error.
To address this question, we consider a measurement vector
y ∈ RM
y = Mf (t) + e,
(3)
The authors are with the Information Theory and Applications Center
(ITA) of the California Institute of Telecommunications and Information
Technologies (CALIT2), Department of Electrical and Computer Engineering, University of California, San Diego CA, 92093, USA. Email: taehyung.lim@hotmail.com, massimo@ece.ucsd.edu. This work was presented
in part at the IEEE International Symposium on Information Theory, Aachen,
Germany, June 2017. This work was partially supported by the National
Science Foundation under Award CCF-1423648.

where
F ϕn (ω) = 0 for ω 6∈ [−Ω, Ω].

(5)

This set-up covers a wide range of real measurements.
Possible bandlimited kernels that fall in this framework include
the Shannon cardinal basis sinc(·) functions [1], the Slepian
prolate spheroidal wave functions (PSWF) [2], as well as other
bandlimited functions of practical interest, such as wavelets,
and splines. The measurements are functionals of the signal
over the entire observation interval, but in some cases they
can reduce to the sampled signal values. For example, for the
cardinal basis the measurements in (4) also correspond to lowpass filtering and sampling, and the signal can be recovered by
low-pass filtering the sampled signal values [3]. This special
case is illustrated in Figure 2. The general case is illustrated
in Figure 3.
In the general setting, our aim is to determine the smallest
measurement rate
M
(6)
M̄ = lim
T →∞ T
for which it is possible to obtain an approximation fM of f
from y, such that the energy of the reconstruction error is
at most proportional to the energy of the measurement error,

2

Post-Filter

Pre-Filter

+

*

x

dN

*

Ω
π

Fig. 2. Block diagram for sampling measurement and reconstruction. The
symbol ∗ indicates convolution.

N
T

as

Fig. 4. Phase transition of the Kolmogorov N -width dN of bandlimited
signals.

+

x

Ω
π

and such that
lim kf − fN k2 = 0.

D/C

T →∞

+

x

Fig. 3. Block diagram for general measurement and reconstruction. The
box D/C stands for discrete-to-continuous transformation and performs the
reconstruction of the signal from the discrete measurements.

as the size of the observation interval T → ∞. This corresponds to determining the scaling of the minimum number of
measurements M = M (T ) that guarantees robust recovery
of any multi-band signal, namely a small perturbation in the
measurement does not lead to a large reconstruction error.
Definition 2. (Robust recovery). There exists a universal
constant c ≥ 0, such that for T large enough
Z T /2
kf − fM k2 =
[f (t) − fM (t)]2 dt
≤c

−T /2
M
X

e2n .

(7)

n=1

When the measurement error tends zero, robust recovery
reduces to perfect recovery of the signal. Namely,
Definition 3. (Perfect recovery).
lim kf − fM k2 = 0.

T →∞

(8)

B. Bandlimited signals
Since our signals are assumed to be bandlimited to Ω,
one may readily observe that in the absence of measurement
error they can be perfectly recovered from a number of
measurements slightly above the Nyquist number
N0 = ΩT /π.

(9)

For any f satisfying (1) and (2), and ν > 0, we can construct
an approximation fN of f from a measurement vector y of
size
N = (1 + ν)ΩT /π,
(10)

(11)

This classic result is equivalent to stating that a measurement
rate strictly above Ω/π is sufficient for reconstruction of any
bandlimited singnal, and constitutes one of the milestones of
electrical and communication engineering.
For bandlimited signals, the rate Ω/π is also optimal, in the
following approximation-theoretic sense. Consider performing
signal reconstruction by a linear interpolation of a number
N > 0 of orthogonal basis functions
fN (t) =

N
X

yn ϕn (t),

(12)

n=1

and let the Kolmogorov N -width be the smallest approximation error achievable for all signals in the space, over
all possible choices of basis sets. This minimum error is
achieved by measurements that provide the coefficients of the
interpolation through the integrals
Z T /2
1
yn =
f (t)ϕn (t)dt, n ∈ {1, . . . , N },
(13)
λn −T /2
where {λn } are the eigenvalues of a Fredholm integral equation of the second kind arising from Slepian’s concentration
problem [2], and the basis functions {ϕn } are the corresponding eigenfunctions, called PWSF [4]. The measurement
rate Ω/π corresponds to the critical threshold at which the
Kolmogorov N -width transitions from strictly positive values
to zero, as T → ∞ [5]. This phase transition behavior of the
approximation error is illustrated in Figure 4. With a number
of measurements (1+ν)ΩT the error tends to zero as T → ∞,
while with a number of measurements ΩT /π + o(T ) the error
remains positive as T → ∞.
C. Multi-band signals
For bandlilmtied signals that are supported over disjoint
sub-bands, an important extension of the results above, due
to Landau and Widom [6], states that if we have a priori
knowledge of the size and positions of all the sub-bands, then
signal reconstruction with vanishing error as T → ∞ is also
possible using the smaller number of measurements
S = (1 + ν)Ω′ T /π.

(14)

3

A simple way to achieve this result is to demodulate
each sub-band down to baseband, isolate it through low-pass
filtering, and then sample each sub-band separately. The key
contribution of Landau and Widom is to consider the optimal
subspace approximation, and show a phase transition of the
error expressed in terms of Kolmogorov N -width. As in the
single-band case, a subspace approximation with vanishing
error for all multi-band signals of a given frequency allocation
is obtained with a number of measurements (1 + ν)Ω′ T , while
a subspace approximation with vanishing error is not possible
for all multi-band signals using a number of measurements
Ω′ T /π + o(T ), and the value of the error is controlled by the
pre-constant in the o(T ) term. It follows that for multi-band
signals the Nyquist number N0 = ΩT /π can be replaced by
the “sparsity number”
S0 = Ω′ T /π,

(15)

and the occupied portion of the frequency bandwidth determines the critical measurement rate Ω′ /π required for reconstruction. In the case of sampling measurements, Landau [7]
also showed that a rate Ω′ /π is necessary for reconstruction,
regardless of the reconstruction strategy being linear or not.
The results of above rely on two critical assumptions. First,
they need a priori knowledge of the spectral occupation,
since the eigenvalues and the optimal eigenfunctions used
for reconstruction are solutions of an integral equation that
depends on the spectral support set. In practice, it might be
difficult to know the exact number of sub-bands, their location,
and their widths prior to the measurements. A second critical
assumption is the absence of measurement error. In practice,
the measurement process always carries a certain amount of
error and its impact on the reconstruction error should be taken
into account.
D. Completely blind sensing
In this paper, we consider robust signal reconstruction in
the presence of measurement error and without any a priori
knowledge of the sub-bands beside an upper bound on the
measure of the whole support set of the signal in the frequency
domain. We call this robust, completely blind sensing. The
blindness requirement is important when detecting the subbands is impossible or too expensive to implement. The
robustness requirement is important to guarantee stability in
the reconstruction process.
Partially blind sensing, where some partial spectral information is assumed, has been studied extensively. First key
results were given in a series of papers by Bresler and coauthors [8], [9], [10]. Later extensions [11], [12] reduced the
number of a priori assumptions, but still require knowledge
of the number of sub-bands, and of their widths. The same
assumptions are made in [13], [14], [15]. The main result in
this setting is that the price to pay for partial blindness is a
factor of two in the measurement rate. Several reconstruction
strategies have been proposed using a measurement rate above
2Ω′ /π, all assuming some partial spectral knowledge, and
lacking an information-theoretic converse. We remove these
assumptions, show that a measurement rate 2Ω′ /π is sufficient

for robust reconstruction in a completely blind setting, and
provide a tight converse result. We also provide a deterministic
coding theorem for continuous analog sources, giving an
interpretation of the minimum number of measurements in
terms of the “effective” Minkowski-Boulingand dimension of
the infinite-dimensional set of multi-band signals, expressed
in terms of the Kolmogorov ǫ-entropy. This is compared
with an analogous interpretation arising in the framework of
compressed sensing, where the objective is the lossless source
coding of a discrete, analog, stochastic process [16], [17]. In
that case, an analogous coding theorem has been given in terms
of the Rény dimension, expressed in terms of the Shannon
entropy.
Finally, we remark that while in the case of multi-band signals of a given sub-band allocation the results of Landau and
Widom provide an optimal subspace approximation in terms of
a linear interpolation of eigenfunctions supported over multiple
sub-bands, and having the highest energy concentration over
the observation domain, our results only provide an answer to
the question of whether recovery is possible or not, without
giving an explicit approximation procedure. In our case, the
discrete-to-continuous block in Figure 3 remains unknown.
Nevertheless, from an information-theoretic perspective one
is primarily interested in the possibility of recovery using any
discrete to continuous transformation, and does not wish to
restrict reconstruction to a linear approximation strategy. The
explicit construction of practical blind recovery strategies is
certainly of interest, and these should be compared with the
information-theoretic optimum determined here.
The rest of the paper is organized as follows: In section II
we describe our results. In section III we compare our results
with compressed sensing and illustrate coding theorems in
deterministic and stochastic settings. In section IV we provide
some definitions and preliminaries that are useful for our
derivation. Proofs are given in section V and VI. Section VII
draws conclusions and discusses future work.
II. D ESCRIPTION

OF THE RESULTS

A. Noiseless Case
Theorem 1. (Direct). In the absence of measurement error,
we can perfectly recover any signal f satisfying (1) and (2)
using a measurement rate
2Ω′
.
(16)
π
Theorem 2. (Converse). In the absence of measurement error,
we cannot perfectly recover all signals f satisfying (1) and (2)
using a measurement rate
M̄ >

2Ω′
.
(17)
π
These results can interpreted in terms of the effective dimensionality of the signals’ space, leading to a coding theorem.
For bandlimited signals, the effective number of dimensions
can be identified with the Nyquist number N0 = ΩT /π. For
multi-band signals for which the location and widths of all the
sub-bands is fixed a priori, as in the Landau-Widom case, it
can be identified with the sparsity number S0 = Ω′ T /π. On
M̄ ≤

4

the other hand, without any a priori knowledge, we need to
account for the additional degrees of freedom of allocating the
sub-bands in the frequency domain, and our results indicate
that the effective dimensionality increases to 2S0 .
To make these considerations precise, we consider an
information-theoretic quantity that measures the dimensionality of a set in metric space, namely its fractal (MinkowskiBouligand) dimension, which corresponds to the rate of growth
of the Kolmogorov ǫ-entropy of successively finer discretizations of the space, and represents the degree of fractality of
the set [18].
Definition 4. (Fractal dimension). For any subset X of a
metric space, the fractal dimension is
Hǫ (X )
,
− log ǫ
where Hǫ is the Kolmogorov ǫ-entropy [19].
dimF (X ) = lim

ǫ→0

(18)

If this limit does not exist, then the corresponding upper
and lower fractal dimensions are defined using lim sup and
lim inf, respectively.
We also define the dilation
Definition 5. (Minkowski sum).
X ⊕ X = {x1 + x2 : x1 , x2 ∈ X }.

(19)

Consider now the set of all bandlimited signals whose energy is at most one. These signals can be approximated by an
infinite set XB of vectors, each containing N = (1 + ν)ΩT /π
real coefficients. Using the PSWF as a basis for interpolation,
every assignment of coefficients satisfying the given energy
constraint approximates, with vanishing error as T → ∞, a
bandlimited signal. In the appendix, we show that
dimF (XB ) = dimF (XB ⊕ XB ),

(20)

and letting the fractal dimension rate of the approximating set
be
dimF (XB )
RF (XB ) = lim
,
(21)
T →∞
T
we have
RF (XB ) = Ω/π,
(22)
which coincides with the measurement rate needed for reconstruction.
Next, we quantize the bandwidth at level ∆ > 0 and let
J = {−Ω, −Ω + ∆, −Ω + 2∆, · · · , Ω}.

(23)

We consider the subset of all multi-band signals of a given
sub-band allocation, whose energy is at most one, and such
that the extremal points of all sub-bands belong to J . This
subset of signals approximates, with vanishing energy error
as ∆ → 0, the one of all multi-band signals of a given subband allocation and of energy at most one. It can also be
approximated, with vanishing error as T → ∞, by an infinite
set XMB (∆) of vectors, each containing N = (1 + ν)ΩT /π
real coefficients of a PSWF interpolation. Compared to the
previous case, the choice of the coefficients is now restricted
by the given sub-band allocation, so that we have
XMB (∆) ⊂ XB .

(24)

Following the same argument used to derive (20), we obtain
dimF [XMB (∆)] = dimF [XMB (∆) ⊕ XMB (∆)].

(25)

In this case, however, the N -dimensional prolate spheroidal
approximation is somewhat redundant, and following the same
argument used to derive (22), we obtain
lim RF [XMB (∆)] = Ω′ /π,

∆→0

(26)

which coincides with the Landau-Widom rate [6], [7] needed
for reconstruction.
Finally, consider the subset of all multi-band signals whose
energy is at most one, having an arbitrary sub-band allocation
of measure at most 2Ω′ , and such that the extremal points of
all sub-bands belong to J . These signals can be approximated,
as T → ∞, by an infinite set X (∆) of vectors, each containing
N = (1 + ν)ΩT /π real coefficients of a PSWF interpolation.
The choice of the coefficients is now restricted only by the
measure of the occupied portion of the spectrum and not by
a specific sub-band allocation, and we have
XMB (∆) ⊂ X (∆) ⊂ XB .

(27)

By combining Theorems 1 and 2 with Theorems 3 and 4
below, we obtain
lim RF [X (∆)] = Ω′ /π.

∆→0

(28)

Theorem 3. (Direct). In the absence of measurement error,
we can perfectly recover any signal f satisfying (1) and (2)
using a measurement rate
M̄ > 2 lim RF [X (∆)].
∆→0

(29)

Theorem 4. (Converse). In the absence of measurement error,
we cannot perfectly recover all signals f satisfying (1) and (2)
using a measurements rate
M̄ ≤ 2 lim RF [X (∆)].
∆→0

(30)

In section VI, we also show that
RF [X (∆) ⊕ X (∆)] = 2RF [X (∆)],

(31)

which also implies
lim

T →∞

dimF [X (∆) ⊕ X (∆)]
= 2.
dimF [X (∆)]

(32)

We now give a geometric interpretation of these results.
The set of all multi-band signals is the union of infinitely
many subsets, each corresponding to the multi-band signals of
a given sub-band allocation. The Minkowski sum in (19) takes
into account the additional degrees of freedom of allocating
the sub-bands in the frequency domain. Within any subset,
any multi-band signal is specified by essentially dimF [X (∆)]
coordinates, but when considering the union of all subsets, it
is specified by essentially 2dimF [X (∆)] coordinates. By (31)
it then follows that the relevant information-theoretic quantity
that characterizes the possibility of reconstruction is the fractal
dimension rate of the dilation, rather than the fractal dimension
rate of the set itself.

5

Finally, it is useful introduce the sparsity fraction as the
ratio of the fractal dimension of the approximating set and its
ambient dimension:

Φ

...
1 2

3 4

...

N-1 N

x

Definition 6. (Sparsity fraction).
dimF [X (∆)]
.
(33)
N
By the results above, it is easy to see that the sparsity
fraction is equal to the fraction of occupied bandwidth, namely
substituting N = (1 + ν)ΩT /π into (33) we get
σ = inf lim lim

...
1 2

3 4

...

N-1 N

X

Fig. 5. Illustration of a discrete vector with a sparse representation.

ν>0 ∆→0 T →∞

Ω′
RF [X (∆)] π
=
,
ν>0 ∆→0
Ω
(1 + ν)
Ω

σ = inf lim

(34)

and twice the sparsity fraction corresponds to the critical number of measurements per unit ambient dimension necessary
and sufficient for reconstruction.
B. General Case
Results generalize to the noisy case. The critical threshold
for the number of measurements is not affected by the presence
of a measurement error, provided that we ask for robust, rather
than perfect reconstruction.
Theorem 5. (Direct). We can robustly recover all signals f
satisfying (1) and (2) using a measurements rate
2Ω′
.
(35)
∆→0
π
Theorem 6. (Converse). We cannot robustly recover all signals f satisfying (1) and (2) using a measurements rate
M̄ > 2 lim RF [X (∆)] =

2Ω′
.
(36)
∆→0
π
A factor of two is the price to pay for blindness for both
robust recovery and perfect recovery of multi-band signals,
and in virtue of (31) the relevant dimensionality notion is the
one associated to the dilation of the set.
M̄ ≤ 2 lim RF [X (∆)] =

III. C OMPARISON

WITH COMPRESSED SENSING

There are analogies between our results and the ones in
compressed sensing. We illustrate similarities and differences
in deterministic and stochastic settings. For simplicity, we only
consider the case of zero measurement error, but the same
considerations apply to the case of non-zero measurement
error.
A. Deterministic setting
Consider an N -dimensional vector x such that
x = ΦX,

(37)

where Φ is an N × N orthogonal matrix and X has at most
S non-zero elements. If S ≪ N we say that X is a sparse
representation of x. An example is illustrated in Figure 5.
We define a measurement vector
y = Ax,

(38)

where A is an M × N matrix, and M is the number of measurements. Cleary, x can be recovered from N measurements

by observing all the elements of x. In this case, the N × N
measurement matrix A is diagonal. If we know the position
of the nonzero elements of X, then S measurements are also
enough to perfectly reconstruct x. In this case, each measurement extracts the nth coefficient of X from Φ−1 x, and the
signal is recovered by performing a final multiplication by Φ.
However, if we only know that x has a sparse representation,
but we do not know the positions of the nonzero elements
of X, without further investigation we can only conclude that
that the minimum number M of measurements sufficient for
reconstruction is S ≤ M ≤ N . The objective of compressed
sensing is to reconstruct any sparse, discrete signal x using
M ≪ N measurements [20].
Without worrying about an explicit reconstruction procedure, a simple linear algebra argument [16, Remark 2], [20,
Section 2.2] shows that the necessary and sufficient number
of measurements for reconstruction is 2S. It follows that
in both the continuous and discrete settings, the number of
linear measurements necessary and sufficient for reconstruction is equal to twice the sparsity level of the signal. The
main differences between the two settings are as follows:
the compressed sensing formulation assumes knowledge of
the matrix Φ, corresponding to the basis where the discrete
signal is sparse. In the case of blind sensing, it is only
assumed that the signal does not occupy the whole frequency
spectrum, but the discrete basis set required for the optimal
representation is unknown a priori. A more extreme situation
is the blind compressed sensing set-up [21], [22], where there
is a complete lack of knowledge about the signal. In this case,
the basis must either be learned from data, or selected from a
restricted set. Finally, in blind sensing the reconstruction error
tends to zero as T → ∞, while in compressed sensing perfect
reconstruction is possible for all N .
B. Stochastic setting
The problem of compressed sensing can also be formulated
in a probabilistic setting. In this case, the discrete signal to be
recovered is modeled as a stochastic process and the objective
is to reconstruct the signal with arbitrarily small probability of
error, given a sufficiently long observation sequence. Viewing
the measurement operator as an encoder and the reconstruction
operator as a decoder acting on a sequence of independent,
identically distributed (i.i.d.), real-valued random variables,
the compressed sensing set-up corresponds to lossless source
coding of analog memoryless sources when the encoding
operation C : RN → RM is the multiplication by a realvalued matrix, see Figure 6. Compared to the deterministic
setting, where reconstruction is required for all possible source
signals, here the performance is measured on a probabilistic
basis by considering long block lengths and averaging with

6

x

Encoder

y

Decoder

We can also give an information-theoretic definition of the
sparsity fraction in the stochastic setting that is analogous to
Definition 6.

x

Definition 8. (Sparsity fraction —stochastic setting).

Fig. 6. Source coding view of compressed sensing.

respect to the distribution of the source signal. Compared to
the continuous setting, probabilistic concentration is used to
bound the error performance as N → ∞, instead than spectral
concentration as T → ∞.
Modeling x in (38) as a random vector composed of N
independent random variables (X1 , X2 , . . . XN ), all distributed
as X, to capture the notion of sparsity in a probabilistic setting
we may consider the following mixture distribution for the
source sequence
pX (x) = (1 − γ)δ(x) + γp′ (x),

(39)
′

where δ(·) is Dirac’s distribution, 0 ≤ γ ≤ 1, and p is an
absolutely continuous probability measure 1 .
By the law of large numbers, the parameter γ in (39) represents, for large values of N , the level of sparsity of the signal
in terms of the fraction of its nonzero elements. Given this
source model, a basic result for probabilistic reconstruction
by Wu and Verdú [16], [17] shows that the threshold for
the smallest measurement rate that guarantees reconstruction
with vanishing probability of error is independent of the prior
distribution of the non-zero elements p′ , and equals the sparsity
level γ. Comparing this result with the deterministic case,
it follows that probabilistic reconstruction, rather than reconstruction for all signals in the space, yields an improvement
in the number of measurements of a factor of two.
Wu and Verdú also showed that their result can be viewed
in terms of the infomation (Rényi) dimension of the source
process. This is somewhat analogous to a coding theorem,
where an operational quantity, such as the smallest rate for
recovery, is shown to be equal to an information-theoretic one.
Consider the quantized version Xǫ of X obtained from the
discrete probability measure induced by partitioning the real
line into intervals of size ǫ and assigning to the quantized
variable the probability of lying in each interval. The Rényi
dimension of X is defined as [23]
Definition 7. (Information dimension).
HXǫ
,
dimI (X) = lim
ǫ→0 − log ǫ
where HXǫ indicates the Shannon entropy of Xǫ .

(40)

dimI (X1 , X2 , . . . XN )
.
N

(42)

For a mixture distribution such as (39), assuming H(⌊X⌋) <
∞, Rényi showed that [23]
dimI (X) = γ.

(43)

Combining this result with (41) it follows that the sparsity
fraction is also equal to γ, and the fraction of non-zero elements of the signal coincides with the information dimension
per unit ambient dimension. In the analogous deterministic
setting, the fraction of occupied bandwidth plays the role of
the fraction of non-zero elements of the discrete-time signal,
and this coincides with the fractal dimension per unit ambient
dimension of its prolate spheroidal approximation.
C. Coding theorems
The results of Wu and Verdú combined with Rényi’s one in
(43) yield the following general coding theorem:
Theorem 7. (Coding theorem —stochastic setting).
The minimum number of measurement per unit dimension
sufficient for reconstruction with vanishing probability of error
of an analog, γ-sparse, memoryless, discrete-time process
coincides with the information dimension per unit ambient
dimension of the space, which is equal to γ.
The analogous deterministic coding theorem in our continuous setting is obtained by combining Theorems 3 and 4, and
using Definition 6:
Theorem 8. (Coding theorem —deterministic setting).
The minimum number of measurement per unit dimension
sufficient for reconstruction with vanishing error of any σsparse, continuous-time signal coincides with twice the fractal
dimension per unit ambient dimension of its prolate spheroidal
approximation, which is equal to 2σ.
A factor of two appears in the deterministic formulation,
due to the worst case reconstruction scenario.
IV. T ECHNICAL P RELIMINARIES

In the case the limit in (40) does not exist, then lower and
upper information dimensions are defined by taking lim inf
and lim sup, respectively.
The definition immediately extends to a sequence of N i.i.d.
random variables
dimI (X1 , X2 , . . . XN ) = N dimI (X),

γ=

(41)

and should be compared with Definition 4 for continuous
signals in a deterministic setting.
1 Results hold more generally for discrete-continuous mixtures, not only
when the discrete part is a Dirac’s distribution.

A. Metric spaces
We begin our proofs by defining the metric spaces associated to the bandlimited and multi-band signals satisfying (1)
and (2). Let f ∈ L2 (−∞, ∞), 2Ω′ < Ω, and
BΩ = {f (t) : Ff (ω) = 0, for |ω| > Ω},
BQ = {f (t) : Ff (ω) = 0, for ω ∈
/ Q},

Q′ = {Q : Q ⊂ [−Ω, Ω] and m(Q) ≤ 2Ω′ },
[
BQ′ =
BQ .
Q∈Q′

(44)
(45)
(46)
(47)

7

It follows that BQ′ ⊂ BΩ . We equip BΩ and BQ′ with the
L2 [−T /2, T /2] norm
!1/2
Z

C. Measurement vector

It follows that (BΩ , k · k) and (BQ′ , k · k) are metric spaces,
whose elements are square-integrable, real, bandlimited or
multi-band signals, of infinite duration and observed over the
finite interval [−T /2, T /2].

where en is the measurement error and each measurement kernel ϕn is a bandlimited function. Since ϕn is bandlimited, this
can be represented by a linear combination of the “canonical”
PSWF basis of BΩ , namely

T /2

kf k =

f 2 (t)dt

.

(48)

−T /2

We consider the measurements of f (t) ∈ BQ′ ⊂ BΩ
Z T /2
f (t)ϕn (t)dt + en , n ∈ {1, . . . , M },
yn =

ϕn (t) =

B. Optimal representations

∞
X

ank ψk (t)

(56)

k=1

Let Q be a measurable subset of R and T = [−T /2, T /2].
We define the following time-limiting and band-limiting operators
TT f (t) = 1T f (t)
BQ f (t) = F

−1

1Q Ff (t),

(49)
(50)

where 1(·) is the indicator function. We consider the following
eigenvalues equation
TT BQ TT ψ Q (t) = λQ ψ Q (t).

(51)

There exists a countably infinite set of real functions
Q
{ψnQ (t)}∞
n=1 and a set of real positive numbers 1 > λ1 >
Q
λ2 > · · · > 0 with the following properties, see [24].
Q
Property 1. The elements of {λQ
n } and {ψn (t)} are solutions of (51).
Property 2. The elements of {ψnQ (t)} are in BQ .
Property 3. {ψnQ (t)} is complete in BQ .
Property 4. The elements of {ψnQ (t)} are orthonormal in
(−∞, ∞).
Property 5. The elements of {ψnQ (t)} are orthogonal in
(−T /2, T /2)
(
Z T /2
λQ
n = m,
n
Q
Q
ψn (t)ψm (t)dt =
(52)
0
otherwise.
−T /2
We write ψ(t) and λ instead of ψ Q (t) and λQ when Q =
[−Ω, Ω]. In this special case, the eigenfunctions {ψn (t)} are
the prolate spheroidal wave functions (PWSF) [4].
Lemma 1. (Slepian [2]). For any ν > 0, N = (1 + ν)ΩT /π,
and f ∈ BΩ , there exist real coefficients {xn }, such that the
approximation
N
X
xn ψn (t)
(53)
fN (t) =
n=1

has vanishing error norm kf − fN k, as T → ∞.
Lemma 2. (Landau and Widom [6]). For any ν > 0, S =
(1+ν)Ω′ T /π, and f ∈ BQ′ , there exist real coefficients {αn },
such that the approximation
fS (t) =

(55)

−T /2

S
X

αn ψnQ (t),

n=1

has vanishing error norm kf − fS k, as T → ∞.

(54)

Using the completeness of the {ψn (t)} in BΩ , and their
orthogonality property, it follows that the n-th measurement
can also be expressed as
Z T /2
f (t)ϕn (t)dt + en
yn =
=

−T /2
∞
T /2 X

Z

xj ψj (t)

−T /2 j=1

=

N
X

anj xj

j=1

∞
X

ank ψk (t)dt + en

k=1

∞
X
p
p
λj +
anj xj λj + en .

(57)

j=N +1

Letting N = (1 + ν)ΩT /π, we have
lim

T →∞

∞
X

anj xj

j=N +1

p
λj = 0.

(58)

It follows that as T → ∞ the measurements become
yn =

N
X

anj xj

j=1

p
λj + en + o(1).

(59)

√
√
Letting y = (y1 , · · · , yM ), x = (x1 λ1 , · · · , xN λN ), and
A be an M × N matrix such that [A]nj = anj , we define
y = Ax + e,

(60)

and consider the set
n
 p
p o
X = x : x = x1 λ1 , · · · , xN λN
.

(61)

In virtue of Lemma 1, there exists a one-to-one correspondence
between BQ′ and X , as T → ∞. By (59) it then follows that
to complete our proofs we can derive lower and upper bounds
on the number of rows of A required to recover x ∈ X from
y = Ax + e in (60), and then evaluate their order of growth
as T → ∞.
V. P ROOFS

OF

T HEOREMS 1

AND

2

We consider a function ζ(t) such that
fN (t) = fS (t) + ζ(t),

(62)

where fN (t) and fS (t) are given in (53) and (54), and let
Z T /2
ζk =
ζ(t)ψk (t)dt.
(63)
−T /2

8

which implies rank(AΦ′ ) = r. We can then conclude that
AΦ contains at least r independent columns, which implies
rank(AΦ) ≥ r = rank(Φ).

It follows that for all 1 ≤ k ≤ N , we have
Z T /2 X
S
p
λk xk =
αn ψnQ (t)ψk (t)dt + ζk
−T /2 n=1

=

S
X

αn

T /2

Z

T /2

−T /2

n=1

We now define

Z

ϕQ
k,n =

−T /2

ψnQ (t)ψk (t)dt + ζk .

(64)

Lemma 4. A number of measurements
m≥

ψnQ (t)ψk (t)dt,

(65)

so that we have
S
X
p
λk xk =
αn ϕQ
k,n + ζk .

(66)

n=1

We rewrite (66) in vector form as

x = ΦQ α + ζ,

(67)

where x ∈ X , α = (α1 , · · · , αS ), ζ = (ζ1 · · · , ζN ), and ΦQ
is an N × S matrix such that
[ΦQ ]k,n = ϕQ
kn .

(68)

By Lemmas 1 and 2, we have that ζ tends to the all zero
vector as T → ∞. Therefore, it is enough to determine the
minimum number of measurements to recover
x = ΦQ α.

(69)

max (rank[Φ1 , Φ2 ]) ,

Φ1 ,Φ2 ∈D

(73)

is sufficient to recover all the elements of X .
Proof: From Lemma 3 it follows that for all Φ1 , Φ2 ∈ D
there exists an m × N matrix A such that rank(A[Φ1 , Φ2 ]) =
rank[Φ1 , Φ2 ]. Let us assume Ax1 = Ax2 where x1 = Φ1 α1
and x2 = Φ2 α2 . The expression Ax1 = Ax2 , can be rewritten
as
 
α
(74)
A[Φ1 , Φ2 ] 1 = 0,
α2
namely [α1 , α2 ]T belongs to the null space of A[Φ1 , Φ2 ]. Since
rank(A[Φ1 , Φ2 ]) = rank[Φ1 , Φ2 ], the null space of A[Φ1 , Φ2 ]
is the same as the null space of [Φ1 , Φ2 ]. It follows that
[α1 , α2 ]T belongs to the null space of [Φ1 , Φ2 ], or equivalently
 
α
[Φ1 , Φ2 ] 1 = 0.
(75)
α2
This means Φ1 α1 = Φ2 α2 , namely x1 = x2 . Therefore, A is
one-to-one on X , which implies that the elements of X can
be recovered.

Let us define the following set
D = {ΦQ : Q ∈ Q′ }.

(70)

Lemma 5. A number of measurements
m<

We rewrite X in (61) as follows:

X = {x : x = ΦQ α where ΦQ ∈ D and α ∈ RS }.

(71)

Lemma 3. For all Φ1 , Φ2 ∈ D, there exists an m × N matrix
A such that rank(A[Φ1 , Φ2 ]) = rank[Φ1 , Φ2 ], provided that
m≥

max (rank[Φ1 , Φ2 ]) .

Φ1 ,Φ2 ∈D

(72)

Proof: It is enough to show that for all Φ1 , Φ2 ∈ D, if
A is an i.i.d Gaussian random matrix of size m × N , then
rank(A[Φ1 , Φ2 ]) = rank([Φ1 , Φ2 ]) with probability 1. Since
rank(A[Φ1 , Φ2 ]) ≤ rank([Φ1 , Φ2 ]), it is enough to show that
rank(A[Φ1 , Φ2 ]) ≥ rank([Φ1 , Φ2 ]). For convenience, we let
[Φ1 , Φ2 ] = Φ and we will show rank(AΦ) ≥ rank(Φ).
Note that Φ is an N × 2S matrix with rank(Φ) = r ≤ m.
Collect r independent columns of Φ and compose an N × r
matrix Φ′ . Using the Gram-Schmidt process, we can transform
Φ′ into ΦG , an N ×r matrix, whose columns are orthonormal.
By adding redundant N − r orthonormal columns followed by
the original r columns of ΦG , we obtain an N × N orthogonal
matrix ΦG .
Let us define σ(X) as the smallest number of linearly
dependent columns of a matrix X. It is well known that,
if A is an i.i.d. Gaussian random matrix of size m × N ,
where m < N , then σ(AP) = m + 1 with probability
1 for any fixed orthogonal matrix P, see for example [21,
Proposition 1] for a proof. Therefore, the first r columns
of AΦG are independent. Thus, we have rank(AΦG ) = r,

max (rank[Φ1 , Φ2 ])

Φ1 ,Φ2 ∈D

(76)

is not sufficient to recover all the elements of X .
Proof: If all elements x ∈ X can be recovered from the
measurements y = Ax, where A is an m × N matrix, this
means A is one-to-one on X . Therefore, for all x1 and x2 ,
Ax1 = Ax2 implies x1 = x2 . Let us assume x1 = Φ1 α1 and
x2 = Φ2 α2 , then AΦ1 α1 = AΦ2 α2 implies Φ1 α1 = Φ2 α2 .
This is equivalent to saying that
 
α
(77)
A[Φ1 , Φ2 ] 1 = 0
α2
implies
[Φ1 , Φ2 ]




α1
= 0.
α2

(78)

Namely, the null space of A[Φ1 Φ2 ] is contained in the null
space of [Φ1 Φ2 ]. By the rank-nullity theorem, we have
rank(A[Φ1 , Φ2 ]) ≥ rank[Φ1 , Φ2 ].

(79)

Since m ≥ rank(A[Φ1 , Φ2 ]) and (79) holds for all Φ1 , Φ2 ∈
D, the result follows.
Lemma 6. We have
lim

T →∞

maxΦ1 ,Φ2 ∈D (rank[Φ1 , Φ2 ])
= 1.
2S

(80)

9

Proof: Let Q1 , Q2 ∈ Q′ , and consider the multi-band
signals
S
X
(81)
f1 (t) =
αn ψnQ1 (t),
n=1

S
X

βn ψnQ2 (t),

(82)

fS (t) = f1 (t) + f2 (t).

(83)

f2 (t) =

n=1

and

Consider the N -dimensional vector



α1
 .. 
 . 
 
 αS 

z = [ΦQ1 , ΦQ2 ] 
 β1  .
 
 . 
 .. 

(84)

whose elements, by (65) and (68), and then using (81), (82),
(83), are
S
X

1
αj ϕQ
n,j +

=

αj

+

βj

Z

=

Z

T /2

Z

T /2

−T /2

j=1

=

Z

−T /2

j=1

S
X

2
βj ϕQ
n,j

j=1

j=1

S
X

S
X

2Ω′
Ω′
2Ω′
+ 2ν
>
,
(89)
π
π
π
and the proof of Theorem 1 is complete.
On the other hand, by combining Lemmas 5 and 6 it follows
that with less than 2S = 2(1 + ν)Ω′ T /π measurements we
cannot recover all possible vectors x in (69) with vanishing
error as T → ∞. This also means that we cannot recover all
possible vectors x in (67). It follows that with a number of
measurements M = 2Ω′ T /π+o(T ), and hence a measurement
rate
M̄ = 2Ω′ /π
(90)
M̄ =

we cannot recover all signals in BQ′ , and the proof of
Theorem 2 is also complete.

βS ,

zn =

(69) with vanishing error as T → ∞, and since the vector ζ
tends zero we can also recover any vector x in (67). It follows
that we can recover the coefficients representing any signal in
BQ′ with vanishing error using a measurement rate

VI. P ROOFS

and the spectral norm for matrices

kAxk
.
x6=0 kxk

ψjQ2 (t)ψn (t)dt

f1 (t)ψn (t)dt +

−T /2
T /2

Z

T HEOREMS 3-6

n=1

ψjQ1 (t)ψn (t)dt

T /2

OF

In the following, we use k · k to denote the Euclidean norm
for vectors in RN
v
u N
uX
x2n ,
(91)
kxk = t
kAk = sup

(92)

We also use the usual notation for signals defined in (48).

T /2

f2 (t)ψn (t)dt

−T /2

fS (t)ψn (t)dt.

A. The key lemmas
(85)

−T /2

We consider the case when z is the all zero vector. In this
case, since by (85) the elements {zn } are also the PSWF
coefficients of fS (t), it follows that
lim fS (t) = 0.

T →∞

(86)

We now choose Q1 and Q2 such that Q1 ∩ Q2 = ∅, so that
(86) implies
lim f1 (t) = lim f2 (t) = 0.

T →∞

T →∞

(87)

It follows that all coefficients {αn } and {βn } in (81) and (82)
must tends to zero as T → ∞, the columns of [ΦQ1 , ΦQ2 ]
become independent, and we have
rank[ΦQ1 , ΦQ2 ]
= 1.
(88)
lim
T →∞
2S
On the other hand, rank[Φ1 , Φ2 ] ≤ 2S for all Φ1 , Φ2 ∈ D
because the number of columns of [Φ1 , Φ2 ] is 2S. It follows
that our choice Φ1 = ΦQ1 and Φ2 = ΦQ2 achieves the
maximum rank and the result follows.
By combining Lemmas 4 and 6 it follows that with 2S =
2(1 + ν)Ω′ T /π measurements we can recover any vector x in

Let B∆ be the collection of all elements in BQ′ such that
the extremal points of all sub-bands belong to the discrete set
J defined in (23). For any signal f ∈ BQ′ , let f∆ ∈ B∆ such
that
(93)
f∆ = arg min kf − f ′ k.
f ′ ∈B∆

Since all f ∈ BQ′ are square-integrable, it follows that
lim kf − f∆ k = 0.

∆→0

(94)

Hence, if f∆ can be recovered using a measurement rate M̄∆ ,
then f can be recovered using a measurement rate
M̄ = lim M̄∆ .
∆→0

(95)

Consider now the set X (∆) of vectors of N = (1+ν)ΩT /π
real coefficients, such that every element of B∆ is approximated, with vanishing error as T → ∞, by an element
of X (∆). We also consider X (∆) ⊂ X (∆) containing all
elements of X (∆) that have norm at most one. To prove
Theorems 3-6, it is enough to prove following two lemmas.
Lemma 7. We can robustly recover all signals f ∈ B∆ using
a measurements rate
M̄∆ > RF [X (∆) ⊕ X (∆)].

(96)

10

Lemma 8. In the absence of measurement error, we cannot
perfectly recover all signals f ∈ B∆ using a measurement
rate
M̄∆ < 2RF [X (∆)].
(97)
To see that Theorems 3-6 follow from these two lemmas,
first note that the lemmas imply
RF [X (∆) ⊕ X (∆)] ≥ 2RF [X (∆)],

(98)

on the other hand, we have
dimF [X (∆) ⊕ X (∆)] ≤ 2 dimF [X (∆)],

(99)

which implies
RF [X (∆) ⊕ X (∆)] ≤ 2RF [X (∆)].

(100)

Combining (98) and (100) it follows that
RF [X (∆) ⊕ X (∆)] = 2RF [X (∆)].

(101)

Theorem 5 now follows from Lemma 7 and (101) by taking
the limit for ∆ → 0, and Theorem 3 follows directly from
Theorem 5. On the other hand, from Lemma 8 it follows by
taking the limit for ∆ → 0 that with a measurement rate
M̄ < lim 2RF [X (∆)]

(102)

∆→0

we cannot perfectly recover all signals f ∈ BQ′ . As for the
equality, combining this result with Theorems 1, 2, and 3, we
conclude that
2Ω′
lim 2RF [X (∆)] =
,
(103)
∆→0
π
which completes the proof of Theorem 4. Theorem 6 follows
directly from Theorem 4.
B. Proof of Lemma 7
Definition 9. (Inverse Lipschitz condition.) A matrix A satisfies the inverse Lipschitz condition on a set U if there exists a
constant β > 0 such that for all u1 , u2 ∈ U, we have
βku1 − u2 k ≤ kAu1 − Au2 k.

(104)

We claim that if A satisfies the inverse Lipschitz condition
on X (∆), then every x ∈ X (∆) can be robustly recovered
from y = Ax + e. To prove this claim, consider the following
two cases: (a) y ∈ AX (∆), where AX (∆) is the set {Ax :
x ∈ X (∆)}, and (b) y ∈
/ AX (∆). In the first case, let x′ be a
′
solution of y = Ax and let x′ be the vector used to recover
x. Then, the recovery error is bounded as
βkx − x′ k ≤ kAx − Ax′ k = kek,

(105)

which guarantees robust recovery. On the other hand, if y ∈
/
AX (∆), let x′′ ∈ X (∆) such that Ax′′ is the closest to y
among all the elements of AX (∆). By letting x′′ be the vector
used to recover x, we can bound the recovery error as
βkx − x′′ k ≤

≤
≤

kAx − Ax′′ k

(106)
′′

kAx − yk + ky − Ax k
2kek,

(107)
(108)

which guarantees robust recovery. The claim now follows and
we can proceed to derive a sufficient condition that ensures A
satisfies the inverse Lipschitz condition on the set X (∆).
By letting Z(∆) = X (∆) ⊕ X (∆), the inverse Lipschitz
condition is equivalent to stating that for all z ∈ Z(∆)
βkzk ≤ kAzk.

(109)

′

Consider the normalized set Z (∆) ⊂ Z(∆) containing all
the elements of Z(∆) that are vectors of unit norm, and let
′
k ′ = dimF [Z (∆)]. If (109) holds for all z ∈ Z(∆), then it
′
also holds for all z ∈ Z (∆), and vice versa. In the following,
′
we consider Z (∆) instead than Z(∆).
′
′
Let Lǫ [Z (∆)] be a minimal ǫ-covering set of Z (∆),
namely a minimum cardinality set such that any point in
′
Z (∆) is within distance ǫ from at least one point of
′
′
Lǫ [Z (∆)]. Let Lǫ [Z ′ (∆)] = |Lǫ [Z (∆)]|. We need the
following preliminary results.
Lemma 9. [26, Fact 2.1.]
′

dimF [Z (∆)] = inf {d : ∀ǫ ∈ (0, 1) ∃γ > 0 :
 d )
′
1
Lǫ [Z (∆)] ≤ γ
.
ǫ

(110)

Let G be the space of all orthogonal projections in RN of
rank m, and µ be the invariant measure on G with respect to
orthogonal transformations.
Definition 10. (Shadow of a set). The shadow of a set B in
RN is
S(B) = {P ∈ G : 0 ∈ PB}.
(111)
Lemma 10. [26, Theorem 5.1.] The measure of the shadow of
a ρ-ball B centered at a distance r from the origin is bounded
as
 ρ m
,
(112)
µ(S(B)) ≤ δ
r
where δ is a positive constant.
We now provide a key lemma.
Lemma 11. For almost every projection P of rank m > k ′ ,
′
there exists a constant c such that, for all z ∈ Z (∆)
kPzk > ckzk.

(113)

Proof: From Lemma 9, it follows that for any 0 < ǫ < 1
there exists a constant γ > 0 such that
 k′
′
1
Lǫ [Z (∆)] ≤ γ
.
(114)
ǫ
′

By definition of ǫ-covering, for any z ∈ Z (∆), there exists a
′
vector l ∈ Lǫ [Z (∆)] such that
kz − lk ≤ ǫ.

(115)

Letting v = z − l, we have
kPzk = kP(l + v)k

≥ kPlk − kPvk
≥ kPlk − ǫ,

(116)

11

Lemma 12. We have

where the last inequality follows from

dimF [Z(∆)] = dimF [X (∆) ⊕ X (∆)]

kPvk ≤ kPkkvk
= kvk
≤ ǫ.

(117)
′

From (116) we have that if for all l ∈ Lǫ [Z (∆)] we have
kPlk > 2ǫ, then we also have kPzk > ǫ = ǫkzk, and letting
c = ǫ the result follows. What remains to be shown then,
is that for almost every projection P of rank m, and for all
′
l ∈ Lǫ [Z (∆)], we have kPlk > 2ǫ.
We let
′
Lǫ [Z (∆)] = {l1 , · · · , lL },
(118)
′

where L = Lǫ [Z (∆)], and for all 1 ≤ i ≤ L we define
Hi = {P ∈ G : kPli k ≤ 2ǫ}.
We also let
H=
so that
µ(H) = µ

L
[

i=1

L
[

i=1

Hi

Hi ,

!

≤

(119)

(120)

L
X

µ(Hi ).

(121)

i=1

l
l
is
, where B2ǫ
We claim that if kPlk ≤ 2ǫ, then 0 ∈ PB2ǫ
a 2ǫ-ball whose center is l. This can be shown as follows: let
l
and Pb = Pl − P2 l = 0. It follows
b = l − Pl, then b ∈ B2ǫ
that


li
µ(Hi ) ≤ µ {P ∈ G : 0 ∈ PB2ǫ
}

=

li
µ(S(B2ǫ
))
m

≤ δ (2ǫ) ,

(122)

where the last inequality follows from Lemma 10. We now
have
µ(H)

≤
≤
≤

L
X

µ(Hi )

Proof: Let z ∈ Z(∆) be a vector of coefficients of a
multi-band function fz whose spectral support is bounded by
4Ω′ and whose energy is bounded by one. It follows that fz
can be represented as
fz = fx1 + fx2

m

Lδ(2ǫ)

′

γδ2m ǫm−k ,

(123)

where the last inequality follows from (114). By taking a
sufficiently small ǫ, we can now make µ(H) arbitrary close to
0, and the proof is complete.
By Lemma 11, there exists a projection P of rank m such
′
that for all z ∈ Z (∆) we have kPzk > ckzk. By applying
Gaussian elimination to such a projection and selecting the
non-zero rows of it, we obtain an m × N matrix A. Since
kPzk = kAzk, it follows that any x ∈ X (∆) can be robustly
recovered from y = Ax + e with a number of measurements
larger than k ′ .
What remains to be done is to show that k ′ =
′
dimF [Z (∆)] ≤ dimF [X (∆) ⊕ X (∆)]. Let Z(∆) ⊂ Z(∆)
containing all elements of Z(∆) that have norm at most one.
′
Since Z (∆) ⊂ Z(∆), we have k ′ ≤ dimF [Z(∆)]. It is then
enough to show that dimF [Z(∆)] = dimF [X (∆) ⊕ X (∆)].

(125)

where fxi , i ∈ {1, 2} is a multi-band signal whose spectral
support is bounded by 2Ω′ and whose energy is bounded by
one. Let xi be a vector of coefficients for fxi , i ∈ {1, 2}.
Then, we have
z = x1 + x2
(126)
where xi ∈ X (∆). Since Z(∆) ⊂ X (∆)⊕X (∆), we conclude
that
dimF [Z(∆)] ≤ dimF [X (∆) ⊕ X (∆)].
(127)
Conversely, let us consider x1 , x2 ∈ X (∆). Then, we have
x1 + x2
∈ Z(∆),
(128)
2
which implies X (∆) ⊕ X (∆) ⊂ 2Z(∆), where 2Z(∆)
indicates the set {2z : z ∈ Z(∆)}. Therefore, we conclude
that
dimF [Z(∆)] ≥ dimF [X (∆) ⊕ X (∆)].
(129)
By combining (127) and (129), we obtain the desired result.

C. Proof of Lemma 8
If all vectors x ∈ X (∆) can be recovered from y = Ax ,
then all vectors x ∈ X (∆) can also be recovered from y =
Ax, and vice versa. In the following, we consider X (∆) rather
than X (∆).
In order to prove Lemma 8, it is enough to show that a
number of measurements
m < 2 dimF [X (∆)]

i=1

(124)

(130)

is not sufficient to recover all the elements of X (∆) as T →
∞.
Let us define the set W(∆) = X (∆) ⊕ X (∆). If all x ∈
X (∆) can be recovered from y, then A is a one-to-one map
on X (∆), and vice versa. Also, if A is a one-to-one map on
X (∆), then
ker(A) ∩ W(∆) = {0},
(131)
and vice versa, where ker(A) indicates the kernel of A. We
then need to show that (130) violates (131). For convenience
of notation, we define k = 2 dimF [X (∆)].
Let us assume that W(∆) contains a k-dimensional Euclidean ball. Note that (130) implies rank(A) < k. Since
rank(A)+ nullity(A) = N , it follows that nullity(A) > N − k.
This means that the dimension of ker(A) is larger than N − k,
which violates (131) because W(∆) contains a k-dimensional
Euclidean ball.
It follows that in order to prove Lemma 8, it is enough to
show that W(∆) contains a k-dimensional Euclidean ball. We
will show that this is the case when T → ∞.

12

We need some additional definitions, followed by a preliminary result.
Definition 11. (Diameter). For any S ⊂ RN , we let
diam(S) = sup kx − yk.

dimH [X (∆)] = dimH (Xi ).
(132)

x,y∈S

Definition 12. (Hausdorff measure). Let U ⊂ RN and {Si }
be a cover of U formed by balls of radius r < µ. We let
X
[diam(Si )]s .
(133)
ζµs (U) = inf
{Si }

i

The s-dimensional Hausdorff measure of U is given by the
limit
(134)
ζ s (U) = lim ζµs (U).
µ→0

Definition 13. (Hausdorff dimension). For any U ⊂ RN , the
Hausdorff dimension of U is
dimH (U) = sup{s ≥ 0 : ζ s (U) = ∞}.

(135)

The Hausdorff dimension has the following two important
properties, see [18].
Property 1. (Unit ball). For any integer d such that 0 ≤ d ≤
N , the Hausdorff dimension of the unit ball B d (0, 1) ⊂ Rd ⊂
RN is d.
N
Property
S∞ 2. (Countable stability). Let Ui ⊂ R . Then,
dimH ( i=1 Ui ) = supi {dimH (Ui )}
From these definitions it follows that
dimH (U) ≤ dimF (U).

(136)

However, by Lemma 13 below, if a set satisfies a quasi selfsimilar property, then the Hausdorff dimension is equal to the
fractal dimension.
Definition 14. (Quasi self-similarity) Let U ⊂ RN . If for all
x, y ∈ U ∩ B, there exist a, r0 > 0 such that for any ball
B with radius r < r0 , there is a mapping φ : U ∩ B → U
satisfying
a · kx − yk ≤ r · kφ(x) − φ(y)k,

(137)

then, we say that U is quasi self-similar.
Lemma 13. [25, Theorem 3.] Let U be a nonempty compact
subset of RN that is quasi self-similar. Then,
dimH (U) = dimF (U).

(138)

We are now ready to show our final step.
Lemma 14. For sufficiently large T , the set W(∆) = X (∆)⊕
X (∆) contains a k-dimensional Euclidean ball.
Proof: We have
X (∆) =

[
i

Xi

(139)

where Xi is the set of coefficient vectors of all multi-band
signals of a fixed sub-band allocation of measure at most 2Ω′
and norm at most one. Since X (∆) is a countable union, by
Property 2 of the Hausdorff dimension we have
dimH [X (∆)] = sup{dimH (Xi )}.
i

Since the Hausdorff dimension of Xi does not depend on i,
we also have that for all i

(140)

(141)

Since X (∆) is a nonempty compact subset of RN that is also
quasi self-similar with a = r0 = 1 and φ(x) = x/r, it follows
that
dimH [X (∆)] = dimF [X (∆)].
(142)
Next, we consider two sets of coefficient vectors X1 and
X2 , whose sub-bands do not have any intersection. We have
Xi = {x : x = Φi α where kxk ≤ 1 and α ∈ RS },

(143)

for i = 1, 2. By the same argument used in the proof of
Lemma 6, it follows that for T large enough the columns
of Φ1 and Φ2 are independent. Also, note that Xi is an
Euclidean ball and by Property one of the Hausdorff dimension
it follows that Xi is a dimH (Xi )-dimensional Euclidean ball.
Now, by definition, W(∆) includes X1 ⊕ X2 , and since
X1 and X2 are dimH (Xi )-dimensional Euclidean balls and
the columns of Φ1 and Φ2 are independent, it follows that
W(∆) contains a 2 dimH (Xi )-dimensional Euclidean ball.
Using (141) and (142), it follows that for T large enough
W∆ contains a 2 dimF [X (∆)] Euclidean ball, or equivalently,
a k-dimensional Euclidean ball.

VII. C ONCLUSION
We have investigated the phase-transition threshold of the
minimum measurement rate sufficient for completely blind
reconstruction of any multi-band signal of given spectral support measure. This threshold has been shown to coincide with
twice the fractal dimension per unit ambient dimension of the
space spanned by the optimal approximation for bandlimited
signals. This result provides an operational characterization
of the fractal dimension, and parallels an analogous coding
theorem for the compression of discrete-time, analog, i.i.d.
sources, where the critical threshold is shown to be equal to
the information dimension per unit ambient dimension of the
source [16], [17]. Advantages of the deterministic approach
include being oblivious to a priori assumptions on the source
distribution, and providing recovery guarantees for all signals,
rather than for a large fraction of them. In both cases, fundamental limits apply to the asymptotic regime of large signal
dimension. In the stochastic case, probabilistic concentration
is achieved exploiting the ergodicity of the process, while
in the deterministic case vanishing error energy is achieved
exploiting spectral concentration. Despite both results can
be viewed at the high level as an instance of dimensional
reduction due to regularity constraints, the tools required in
the deterministic setting are quite different from those used
in traditional information theory, and include machinery from
approximation theory, and geometry of functional spaces.
The systematic study of these techniques is clearly desirable,
and this recommendation dates back to Kolmogorov [19].
Exploiting some of our recent results [28], we have shown
that the price to pay to obtain deterministic guarantees of

13

reconstruction for all signals is only a factor of two in the
measurement rate, compared to probabilistic reconstruction.
It is also the case that the absence of additional spectral
information such as the one assumed in [11], [12], [15], does
not lead to any penalty in the measurement rate.
Practical achievability schemes for blind reconstruction of
continuous signals that come close to the information-theoretic
optimum remain an open problem, while much progress has
been made for both discrete-time and continuous-time settings,
under various assumptions on what information about the
signal is available a priori [11], [12], [15], [16], [17], [29].
Another interesting open question is the determination of
the critical threshold for linear approximation schemes. In
this case, without any knowledge of the spectral support it
is not possible to set-up the eigenvalue equation leading to
the optimal subspace approximation [6], and the challenge is
to infer the basis functions directly from the measurements.
Investigation of sampling schemes for blind reconstruction is
also of interest, due to their relevance for practical applications. Our results provide an information-theoretic baseline
for performance assessment in all of these cases. Finally,
extensions to signals of multiple variables would be of interest
in various settings, for example in the context of remote
sensing. In this case, a desirable outcome would be the
computation of the fractal dimension of signals radiated from a
bounded domain, generalizing the notion of number of degrees
of freedom for bandlimited signals studied in [30], to signals
that are sparse in both the frequency and the wavenumber
spectrum.
A PPENDIX
A. Proofs of (20) and (22)
First let us consider (20). Since XB ⊂ XB ⊕ XB , we have
dimF (XB ) ≤ dimF (XB ⊕ XB ).

(144)

For any x ∈ XB ⊕ XB , we have x/2 ∈ XB , or equivalently
x ∈ 2XB , where 2XB indicates the set {2x : x ∈ XB }. This
implies XB ⊕ XB ⊂ 2XB , and we have
dimF (XB ) ≥ dimF (XB ⊕ XB ).

(145)

Combining (144) and (145), we obatin (20).
Next, we consider (22). We let XB′ be a set of vectors such
that for any x = (x1 , · · · , xN ) ∈ XB , x′ ∈ X ′ is the vector
of its first N ′ components, namely x′ = (x1 , · · · , xN ′ ) where
N ′ = ΩT /π + o(T ). From inequality (137) in Theorem 6 of
[28], we have
Hǫ (XB ) ≥ Hǫ (X ′ B ).
(146)
By inequality (99) of Theorem 3 in [28], we have
 

1
Hǫ (X ′ B ) ≥ N ′ log ζ(N ′ )
,
ǫ

(147)

where ζ(N ′ ) is independent of ǫ. Combining (146) and (147),
we obtain

 
1
.
(148)
Hǫ (XB ) ≥ N ′ log ζ(N ′ )
ǫ

Similarly, by inequality (138) of Theorem 6 in [28] we have
Hǫ (XB ) ≤ Hǫ−µ (X ′ B ),

(149)

and using inequality (100) of Theorem 3 in [28], we have


1
Hǫ−µ (X ′ B ) ≤ N ′ log
+ η(N ′ ),
(150)
ǫ−µ

where 0 < µ < ǫ, and η(N ′ ) is independent of ǫ. Combining
(149) and (150), we obtain


1
+ η(N ′ ).
(151)
Hǫ (XB ) ≤ N ′ log
ǫ−µ
Since µ can be arbitrarily small and the logarithm is a
continuous function, it follows that
Hǫ (XB ) ≤ N ′ log (1/ǫ) + η(N ′ ).
Putting together (148) and (152), we finally obtain
(
Hǫ (XB ) ≥ N ′ log [ζ(N ′ )1/ǫ] ,
Hǫ (XB ) ≤ N ′ log (1/ǫ) + η(N ′ ).

(152)

(153)

Dividing both sides of (153) by − log ǫ and taking the limit
for ǫ → 0, we have
dimF (XB ) = N ′ ,
so that
lim

T →∞

dimF (XB )
= Ω/π.
T

(154)

(155)

R EFERENCES
[1] A. Jerri. “The Shannon sampling theorem —its various extensions and
applications: a tutorial review.” Proceedings of the IEEE, 65(11), pp.
1565–1596, 1977.
[2] D. Slepian. “Some comments on Fourier analysis, uncertainty and
modeling.” SIAM Review, 25(3), pp. 379-393, 1983.
[3] M. Unser. “Sampling —50 years after Shannon.” Proceedings of the
IEEE, 88(4), pp. 569-587, 2000.
[4] C. Flammer. “Spheroidal wave functions.” Stanford University Press,
1957. Reprinted 2005, Dover.
[5] A. Pinkus, “n-Widths in approximation theory,” Springer-Verlag, 1985.
[6] H. J. Landau and H. Widom, “The eigenvalue distribution of time and
frequency limiting,” Journal of Mathematical Analysis and Applications, 77, pp. 469–481, 1980.
[7] H. J. Landau, “Necessary density conditions for sampling and interpolation of certain entire functions” Acta Math., vol. 117, pp. 37-52,
Feb. 1967.
[8] P. Feng and Y. Bresler, “Spectrum-blind minimum-rate sampling and
reconstruction of multiband signals,” in Proc. IEEE Int. Conf. Acoustics, Speech, Signal Processing (ICASSP), 3, pp. 1688–1691, May 1996.
[9] Y. Bresler and P. Feng, “Spectrum-blind minimum-rate sampling and
reconstruction of 2-d multiband signals,” in Proc. IEEE Int. Conf.
Image Process, vol. 1, pp. 701–704, Sep. 1996.
[10] R. Venkataramani and Y. Bresler, “Further results on spectrum blind
sampling of 2D signals,” in Proc. IEEE Int. Conf. Image Process, vol.
2, pp. 752–756, Oct. 1998.
[11] M. Mishali and Y. Eldar, “Blind multi-band signal reconstruction:
compressed sensing for analog signals,” in IEEE Trans. Signal Process,
57 (3), pp. 993–1009, 2009.
[12] M. Mishali and Y. Eldar, “From theory to practice: sub-Nyquist
sampling of sparse wide-band analog signals,” in IEEE J. Select. Top.
Signal Process., 4 (2), pp. 375–391, 2010.
[13] S. Izu and J. Lakey, “Time-frequency localization and sampling of
multiband signals,” in Acta Appl. Math., 107 (1), pp. 399–435, 2009.
[14] E. Sejdic, M. Luccini, S. Primak, K. Baddour, T. Willink, “Channel
estimation using DPSS based frames,” in Proc. IEEE Conf. Accoust.,
Speech, and Signal Processing (ICASSP), Las Vegas, Nevada, March
2008.

14

[15] M. A. Davenport and M. B. Wakin, “Compressive sensing of analog
signals using Discrete Prolate Spheroidal Sequences,” in Appl. Comput.
Harmon. Anal.,, 33, pp. 438-472, 2012.
[16] Y. Wu and S. Verdu, “Renyi information dimension: Fundamental limits
of almost lossless analog compression.” IEEE Trans. on Information
Theory, 56(8), pp. 3721-3748, 2010.
[17] Y. Wu and S. Verdu, ”Optimal phase transitions in compressed sensing,” IEEE Trans. on Information Theory, 58,(10), pp. 6241-6263,
2012.
[18] K. Falconer, “Fractal geometry: mathematical foundations and applications,” John Wiley & Sons, 2004.
[19] A. N. Kolmogorov and V. M. Tikhomirov, “ǫ-entropy and ǫ-capacity of
sets in functional spaces,” in Uspekhi Matematicheskikh Nauk, 14(2),
pp. 3-86, 1959. English translation: American Mathematical Society
Translation Series, 2(17), pp. 277-364, 1961.
[20] S. Foucart and H. Rauhut, “A mathematical introduction to compressive
sensing,” Springer, New York, 2013.
[21] S. Gleichman and Y. Eldar, “Blind compressed sensing,” in IEEE Trans.
on Information Theory, 57(10), pp. 6958-6975, 2011.
[22] S. Ravishankar and Y. Bresler, “Efficient blind compressed sensing using sparsifying transforms with convergence guarantees and application
to MRI,” in SIAM J. Imaging Sciences, 8(4), pp. 2519-2557, 2015.
[23] A. Rényi. On the dimension and entropy of probability distributions.
Acta Mathematica Hungarica, 10(12), pp. 193-215,
[24] H. J. Landau, “An Overview of Time and Frequency Limiting.” Fourier
techniques and applications,” J. F. Price (editor), Plenum, New York,
pp. 201-220, 1985.
[25] K.-J. Falconer, “Dimensions and measures of quasi self-similar sets.”
Proceedings of the American mathematical society 106.(2), pp. 543554, 1989.
[26] E. Olson, “Bouligand dimension and almost Lipschitz embeddings.”
Pacific journal of mathematics, 202.(2), pp. 459-474, 2002
[27] J.-L. Verger-Gaugry, “Covering a ball with smaller equal balls in Rn ”.
Discrete and Computational Geometry,” Springer Verlag, 33, pp.143155, 2005.
[28] T. J. Lim and M. Franceschetti, “Information without rolling dice,”
IEEE Trans. on Information Theory, 63(3), pp. 1349-1363, 2017.
[29] D. L. Donoho, A. Javanmard, A. Montanari. “Information-Theoretically
Optimal Compressed Sensing via Spatial Coupling and Approximate
Message Passing”. IEEE Trans. on Information Theory, 59(11), pp.
7434 - 7464, 2013.
[30] M. Franceschetti. “On Landau’s eigenvalue theorem and information
cut-sets,” IEEE Trans. Inf. Theory, 61(9), pp. 5042-5051, 2015.

