  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 $\epsilon$-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 information-theoretic one. A comparison with parallel results in compressed
sensing is illustrated, where the relevant dimensionality notion in a
stochastic setting is the information (R\'{e}nyi) dimension, defined in terms
of the Shannon entropy.
