1

Lossless Analog Compression
Giovanni Alberti1 , Helmut Bölcskei2 , Camillo De Lellis3 ,
Günther Koliander4 , and Erwin Riegler2
1
2

arXiv:1803.06887v1 [math.FA] 19 Mar 2018

3
4

Dept. of Mathematics, University of Pisa, Italy, Email: galberti1@dm.unipi.it

Dept. IT & EE, ETH Zurich, Switzerland, Email: {boelcskei, eriegler}@nari.ee.ethz.ch

Dept. of Mathematics, University of Zurich, Switzerland, Email: camillo.delellis@math.uzh.ch

ARI, Austrian Academy of Sciences, Vienna, Austria, Email: guenther.koliander@kfs.oeaw.ac.at

Abstract
We establish the fundamental limits of lossless analog compression by considering the recovery of
arbitrary random vectors x ∈ Rm from the noiseless linear measurements y = Ax with measurement
matrix A ∈ Rn×m . Our theory is inspired by the groundbreaking work of Wu and Verdú (2010) on almost
lossless analog compression, but applies to the nonasymptotic, i.e., fixed-m case, and considers zero error
probability. Specifically, our achievability result states that, for Lebesgue-almost all A, the random vector
x can be recovered with zero error probability provided that n > K(x), where the description complexity
K(x) is given by the infimum of the lower modified Minkowski dimensions over all support sets U of

x (i.e., sets U ⊆ Rm with P[x ∈ U] = 1). We then particularize this achievability result to the class

of s-rectifiable random vectors as introduced in Koliander et al. (2016); these are random vectors of
absolutely continuous distribution—with respect to the s-dimensional Hausdorff measure—supported
on countable unions of s-dimensional C 1 -submanifolds of Rm . Countable unions of C 1 -submanifolds
include essentially all signal models used in the compressed sensing literature such as the standard
union of subspaces model underlying much of compressed sensing theory and spectrum-blind sampling,
smooth manifolds, block-sparsity, and low-rank matrices as considered in the matrix completion problem.
Specifically, we prove that, for Lebesgue-almost all A, s-rectifiable random vectors x can be recovered
with zero error probability from n > s linear measurements. This threshold is, however, found not to
be tight as exemplified by the construction of an s-rectifiable random vector that can be recovered with
zero error probability from n < s linear measurements. This leads us to the introduction of the new class
of s-analytic random vectors, which admit a strong converse in the sense of n ≥ s being necessary for
recovery with probability of error smaller than one. The central conceptual tool in the development of
our theory is geometric measure theory.

The material in this paper was presented in part at the 2016 IEEE International Symposium on Information Theory [1].

March 20, 2018

DRAFT

2

I. I NTRODUCTION
Compressed sensing [2]–[6] deals with the recovery of unknown sparse vectors x ∈ Rm from a small

(relative to m) number, n, of linear measurements of the form y = Ax, where A ∈ Rn×m is the

measurement matrix.1 Known recovery guarantees can be categorized as deterministic, probabilistic, and
information-theoretic. The literature in all three categories is abundant and the ensuing overview is hence
necessarily highly incomplete, yet representative.
Deterministic results, such as those in [2], [6]–[10], are uniform in the sense of applying to all ssparse vectors x for a fixed measurement matrix A. Typical guarantees say that s-sparse vectors x can
be recovered through convex optimization algorithms or greedy algorithms provided that s < 21 (1 + 1/µ),
where µ denotes the coherence of A, i.e., the largest (in absolute value) inner product of any two different
columns of A. The Welch bound [11] implies that the minimum number of linear measurements, n,
required for uniform recovery is of order s2 , a result known as the “square-root bottleneck.”
Probabilistic results are either based on random2 measurement matrices A [3]–[5], [12]–[15] or deterministic A and random s-sparse vectors x [13], [14] and typically state that s-sparse vectors can
be recovered, again using convex optimization algorithms or greedy algorithms, with high probability,
provided that n is of order s log m.
An information-theoretic framework for compressed sensing, fashioned as an almost lossless analog
compression problem, was developed by Wu and Verdú [16], [17]. Specifically, [16] derives asymptotic (in
m) achievability results and converses for linear encoders and measurable decoders, measurable encoders

and Lipschitz continuous decoders, and continuous encoders and continuous decoders. For the particular
case of linear encoders and measurable decoders, [16] shows that, asymptotically in m, for Lebesgue
almost all (a.a.) measurement matrices A, the random vector x can be recovered with arbitrarily small
probability of error from n = bRmc linear measurements, provided that R > RB , where RB denotes the
Minkowski dimension compression rate [16, Definition 10] of the random process generating x. For the
special case of x with independent and identically distributed (i.i.d.) discrete-continuous mixture entries,
a matching converse exists. Discrete-continuous mixture distributions ρµc + (1 − ρ)µd are relevant as they
mimic sparse vectors for large m. In particular, if the discrete part µd is a Dirac measure at 0, then the
nonzero entries of x can be generated only by the continuous part µc , and the fraction of nonzero entries
in x converges—in probability—to ρ as m tends to infinity. A nonasymptotic, i.e., fixed-m, statement
in [16] says that a.a. (with respect to a σ -finite Borel measure on Rm ) s-sparse random vectors can be
1

Throughout the paper, we assume that n ≤ m.

2

Random quantities are denoted by sans-serif letters, throughout.

March 20, 2018

DRAFT

3

recovered with zero error probability provided that n > s. Again, this result holds for Lebesgue a.a.
measurement matrices A ∈ Rn×m . A corresponding converse does not seem to be available.
Contributions. We establish the fundamental limits of lossless, i.e., zero error probability, analog
compression in the nonasymptotic, i.e., fixed-m, regime for arbitrary random vectors x ∈ Rm . Specifically,
we show that x can be recovered with zero error probability provided that n > K(x), with the description
complexity K(x) given by the infimum of the lower modified Minkowski dimensions over all support
sets U of x, i.e., all sets U ⊆ Rm with P[x ∈ U] = 1. This statement holds for Lebesgue-a.a. measurement
matrices. Lower modified Minkowski dimension vastly generalizes the notion of s-sparsity and allows
for arbitrary support sets that are not necessarily finite unions of s-dimensional linear subspaces. For
s-sparse vectors, we get the recovery guarantee n > s showing that our information-theoretic thresholds

suffer neither from the square-root bottleneck nor from a log m-factor. We hasten to add, however, that
we do not specify explicit decoders that achieve these thresholds, rather we provide existence results
absent computational considerations. The central conceptual element in the proof of our achievability
result is the probabilistic null-space property first reported in [18]. We emphasize that it is the usage of
modified Minkowski dimension, as opposed to Minkowski dimension [16], [18], that allows us to obtain
achievability results for zero error probability. The asymptotic achievability result for linear encoders in
[16] can be recovered in our framework.
We particularize our achievability result to s-rectifiable random vectors x as introduced in [19]; these
are random vectors supported on countable unions of s-dimensional C 1 -submanifolds of Rm and of
absolutely continuous—with respect to s-dimensional Hausdorff measure—distribution. Countable unions
of C 1 -submanifolds include numerous signal models prevalent in the compressed sensing literature,
namely, the standard union of subspaces model underlying much of compressed sensing theory [20],
[21] and spectrum-blind sampling [22], [23], smooth manifolds [24], block-sparsity [25]–[27], and lowrank matrices as considered in the matrix completion problem [28]–[30]. Our achievability result shows
that s-rectifiable random vectors can be recovered with zero error probability provided that n > s.
Again, this statement holds for Lebesgue-a.a. measurement matrices. Absolute continuity with respect
to s-dimensional Hausdorff measure is a regularity condition ensuring that the distribution is not too
concentrated; in particular, sets of Hausdorff dimension t < s are guaranteed to carry zero probability
mass. One would therefore expect n ≥ s to be necessary for zero error recovery of s-rectifiable random
vectors. It turns out, however, that, perhaps surprisingly, this is not the case in general. An example
elucidating this phenomenon constructs a set G ⊆ R2 of positive 2-dimensional Hausdorff measure that
can be compressed linearly in a one-to-one fashion into R. This will then be seen to lead to the statement
that every 2-rectifiable random vector of distribution absolutely continuous with respect to 2-dimensional

March 20, 2018

DRAFT

4

Hausdorff measure restricted to G can be recovered with zero error probability from a single linear
measurement. What renders this result surprising is that all this is possible even though G contains the
image of a Borel set in R2 of positive Lebesgue measure under a C ∞ -embedding. The picture changes

completely when the embedding is real analytic. Specifically, we show that if a set U ⊆ Rm contains the

real analytic embedding of a Borel set in Rs of positive Lebesgue measure, it can not be compressed
linearly (in fact, not even through a nonlinear real analytic mapping) in a one-to-one fashion into Rn

with n < s. This leads to the new concept of s-analytic random vectors, which allows a strong converse
in the sense of n ≥ s being necessary for recovery of x with probability of error smaller than one. The
qualifier “strong” refers to the fact that recovery from n < s linear measurements is not possible even
if we allow an arbitrary positive error probability strictly smaller than one. The only strong converse
available in the literature applies to random vectors x with i.i.d. discrete-continuous mixture entries [16].
Organization of the paper. In Section II, we present our achievability results, with the central statement
in Theorem II.1. Section III particularizes these results to s-rectifiable random vectors and presents the
2-rectifiable example random vectors that can be recovered with zero error probability from a single linear

measurement. In Section IV, we introduce and characterize the new class of s-analytic random vectors
and we derive a corresponding strong converse, stated in Theorem IV.1. Sections V–VII contain the
proofs of the main technical results stated in Sections II–IV. Appendices A–G contain proofs of further
technical results stated in the main body of the paper. In Appendices H–K, we summarize concepts and
basic results from (geometric) measure theory, the theory of set-valued functions, sequences of functions
in several variables, and real analytic mappings, all needed throughout the paper. The reader not familiar
with these results is advised to consult the corresponding appendices before studying the proofs of our
main results. These appendices also contain new results, which are highly specific and would disrupt the
flow of the paper if presented in the main body.
Notation. We use capital boldface roman letters A, B, . . . to denote deterministic matrices and lowercase boldface roman letters a, b, . . . to designate deterministic vectors. Random matrices and vectors are
set in sans-serif font, e.g., A and x. The m × m identity matrix is denoted by Im . We write rank(A) and
ker(A) for the rank and the kernel of A, respectively. For the matrix A, spark(A) is the smallest number
k such that there exists a set of k column vectors of A that are linearly dependent. The superscript T
√
stands for transposition. The i-th unit vector is denoted by ei . For a vector x ∈ Rm , kxk2 = xT x is its

Euclidean norm and kxk0 denotes the number of nonzero entries of x. For the set A, we write card(A)
for its cardinality, A for its closure, 2A for its power set, and

1A for the indicator function on A. With

A ⊆ Rm and B ⊆ Rn , we let A × B = {(a, b) : a ∈ A, b ∈ B} and A ⊗ B = {a ⊗ b : a ∈ A, b ∈ B},

where ⊗ denotes the Kronecker product. For A, B ⊆ Rm , we write A ( B to express that A ⊆ B
March 20, 2018

DRAFT

5

with A 6= B and let A

B = {a − b : a, b ∈ B}. For the Euclidean space (Rk , k · k2 ), we designate

the open ball of radius ρ centered at u ∈ Rk by Bk (u, ρ), and use V (k, ρ) to refer to its volume. We
write S (X ) for a general σ -algebra on X , B(X ) for the Borel σ -algebra on a topological space X , and
L (Rm ) for the Lebesgue σ -algebra on Rm . The product σ -algebra of S (X ) and S (Y) is denoted by

S (X ) ⊗ S (Y). For measures µ and ν on the same measurable space, we denote absolute continuity

of µ with respect to ν by µ  ν . We write µ × ν for the product measure of µ and ν . The Lebesgue

measure on Rk and Rk×l is designated as λk and λk×l , respectively. The distribution of a random vector

x is denoted by µx . If f : Rk → Rl is differentiable, we write Df (v) ∈ Rl×k for its differential at v ∈ Rk
p
and define the min(k, l)-dimensional Jacobian Jf (v) at v ∈ Rk by Jf (v) = det(Df (v)(Df (v))T )
p
if l < k and by Jf (v) = det((Df (v))T Df (v)) if l ≥ k . For an open set U ⊆ Rk , a differentiable

mapping f : U → Rl , where l ≥ k , is called an immersion if Jf (v) > 0 for all v ∈ U . A one-to-one

immersion is referred to as an embedding. For a mapping f , we write f ≡ 0 if it is identically zero
and f 6≡ 0 otherwise. For f : U → V and g : V → W , the composition g ◦ f : U → W is defined as
(g ◦ f )(x) = g(f (x)) for all x ∈ U . For f : U → V and A ⊆ U , f |A denotes the restriction of f to A.

For f : U → V and B ⊆ V , we set f −1 (B) = {x ∈ U : f (x) ∈ B}.
II. ACHIEVABILITY

In classical compressed sensing theory [3]–[6] one typically deals with the recovery of s-sparse vectors
x ∈ Rm , i.e., vectors x that are supported on a finite union of s-dimensional linear subspaces of Rm . The

purpose of this paper is the development of a comprehensive theory of signal recovery in the sense of
allowing arbitrary support sets U , which are not necessarily unions of (a finite number of) linear subspaces

of Rm . Formalizing this idea requires a suitable dimension measure for general nonempty sets. There is a
rich variety of dimension measures available in the literature [31]–[33]. Our choice will be guided by the
requirement of information-theoretic operational significance. Specifically, the dimension measure should
allow the formulation of nonasymptotic, i.e., fixed-m, achievability results with zero error probability.
Modified Minkowski dimension will turn out to meet these requirements.
We first recall the definitions of Minkowski dimension and modified Minkowski dimension, compare
the two concepts, and state the basic properties of modified Minkowski dimension needed in the remainder
of the paper.
Definition II.1. (Minkowski dimension3 ) [32, Section 3.1] For U ⊆ Rm nonempty, the lower and upper
3

Minkowski dimension is sometimes also referred to as box-counting dimension, which is the origin of the subscript B in

the notation dimB (·) used henceforth.

March 20, 2018

DRAFT

6

Minkowski dimension of U are defined as
dimB (U) = lim inf

log NU (ρ)
log ρ1

(1)

dimB (U) = lim sup

log NU (ρ)
,
log ρ1

(2)

ρ→0

and

ρ→0

respectively, where
n
o
[
NU (ρ) = min k ∈ N : U ⊆
Bm (ui , ρ), ui ∈ Rm

(3)

i∈{1,...,k}

is the covering number of U for radius ρ. If dimB (U) = dimB (U), this common value, denoted by
dimB (U), is the Minkowski dimension of U .

Definition II.2. (Modified Minkowski dimension) [32, Section 3.3] For U ⊆ Rm nonempty, the lower
and upper modified Minkowski dimension of U are defined as
(
dimMB (U) = inf sup dimB (Ui ) : U ⊆
i∈N

)
[
i∈N

Ui

(4)

and
)

(
dimMB (U) = inf sup dimB (Ui ) : U ⊆
i∈N

[
i∈N

Ui ,

(5)

respectively, where in both cases the infimum is over all possible coverings {Ui }i∈N of U by nonempty
compact sets Ui . If dimMB (U) = dimMB (U), this common value, denoted by dimMB (U), is the modified
Minkowski dimension of U .
The main properties of modified Minkowski dimension are summarized in Lemma H.12. In particular,
dimMB (·) ≤ dimB (·) and dimMB (·) ≤ dimB (·). Upper modified Minkowski dimension has the advantage

of being countably stable, a key property we will use frequently. In contrast, upper Minkowski dimension
is only finitely stable [32, Section 3.2, Property (iii)]. For example, all countable subsets of Rm have
modified Minkowski dimension zero (as a single point in Rm has Minkowski dimension zero); the
situation is different for Minkowski dimension as it does not respect countable unions:
Example II.1. [32, Example 3.5] Let F = {0, 1/2, 1/3, . . . }. Then, dimMB (F) = 0 < dimB (F) = 1/2.
Minkowski dimension and modified Minkowski dimension also behave differently for unbounded sets.
Specifically, by monotonicity of (upper) modified Minkowski dimension, dimMB (A) ≤ dimMB (A) ≤
dimMB (Rm ) = m for all A ⊆ Rm , in particular also for unbounded sets, whereas dimB (A) =

March 20, 2018

DRAFT

7

dimB (A) = ∞ for all unbounded sets A as a consequence of NA (ρ) = ∞ for all ρ ∈ (0, ∞). Working

with lower modified Minkowski dimension will allow us to consider arbitrary random vectors, regardless
of whether they admit bounded support sets or not.
The following example shows that modified Minkowski dimension agrees with the sparsity notion used
in classical compressed sensing theory.
Example II.2. Let T1 , . . . , Tk be linear subspaces of Rm with their Euclidean dimensions dim(Ti )
satisfying
max dim(Ti ) = s

(6)

i∈{1,...,k}

and consider the union
U=

k
[
i=1

Ti .

(7)

As every linear subspace is a smooth submanifold of Rm , it follows from Properties i), ii), and v) of
Lemma H.12 that dimMB (U) = s. In the union of subspaces model prevalent in compressed sensing
theory [3]–[6], the subspaces Ti correspond to different sparsity patterns, each of cardinality equal to the
sparsity level s.
The aim of the present paper is to develop a theory of lossless analog compression for arbitrary random
vectors x ∈ Rm . An obvious choice for the stochastic equivalent of the sparsity level s is the stochastic
sparsity level S(x) defined as
(

"

S(x) = min s : ∃T1 , . . . , Tk with P x ∈

k
[
i=1

#
Ti = 1 and

)
max dim(Ti ) = s ,

i∈{1,...,k}

(8)

where every Ti is a linear subspace of Rm . This definition is, however, specific to the union of linear
subspaces structure. The theory we develop here requires a more general notion of description complexity,
which we define in terms of lower modified Minkowski dimension according to
K(x) = inf{dimMB (U) : U ⊆ Rm , P[x ∈ U] = 1}.

(9)

Sets satisfying P[x ∈ U] = 1 are hereafter referred to as support sets of x. While the definition of S(x)
involves minimization of Euclidean dimensions of linear subspaces, K(x) is defined by minimizing the
lower modified Minkowski dimensions of general support sets. The definitions (8) and (9) imply directly
that K(x) ≤ S(x) for all random vectors x ∈ Rm (cf. Example II.2). We will see in Section III that this
inequality can actually be strict.
Next, we show that application of a locally Lipschitz map can not increase the random vector’s
description complexity. This result will allow us to construct random vectors with low description

March 20, 2018

DRAFT

8

complexity out of existing ones simply by applying locally Lipschitz mappings. The formal statement is
as follows.
Lemma II.1. Let x ∈ Rk and f : Rk → Rm be locally Lipschitz. Then, K(f (x)) ≤ K(x).
Proof.
K(f (x)) = inf{dimMB (V) : V ⊆ Rm , P[f (x) ∈ V] = 1}

(10)

= inf{dimMB (f (U)) : U ⊆ Rk , P[x ∈ U] = 1}

(11)

≤ inf{dimMB (U) : U ⊆ Rk , P[x ∈ U] = 1}

(12)

= K(x),

(13)

where (12) follows from Property iv) of Lemma H.12.
When the mapping f is locally bi-Lipschitz, the description complexity remains unchanged:
Corollary II.1. Let x ∈ Rm and f : Rm → Rm be locally bi-Lipschitz, i.e., f is invertible and both f
and f −1 are locally Lipschitz. Then, K(x) = K(f (x)).

Proof. K(x) = K((f −1 ◦ f )(x)) ≤ K(f (x)) ≤ K(x), where we applied Lemma II.1 twice.
As a consequence of Corollary II.1, the description complexity K(x) is invariant under a basis change.
Our main achievability result can now be formulated as follows.
Theorem II.1. (Achievability) For x ∈ Rm , n > K(x) is sufficient for the existence of a Borel measurable
mapping g : Rn×m × Rn → Rm , referred to as (measurable) decoder, satisfying
P[g(A, Ax) 6= x] = 0

for λn×m -a.a. A ∈ Rn×m .

(14)

Proof. See Section V.
Theorem II.1 generalizes the achievability result for linear encoders in [16] in the sense of being
nonasymptotic (i.e., it applies for finite m) and guaranteeing zero error probability.
The central conceptual element in the proof of Theorem II.1 is the following probabilistic null-space
property for arbitrary (possibly unbounded) nonempty sets, first reported in [18] for bounded sets and
expressed in terms of lower Minkowski dimension: If the lower modified Minkowski dimension of a
nonempty set U is smaller than n, then, for λn×m -a.a. measurement matrices A ∈ Rn×m , the set U
intersects the (m − n)-dimensional kernel of A at most trivially. What is remarkable here is that the

March 20, 2018

DRAFT

9

notions of Euclidean dimension (for the kernel of the mapping induced by A) and of lower modified
Minkowski dimension (for U ) are compatible. The formal statement is as follows.
Proposition II.1. Let U ⊆ Rm be nonempty with dimMB (U) < n. Then,
for λn×m -a.a. A ∈ Rn×m .

ker(A) ∩ (U \{0}) = ∅

(15)

Proof. By definition of lower modified Minkowski dimension, there exists a covering {Ui }i∈N of U by

nonempty compact sets Ui with dimB (Ui ) < n for all i ∈ N. The countable subadditivity of Lebesgue
measure now implies that
X


λn×m A ∈ Rn×m : ker(A) ∩ (U \{0}) 6= ∅ ≤
λn×m A ∈ Rn×m : ker(A) ∩ (Ui \{0}) 6= ∅ .
i∈N

(16)
The proof is concluded by noting that [18, Proposition 1] with dimB (Ui ) < n for all i ∈ N implies that
every term in the sum on the right-hand side of (16) equals zero.
We close this section by elucidating the level of generality of our theory through particularization of the
achievability result Theorem II.1 to random vectors supported on attractor sets of systems of contractions
as defined below. Such sets include the Cantor sets, Sierpinski gaskets, the modified Koch curves, and
many other fractals. For an excellent in-depth treatment of attractor sets of systems of contractions, the
interested reader is referred to [32, Section 9]. The formal definition is as follows. Let A ⊆ Rm be
closed. For i = 1, . . . , k , consider si : A → A and ci ∈ (0, 1) such that
ksi (u) − si (v)k2 ≤ ci ku − vk2

for all u, v ∈ A.

(17)

Such mappings are called contractions. By [32, Theorem 9.1], there exists a unique compact set K ⊆ A,
referred to as attractor set, such that
K=

k
[

si (K).

(18)

i=1

Thanks to [32, Proposition 9.6], dimB (K) ≤ d, where d > 0 is the unique solution of
k
X

cdi = 1.

(19)

i=1

If, in addition, K satisfies the open set condition [32, Equation (9.11)], then dimB (K) = d by [32,
Theorem 9.3]. Cantor sets, Sierpinski gaskets, and the modified Koch curves all meet the open set
condition [32, Section 9]. As dimMB (K) ≤ dimB (K) by Property iii) of Lemma H.12, every x ∈ Rm
such that P[x ∈ K] = 1 has description complexity K(x) ≤ d.
We finally note that for self-similar distributions on attractor sets K satisfying the open set condition
[32, Equation (9.11)], an achievability result in terms of information dimension was reported in [16].

March 20, 2018

DRAFT

10

III. R ECTIFIABLE S ETS AND R ECTIFIABLE R ANDOM V ECTORS
The signal models employed in classical compressed sensing [3], [4], model-based compressed sensing
[21], and block-sparsity [25]–[27] all fall under the rubric of unions of linear subspaces. More general
prevalent signal models in sparse signal recovery theory include finite unions of smooth manifolds, either
in explicit form as in [24] or implicitly in the context of low-rank matrix recovery [28]–[30]. All these
models are subsumed by the countable unions of C 1 -manifolds structure, formalized next using the notion
of rectifiable sets. We start with the definition of rectifiable sets.
Definition III.1. (Rectifiable sets) [34, Definition 3.2.14] For s ∈ N, a nonempty set U ⊆ Rm is
i) s-rectifiable if there exist a compact set A ⊆ Rs and a Lipschitz mapping ϕ : A → Rm such that
U = ϕ(A),

ii) countably s-rectifiable if it is the countable union of s-rectifiable sets,
iii) countably (H s , s)-rectifiable if it is H s -measurable and there exists a countably s-rectifiable set V
such that H s (U \V) = 0, where H s denotes the s-dimensional Hausdorff measure (cf. Definition
H.7),
iv) (H s , s)-rectifiable if it is countably (H s , s)-rectifiable and H s (U) < ∞.
Our definitions of s-rectifiability and countably s-rectifiability differ from those of [34, Definition
3.2.14] as we require the s-rectifiable set to be the Lipschitz image of a compact rather than a bounded
set. We note, however, that by [35, Theorem 7.2] our definitions of (H s , s)-rectifiability and countably
(H s , s)-rectifiability are nonetheless equivalent to those of [34, Definition 3.2.14]. The more restrictive

definitions i) and ii) above have the advantage of s-rectifiable sets and countably s-rectifiable sets
being guaranteed to be Borel. Therefore, s-rectifiable sets and countably s-rectifiable sets are also H s measurable, which leads to the following chain of implications:
U is s-rectifiable ⇒ U is countably s-rectifiable ⇒ U is countably (H s , s)-rectifiable.

The following result collects properties of (countably) s-rectifiable sets for later use.
Lemma III.1.
i) If U ⊆ Rm is s-rectifiable, then it is t-rectifiable for all t ∈ N with t > s.

ii) For locally Lipschitz ϕi , i ∈ N, the set

V=

[

ϕi (Rs )

(20)

i∈N

is countably s-rectifiable.

March 20, 2018

DRAFT

11

iii) If U ⊆ Rm is countably s-rectifiable and V ⊆ Rn is countably t-rectifiable, then
W = {(u v)T : u ∈ U, v ∈ V} ⊆ Rm+n

(21)

is countably (s + t)-rectifiable.
iv) Every s-dimensional C 1 -submanifold [36, Definition 5.3.1] of Rm is countably s-rectifiable. In
particular, every s-dimensional affine subspace of Rm is countably s-rectifiable.
v) For Ai countably si -rectifiable and si ≤ s, i ∈ N, the set
[
A=
Ai

(22)

i∈N

is countably s-rectifiable.
Proof. See Appendix A.
Countable unions of s-dimensional C 1 -submanifolds of Rm are countably s-rectifiable by Properties
iv) and v) of Lemma III.1. For countably (H s , s)-rectifiable sets we even get an equivalence result,
namely:
Theorem III.1. [34, Theorem 3.2.29] A set U ⊆ Rm is countably (H s , s)-rectifiable if and only if

H s -a.a. of U is contained in the countable union of s-dimensional C 1 -submanifolds of Rm .

We now show that the upper modified Minkowski dimension of a countably s-rectifiable set is upperbounded by s. This will allow us to conclude that, for a random vector x admitting a countably s-rectifiable
support set, K(x) ≤ s. The formal statement is as follows.
Lemma III.2. If U ⊆ Rm is countably s-rectifiable, then dimMB (U) ≤ s.
Proof. Suppose that U ⊆ Rm is countably s-rectifiable. Then, Definition III.1 implies that there exist
nonempty compact sets Ai ⊆ Rs and Lipschitz mappings ϕi : Ai → Rm , i ∈ N, such that
[
U=
ϕi (Ai ).

(23)

i∈N

Thus,
dimMB (U) = sup dimMB (ϕi (Ai ))

(24)

i∈N

≤ sup dimMB (Ai )

(25)

≤ sup dimMB (Rs )

(26)

= s,

(27)

i∈N

i∈N

March 20, 2018

DRAFT

12

where the individual steps follow from Properties of Lemma H.12, namely, (24) is by Property v), (25)
by Property iv), (26) by Property ii), and (27) by Property i).
We next investigate the effect of locally Lipschitz mappings on (countably) s-rectifiable and countably
(H s , s)-rectifiable sets.

Lemma III.3. Let U ⊆ Rm and consider a locally Lipschitz f : Rm → Rn . If U is
i) s-rectifiable, then f (U) is s-rectifiable,
ii) countably s-rectifiable, then f (U) is countably s-rectifiable,
iii) countably (H s , s)-rectifiable and Borel, then f (U) = A ∪ B , where A is a countably (H s , s)rectifiable Borel set and H s (B) = 0.
Proof. See Appendix B.
A slightly weaker version of this statement valid for Lipschitz mappings was derived previously in
[19, Lemma 4].
We are now ready to define rectifiable random vectors.
Definition III.2. (Rectifiable random vectors) [19, Definition 11] A random vector x ∈ Rm is s-rectifiable

if there exists a countably (H s , s)-rectifiable set U ⊆ Rm such that µx  H s |U . The corresponding
value s is the rectifiability parameter.
It turns out that an s-rectifiable random vector x always admits a countably s-rectifiable support set
and, therefore, has description complexity K(x) ≤ s by Lemma III.2. The formal statement is as follows.

Lemma III.4. Every s-rectifiable random vector x ∈ Rm admits a countably s-rectifiable support set. In
particular, every s-rectifiable random vector x has description complexity K(x) ≤ s.
Proof. Suppose that x is s-rectifiable. Then, there exists a countably (H s , s)-rectifiable set U ⊆ Rm
such that µx  H s |U . As U is countably (H s , s)-rectifiable, by Definition III.1 there exists a countably

s-rectifiable set V ⊆ Rm such that H s (U \V) = 0. Set W = (U \V) ∪ V and note that U ⊆ W implies
H s |U  H s |W by monotonicity of H s . Moreover, it follows from the definition of W , the countable

additivity of H s , and H s (U \V) = 0 that H s |W = H s |V . Thus, H s |U  H s |V , and µx  H s |U

implies µx  H s |V . Therefore, as H s |V (Rm \V) = 0, we can conclude that P[x ∈ Rm \V] = 0, which
is equivalent to P[x ∈ V] = 1, that is, the countably s-rectifiable set V is a support set of x. The proof is
now concluded by noting that K(x) ≤ dimMB (V) ≤ s, where the latter inequality follows from Lemma
III.2.

March 20, 2018

DRAFT

13

In light of Theorem III.1, an s-rectifiable random vector x ∈ Rm is supported on a countable union

of s-dimensional C 1 -submanifolds of Rm . Absolute continuity of µx with respect to the s-dimensional
Hausdorff measure is a regularity condition guaranteeing that x can not have positive probability measure
on sets of Hausdorff dimension t < s (cf. Property i) of Lemma H.13). This regularity condition together
with the sharp transition behavior of Hausdorff measures (see Figure 4 in Appendix H) implies uniqueness
of the rectifiability parameter. The corresponding formal statement is as follows.
Lemma III.5. If x ∈ Rm is s-rectifiable and t-rectifiable, then s = t.
Proof. See Appendix C.
We are now ready to particularize our achievability result to s-rectifiable random vectors.
Corollary III.1. For s-rectifiable x ∈ Rm , n > s is sufficient for the existence of a Borel measurable
mapping g : Rn×m × Rn → Rm satisfying

P[g(A, Ax) 6= x] = 0

for λn×m -a.a. A ∈ Rn×m .

(28)

Proof. Follows immediately from the general achievability result, Theorem II.1, and Lemma III.4.
Again, this result is nonasymptotic (i.e., it applies for finite m) and guarantees zero error probability.
Next, we present three examples of s-rectifiable random vectors aimed at illustrating the relationship
between the rectifiability parameter and the stochastic sparsity level defined in (8). Specifically, in the
first example the random vector’s rectifiability parameter will be seen to agree with its stochastic sparsity
level. The second example constructs an (r + t − 1)-rectifiable random vector of stochastic sparsity
level S(x) = rt for general r, t. In this case, the stochastic sparsity level rt can be much larger than
the rectifiability parameter r + t − 1, and hence Corollary III.1 implies that this random vector can be
recovered with zero error probability from a number of linear measurements that is much smaller than
its stochastic sparsity level. The third example constructs a random vector that is uniformly distributed
on a manifold, namely, the unit circle. In this case the random vector’s rectifiability parameter equals
the dimension of the manifold, whereas its stochastic sparsity level equals the dimension of the ambient
space, i.e., the random vector is not sparse at all.
Example III.1. Suppose that x = (ek1 . . . eks )z ∈ Rm , where z ∈ Rs with µz  λs and k =
(k1 . . . ks )T ∈ {1, . . . , m}s satisfies k1 < · · · < ks . We first show that S(x) = s. To this end, let
U = {x ∈ Rm : kxk0 ≤ s}.

March 20, 2018

(29)

DRAFT

14

Since P[x ∈ U] = 1 by construction, it follows that S(x) ≤ s. To establish that S(x) ≥ s, and hence

S(x) = s, towards a contradiction, assume that there exists a linear subspace T ⊆ Rm of dimension
d < s such that P[x ∈ T ] > 0. Since
0 < µx (T )

(30)

= P[(ek1 . . . eks )z ∈ T ]
X
=
P[(ei1 . . . eis )z ∈ T ] P[k = (i1 . . . is )T ],

(31)
(32)

1≤i1 <···<is ≤m

there must exist a set of indices {i1 , . . . , is } ⊆ {1, . . . , m} with i1 < · · · < is such that
P[Ez ∈ T ] > 0,

(33)

where E = (ei1 . . . eis ). Next, consider the linear subspace
Te = {z ∈ Rs : Ez ∈ T } ⊆ Rs ,

(34)

which, by (33), satisfies P[z ∈ Te ] > 0. As E is obtained by removing column vectors from the identity
matrix, it follows that dim(Te ) = dim(T ) = d. Since d < s by assumption, there must exist a nonzero
T
e
e
vector b0 ∈ Rs such that bT
0 z = 0 for all z ∈ T . It follows that P[b0 z = 0] ≥ P[z ∈ T ] > 0, which

stands in contradiction to µz  λs because λs ({z : bT
0 z = 0}) = 0. Thus, we indeed have S(x) = s. It
follows from Properties iv) and v) in Lemma III.1 that U in (29) is countably s-rectifiable and, therefore,
also countably (H s , s)-rectifiable. We will see in Example IV.3 that x is in fact s-analytic, which, by
Property ii) of Lemma IV.3, implies µx  H s . Finally, by P[x ∈ U] = 1, we get µx  H s |U , which,
thanks to countable (H s , s)-rectifiability of U establishes s-rectifiability of x.
Example III.2. Let x = a ⊗ b with a ∈ Rk and b ∈ Rl . Suppose that a = (ep1 . . . epr )u and b =
(eq1 . . . eqt )v, where u ∈ Rr and v ∈ Rt with µu × µv  λr+t , and p = (p1 . . . pr )T ∈ {1, . . . , k}r

and q = (q1 . . . qt )T ∈ {1, . . . , l}t satisfy p1 < · · · < pr and q1 < · · · < qt , respectively. We first show
that S(x) = rt. Since P[kxk0 ≤ rt] = 1 by construction, it follows that S(x) ≤ rt. To establish that
S(x) ≥ rt, and hence S(x) = rt, towards a contradiction, assume that there exists a linear subspace
T ⊆ Rm of dimension d < rt such that P[x ∈ T ] > 0. Since
0 < µx (T )

(35)

= P[((ep1 . . . epr )u) ⊗ ((eq1 . . . eqt )v) ∈ T ]

(36)

= P[((ep1 . . . epr ) ⊗ (eq1 . . . eqt ))(u ⊗ v) ∈ T ]
X
=
P[((ei1 . . . eir ) ⊗ (ej1 . . . ejt ))(u ⊗ v) ∈ T ]

(37)
(38)

1≤i1 <···<ir ≤k
1≤j1 <···<jt ≤l

March 20, 2018

DRAFT

15

P[p = (i1 . . . ir )T , q = (j1 . . . jt )T ],

(39)

there must exist a set of indices {i1 , . . . , ir } ⊆ {1, . . . , k} with i1 < · · · < ir and a set of indices
{j1 , . . . , jt } ⊆ {1, . . . , l} with j1 < · · · < jt such that
P[(E1 ⊗ E2 )(u ⊗ v) ∈ T ] > 0,

(40)

where E1 = (ei1 . . . eir ) and E2 = (ej1 . . . ejt ). Next, consider the linear subspace
Te = {z ∈ Rrt : (E1 ⊗ E2 )z ∈ T } ⊆ Rrt ,

(41)

which, by (40), satisfies P[u ⊗ v ∈ Te ] > 0. As E1 ⊗ E2 is obtained by removing column vectors from
the identity matrix, it follows that dim(Te ) = dim(T ) = d. Since d < rt by assumption, there must exist

T
e
a nonzero vector b0 ∈ Rrt such that bT
0 z = 0 for all z ∈ T . It follows that P[b0 (u ⊗ v) = 0] ≥ P[u ⊗ v ∈

Te ] > 0. As µu × µv  λr+t by assumption, we also have
n
o
(u
⊗
v)
=
0
> 0.
λr+t (uT v T )T : u ∈ Rr , v ∈ Rt , bT
0

(42)

We now view bT
0 (u ⊗ v) as a polynomial in the entries of u and v . Since a polynomial vanishes either
on a set of Lebesgue measure zero or is identically zero (cf. Corollary K.1 and Lemma K.5), it follows
that
bT
0 (u ⊗ v) = 0

for all u ∈ Rr and v ∈ Rt ,

(43)

which stands in contradiction to b0 6= 0. Thus, we indeed have S(x) = rt. We next construct a countably
(r + t − 1)-rectifiable support set U of x. To this end, we let
A = {a ∈ Rk : kak0 ≤ r}

(44)

B = {b ∈ Rl : kbk0 ≤ t}

(45)

and set U = A ⊗ B . Since A is a support set of a and B is a support set of b, U is a support set of
x = a ⊗ b. Note that U = (A\{0}) ⊗ B . For a ∈ A\{0}, let ā denote the first nonzero entry of a. We

can now write
a⊗b=

a
ā

⊗ (ā b)

for all a ∈ A\{0}, b ∈ B.

(46)

This allows us to decompose U according to U = Ã ⊗ B , where
Ã = {a ∈ A\{0} : kak0 ≤ r, ā = 1}.

March 20, 2018

(47)

DRAFT

16

Now, since Ã is a finite union of affine subspaces of dimensions r − 1, it is countably (r − 1)-rectifiable
by Properties iv) and v) in Lemma III.1. By the same token, B as a finite union of linear subspaces of
dimensions t is countably t-rectifiable. Therefore, the set
C = {(a b)T : a ∈ Ã, b ∈ B} ⊆ Rk+l

(48)

is countably (r + t − 1)-rectifiable thanks to Property iii) of Lemma III.1. Now, the multivariate mapping

σ : Rk+l → Rkl , (a b)T 7→ a ⊗ b is bilinear and as such locally Lipschitz. Moreover, since U = σ(C)

with C countably (r + t − 1)-rectifiable, it follows from Property ii) of Lemma III.3 that U is countably
(r + t − 1)-rectifiable and, therefore, also countably (H r+t−1 , r + t − 1)-rectifiable. We will see in

Example IV.4 that x is in fact (r + t − 1)-analytic, which, by Property ii) of Lemma IV.3, implies
µx  H r+t−1 . With P[x ∈ U] = 1 this yields µx  H r+t−1 |U and, in turn, thanks to countable
(H r+t−1 , r + t − 1)-rectifiability of U , establishes (r + t − 1)-rectifiability of x.

Example III.3. Let S 1 denote the unit circle in R2 , z ∈ R with µz  λ1 , and g : R → S 1 , z 7→
(cos(z) sin(z))T . Set x = g(z), and note that this implies P[x ∈ S 1 ] = 1. We first establish that

S(x) = 2. Since P[x ∈ R2 ] = 1, it follows that S(x) ≤ 2. To establish that S(x) ≥ 2, and hence

S(x) = 2, towards a contradiction, assume that there exists a linear subspace T ⊆ R2 of dimension one

such that P[x ∈ T ] > 0. Set A = T ∩ S 1 , which consists of two antipodal points on S 1 (cf. Figure
2). Now, 0 < P[x ∈ T ] = P[x ∈ A] = P[z ∈ g −1 (A)], which constitutes a contradiction to µz  λ1

because g −1 (A)—as a countable set—must have Lebesgue measure zero. Therefore, S(x) = 2. Finally,
x is 1-rectifiable by [19, Section III.D].

As s-rectifiable random vectors can not have positive probability measure on sets of Hausdorff dimension t < s, it is natural to ask whether taking n ≥ s linear measurements is necessary for zero error
recovery of s-rectifiable random vectors. Surprisingly, it turns out that this is not the case. This will be
demonstrated by first constructing a 2-rectifiable (and therefore also (H 2 , 2)-rectifiable) set G ⊆ R3 of
3
T
strictly positive 2-dimensional Hausdorff measure with the property that eT
3 : R → R, (x1 x2 x3 ) 7→ x3

is one-to-one on G . Then, we show that every 2-rectifiable random vector x satisfying µx  H 2 |G can
be recovered with zero error probability from one linear measurement, specifically from y = eT
3 x. What
is more, all this is possible even though G contains the image of a Borel set in R2 of positive Lebesgue
measure under a C ∞ -embedding (see Figure 1 for an illustration).

The construction of our example is based on the following result.
Theorem III.2. There exist a compact set A ∈ B(R2 ) with λ2 (A) = 1/4 and a C ∞ -function κ : R2 → R
such that κ is one-to-one on A.
March 20, 2018

DRAFT

17

A ✓ Rs , L s (A) > 0

U ✓ Rm

h

h(A)

Figure 1. U contains the embedded image of a set A of positive Lebesgue measure.

Proof. See Section VI for the explicit construction of κ and A.
We now proceed to the construction of our example.
Example III.4. Let κ and A be as constructed in the proof of Theorem III.2 and consider the mapping
h : R2 → R3

(49)

z 7→ (z T κ(z))T .

(50)

We set G = h(A) and show the following:
i) h is a C ∞ -embedding;
1

ii) G is 2-rectifiable;
iii) 0 < H 2 (G) < ∞;

3
T
iv) eT
3 : R → R, (x1 x2 x3 ) 7→ x3 is one-to-one on G .

v) For every 2-rectifiable random vector x ∈ R3 with µx  H 2 |G , there exists a Borel measurable



mapping g : R3 × R → R3 satisfying P g e3 , eT
3 x 6= x = 0.

It follows immediately that h is one-to-one. Thus, to establish Property i), it suffices to prove that h is
a C ∞ -immersion. Since κ is C ∞ , so is h. Furthermore,
q
Jh(z) = det((Dh(z))T Dh(z))
q
= det(I2 + a(z)a(z)T ) for all z ∈ R2 ,

(51)
(52)

where

a(z) =



∂κ(z)
 ∂z1  .
∂κ(z)
∂z2

Since a(z)a(z)T is positive semidefinite, [37, Corollary 7.7.4] implies Jh(z) ≥

(53)
p

det(I2 ) = 1 for all

z ∈ R2 , which establishes that h is an immersion and completes the proof of i).

March 20, 2018

DRAFT

18

To prove ii), note that h is C ∞ and as such locally Lipschitz. As A is compact, Lemma H.9 implies

that h|A is Lipschitz. The set G = h(A) is hence the Lipschitz image of a compact set in R2 and as
such 2-rectifiable.
To establish iii), we first note that
H 2 (G) = H 2 (h(A))

(54)

≤ L2 H 2 (A)

(55)

= L2 λ2 (A)

(56)

< ∞,

(57)

where the individual steps follow from Properties of Lemma H.13, namely, (55) from Property ii) with
L denoting the Lipschitz constant of h|A , and (56) from Property iii).

To establish H 2 (G) > 0, consider the linear mapping
π : R3 → R2

(58)

(x1 x2 x3 )T 7→ (x1 x2 )T .

(59)

Clearly, π is Lipschitz with Lipschitz constant equal to 1. Therefore,
H 2 (G) ≥ H 2 (π(G))

(60)

= H 2 (A)

(61)

= λ2 (A)

(62)

1
= ,
4

(63)

where (60) follows from Property ii) of Lemma H.13, (61) from π(G) = A, and (62) is by Property iii)
of Lemma H.13.
To show iv), let x1 , x2 ∈ G with x1 6= x2 . Thus, x1 = (z1T κ(z1 ))T and x2 = (z2T κ(z2 ))T with
z1 , z2 ∈ A and z1 6= z2 . As κ is one-to-one on A, we conclude that eT
3 is one-to-one on G .

It remains to establish v). Since µx  H 2 |G by assumption, it follows that P[x ∈ G] = 1. We show

that there exists a Borel measurable mapping g : R3 × R → R3 such that



∈ v ∈ G : aT v = y
if ∃v ∈ G : aT v = y
g(a, y)

= e
else,

March 20, 2018

(64)

DRAFT

19

where e is an arbitrary vector not in G , used to declare a decoding error. Since P[x ∈ G] = 1 and eT
3



T
is one-to-one on G , this then implies P g e3 , e3 x 6= x = 0. To construct g in (64), consider first the
mapping
f : R3 × R × R3 → R
(a, y, u) 7→ |y − aT u|.

(65)
(66)

Since f is continuous, Lemma I.3 implies that f is a normal integrand (see Definition I.4) with respect
to B(R3 × R). Let
T = {(a, y) ∈ R3 × R : ∃u ∈ G with f (a, y, u) ≤ 0}
= {(a, y) ∈ R3 × R : ∃u ∈ G with aT u = y}.

(67)
(68)

Note that G as the Lipschitz image of the compact set A is compact (cf. Lemma H.10). It now follows

from Properties ii) and iii) of Lemma I.5 (with T = R3 × R, α = 0, K = G , and f as in (65)–(66),
which is a normal integrand with respect to B(R3 × R)) that i) T ∈ B(R3 × R) and ii) there exists a
Borel measurable mapping
p : T → R3

 
a, y 7→ p a, y ∈ u ∈ G : aT u = y .

(69)
(70)

This mapping can then be extended to a mapping g : R3 × R → R3 by setting
g|T = p
g|(R3 ×R)\T = e.

(71)
(72)

Finally, g is Borel measurable thanks to Lemma H.6 as p is Borel measurable and T ∈ B(R3 × R).
IV. S TRONG C ONVERSE
Example III.4 in the previous section demonstrates that n ≥ s is not necessary for zero error recovery
of s-rectifiable random vectors in general. In this section, we introduce the class of s-analytic random
vectors x, which will be shown to allow for a strong converse in the sense of n ≥ s being necessary for
recovery of x with probability of error smaller than one. The adjective “strong” refers to the fact that
n < s linear measurements are insufficient even if we allow a recovery error probability arbitrarily close

to one. We prove that an s-analytic random vector is s-rectifiable if and only if it admits a support set
U that is “not too rich” (in terms of σ -finiteness of H s |U ), show that the s-rectifiable random vectors

considered in Examples III.1–III.3 are all s-analytic, and discuss examples of s-analytic random vectors

March 20, 2018

DRAFT

20

that fail to be s-rectifiable. Random vectors that are both s-analytic and s-rectifiable can be recovered
with zero error probability from n > s linear measurements, and n ≥ s linear measurements are necessary
for recovery with error probability smaller than one. The border case n = s remains open.
We now make our way towards developing the strong converse and the formal definition of s-analyticity.
The following auxiliary result will turn out useful.
Lemma IV.1. For x ∈ Rm and A ∈ Rn×m , consider the following statements:
i) There exists a Borel measurable mapping g : Rn×m × Rn → Rm satisfying P[g(A, Ax) 6= x] < 1.

ii) There exists a U ∈ B(Rm ) with P[x ∈ U] > 0 such that A is one-to-one on U .
Then, i) implies ii).
Proof. See Appendix D.

We first establish a strong converse for the class of random vectors considered in Example III.1. This
will guide us to the crucial defining property of s-analytic random vectors.
Lemma IV.2. Let x = (ek1 . . . eks )z ∈ Rm , where z ∈ Rs with µz  λs and k = (k1 . . . ks )T ∈

{1, . . . , m}s satisfies k1 < · · · < ks . If there exist a measurement matrix A ∈ Rn×m and a Borel

measurable mapping g : Rn×m × Rn → Rm such that P[g(A, Ax) 6= x] < 1, then n ≥ s.

Proof. Towards a contradiction, suppose that there exist a measurement matrix A ∈ Rn×m and a Borel

measurable mapping g : Rn×m × Rn → Rm so that P[g(A, Ax) 6= x] < 1 for n < s. By Lemma IV.1,
there then must exist a U ∈ B(Rm ) with P[x ∈ U] > 0 such that A is one-to-one on U . Since
P[x ∈ U] = P[(ek1 . . . eks )z ∈ U]
X
=
P[(ei1 . . . eis )z ∈ U] P[k = (i1 . . . is )T ],

(73)
(74)

1≤i1 <···<is ≤m

there must exist a set of indices {i1 , . . . , is } ⊆ {1, . . . , m} with i1 < · · · < is such that the rank-

s matrix H := (ei1 . . . eis ) satisfies P[Hz ∈ U] > 0. Setting A = {z ∈ Rs : Hz ∈ U } yields

µz (A) = P[Hz ∈ U] > 0. Furthermore, A as the inverse image of the Borel set U under a linear

mapping is Borel. Finally, since µz  λs by assumption, we conclude that λs (A) > 0. Summarizing,

there exist a set A ∈ B(Rs ) with λs (A) > 0 and a matrix H ∈ Rm×s such that U contains the one-toone image of A under H . Since A is one-to-one on U and H is one-to-one on Rs , it follows that AH
is one-to-one on A, i.e.,
ker(AH) ∩ (A

March 20, 2018

A) = {0}.

(75)

DRAFT

21

x2

Th

S1

x1

Figure 2. For every vector h ⊆ R2 \{0}, the linear subspace Th := {hz : z ∈ R} intersects the unit circle S1 in the two
antipodal points ±h/khk2 .

Finally, since λs (A) > 0, the Steinhaus Theorem [38] implies the existence of an r > 0 such that
Bs (0, r) ⊆ A

A ⊆ Rs . Since dim ker(AH) ≥ s − n > 0, we conclude that the linear subspace

ker(AH) must have a nontrivial intersection with A

A, which stands in contradiction to (75) and

thereby finishes the proof.
The strong converse just derived hinges critically on the specific structure of the s-rectifiable random
vector x considered. Concretely, we used the fact that, for every U ∈ B(Rm ) with P[x ∈ U] > 0, there

exist a set A ∈ B(Rs ) with λs (A) > 0 and a matrix H ∈ Rm×s such that U contains the one-to-one
image of A under H . The following example demonstrates, however, that this property is too strong for
our purposes as it fails to hold for random vectors on general manifolds like, e.g., the unit circle:
Example IV.1. Let S 1 ⊆ R2 denote the unit circle and consider x ∈ R2 supported on S 1 , i.e., P[x ∈

S 1 ] = 1. Towards a contradiction, suppose that there exist a set A ∈ B(R) with λ1 (A) > 0 and a vector
h ∈ R2 such that {hz : z ∈ A} ⊆ S 1 and h is one-to-one on A. Since h is one-to-one on A and

λ1 (A) > 0, it follows that h 6= 0. Noting that {hz : z ∈ A} ⊆ {h/khk2 , −h/khk2 } (cf. Figure 2), A

necessarily satisfies A ⊆ {1/khk2 , −1/khk2 }. Thus, λ1 (A) = 0, which is a contradiction to λ1 (A) > 0.
The reason for this failure is that every h ∈ R2 maps into a 1-dimensional linear subspace in R2 ,

and 1-dimensional linear subspaces in R2 intersect the unit circle in two antipodal points only. To map
a set A ∈ B(R) to a set in R2 that is not restricted to be a subset of a 1-dimensional linear subspace,
we have to employ a nonlinear mapping. But this puts us into the same dilemma as in Example III.4,

March 20, 2018

DRAFT

22

where we demonstrated that even the requirement of every U ∈ B(Rm ) with P[x ∈ U] > 0 containing

the embedded image—under a C ∞ -mapping—of a set A ∈ B(Rs ) of positive Lebesgue measure is not

sufficient to obtain a strong converse for general x. We therefore need to impose additional constraints
on the mapping. It turns out that requiring real analyticity is enough. Examples of real analytic mappings
include, e.g., multivariate polynomials, the exponential function, or trigonometric mappings. This finally
leads us to the new concept of s-analytic measures and s-analytic random vectors.
Definition IV.1. (Analytic measures) A Borel measure µ on Rm is s-analytic, with s ∈ {1, . . . , m}, if,
for each U ∈ B(Rm ) with µ(U) > 0, there exist a set A ∈ B(Rs ) of positive Lebesgue measure and a
real analytic mapping h : Rs → Rm of s-dimensional Jacobian Jh 6≡ 0 such that h(A) ⊆ U .

Note that the only requirement on the real analytic mappings in Definition IV.1 is that their sdimensional Jacobians do not vanish identically. Since the s-dimensional Jacobian of a real analytic
mapping is a real analytic function, it vanishes either identically or on a set of Lebesgue measure zero
(cf. Lemma K.7). By Lemma K.8, this guarantees that, for an analytic measure µ, every U ∈ B(Rm )

with µ(U) > 0 contains the real analytic embedding of a set A ∈ B(Rs ) of positive Lebesgue measure.
We have the following properties of s-analytic measures.
Lemma IV.3. If µ is an s-analytic measure on Rm , then the following holds:
i) µ is t-analytic for all t ∈ {1, . . . , s − 1};
ii) µ  H s ;

iii) there exists a set U ⊆ Rm such that µ = µ|U and H s |U is σ -finite if and only if there exists a
countably (H s , s)-rectifiable set W ⊆ Rm such that µ = µ|W .

Proof. See Appendix E.
We are now ready to define s-analytic random vectors.
Definition IV.2. (Analytic random vectors) A random vector x ∈ Rm is s-analytic if µx is s-analytic.
The corresponding value s is the analyticity parameter.
We have the following immediate consequence of Lemma IV.3.
Corollary IV.1. Let x be s-analytic. Then, x is s-rectifiable if and only if it admits a support set U such
that H s |U is σ -finite.
Proof. Follows from Properties ii) and iii) in Lemma IV.3 and Definition III.2.

March 20, 2018

DRAFT

23

By Corollary IV.1, an s-analytic random vector is s-rectifiable if and only if it admits a support set U
that is “not too rich” (in terms of σ -finiteness of H s |U ). As an example of an s-analytic random vector
that is not s-rectifiable, consider an (s+1)-analytic random vector x with s > 0. By Property i) in Lemma
IV.3, this x is also s-analytic, but it can not be s-rectifiable, as shown next. Towards a contradiction,
suppose that x is s-rectifiable. Then, by Lemma III.4, x has a countably s-rectifiable support set U ,
which by Property i) in Lemma III.1 is also countably (s + 1)-rectifiable. As, by assumption, x is (s + 1)analytic, Property ii) in Lemma IV.3 implies µx  H s+1 . Thus, µx  H s+1 |U with U countably
(s + 1)-rectifiable, and we conclude that x would also be (s + 1)-rectifiable, which contradicts uniqueness

of the rectifiability parameter, as guaranteed by Lemma III.5.
We just demonstrated that s-analytic random vectors can not be s-rectifiable if they are also (s + 1)analytic. The question now arises whether s-analytic random vectors that fail to be (s + 1)-analytic (and,
therefore, fail to be t-analytic for all t > s by Property i) in Lemma IV.3) are necessarily s-rectifiable.
The next example shows that this is not the case.
Example IV.2. Let C be the middle third Cantor set [32, p. xii] and consider U = {(c t)T : c ∈ C, t ∈
[0, 1]} ⊆ R2 . Since 0 < H ln 2/ ln 3 (C) < ∞ [32, Example 4.5], it follows that the random vector x with

distribution µx = π × (λ1 |[0,1] ), where π = H ln 2/ ln 3 |C /H ln 2/ ln 3 (C), is well defined. We now show
that
i) x is 1-analytic;
ii) x is not 2-analytic;
iii) x is not 1-rectifiable.
To establish i), consider B ∈ B(R2 ) with P[x ∈ B] > 0. Now,
0 < µx (B)
Z


= λ1 t ∈ [0, 1] : (c t)T ∈ B dπ(c)
ZC


≤ λ1 t ∈ R : (c t)T ∈ B dπ(c),

(76)
(77)
(78)

C

where in (77) we applied Corollary H.1 (with the finite measure spaces (R, B(R), π) and (R, B(R), λ1 |[0,1] )
and (78) is by monotonicity of Lebesgue measure. Thus, by Lemma H.2, there must exist a c0 ∈ C such

that A := t ∈ R : (c0 t)T ∈ B satisfies λ1 (A) > 0. Now, define the mapping h : R → R2 , t 7→ (c0 t)T
and note that this mapping is (trivially) real analytic with Jh ≡ 1. Moreover, h(A) ⊆ B by construction,
and A is Borel measurable as the inverse image of the Borel set B under the real analytic and, therefore,
continuous mapping h. Thus, x is 1-analytic.

March 20, 2018

DRAFT

24

We next show that x is not 2-analytic. Towards a contradiction, suppose that x is 2-analytic. Since
µx (U) = 1, by 2-analyticity of x, there must exist a set D ∈ B(R2 ) with λ2 (D) > 0 and a real-analytic

mapping g : R2 → R2 of 2-dimensional Jacobian Jg 6≡ 0 such that g(D) ⊆ U . By Property ii) in Lemma

K.8, we can assume, without loss of generality (w.l.o.g.), that g|D is an embedding. It follows that
Z
2
H (g(D)) =
Jg(z)dλ2 (z)
(79)
D

> 0,

(80)

where in (79) we applied the area formula Corollary H.3 upon noting that g|D is one-to-one as an
embedding and locally Lipschitz by real analyticity of g , and (80) is by Lemma H.2, λ2 (D) > 0, and
Jg(z) > 0 for all z ∈ D. Since g(D) ⊆ U and H 2 (g(D)) > 0, monotonicity of H 2 yields H 2 (U) > 0.

Upon noting that H 1+ln 2/ ln 3 (U) < ∞ [32, Example 4.3], this results in a contradiction to Property i)
in Lemma H.13.
Finally, to establish iii), towards a contradiction, suppose that x is 1-rectifiable. Then, Lemma III.4
implies that x admits a countably 1-rectifiable support set. As every countably 1-rectifiable set is the
countable union of 1-rectifiable sets, the union bound implies that there must exist a 1-rectifiable set V

with P[x ∈ V] > 0. By Definition III.1, there must therefore exist a compact set K ⊆ R and a Lipschitz
mapping f : K → R2 such that V = f (K). It follows that
0 < µx (V)

(81)

= µx (f (K))
Z


= λ1 t ∈ [0, 1] : (c t)T ∈ f (K) dπ(c),
ZC


= λ1 t ∈ [0, 1] : (c t)T ∈ f (Ac ) dπ(c),

(82)
(83)
(84)

C

where in (83) we applied Corollary H.1 (with the finite measure spaces (R, B(R), π) and (R, B(R), λ1 |[0,1] )
and in (84) we set, for every c ∈ C ,
Ac = f −1



(c t)T : t ∈ [0, 1]



⊆ K.

(85)

Note that the sets Ac ⊆ K are pairwise disjoint as inverse images of pairwise disjoint sets. Now, Lemma
H.2 together with (81)–(84) implies that there must exist a set F ⊆ C with π(F) > 0 such that
λ1

March 20, 2018



t ∈ [0, 1] : (c t)T ∈ f (Ac )



>0

for all c ∈ F.

(86)

DRAFT

25

Since π = H ln 2/ ln 3 |C /H ln 2/ ln 3 (C) and 0 < π(F) ≤ 1, the definition of Hausdorff dimension (cf.
Definition H.8) implies dimH (F) = ln 2/ ln 3. As every countable set has Hausdorff dimension zero [32,
p. 29], we conclude that F must be uncountable. Moreover,
λ1 (Ac ) = H 1 (Ac )

(87)

1 1
H (f (Ac ))
L


1
≥ H 1 t ∈ [0, 1] : (c t)T ∈ f (Ac )
L


1
= λ1 t ∈ [0, 1] : (c t)T ∈ f (Ac )
L
≥

>0

(88)
(89)
(90)

for all c ∈ F,

(91)

where (87) and (90) follow from Property iii) in Lemma H.13, (88) is by Property ii) in Lemma H.13
with L the Lipschitz constant of f , (89) is again by Property ii) in Lemma H.13 with the Lipschitz
2
T
constant of the projection eT
2 : R → R, (c t) 7→ t equal to one, and in (91) we used (86). As the sets

Ac are pairwise disjoint subsets of positive Lebesgue measure of the compact set K, it follows that
sup

X

E⊆F :|E|<∞ c∈E

λ1 (Ac ) ≤ λ1 (K) < ∞,

(92)

which, by Lemma H.14, contradicts the uncountability of F . Therefore, x can not be 1-rectifiable.
Our strong converse for analytic random vectors will be based on the following result.
Theorem IV.1. Let A ∈ B(Rs ) be of positive Lebesgue measure, h : Rs → Rm , with s ≤ m, real

analytic of s-dimensional Jacobian Jh 6≡ 0, and f : Rm → Rn real analytic. If f is one-to-one on h(A),
then n ≥ s.
Proof. See Section VII.
With the help of Theorem IV.1, we can now prove the strong converse for s-analytic random vectors.

Corollary IV.2. For x ∈ Rm s-analytic, n ≥ s is necessary for the existence of a measurement matrix

A ∈ Rn×m and a Borel measurable mapping g : Rn×m × Rn → Rm such that P[g(A, Ax) 6= x] < 1.

Proof. Suppose, to the contrary, that there exist a measurement matrix A ∈ Rn×m and a Borel measurable

mapping g : Rn×m × Rn → Rm satisfying P[g(A, Ax) 6= x] < 1 for n < s. Then, by Lemma IV.1, there
must exist a U ∈ B(Rm ) with P[x ∈ U] > 0 such that A is one-to-one on U . As P[x ∈ U] > 0, the
s-analyticity of µx implies the existence of a set A ∈ B(Rs ) of positive Lebesgue measure along with

a real analytic mapping h : Rs → Rm of s-dimensional Jacobian Jh 6≡ 0 such that h(A) ⊆ U . As A is

March 20, 2018

DRAFT

26

one-to-one on h(A) and linear mappings are trivially real-analytic, Theorem IV.1 implies that we must
have n ≥ s, which contradicts n < s.
We next show that the s-rectifiable random vectors considered in Examples III.1–III.3 are all s-analytic
with the analyticity parameter equal to the corresponding rectifiability parameter. We need the following
result, which states that real analytic immersions preserve analyticity in the following sense.
Lemma IV.4. If x ∈ Rm is s-analytic and f : Rm → Rk , with m ≤ k , is a real analytic immersion, then
f (x) is s-analytic.

Proof. See Appendix F.
Example IV.3. We show that x in Example III.1 is s-analytic. To this end, we consider an arbitrary
but fixed U ∈ B(Rm ) with µx (U) > 0 and establish the existence of a set A ∈ B(Rs ) of positive
Lebesgue measure and a real analytic mapping h : Rs → Rm of s-dimensional Jacobian Jh 6≡ 0 such
that h(A) ⊆ U . Since
0 < µx (U)

(93)

= P[(ek1 . . . eks )z ∈ U]
X
=
P[(ei1 . . . eis )z ∈ U] P[k = (i1 . . . is )T ],

(94)
(95)

1≤i1 <···<is ≤m

there must exist a set of indices {i1 , . . . , is } ⊆ {1, . . . , m} with i1 < · · · < is such that
P[u(z) ∈ U] > 0,

(96)

where u : Rs → Rm , z 7→ (ei1 . . . eis )z . As µz  λs by assumption, z is s-analytic thanks to Lemma
IV.5 below. The mapping u is linear and, therefore, trivially real analytic. Furthermore,
r


Ju(z) = det (ei1 . . . eis )T (ei1 . . . eis )
=

p

=1

det Is

for all z ∈ Rs ,

(97)
(98)
(99)

where (97) follows from Du(z) = (ei1 . . . eis ) for all z ∈ Rs , which proves that u is an immersion. We
can therefore employ Lemma IV.4 and conclude that u(z) is s-analytic. Hence, Definition IV.2 together
with (96) implies that there must exist a set A ∈ B(Rs ) of positive Lebesgue measure and a real analytic
mapping h : Rs → Rm of s-dimensional Jacobian Jh 6≡ 0 such that h(A) ⊆ U .
Lemma IV.5. If x ∈ Rm with µx  λm , then x is m-analytic.
March 20, 2018

DRAFT

27

Proof. We have to show that, for each U ∈ B(Rm ) with µx (U) > 0, we can find a set A ∈ B(Rm )

of positive Lebesgue measure and a real analytic mapping h : Rm → Rm of m-dimensional Jacobian
Jh 6≡ 0 such that h(A) ⊆ U . For given such U ∈ B(Rm ), simply take A = U and h the identity mapping

on Rm .

Example IV.4. We show that x = a ⊗ b ∈ Rkl as in Example III.2 is (r + t − 1)-analytic. To this
end, let U ∈ B(Rkl ) with µx (U) > 0 be arbitrary but fixed. We have to establish that there exist a

set A ∈ B(Rr+t−1 ) of positive Lebesgue measure and a real analytic mapping h : Rr+t−1 → Rkl of
(r + t − 1)-dimensional Jacobian Jh 6≡ 0 such that h(A) ⊆ U . Since
0 < µx (U)

(100)

= P[((ep1 . . . epr )u) ⊗ ((eq1 . . . eqt )v) ∈ U]

(101)

= P[((ep1 . . . epr ) ⊗ (eq1 . . . eqt ))(u ⊗ v) ∈ U]
X
P[((ei1 . . . eir ) ⊗ (ej1 . . . ejt ))(u ⊗ v) ∈ U]
=

(102)
(103)

1≤i1 <···<ir ≤k
1≤j1 <···<jt ≤l

P[p = (i1 . . . ir )T , q = (j1 . . . jt )T ],

(104)

there must exist a set of indices {i1 , . . . , ir } ⊆ {1, . . . , m} with i1 < · · · < ir and a set of indices
{j1 , . . . , jt } ⊆ {1, . . . , m} with j1 < · · · < jt such that
P[v(u ⊗ v) ∈ U] > 0,

(105)

where
v : Rrt → Rkl
w 7→ ((ei1 . . . eir ) ⊗ (ej1 . . . ejt ))w.

(106)
(107)

Since µu ×µv  λr+t by assumption, it follows from Lemma IV.6 below that u⊗v is (r +t−1)-analytic.
The mapping v is linear and, therefore, trivially real analytic. Furthermore,
r


Jv(w) = det (E1 ⊗ E2 )T (E1 ⊗ E2 )
r


=

=

p

=1

March 20, 2018

(108)

det (E1T E1 ) ⊗ (E2T E2 )

(109)

det(Ir ⊗ It )

(110)

for all w ∈ Rrt ,

(111)

DRAFT

28

where (108) follows from Dv(w) = E1 ⊗ E2 , with E1 = (ei1 . . . eir ) and E2 = (ej1 . . . ejt ), for all

w ∈ Rrt , which proves that v is an immersion. We can therefore employ Lemma IV.4 and conclude that
v(u ⊗ v) is (r + t − 1)-analytic. Hence, Definition IV.2 together with (105) implies that there must exist

a set A ∈ B(Rr+t−1 ) of positive Lebesgue measure and a real analytic mapping h : Rr+t−1 → Rkl of
(r + t − 1)-dimensional Jacobian Jh 6≡ 0 such that h(A) ⊆ U .

Lemma IV.6. If a ∈ Rk and b ∈ Rl with µa × µb  λk+l , then a ⊗ b is (k + l − 1)-analytic.
Proof. See Appendix G.
Example IV.5. Let x, z, and h be as in Example III.3. We first note that sin and cos are real analytic.
In fact, it follows from the ratio test [39, Theorem 3.34] that the power series
sin(z) =
cos(z) =

∞
X
(−1)n z 2n+1
n=0
∞
X
n=0

(2n + 1)!
(−1)n z 2n
(2n)!

(112)

(113)

are absolutely convergent for all z ∈ R. Thus, sin and cos can both be represented by convergent power
series at 0 with infinite convergence radius. Lemma K.1 therefore implies that sin and cos are both real
p
analytic. As each component of h is real analytic, so is h. Furthermore, Jh(z) = sin2 (z) + cos2 (z) = 1
for all z ∈ R, which implies that h is a real analytic immersion. Since z is 1-analytic by Lemma IV.5
and x = h(z), Lemma IV.4 implies that x is 1-analytic.
V. P ROOF OF T HEOREM II.1 (ACHIEVABILITY )
Suppose that K(x) < n. It then follows from (9) that x must admit a support set U ⊆ Rm with

dimMB (U) < n. We first construct a new support set V ⊆ Rm for x as a countable union of compact sets

satisfying dimMB (V) < n. Based on this support set V we will then prove the existence of a measurable
decoder g satisfying P[g(A, Ax) 6= x] = 0. The construction of V starts by noting that, thanks to
Definition II.2, dimMB (U) < n implies the existence of a covering {Ui }i∈N of U by nonempty compact
sets Ui satisfying
sup dimB (Ui ) < n.

(114)

i∈N

For this covering, we set
V=

March 20, 2018

[
i∈N

Ui ,

(115)

DRAFT

29

and note that
)

(
dimMB (V) = inf sup dimB (Vi ) : V ⊆
i∈N

[
i∈N

Vi

(116)

≤ sup dimB (Ui )

(117)

< n,

(118)

i∈N

where (116) follows from Definition II.2 with the infimum taken over all coverings {Vi }i∈N of V by
nonempty compact sets Vi , (117) is by (115), and in (118) we used (114). Since dimMB (Rm ) = m by

Property i) of Lemma H.12, and dimMB (V) < n ≤ m, we must have V ( Rm . Now, V is a support set

because it contains the support set U as a subset. Furthermore, since P[x ∈ V] = 1 and V ( Rm , there

must exist an e ∈ Rm \V such that P[x = e] = 0. This e will be used to declare a decoding error. We
will show in Section V-A that there exists a Borel measurable mapping g : Rn×m × Rn → Rm satisfying


∈ {v ∈ V : Av = y} if ∃v ∈ V : Av = y
g(A, y)
(119)

= e
else.
The mapping g is guaranteed to deliver a v ∈ V that is consistent with (A, y) (in the sense of Av = y ) if
at least one such consistent v ∈ V exists, otherwise an error is declared by delivering the “error symbol”
e. Next, for each A ∈ Rn×m , let pe (A) denote the probability of error defined as
pe (A) = P[g(A, Ax) 6= x].

(120)

It remains to show that pe (A) = 0 for λn×m -a.a. A. Now,
pe (A) = P[g(A, Ax) 6= x, x ∈ V] + P[g(A, Ax) 6= x, x ∈
/ V]
= P[g(A, Ax) 6= x, x ∈ V]
= P[(A, x) ∈ A]

for all A ∈ Rn×m ,

(121)
(122)
(123)

where (122) follows from P[x ∈ V] = 1 and in (123) we set
A = {(A, x) ∈ Rn×m × V : g(A, Ax) 6= x}.

(124)

Since A ∈ B(Rn×m )⊗B(Rm ) by Lemma V.1 below (with X = Rm , Y = Rn×m , f (x, A) = g(A, Ax),

and V ∈ B(Rm ) as a countable union of compact sets), we can apply Corollary H.1 (with the σ -finite
measure spaces (Rm , B(Rm ), µx ) and (Rn×m , B(Rn×m ), λn×m )) to A and get
Z
Z
pe (A)dλn×m (A) =
λn×m ({A : (A, x) ∈ A})dµx (x).
Rn×m

March 20, 2018

(125)

Rm

DRAFT

30

Next, note that for y = Ax with x ∈ V , the vector g(A, y) can differ from x only if there is a v ∈ V \{x}
that is consistent with y , i.e., if y = Av for some v ∈ V \{x}. Thus,
A ⊆ {(A, x) ∈ Rn×m × V : ker(A) ∩ Vx 6= {0}},

(126)

where, for each x ∈ V , we set
Vx = {v − x : v ∈ V}.

(127)


{A ∈ Rn×m : (A, x) ∈ A} ⊆ A ∈ Rn×m : ker(A) ∩ Vx 6= {0} ,

(128)

As (126) yields

monotonicity of λn×m implies
λn×m ({A ∈ Rn×m : (A, x) ∈ A})


≤ λn×m A ∈ Rn×m : ker(A) ∩ Vx 6= {0}

(129)
for all x ∈ V.

(130)

The null-space property Proposition II.1, with U = Vx and dimMB (Vx ) = dimMB (V) < n ((lower)
modified Minkowski dimension is invariant under translation, as seen by translating covering balls
accordingly) now implies that (130) equals zero for all x ∈ V . Therefore, (129) must equal zero as
well for all x ∈ V . We conclude that both sides of (125) must equal zero as the integrand on the righthand side is identically zero (recall that V is a support set of x), which, by Lemma H.2, implies that we
must have pe (A) = 0 for λn×m -a.a. A, thereby completing the proof.
A. Existence of Borel Measurable g
S
Recall that i) V = i∈N Ui ( Rm , where Ui ⊆ Rm is nonempty and compact for all i ∈ N and ii) the

error symbol e ∈ Rm\V . We have to show that there exists a Borel measurable mapping g : Rn×m × Rn →
Rm such that

g(A, y)



∈ {v ∈ V : Av = y}

if ∃v ∈ V : Av = y


= e

else.

(131)

To this end, first consider the mapping
f : Rn×m × Rn × Rm → R
(A, y, v) 7→ ky − Avk2 .

March 20, 2018

(132)
(133)

DRAFT

31

Since f is continuous, Lemma I.3 implies that f is a normal integrand (see Definition I.4) with respect
to B(Rn×m × Rn ). For each i ∈ N, let
Ti = {(A, y) ∈ Rn×m × Rn : ∃u ∈ Ui with f (A, y, u) ≤ 0}
= {(A, y) ∈ Rn×m × Rn : ∃u ∈ Ui with Au = y}.

(134)
(135)

It now follows from Properties ii) and iii) of Lemma I.5 (with T = Rn×m × Rn , α = 0, K = Ui , and f as

in (132)–(133), which is a normal integrand with respect to B(Rn×m × Rn )) that i) Ti ∈ B(Rn×m × Rn )

for all i ∈ N and ii) for every i ∈ N, there exists a Borel measurable mapping
pi : Ti → Rm

(136)

(A, y) 7→ pi (A, y) ∈ {u ∈ Ui : Au = y}.

(137)

For each i ∈ N, the mapping pi can be extended to a mapping gi : Rn×m × Rn → Rm by setting
gi |Ti = pi

(138)

gi |(Rn×m ×Rn )\Ti = e,

(139)

which is Borel measurable thanks to Lemma H.6 as pi is Borel measurable and Ti ∈ B(Rn×m × Rn ).
Based on this sequence {gi }i∈N of Borel measurable mappings gi , we now construct a Borel measurable
mapping satisfying (131). The idea underlying this construction is as follows. For a given pair (A, y),
we first use g1 to try to find a consistent (in the sense of y = Au) u ∈ U1 . If g1 delivers the error
symbol e, we use g2 to try to find a consistent u ∈ U2 . This procedure is continued until a gi delivers a
consistent u ∈ Ui . If no gi yields a consistent u ∈ Ui , we deliver the error symbol e as the final decoder

output. The formal construction is as follows. We set G1 = g1 and, for every i ∈ N \{1}, we define the

mapping Gi : Rn×m × Rn → Rm iteratively by setting


Gi−1 (A, y) if Gi−1 (A, y) 6= e
Gi (A, y) =

gi (A, y)
else.

(140)

Then, G1 (= g1 ) is Borel measurable, and, for each i ∈ N \{1}, the Borel-measurability of Gi follows
from the Borel-measurability of Gi−1 and gi thanks to Lemma V.2 below. Note that by construction
 n
o
S
S

∈ v ∈ i Uj : Av = y
if ∃v ∈ ij=1 Uj : Av = y
j=1
Gi (A, y)
(141)

= e
else.
Finally, we obtain g : Rn×m × Rn → Rm according to
g(A, y) = lim Gi (A, y),
i→∞

March 20, 2018

(142)

DRAFT

32

which satisfies (131) by construction. As the pointwise limit of a sequence of Borel measurable mappings,
g is Borel measurable thanks to Corollary H.2.

Lemma V.1. Let X and Y be Euclidean spaces, consider a Borel measurable mapping
f : X × Y → X,

(143)

A = {(x, y) ∈ V × Y : f (x, y) 6= x} ∈ B(X × Y) = B(X ) ⊗ B(Y).

(144)

and let V ∈ B(X ). Then,

Proof. We first note that B(X × X ) = B(X ) ⊗ B(X ) and B(X × Y) = B(X ) ⊗ B(Y), both thanks to
Lemma H.3. Therefore, V × X ∈ B(X × X ). Now, consider the diagonal D = {(x, x) : x ∈ X } and note
that D as the inverse image of {0} under the Borel measurable mapping g : X × X → X , (u, v) 7→ u − v
is in B(X × X ). Let C = (V × X ) ∩ ((X × X )\D). Since D ∈ B(X × X ), it follows that C ∈ B(X × X ).
Define the mapping
F: X ×Y →X ×X
(x, y) 7→ (x, f (x, y)),

(145)
(146)

and note that it is Borel measurable thanks to Lemma H.5 (with f1 : X × Y → X , (x, y) 7→ x and
f2 : X × Y → X , (x, y) 7→ f (x, y)). Finally, A ∈ B(X × Y) as A = F −1 (C).

Lemma V.2. Let X and Y be topological spaces and y0 ∈ Y and suppose that f, g : X → Y are both
Borel measurable. Then, h : X → Y ,
h(x) =



f (x)

g(x)

if f (x) 6= y0

(147)

else

is Borel measurable.
Proof. We have to show that h−1 (U) ∈ B(X ) for all U ∈ B(Y). To this end, consider an arbitrary but

fixed U ∈ B(Y). Now, {y0 } ∈ B(Y) implies U \{y0 } ∈ B(Y). We write h−1 (U) = A ∪ B with
A = {x ∈ X : h(x) ∈ U, f (x) 6= y0 }

(148)

B = {x ∈ X : h(x) ∈ U, f (x) = y0 }

(149)

and show that A and B are both in B(X ), which in turn implies h−1 (U) ∈ B(X ). Since
A = {x ∈ X : f (x) ∈ U, f (x) 6= y0 }
= f −1 (U \{y0 }),

March 20, 2018

(150)
(151)

DRAFT

33

z2
1

Q2,3

Q2,4

Q2,1

Q2,2

1

z1

Figure 3. The set Q2 consists of the four grey squares. The set Q3 consists of the sixteen shaded black squares.

U \{y0 } ∈ B(Y), and f is Borel measurable by assumption, it follows that A ∈ B(X ). Finally, as
B = {x ∈ X : g(x) ∈ U, f (x) = y0 }
= f −1 ({y0 }) ∩ g −1 (U),

(152)
(153)

{y0 } ∈ B(Y), U ∈ B(Y), and f and g are both Borel measurable by assumption, it follows that

B ∈ B(X ). Thus, h−1 (U) = A ∪ B ∈ B(X ). Since U was arbitrary, we conclude that h is Borel

measurable.
VI. P ROOF OF T HEOREM III.2
Construction of A. Consider the sequence {ak }k∈N , where ak = 1/2 + 1/2k , and note that
lim ak =

k→∞

1
2

ak > ak+1

(154)
for all k ∈ N.

(155)

Let Q1 = [0, 1]2 be the unit square of side length one. We define
Q2 = Q2,1 ∪ Q2,2 ∪ Q2,3 ∪ Q2,4 ,

(156)

where every square Q2,i ⊆ Q1 has side length a2 /2 with (0 0)T ∈ Q2,1 , (1 0)T ∈ Q2,2 , (0 1)T ∈ Q2,3 ,
and (1 1)T ∈ Q2,4 . It follows from (155) that the squares Q2,1 , . . . , Q2,4 are pairwise disjoint and

Q2 ( Q1 . To define Q3 , we follow the same procedure and split up every set Q2,i into the disjoint

union of four squares with side length a3 /4. The sets Q1 , Q2 , and Q3 are depicted in Figure 3. We
iterate this construction and obtain a sequence {Qk }k∈N , where Qk is the disjoint union of 4k−1 squares
Qk,i , i = 1, . . . , 4k−1 , of side length ak /2k−1 and
Qk+1 ( Qk

March 20, 2018

for all k ∈ N.

(157)

DRAFT

34

Next, we set
A=

\
k∈N

Qk ,

(158)

which, as the intersection of closed sets, is closed. Since A is also bounded it must be compact by the
Heine-Borel theorem [39, Theorem 2.41]. Finally,
λ2 (A) = lim λ2 (Qk )

(159)

= lim

4k−1 a2k
k→∞ (2k−1 )2

(160)

= lim a2k

(161)

1
= ,
4

(162)

k→∞

k→∞

where (159) follows from Property iii) of Lemma H.1.
Construction of κ. We now construct a C ∞ -function κ : R2 → R that is one-to-one on A as defined

in (158). This will be accomplished by building compactly supported C ∞ -functions ϕk,i : R2 → [0, 1],
i = 1, . . . , 4k−1 , k ∈ N, such that

ϕk,i (z) =



1

0

if z ∈ Qk,i ,

(163)

if z ∈ Qk,j , j ∈

{1, . . . , 4k−1 }\{i}.

The construction of these functions is effected by Lemma VI.1 below with ϕk,i (z) = ψδk,i ,ak,i ,wk,i (z),
where wk,i denotes the center of Qk,i , ak,i equals half the side-length of Qk,i , and δk,i is chosen
sufficiently small for (163) to hold (recall that the squares Qk,i are closed and disjoint). Next, we define

the C ∞ -functions

ϕk =

k−1
4X

i=1

i
ϕk,i
4k−1

(164)

i
4k−1

(165)

and note that
ϕk (z) =

for all z ∈ Qk,i , i = 1, . . . , 4k−1 , and k ∈ N, and
|i − j|
4k−1
1
≥ k−1
4

|ϕk (z) − ϕk (w)| =

March 20, 2018

(166)
(167)

DRAFT

35

for all z ∈ Qk,i , w ∈ Qk,j , 1 ≤ i < j ≤ 4k−1 , and k ∈ N. For l ∈ N and a, b ∈ N0 , consider now the

C ∞ -function

(a,b)

sl

(z) :=

=

l
∂ a+b X
1
ϕk (z)
k
a
b
2
∂z1 ∂z2 k=1 8 (Mk + 1)

l
X

∂ a+b ϕk (z)
1
82 (Mk + 1) ∂z1a ∂z2b
k=1
k

(168)

(169)

with
Mk = max max d(i, j),
1≤i≤k 1≤j<k
(
)
∂ j ϕi (z)
d(i, j) = sup max
: a, b ∈ N0 , a + b = j .
∂z1a ∂z2b
z∈R2

(170)
(171)

We now show that this particular choice for the constants Mk guarantees, for each a, b ∈ N0 , that
(a,b)

the sequence {sl

}l∈N of C ∞ -functions converges uniformly and denote the corresponding limiting

functions by κ(a,b) . Corollary J.1 then implies
∂κ(a,b) (z)
= κ(a+1,b) (z)
∂z1

(172)

∂κ(a,b) (z)
= κ(a,b+1) (z)
∂z2

(173)

for all a, b ∈ N0 and z ∈ R2 , and κ(0,0) must therefore be C ∞ . We set κ = κ(0,0) . It remains to prove
(a,b)

uniform convergence of the sequences {sl

a, b ∈ N0 be arbitrary but fixed and note that

}l∈N of C ∞ -functions for all a, b ∈ N0 . To this end, let

d(k, a + b)
∂ a+b ϕk (z)
≤ 2k
a
b
8 (Mk + 1)
∂z1 ∂z2
k + 1)
1
< 2k
8

1
82k (M

(174)
(175)

for all k > a + b and z ∈ R2 . Furthermore, by the sum formula for the geometric series,
∞
X

k=a+b+1

X 1
1
1
<
= .
k
7
8k
82
(a,b)

We can now conclude from (174) and (176) that the sequence {tl
(a,b)
tl (z)

:=

(176)

k∈N

}l∈N of C ∞ -functions

a+b+l
X

∂ a+b ϕk (z)
1
82 (Mk + 1) ∂z1a ∂z2b
k=a+b+1
k

(177)

satisfies the assumptions of Theorem J.1 and therefore converges uniformly to a function, which we
denote by ρ(a,b) . As
(a,b)
sl (z)

=

a+b
X
k=1

March 20, 2018

1
∂ a+b ϕk (z)
(a,b)
+ tl−a−b (z)
82 (Mk + 1) ∂z1a ∂z2b
k

(178)

DRAFT

36

(a,b)

}l∈N must converge uniformly to

a+b
X

1
∂ a+b ϕk (z)
+ ρ(a,b) (z).
82 (Mk + 1) ∂z1a ∂z2b

for all l > a + b, we conclude that {sl
κ(a,b) (z) :=

k

k=1

(a,b)

Since a and b are arbitrary, this implies that {sl
concluding the proof of κ being C ∞ .

(179)

}l∈N converges uniformly for all a, b ∈ N0 , thereby

It remains to show that κ is one-to-one on A. To this end, consider arbitrary but fixed z0 and w0 in A
with z0 6= w0 . We have to show that κ(z0 ) 6= κ(w0 ). Note that by construction of A (cf. (158)), there
exists a k0 ∈ N such that

i) for every k ≥ k0 , there exist ik and jk in {1, . . . , 4k−1 } with ik 6= jk such that z0 ∈ Qk,ik and
w0 ∈ Qk,jk , and

ii) for every k < k0 , there exists an ik such that z0 and w0 are both in Qk,ik .
We therefore have
|κ(z0 ) − κ(w0 )| =
=

X ϕk (z0 ) − ϕk (w0 )
k∈N

(180)

82k (Mk + 1)

∞
X
ϕk (z0 ) − ϕk (w0 )
82k (Mk + 1)

(181)

k=k0

|ϕk0 (z0 ) − ϕk0 (w0 )|
−
≥
k
82 0 (Mk0 + 1)
≥

|ϕk0 (z0 ) − ϕk0 (w0 )|
−
k
82 0 (Mk0 + 1)

1
≥
Mk0 + 1

∞
X
ϕk (z0 ) − ϕk (w0 )
82k (Mk + 1)

k=k0 +1
∞
X
k=k0 +1

|ϕk (z0 ) − ϕk (w0 )|
82k (Mk + 1)

!
∞
X
|ϕk0 (z0 ) − ϕk0 (w0 )|
|ϕk (z0 ) − ϕk (w0 )|
−
,
k
82k
82 0

(182)

(183)

(184)

k=k0 +1

(0,0)

where (180) follows from the uniform convergence of {sl

}l∈N to κ, in (181) we used (165) and ii)

above, (182) is by the reverse triangle inequality, and (184) follows from Mk ≤ Mk+1 for all k ∈ N (cf.
(170)). Moreover, (166)–(167) imply |ϕk0 (z0 ) − ϕk0 (w0 )| ≥ 1/4k0 −1 and (164)–(165) yield
|ϕk (z0 ) − ϕk (w0 )| ≤ |ϕk (z0 )| + |ϕk (w0 )|

(185)

=

(186)

ik + jk
4k−1

≤2

March 20, 2018

for all k ∈ N.

(187)

DRAFT

37

We can therefore further lower-bound |κ(z0 ) − κ(w0 )| according to
1
|κ(z0 ) − κ(w0 )| ≥
Mk 0 + 1
1
=
Mk 0 + 1
1
≥
Mk 0 + 1
=

(Mk0

1
4k0 −1 82

k0

1
4k0 −1 82

k0

1
4k0 −1 82

1
k
+ 1)82 0

k0

−
−
−

1
4k0 −1

∞
X

2
82k

k=k0 +1

!

2

X

(188)
!
(189)

k+k0 +1

82

k∈N0

2
82

−

k0 +1

X 1
8k

!

X 1
8k
k∈N0
| {z }

!

(190)

k∈N0

2
k0

82

(191)

= 87

>

1
k
82 0 (Mk0 + 1)

4
1
−
4k0 −1 82k0

!
(192)

k

82 0 − 4k0
1
= 2k0
k
8 (Mk0 + 1) 4k0 −1 82 0

(193)

> 0.

(194)

Since z0 and w0 are arbitrary, this establishes that κ is indeed one-to-one, thereby finishing the proof.
Lemma VI.1. For a > 0, δ > 0, and w = (w1 w2 )T ∈ R2 , consider the mapping
ψδ,a,w : R2 → [0, 1]
z 7→ ρδ,a (z1 − w1 )ρδ,a (z2 − w2 ),

(195)
(196)

where
ρδ,a : R → [0, 1]
t 7→

f (a + δ − |t|)
f (a + δ − |t|) + f (|t| − a)

with f (t) = e−1/t 1R+ (t). Then, ψδ,a,w is C ∞ and satisfies


1 if max(|z1 − w1 |, |z2 − w2 |) ≤ a,
ψδ,a,w (z) =

0 if min(|z1 − w1 |, |z2 − w2 |) ≥ a + δ.

(197)
(198)

(199)

Proof. It follows from [40, Lemma 2.22] with H = ρδ,a , r1 = a, and r2 = a + δ that ρδ,a is C ∞ and
satisfies
ρδ,a (t) =



1 if |t| ∈ [0, a],

(200)


0 if |t| ∈ [a + δ, ∞).
The claim now follows from ψδ,a,w = ρδ,a (z1 − w1 )ρδ,a (z2 − w2 ) and the properties of ρδ,a .
March 20, 2018

DRAFT

38

VII. P ROOF OF T HEOREM IV.1 (S TRONG C ONVERSE )
Towards a contradiction, suppose that the statement is false. That is, we can find an s ∈ N such that
there exist
i) an A ∈ B(Rs ) with λs (A) > 0,

ii) a real analytic mapping h : Rs → Rm , with s ≤ m, of s-dimensional Jacobian Jh 6≡ 0, and

iii) an n ∈ N with n < s and a real analytic mapping f : Rm → Rn that is one-to-one on h(A).
Let s0 be the smallest s ∈ N such that i)–iii) hold. The proof will be effected by showing that this implies
validity of i)–iii) for s0 − 1 and n − 1, which contradicts the assumption that s0 is the smallest natural
number for i)–iii) to hold. The reader might wonder what happens to this argument in the case where
n = 1. In fact we establish below that, if i)–iii) is satisfied, then necessarily n ≥ 2, cf. the claims a)–c)

right after (215).
Let A, h, n, and f satisfy i)–iii) for this minimum value s0 . We start by noting that
m ≥ s0 > n ≥ 1

(201)

f (x) = (f1 (x) . . . fn (x))T

(202)

by ii) and iii). Next, we write

and set ψi = fi ◦ h, i = 1, . . . , n, and ψ = f ◦ h, which, by Corollary K.2, are all real analytic as
compositions of real analytic mappings. We now show that there must exist an i0 ∈ {1, . . . , n} and a set
Ai0 ⊆ A such that
λs0 (Ai0 ) > 0,

(203)

Jψi0 (z) > 0, and Jh(z) > 0 for all z ∈ Ai0 . To this end, we first decompose
A = A0 ∪

n
[

i=1

Ai ,

(204)

where
Ai = {z ∈ A : Dψi (z) 6= 0, Jh(z) > 0}
= {z ∈ A : Jψi (z) > 0, Jh(z) > 0},

(205)
i = 1, . . . , n,

A0 = {z ∈ A : Dψ(z) = 0} ∪ {z ∈ A : Jh(z) = 0}.

(206)
(207)

By Lemma VII.1 below (with s = s0 ), Dψ(z) 6= 0 for λs0 -a.a. z ∈ A. Furthermore, Jh(z) 6= 0 for
λs0 -a.a. z ∈ A because of Jh 6≡ 0 and Lemma K.7. Thus, λs0 (A0 ) = 0 by countable subadditivity of

Lebesgue measure. Since λs0 (A) > 0 by assumption, and λs0 (A0 ) = 0, it follows, again by countable
subadditivity of Lebesgue measure, that there must exist an i0 such that (203) holds.

March 20, 2018

DRAFT

39

Now, for each y ∈ R, let
My = ψi−1
({y}).
0

(208)

We show in Section VII-A below that there exist a y0 ∈ R and a z0 ∈ Ai0 ∩ My0 such that

H s0 −1 Bs0 (z0 , r) ∩ Ai0 ∩ My0 > 0
Jψi0 (z) > 0

for all r > 0,

(209)

for all z ∈ My0 ,

(210)

Jh(z0 ) > 0.

(211)

It now follows from (210), real analyticity of ψi0 , My0 6= ∅, and Lemma K.11 that My0 is a (s0 − 1)-

dimensional real analytic submanifold of Rs0 . Therefore, by Lemma K.9, there exist a real analytic
embedding ζ : Rs0 −1 → Rs0 and an η > 0 such that
ζ(0) = z0 ,


Bs0 (z0 , η) ∩ My0 ⊆ ζ Rs0 −1 ,

(212)
(213)



and ζ Rs0 −1 is relatively open in My0 , i.e., there exists an open set V ⊆ Rs0 with ζ Rs0 −1 = V ∩My0 .
Combining (209) and (213) yields


H s0 −1 ζ Rs0 −1 ∩ Ai0 > 0.

(214)



Ci0 = ζ −1 ζ Rs0 −1 ∩ Ai0 .

(215)

Next, let

We now show that
a) Ci0 ∈ B(Rs0 −1 ) with λs0 −1 (Ci0 ) > 0,

b) h̃ = h ◦ ζ : Rs0 −1 → Rm is real analytic and of (s0 − 1)-dimensional Jacobian J h̃ 6≡ 0, and
c) s0 − 1 > n − 1 > 0 and the real analytic mapping
f˜: Rm → Rn−1
x 7→ (f1 (x) . . . fi0 −1 (x) fi0 +1 (x) . . . fn (x))T

(216)
(217)

is one-to-one on h̃(Ci0 ),
which finally yields the desired contradiction to the statement of s0 being the smallest natural number
such that i)–iii) at the beginning of the proof are satisfied.

Proof of a). We first establish that Ci0 ∈ B(Rs0 −1 ). Since ζ Rs0 −1 is relatively open in My0 and,

therefore, a Borel set in Rs0 , it follows from (215) that Ci0 is the inverse image of a finite intersection

March 20, 2018

DRAFT

40

of Borel sets under the real analytic embedding ζ and, therefore, also a Borel set. Next, we show that
λs0 −1 (Ci0 ) > 0. Since

Z

Jζ(w)dλs0 −1 (w) = H s0 −1 (ζ(Ci0 ))

(218)

Ci0

= H s0 −1 ζ(Rs0 −1 ) ∩ Ai0



> 0,

(219)
(220)

where (218) follows from the area formula Corollary H.3 upon noting that ζ is one-to-one as an embedding
and locally Lipschitz by real analyticity, (219) is by (215), and in (220) we applied (214). Using Lemma
H.2, we conclude from (218)–(220) that λs0 −1 (Ci0 ) > 0.
Proof of b). By Corollary K.2, h̃ is real analytic as the composition of real analytic mappings. It
remains to show that J h̃ 6≡ 0. To this end, we establish J h̃(0) > 0. First note that the chain rule yields
Dh̃(0) = (Dh)(ζ(0))Dζ(0)
= Dh(z0 )Dζ(0),

(221)
(222)

where the second equality is by (212). Since ζ : Rs0 −1 → Rs0 is an embedding, it follows that
rank(Dζ(0)) = s0 − 1.

(223)

Moreover, as h : Rs0 → Rm with m ≥ s0 , (211) implies
rank(Dh(z0 )) = s0 .

(224)

Applying Lemma K.12 to Dh̃(0) = Dh(z0 )Dζ(0) therefore yields rank(Dh̃(0)) ≥ s0 − 1, which in
turn implies J h̃(0) > 0 because Dh̃(0) ∈ Rm×(s0 −1) .

Proof of c). s0 − 1 > n − 1 simply follows from s0 > n (cf. (201)). To prove that f˜ is one-to-one

on h̃(Ci0 ), we first show that fi0 is constant on h̃(Ci0 ). In fact, since ζ(Ci0 ) ⊆ My0 by (215), and
My0 = (fi0 ◦ h)−1 ({y0 }), it follows that

fi0 (h̃(w)) = y0

for all w ∈ Ci0 .

(225)

As f is one-to-one on h(A) and fi0 is constant on h̃(Ci0 ) with h̃(Ci0 ) = (h ◦ ζ)(Ci0 ) ⊆ h(A) by (215),

we conclude that f˜ must also be one-to-one on h̃(Ci0 ). It remains to show that we must have n > 1,

which obviously implies n − 1 > 0. Suppose, to the contrary, that n = 1. Since h̃ is real analytic with

J h̃ 6≡ 0 and λs0 −1 (Ci0 ) > 0, it follows from Property ii) of Lemma K.8 that h̃ is one-to-one on a subset

of Ci0 of positive Lebesgue measure. Thus, the set h̃(Ci0 ) is uncountable. Now, since by (225) fi0 is
constant on h̃(Ci0 ), and a constant function can not be one-to-one on a set of cardinality larger than one,

March 20, 2018

DRAFT

41

the uncountability of h̃(Ci0 ) implies that fi0 can not be one-to-one on h̃(Ci0 ). But f = fi0 for n = 1
(with i0 = 1) and f is one-to-one on h̃(Ci0 ) ⊆ h(A) by assumption, which results in a contradiction.
Therefore, we necessarily have n > 1 and we can conclude that a)–c) must hold, which finalizes the
proof of the theorem.
A. Proof of (209)–(211)
We start by noting that
Z
Z
1
s0 −1
H
(Ai0 ∩ My )dλ (y) =
R

Jψi0 (z)dλs0 (z)

(226)

Ai0

Z
=

1A (z)Jψi (z)dλs (z)
0

Rs0

i0

0

> 0,

(227)
(228)

where (226) is by the coarea formula Corollary H.4 upon noting that ψi0 is locally Lipschitz by real
analyticity, and (228) follows from

1A (z)Jψi (z) > 0 for all z ∈ Ai , λs (Ai ) > 0 (cf. (203)), and
0

i0

0

0

0

Lemma H.2. Also by Lemma H.2 and (226)–(228), there must exist a set D ⊆ R with λ1 (D) > 0 such
that

H s0 −1 Ai0 ∩ My > 0

for all y ∈ D.

(229)

Furthermore,


λ1 {y ∈ R : ∃z ∈ My with Jψi0 (z) = 0} = λ1 ψi0 {z ∈ Rs0 : Jψi0 (z) = 0}
= 0,

(230)
(231)

where (230) is by (208) and (231) follows from Property ii) of Theorem H.2 with ψi0 being C ∞ (recall
that ψi0 = fi0 ◦ h is real analytic as a composition of real analytic mappings and, therefore, C ∞ by
Lemma K.3). Now, (230)–(231) together with λ1 (D) > 0 implies the existence of a y0 ∈ D such that

(210) holds. For this y0 , we must have H s0 −1 (Ai0 ∩ My0 ) > 0 by (229). Therefore, Lemma H.7 implies

that there must exist a z0 ∈ Ai0 ∩ My0 such that (209) holds. As this z0 ∈ Ai0 ∩ My0 ⊆ Ai0 , (211)
finally follows from (206).
Lemma VII.1. Let A ∈ B(Rs ) be of positive Lebesgue measure, h : Rs → Rm , with s ≤ m, real

analytic of s-dimensional Jacobian Jh 6≡ 0, and f : Rm → Rn real analytic. If f is one-to-one on h(A),
then D(f ◦ h)(z) 6= 0 for λs -a.a. z ∈ A.
Proof. Towards a contradiction, suppose that f is one-to-one on h(A) and D(f ◦ h) ≡ 0 on a set B ⊆ A
with λs (B) > 0. Since f ◦ h is real analytic by Corollary K.2, D(f ◦ h) is real analytic as a consequence
March 20, 2018

DRAFT

42

of Lemma K.3. It therefore follows from Lemma K.5 that D(f ◦ h) is identically zero. Hence, f ◦ h
must be constant. In particular, f ◦ h must be constant on B and, therefore, f must be constant on h(B).
Since f is one-to-one and constant on h(B), it follows that h must be constant on B . Thus, Jh(z) = 0
for all z ∈ B , and Lemma K.5 implies Jh ≡ 0. This is a contradiction to Jh 6≡ 0.
A PPENDIX A
P ROOF OF L EMMA III.1
Proof of i). Suppose that U is s-rectifiable. Then, U = ϕ(A) with A ⊆ Rs compact and ϕ Lipschitz.

For t ∈ N with t > s, take

 

 z



B=
: z ∈ A ⊆ Rt
 0


(232)

and define
ψ : B → Rm
 
z
  7→ ϕ(z).
0

(233)
(234)

Then, U = ψ(B) is t-rectifiable as a consequence of B compact and ψ Lipschitz.
Proof of ii). First note that we can cover Rs according to
[
Ak ,
Rs =

(235)

k∈N

with Ak ⊆ Rs compact for all k ∈ N (take, for example, Ak = Bs (0, k)). Setting, for every i, k ∈ N,
ϕi,k = ϕi |Ak (locally Lipschitz mappings are Lipschitz on compact sets by Lemma H.9), we can write
[
V=
ϕi,k (Ak ),
(236)
i,k∈N

which implies that V is countably s-rectifiable.
Proof of iii). Suppose that U is countably s-rectifiable and V is countably t-rectifiable. Then, we can
write
U=
V=

where the Ai ⊆

Rs

and the Bj ⊆

Rt

[

ϕi (Ai )

(237)

ψj (Bj ),

(238)

i∈N

[
j∈N

are compact and the ϕi : Rs → Rm and the ψj : Rt → Rn are

Lipschitz. Thus,
W=

March 20, 2018

[

θi,j (Ci,j ),

(239)

i,j∈N

DRAFT

43

where we defined
θi,j : Rs+t → Rm+n
(a b)T 7→ (ϕi (a) ψj (b))T

(240)
(241)

and set
Ci,j = {(a b)T : a ∈ Ai , b ∈ Bj }.

(242)

Now, the θi,j are Lipschitz because the ϕi and the ψj are Lipschitz for all i, j ∈ N, and the Ci,j are
compact by Tychonoff’s theorem [41, Theorem 4.42] thanks to Ai and Bj compact for all i, j ∈ N.
Therefore, W is countably (s + t)-rectifiable.

Proof of iv). Let M be a s-dimensional C 1 -submanifold of Rm . By [36, Definition 5.3.1], we can

write
M=

[

ϕx (Ux ),

(243)

x∈M

where, for every x ∈ M, Ux ⊆ Rs is open, and ϕx : Ux → Rm is C 1 and satisfies x ∈ ϕx (Ux ) and

ϕx (Ux ) = Vx ∩ M with Vx ⊆ Rm open. Now, there must exist a countable set {xi : i ∈ N} ⊆ M such

that
M=

[
i∈N

Vxi ∩ M.

(244)

For if such a countable set does not exist, the open set
[

V=

x∈M

Vx

(245)

would not admit a countable subcover, which would contradict that V as an open set in Rm is Lindelöf

[42, Definition 5.6.19, Proposition 5.6.22]. With the countable set {xi : i ∈ N} ⊆ M we can now write
M=

[

ϕi (Ui ),

(246)

i∈N

where we set ϕi = ϕxi and Ui = Uxi . Now fix i ∈ N arbitrarily. As Ui is open, for every ui ∈ Ui , there
exists an rui > 0 such that
B s (ui , rui ) ⊆ Ui .

(247)

We can thus write
Ui =

March 20, 2018

[
ui ∈Ui


ru 
B s ui , i .
2

(248)

DRAFT

44

Since Ui as an open set in Rm is Lindelöf [42, Definition 5.6.19, Proposition 5.6.22], there exists a

countable set {ui,j : j ∈ N} ⊆ Ui such that

Ui =

[
j∈N


ri,j 
B ui,j ,
,
2
s

(249)

where we set ri,j = rui,j for all j ∈ N. Using B s (ui,j , ri,j ) ⊆ Ui for all j ∈ N (cf. (247)), it follows that
[ 
ri,j 
Ui =
B s ui,j ,
.
(250)
2
j∈N

Since i ∈ N was arbitrary, using (246) and (250), we get

[  
ri,j 
s
M=
ϕi B ui,j ,
.
2

(251)

i,j∈N

Finally, all the ϕi as C 1 mappings are locally Lipschitz and, therefore, Lipschitz on the compact sets

B s ui,j , ri,j
for all j ∈ N, which establishes countable rectifiability of M.
2
Proof of v). Since every si -rectifiable set, with si ≤ s, is s-rectifiable by i), it follows that A is a
countable union of s-rectifiable sets and, therefore, countably s-rectifiable.
A PPENDIX B
P ROOF OF L EMMA III.3
Proof of i). Suppose that U is s-rectifiable. Then, there exist a compact set A ⊆ Rs and a Lipschitz

mapping ϕ : A → Rm such that U = ϕ(A). As f ◦ ϕ : A → Rn is Lipschitz owing to Lemmata H.9 and
H.11, f (U) = (f ◦ ϕ)(A) is s-rectifiable.
S
Proof of ii). Suppose that U is countably s-rectifiable. We can write U = i∈N Ui , where Ui is sS
rectifiable for all i ∈ N. As f (U) = i∈N f (Ui ) and f (Ui ) is s-rectifiable for all i ∈ N by i), it follows
that f (U) is countably s-rectifiable.
Proof of iii). Suppose that U ∈ B(Rm ) is countably (H s , s)-rectifiable. We have to show that f (U) =

A∪B, where A ∈ B(Rn ) is countably (H s , s)-rectifiable and H s (B) = 0. As U ∈ B(Rm ) is countably
(H s , s)-rectifiable, [35, Lemma 15.5] implies that H s |U is σ -finite. We can therefore employ Lemma

H.8 to decompose
U = V0 ∪

[
j∈N

Vj ,

(252)

where H s (V0 ) = H s |U (V0 ) = 0 and Vj ⊆ Rm is compact for all j ∈ N. This decomposition allows us
to write f (U) = A ∪ B , where
A=

[

f (Vj )

B = f (V0 ).

March 20, 2018

(253)

j∈N

(254)

DRAFT

45

Now, thanks to Lemma H.10, the f (Vj ) are compact. Therefore, A as a countable union of compact sets
is Borel. Furthermore, H s (B) = 0 because of H s (V0 ) = 0 and Lemma B.1 below. It remains to show
that A is countably (H s , s)-rectifiable. Since U is countably (H s , s)-rectifiable, there exists a countably
s-rectifiable set U1 such that H s (U \U1 ) = 0. Furthermore, as U1 is countably s-rectifiable, f (U1 ) is

countably s-rectifiable by ii). Finally,
H s (A\f (U1 )) ≤ H s (f (U)\f (U1 ))

(255)

≤ H s (f (U \U1 ))

(256)

= 0,

(257)

where (255) follows from the monotonicity of H s and f (U) = A ∪ B , (256) is by monotonicity of H s
and f (U)\f (U1 ) ⊆ f (U\U1 ), and (257) follows from Lemma B.1 below. This proves that A is countably
(H s , s)-rectifiable, thereby concluding the proof.

Lemma B.1. If U ⊆ Rm with H s (U) = 0 and f : Rm → Rn is locally Lipschitz, then H s (f (U)) = 0.
Proof. We employ the following chain of arguments:
 

[
H s (f (U)) = H s f U ∩
Bm (0, l)

(258)

l∈N

=Hs

[
l∈N

≤

X

≤

X

≤

X

l∈N

l∈N


f (Bm (0, l) ∩ U)

(259)

H s (f (Bm (0, l) ∩ U))

(260)

Lsl H s (Bm (0, l) ∩ U)

(261)

Lsl H s (U)

(262)

l∈N

= 0,

(263)

where (260) follows from the countable subadditivity of H s , in (261) we applied Property ii) of Lemma
H.13, where, for every l ∈ N, Ll denotes the Lipschitz constant of f |Bm (0,l) , and in (262) we used the
monotonicity of H s .
A PPENDIX C
P ROOF OF L EMMA III.5
Towards a contradiction, suppose that there exist r, t ∈ N with r 6= t such that x is r-rectifiable and
t-rectifiable. We can assume, w.l.o.g., that r < t. Now, Lemma III.4 implies the existence of

March 20, 2018

DRAFT

46

i) a countably r-rectifiable set U satisfying P[x ∈ U] = 1 and
ii) a countably t-rectifiable set V satisfying P[x ∈ V] = 1.
With Definition III.1, we can conclude that there exist
i) compact sets Ai ⊆ Rr and Lipschitz mappings ϕi : Ai → Rm , i ∈ N, such that
[

U=

ϕi (Ai ),

(264)

i∈N

and
ii) compact sets Bj ⊆ Rt and Lipschitz mappings ψj : Bj → Rm , j ∈ N, such that
[

V=

ψj (Bj ).

(265)

j∈N

The union bound now yields
h
i
[[
P[x ∈ U ∩ V] = P x ∈
ϕi (Ai ) ∩ ψj (Bj )

(266)

i∈N j∈N

≤

XX
i∈N j∈N

P[x ∈ ϕi (Ai ) ∩ ψj (Bj )].

(267)

Since P[x ∈ U ∩ V] = 1, which follows from P[x ∈ U] = 1 and P[x ∈ V] = 1, (266)–(267) guarantee the
existence of an i0 and a j0 , both in N, such that µx (ϕi0 (Ai0 ) ∩ ψj0 (Bj0 )) > 0. As µx  H t |V by the trectifiability of x and H t |V  H t by the monotonicity of H t , it follows that H t (ϕi0 (Ai0 )∩ψj0 (Bj0 )) >
0. Property i) of Lemma H.13 therefore implies (recall that r < t by assumption) H r (ϕi0 (Ai0 ) ∩
ψj0 (Bj0 )) = ∞. The monotonicity of H r then yields
H r (ϕi0 (Ai0 )) ≥ H r (ϕi0 (Ai0 ) ∩ ψj0 (Bj0 ))
= ∞.

(268)
(269)

But we also have
H r (ϕi0 (Ai0 )) ≤ Lr H r (Ai0 )

(270)

= Lr λr (Ai0 )

(271)

< ∞,

(272)

where (270) follows from Property ii) of Lemma H.13 with L the Lipschitz constant of ϕi0 , (271) is by
Property iii) of Lemma H.13 and the fact that Ai0 as a compact set is in B(Rr ), and finally (272) is a
consequence, again, of Ai0 being compact. This contradicts (269) and thereby concludes the proof.

March 20, 2018

DRAFT

47

A PPENDIX D
P ROOF OF L EMMA IV.1
Suppose that there exists a Borel measurable mapping g : Rn×m × Rn → Rm such that P[g(A, Ax) 6=

x] < 1 and set U = {x ∈ Rm : g(A, Ax) = x}. We first show that U ∈ B(Rm ). To this end, consider the

mapping hA : Rm → Rm , x 7→ g(A, Ax), which as the composition of two Borel measurable mappings,
namely, x 7→ (A, Ax) and g , is Borel measurable. Application of Lemma H.5 (with X = Y = Rm , f1
the identity mapping on Rm , and f2 = hA ) therefore establishes that
F : Rm → Rm × Rm
x 7→ (x, hA (x))

(273)
(274)

is Borel measurable. Now, consider the diagonal D = {(x, x) : x ∈ Rm } and note that D as the

inverse image of {0} under the Borel measurable mapping d : Rm × Rm → Rm , (u, v) 7→ u − v is
in B(Rm × Rm ). Since U = F −1 (D), we conclude that U ∈ B(Rm ). Now, P[x ∈ U] > 0 as P[x ∈
/

U] = P[g(A, Ax) 6= x] < 1 by assumption. It remains to show that A is one-to-one on U . To this end,

consider arbitrary but fixed u, v ∈ U and suppose that Au = Av . This implies g(A, Au) = g(A, Av).
As u, v ∈ U by assumption, this is only possible if u = v . Thus, A is one-to-one on U , which concludes
the proof.
A PPENDIX E
P ROOF OF L EMMA IV.3
Proof of i). The proof is by induction. Suppose that µ is s-analytic for s ∈ N \{1}. We have to show

that this implies (s − 1)-analyticity of µ. Consider C ∈ B(Rm ) with µ(C) > 0. Then, by Definition IV.1,
there exist a set A ∈ B(Rs ) of positive Lebesgue measure and a real analytic mapping h : Rs → Rm

of s-dimensional Jacobian Jh 6≡ 0 such that h(A) ⊆ C . By Property ii) of Lemma K.8, we can assume,
w.l.o.g., that h|A is an embedding. For each z ∈ R, let

Az = {v ∈ Rs−1 : (v z)T ∈ A}.

(275)

We now use Fubini’s Theorem to show that there exists a z0 ∈ R such that λs−1 (Az0 ) > 0. Concretely,
Z
0<
1A (z)Jh(z)dλs (z)
(276)
s
R

Z Z

 s−1
T
T
=
1A (v z) Jh (v z) dλ (v) dλ1 (z)
(277)
R
Rs−1

Z Z
 s−1
T
(278)
=
1Az (v)Jh (v z) dλ (v) dλ1 (z),
R

March 20, 2018

Rs−1

DRAFT

48

where (276) follows from Lemma H.2 with λs (A) > 0 and Jh(z) > 0 for all z ∈ A, and in (277) we
applied Theorem H.1. We conclude that there must exist a z0 ∈ R such that
Z

1Az0 (v)Jh (v z0 )T dλs−1 (v) > 0.

(279)

Rs−1

Again using Lemma H.2 establishes that λs−1 (Az0 ) > 0. It remains to show that there exists a real
analytic mapping h̃ : Rs−1 → Rm with h̃(Az0 ) ⊆ C and of (s − 1)-dimensional Jacobian J h̃ 6≡ 0. To this
end, consider the mapping
ϕ : Rs−1 → Rs

(280)

v 7→ (v z0 )T

(281)

and set h̃ = h◦ϕ : Rs−1 → Rm . Now, ϕ is real analytic thanks to Corollary K.1. Thus, h̃ as a composition
of real analytic mappings is real analytic by Corollary K.2. Furthermore, since ϕ(Az0 ) ⊆ A by (275), it
follows that h̃(Az0 ) ⊆ C . It remains to establish that J h̃ 6≡ 0. To this end, we first note that the chain
rule implies Dh̃(v) = Dh(v, z0 )Dϕ(v). Therefore,
rank(Dh̃(v)) = rank(Dh(v, z0 )Dϕ(v))
= rank Dh(v, z0 )(Is−1 0)T
≥s−1

(282)


for all v ∈ Az0 ,

(283)
(284)

where (284) is by Lemma K.12 upon noting that Dh(v, z0 ) ∈ Rm×s , with rank(Dh(v, z0 )) = s (recall
that (v z0 )T ∈ A for all v ∈ Az0 by (275) and that the s-dimensional Jacobian Jh(z) > 0 for all

z ∈ A), and (Is−1 0)T ∈ Rs×(s−1) . Since rank(Dh̃(v)) ≥ s − 1 and Dh̃(v) ∈ Rm×(s−1) , we conclude

that J h̃(v) > 0 for all v ∈ Az0 . Thus, J h̃ 6≡ 0, which finalizes the proof.

Proof of ii). Suppose that µ is s-analytic and consider C ∈ B(Rm ) with µ(C) > 0. We have to show

that H s (C) > 0. By Definition IV.1, there exist a set A ∈ B(Rs ) of positive Lebesgue measure and a

real analytic mapping h : Rs → Rm of s-dimensional Jacobian Jh 6≡ 0 such that h(A) ⊆ C . By Property
ii) of Lemma K.8, we can assume, w.l.o.g., that h|A is an embedding. We now use the area formula
Corollary H.3 to conclude that H s (C) > 0. Concretely,
Z
0<
Jh(z)dλs (z)

(285)

A

= H s h(A)
≤ H s (C),

March 20, 2018



(286)
(287)

DRAFT

49

where (285) is by Lemma H.2, λs (A) > 0, and Jh(z) > 0 for all z ∈ A, in (286) we applied the area
formula Corollary H.3 upon noting that h|A is one-to-one as an embedding and locally Lipschitz by real
analyticity of h, and (287) is by monotonicity of H s together with h(A) ⊆ C .

Proof of iii). ,,⇒”: Suppose that µ is s-analytic and there exists a set U ⊆ Rm such that µ = µ|U

and H s |U is σ -finite. Since H s is Borel regular (cf. Definition H.2), we may assume, w.l.o.g., that
U ∈ B(Rm ). By σ -finiteness of H s |U , there exist sets Vi ∈ B(Rm ), i ∈ N, such that
[
U=
U ∩ Vi

(288)

i∈N

and H s (U ∩ Vi ) < ∞ for all i ∈ N. For every i ∈ N, since U ∩ Vi as the intersection of two Borel sets

fi , where Wi is countably
is in B(Rm ) and H s (U ∩ Vi ) < ∞, we can write [43, p. 83] U ∩ Vi = Wi ∪ W
fi is purely H s -unrectifiable, i.e., H s (W
fi ∩ E) = 0 for all countably (H s , s)(H s , s)-rectifiable and W
f with W = S Wi
rectifiable sets E ⊆ Rm . This allows us to decompose U according to U = W ∪ W
i∈N
S
s
f
fi
f
and W = i∈N Wi . Since all the Wi are countably (H , s)-rectifiable, so is W ; and since all the W
f.
are purely H s -unrectifiable, so is W
f, it remains to show that µ(W)
f = 0 to conclude that
As µ = µ|U by assumption, and U = W ∪ W
f > 0.
µ = µ|W for the countably (H s , s)-rectifiable set W . Towards a contradiction, suppose that µ(W)

Analyticity of µ then implies that there exist a set A ∈ B(Rs ) of positive Lebesgue measure and a real
f. By countable
analytic mapping h : Rs → Rm of s-dimensional Jacobian Jh 6≡ 0 such that h(A) ⊆ W

subadditivity of λs , we can assume, w.l.o.g., that A is bounded; and by Property ii) in Lemma K.8, we
can assume, w.l.o.g., that h|A is an embedding. It follows that
Z
0<
Jh(z)dλs (z)

(289)

A


= H s h(A) ,

(290)

where (289) is by Lemma H.2, λs (A) > 0, and Jh(z) > 0 for all z ∈ A, and in (290) we applied the
area formula Corollary H.3 upon noting that h|A is one-to-one as an embedding and locally Lipschitz
by real analyticity of h. Moreover, as H s is Borel regular (cf. Property ii) in Definition H.2), there
must exist a set C ∈ B(Rm ) with h(A) ⊆ C and H s (C \ h(A)) = 0. It follows that C is countably
(H s , s)-rectifiable as H s (C \h(A)) = 0 and h is Lipschitz on the compact set A by Lemma H.9. But

this implies
f ∩ C) ≥ H s (h(A) ∩ C)
H s (W

March 20, 2018

(291)

= H s (h(A))

(292)

> 0,

(293)

DRAFT

50

f is purely H s -unrectifiable, thereby concluding the proof.
which is not possible as W

,,⇐”: Suppose that there exists a countably (H s , s)-rectifiable set W ⊆ Rm such that µ = µ|W . Since

H s is Borel regular (cf. Definition H.2), we may assume, w.l.o.g., that W ∈ B(Rm ). As this W is

countably (H s , s)-rectifiable, [35, Lemma 15.5] implies that H s |W is σ -finite.
A PPENDIX F
P ROOF OF L EMMA IV.4
Suppose that x ∈ Rm is s-analytic and u = f (x), where f : Rm → Rk is a real analytic immersion,

and consider C ∈ B(Rk ) with µu (C) > 0. We have to show that there exist a set A ∈ B(Rs ) of positive
Lebesgue measure and a real analytic mapping g : Rs → Rk of s-dimensional Jacobian Jg 6≡ 0 such that

g(A) ⊆ C . Set D = f −1 (C) ∈ B(Rm ). Since µx (D) = µu (C) > 0 and x is s-analytic, there exist a set

A ∈ B(Rs ) of positive Lebesgue measure and a real analytic mapping h : Rs → Rm of s-dimensional

Jacobian Jh 6≡ 0 such that h(A) ⊆ D. We set g = f ◦ h. Now, g(A) = f (h(A)) ⊆ f (D) ⊆ C .
Furthermore, g as the composition of real analytic mappings is real analytic by Corollary K.2. It remains
to show that Jg 6≡ 0. To this end, we first note that the chain rule implies Dg(z) = (Df )(h(z))Dh(z).

Since Jh 6≡ 0, there exists a z0 ∈ Rs such that Jh(z0 ) 6= 0. Thus
rank(Dh(z0 )) = s.

(294)

Now, as f is an immersion, it follows that k ≥ m and Jf > 0. Thus,
rank((Df )(h(z0 ))) = m.

(295)

Applying Lemma K.12 to (Df )(h(z0 )) ∈ Rk×m and Dh(z0 ) ∈ Rm×s and using (294) and (295)
establishes that rank(Dg(z0 )) ≥ s, which in turn implies Jg(z0 ) 6= 0 as Dg(z0 ) ∈ Rk×s .
A PPENDIX G
P ROOF OF L EMMA IV.6
Suppose that a ∈ Rk and b ∈ Rl with µa × µb  λk+l , set x = a ⊗ b, and consider C ∈ B(Rkl )

with µx (C) > 0. We have to show that there exist a set A ∈ B(Rk+l−1 ) of positive Lebesgue measure

and a real analytic mapping h : Rk+l−1 → Rkl of (k + l − 1)-dimensional Jacobian Jh 6≡ 0 such that
h(A) ⊆ C . Let
E = {(aT bT )T : a ∈ Rk , b ∈ Rl , a ⊗ b ∈ C}.

March 20, 2018

(296)

DRAFT

51

Since C ∈ B(Rkl ) and ⊗ is Borel measurable, E as the inverse image of C under ⊗ is Borel measurable.
Furthermore, as x = a ⊗ b, it follows that
(µa × µb )(E) = µx (C)
> 0,

(297)
(298)

which implies λk+l (E) > 0 as µa × µb  λk+l by assumption. Using Corollary H.1, we can write
Z
k+l
λ (E) =
λk+l−1 (Ez )dλ1 (z),
(299)
R

where, for each z ∈ R,
Ez =



aT v T

T

: a ∈ Rk , v ∈ Rl−1 , (aT v T z)T ∈ E .

(300)

As λk+l (E) > 0 we can conclude that there must exist a z0 ∈ R\{0} such that λk+l−1 (Ez0 ) > 0. We set
A = Ez0 . Next, we define the mapping
h : Rk+l−1 → Rkl
(c1 . . . ck+l−1 )T 7→ (c1 . . . ck )T ⊗ (ck+1 . . . ck+l−1 z0 )T ,

(301)
(302)

which is real analytic thanks to Corollary K.1, and we write
A=



aT v T

T

: a ∈ Rk , v ∈ Rl−1 , (aT v T z0 )T ∈ E

(303)

=



aT v T

T

: a ∈ Rk , v ∈ Rl−1 , a ⊗ (v T z0 )T ∈ C

(304)

= h−1 (C),

(305)

where (304) follows from (296), and (305) is by (301)–(302). By construction, h(A) ⊆ C . Furthermore,

A as the inverse image of C ∈ B(Rkl ) under a real analytic and, therefore, Borel measurable mapping

is in B(Rk+l−1 ). It remains to show that there exist an a0 ∈ Rk and a v0 ∈ Rl−1 such that
r
 


 T  T T T 

T
T
T T
= det Dh aT
v
Dh a0 v0
Jh aT
0 v0
0
0
> 0.

This will be accomplished by showing that there exist an a0 ∈ Rk and a v0 ∈ Rl−1 such that
 
 
T T
rank Dh aT
v
= k + l − 1.
0
0

March 20, 2018

(306)
(307)

(308)

DRAFT

52

Now,


v

...

0



z0 0


0 v


 0 z0




..
.
T T T
Dh a v
=  ..
.


0 0


0 0


0 0

0

0

0

a1 Il−1

0

...

0

0

...

0

0

...
..
.

0
..
.

0
..
.

...

v

0

. . . z0

0

...

0

v

...

0

z0





0



a2 Il−1 


0


..


.


ak−1 Il−1 



0


ak Il−1 


(309)

0

for general a ∈ Rk and v ∈ Rl−1 , and




0

...

0

0

Il−1



z0 0


0 0


 0 z0

 

..
T
.
T
Dh aT
=  ..
.
0 v0


0 0


0 0


0 0


...

0

0

...

0

0

...
..
.

0
..
.

0
..
.

...

0

0

. . . z0

0

...

0

0

...

0

z0



0 


Il−1 


0 

.. 
. 


Il−1 


0 


Il−1 

0

0

0

0

(310)

for the specific choices a0 = (1 . . . 1)T ∈ Rk and v0 = (0 . . . 0)T ∈ Rl−1 . Since the (kl) × (k + l − 1)

T T has the regular (k + l − 1) × (k + l − 1) submatrix (recall that z 6= 0)
matrix Dh (aT
0
0 v0 )


0
Il−1

,
(311)
z0 I k
0
(308) indeed holds, which concludes the proof.
A PPENDIX H
T OOLS FROM (G EOMETRIC ) M EASURE T HEORY
In this appendix, we state some basic definitions and results from measure theory and geometric
measure theory used throughout the paper. We start with measure theory.
Definition H.1. [36, Definition 1.2.1] A measure (sometimes called pre-measure) on a nonempty set X
is a nonnegative function µ defined on all subsets of X with the following properties:
March 20, 2018

DRAFT

53

i) µ(∅) = 0.
ii) Monotonicity:
µ(A) ≤ µ(B)

for all A ⊆ B ⊆ X .

(312)

iii) Countable subadditivity:
!
[

µ

i∈N

Ai

≤

X

µ(Ai )

(313)

for all E ⊆ X .

(314)

i∈N

for all sequences {Ai }i∈N of sets Ai ⊆ X .
A set A ⊆ X is µ-measurable if it satisfies
µ(E) = µ(E ∩ A) + µ(E \A)

For a probability measure µx , countable subadditivity is equivalent to the union bound
#
"
X
[
P[x ∈ Ai ].
Ai ≤
P x∈
i∈N

(315)

i∈N

The collection of µ-measurable sets forms a σ -algebra [36, Theorem 1.2.4], which we denote by Sµ (X ).
For a topological space X , the smallest σ -algebra containing the open sets is the Borel σ -algebra
B(X ). A measurable space (X , S (X )) is a set X equipped with a σ -algebra S (X ). A measure space
(X , S (X ), µ) is a set X with a measure µ and a σ -algebra S (X ) ⊆ Sµ (X ).

Lemma H.1. [36, Theorem 1.2.5] If (X , S (X ), µ) is a measure space and {An }n∈N a sequence of sets
An ∈ S (X ), then the following properties hold.

i) If the sets An , n ∈ N, are pairwise disjoint, then µ is countably additive on their union. That is,
[
 X
µ(An ).
(316)
µ
An =
n∈N

n∈N

ii) If An ⊆ An+1 for all n ∈ N, then
[

An = lim µ(An ).
µ
n∈N

n→∞

iii) If An+1 ⊆ An for all n ∈ N and µ(A1 ) < ∞, then
\

An = lim µ(An ).
µ
n∈N

n→∞

(317)

(318)

Definition H.2. [36, Definition 1.2.10] A measure µ on a topological space X is
i) Borel if all open sets are µ-measurable;
ii) Borel regular if it is Borel and, for each A ⊆ X , there exists a B ∈ B(X ) such that A ⊆ B and
µ(A) = µ(B).

March 20, 2018

DRAFT

54

As a consequence of Carathéodory’s criterion [36, Theorem 1.2.13], Lebesgue and Hausdorff measures
are Borel regular.
Definition H.3. (Measurable mapping) [44, Chapter 2]
i) Let (X , S (X )) and (Y, S (Y)) be measurable spaces. A mapping f : D → Y , with D ∈ S (X ), is
(S (X ), S (Y))-measurable if f −1 (A) ∈ S (X ) for all A ∈ S (Y).

ii) Let (X , S (X )) be a measurable space and Y a topological space. A mapping f : D → Y , with
D ∈ S (X ), is S (X )-measurable if f −1 (A) ∈ S (X ) for all A ∈ B(Y).

iii) Let X and Y be topological spaces. A mapping f : D → Y , with D ∈ B(X ), is Borel measurable
if f −1 (A) ∈ B(X ) for all A ∈ B(Y).

Lemma H.2. [44, Corollary 4.10] Let (X , S (X ), µ) be a measure space and consider a nonnegative
measurable function f : X → R. Then, f (x) = 0 µ-almost everywhere if and only if
Z
f (x)dµ(x) = 0.

(319)

X

Definition H.4. [36, Definition 1.3.25] The measure space (X , S (X ), µ) is σ -finite if X =

S

i∈N Ai ,

with Ai ∈ S (X ) and µ(Ai ) < ∞ for all i ∈ N. The measure space is finite if µ(X ) < ∞. A

Borel measure µ on a topological space X is σ -finite (respectively finite) if (X , B(X ), µ) is a σ -finite
(respectively finite) measure space.
For example, all probability measures are finite and the Lebesgue measure is σ -finite. However, the
s-dimensional Hausdorff measure with s < m is not σ -finite.

Theorem H.1. (Fubini’s theorem) [44, Theorem 10.9] Let (X , S (X ), µ) and (Y, S (Y), ν) be σ -finite
measure spaces and suppose that f : X × Y → R is nonnegative and (S (X ) ⊗ S (Y))-measurable. Then,
Z
ϕ(x) =
f (x, y)dν(y) is S (X )-measurable,
(320)
Y
Z
ψ(y) =
f (x, y)dµ(x) is S (Y)-measurable,
(321)
X

and
Z

Z
ϕ(x)dµ(x) =

X

X ×Y

f (x, y)d(µ × ν)(x × y)

(322)

Z
=

ψ(y)dν(y).

(323)

Y

March 20, 2018

DRAFT

55

Corollary H.1. Let (X , S (X ), µ) and (Y, S (Y), ν) be σ -finite measure spaces and suppose that A ∈
S (X ) ⊗ S (Y). Then,
Z
X

ν({y : (x, y) ∈ A})dµ(x) =

Z
X ×Y

Z
=
Y

1A (x, y)d(µ × ν)(x × y)

µ({x : (x, y) ∈ A})dν(y).

Proof. Follows from Theorem H.1 with f (x, y) = 1A (x, y), noting that
Z
1A (x, y)dν(y) = ν({y : (x, y) ∈ A}),
Y
Z
1A (x, y)dµ(x) = µ({x : (x, y) ∈ A}).

(324)
(325)

(326)
(327)

X

Lemma H.3. [45, Exercise 1.7.19] If X and Y are Euclidean spaces, then B(X × Y) = B(X ) ⊗ B(Y).
Lemma H.4. [44, Corollary 2.10] Let (X , S (X )) be a measurable space and suppose that {fi }i∈N is
a sequence of S (X )-measurable functions fi : X → R converging pointwise to f : X → R. Then, f is
S (X )-measurable.

Lemma H.5. Let X and Y be Euclidean spaces and suppose that fi : X → Y , i = 1, . . . , n, are Borel
measurable mappings. Then,
f : X → Ỹ = Y × · · · × Y
{z
}
|

(328)

n times

x 7→ (f1 (x), . . . , fn (x))

(329)

is Borel measurable.
Proof. Lemma H.3 implies B(Ỹ) = B(Y) ⊗ · · · ⊗ B(Y). Thus, B(Ỹ) is generated by sets U1 × · · · × Un ,
where Ui ∈ B(Y) for i = 1, . . . , n. It is therefore sufficient (cf. Part iii) in Definition H.3) to show

that f −1 (U1 × · · · × Un ) ∈ B(X ) for all Ui ∈ B(X ), i = 1, . . . , n. But f −1 (U1 × · · · × Un ) =

f1−1 (U1 )∩· · ·∩fn−1 (Un ) ∈ B(X ) for all Ui ∈ B(Y), i = 1, . . . , n, as all the fi are Borel measurable.

Corollary H.2. Let X be a Euclidean space and suppose that {fi }i∈N is a sequence of Borel measurable

mappings fi : X → Rn converging pointwise to f : X → Rn . Then, f is Borel measurable.

Proof. We can write f (x) = (f (1) (x), . . . , f (n) (x))T , where f (j) : X → R is Borel measurable for j =
T
(1)
(n)
(j)
1, . . . , n, and fi (x) = fi (x), . . . , fi (x) , where fi : X → R is Borel measurable for j = 1, . . . , n
(j)

and all i ∈ N. Then, for each j = 1, . . . , n, the sequence (fi )i∈N of Borel measurable functions
March 20, 2018

DRAFT

56

converges pointwise to f (j) , which is Borel measurable thanks to Lemma H.4. Finally, Lemma H.5
implies that f is Borel measurable as its individual components f (1) , . . . , f (n) are Borel measurable.
Lemma H.6. Let X and Y be topological spaces, C ∈ B(X ), f : C → Y Borel measurable, and
y0 ∈ Y \f (C). Consider h : X → Y with h|C = f and h|X \C = y0 . Then, h is Borel measurable.

Proof. We have to show that h−1 (A) ∈ B(X ) for all A ∈ B(Y). Consider an arbitrary but fixed
A ∈ B(Y) and suppose first that y0 ∈ A. Now, A ∈ B(Y) and {y0 } ∈ B(Y) imply A\{y0 } ∈ B(Y).

Therefore,
h−1 (A) = h−1 (A\{y0 }) ∪ h−1 ({y0 })
= f −1 (A\{y0 }) ∪ (X \C) ∈ B(X )

(330)
(331)

because f is Borel measurable, A\{y0 } ∈ B(Y), and X \C ∈ B(X ). If y0 ∈
/ A, then
h−1 (A) = f −1 (A) ∈ B(X )

(332)

as f is Borel measurable and A ∈ B(Y).
Lemma H.7. Let µ be a measure on Rk and consider A ⊆ Rk with µ(A) > 0. Then, there exists a
z0 ∈ A such that


µ Bk (z0 , r) ∩ A > 0

for all r > 0.

(333)

Proof. Suppose, to the contrary, that such a z0 does not exist. Then, for every z ∈ A, there must exist

a rz > 0 such that µ Bk (z, rz ) ∩ A = 0. With these rz , we write
[

A=

z∈A

(Bk (z, rz ) ∩ A).

(334)

It now follows from the Lindelöf property of Rk [42, Definition 5.6.19, Proposition 5.6.22] that there
must exist a countable subset {zi : i ∈ N} ⊆ A such that
A=

[

(Bk (zi , rzi ) ∩ A).

(335)

i∈N


Since µ Bk (zi , rzi ) ∩ A = 0 for all i ∈ N, the countable subadditivity of µ implies
µ(A) ≤

X
i∈N

µ Bk (zi , rzi ) ∩ A



= 0,

(336)
(337)

which contradicts the assumption µ(A) > 0 and thereby concludes the proof.

March 20, 2018

DRAFT

57

Lemma H.8. Let (X , B(X ), µ) be a σ -finite measure space and B ∈ B(X ). Then,
B = N ∪ A,

where µ(N ) = 0 and A =

S

i∈N Ai

(338)

with Ai ⊆ Rm compact for all i ∈ N.

Proof. By [43, Proposition 1.43], we can find, for each i ∈ N, a compact set Ki such that Ki ⊆ B and
S
µ(B\Ki ) ≤ 1/i. For j ∈ N, let Aj = ji=1 Ki . It follows that {Aj }j∈N is an increasing (in terms of ⊆)
sequence of compact sets Aj ⊆ B satisfying µ(B) − µ(Aj ) = µ(B \Aj ) ≤ 1/j for all j ∈ N. We set
S
A = j∈N Aj ⊆ B . Thus, µ(A) ≤ µ(B) by monotonicity of µ. Now,
µ(A) = lim µ(Aj )

(339)

j→∞

= µ(B) − lim µ(B\Aj )
j→∞

1
j→∞ j

(340)

≥ µ(B) − lim

(341)

= µ(B),

(342)

where (339) follows from Lemma H.1. We conclude that µ(A) = µ(B), which, together with A ⊆ B ,
yields (338).
Definition H.5. (Locally Lipschitz mapping) [46, Definition 3.118]
i) A mapping f : U → Rl , where U ⊆ Rk , is Lipschitz if there exists a constant L ≥ 0 such that
kf (u) − f (v)k2 ≤ Lku − vk2

for all u, v ∈ U.

(343)

The smallest constant L for (343) to hold is the Lipschitz constant of f .
ii) A mapping f : Rk → Rl is locally Lipschitz if every x ∈ Rk admits an open neighborhood Ux ⊆ Rk
containing x such that f |Ux is Lipschitz.
The following result establishes a necessary and sufficient condition for a mapping to be locally
Lipschitz. Since we could not find a proof for this statement in the literature, we present one here for
completeness.
Lemma H.9. The mapping f : Rk → Rl is locally Lipschitz if and only if f |K is Lipschitz for all
compact sets K ⊆ Rk .

Proof. ,,⇒”: Suppose that f : Rk → Rl is locally Lipschitz and consider a compact set K ⊆ Rk . We
have to show that f |K is Lipschitz. For every x ∈ K, by the local Lipschitz property of f , there exists
S
an open neighborhood Ux containing x such that f |Ux is Lipschitz. As K is compact and K ⊆ x∈K Ux ,
March 20, 2018

DRAFT

58

there must exist Uxi , denoted by Ui , i = 1, . . . , n, such that K ⊆

Sn

i=1 Ui .

For i = 1, . . . , n, let Li denote

the Lipschitz constant of f |Ui . Now, as shown below, there exists a δ > 0 such that, for every x, y ∈ K
with kx − yk2 < δ , we can find a Ui in the finite subcover of U with x, y ∈ Ui . With this δ we let


2∆
L = max L1 , . . . , Ln ,
,
(344)
δ
where ∆ := maxx∈K f (x). Consider an arbitrary pair x, y ∈ K. If kx − yk2 < δ , then this pair
must be in the same Ui , which implies kf (x) − f (y)k ≤ Li kx − yk ≤ Lkx − yk. If kx − yk2 ≥ δ ,
then kf (x) − f (y)k ≤ 2∆ = 2∆δ/δ ≤ (2∆/δ)kx − yk2 ≤ Lkx − yk2 . Thus, f |K is Lipschitz with
Lipschitz constant L. It remains to establish the existence of a δ with the desired properties. Towards a
contradiction, suppose that such a δ does not exist. This implies that, for every m ∈ N, we can find a pair
xm , ym ∈ K such that kxm −ym k2 < 1/m, but there is no Ui containing this pair. Since K×K is compact

by Tychonoff’s Theorem [41, Theorem 4.42], there exists a convergent subsequence {xmj , ymj }j∈N of
the sequence {xm , ym }m∈N [39, Theorem 2.41]. Let (x̄, ȳ) denote the limit point of this subsequence.

Note that x̄ and ȳ can not be in the same Ui , for if they were there would be an M ∈ N such that

(xmj , ymj ) ∈ Ui × Ui for all j ≥ M , which is not possible as xm and ym are in different Ui ’s for all
m ∈ N. But

x̄ − ȳ = lim (xmj − ymj )
j→∞

= 0,

(345)
(346)

where the second equality follows from limj→∞ k(xmj − ymj )k2 < limj→∞ 1/mj = 0 and continuity
of k · k2 . Thus, x̄ = ȳ , which is not possible as there is no Ui containing x̄ and ȳ .

,,⇐”: Suppose that f |K is Lipschitz for all compact sets K ⊆ Rk . It is sufficient to show that f |Bk (x,1)

is Lipschitz for every x ∈ Rk . As Bk (x, 1) is compact, f |Bk (x,1) is Lipschitz. The Lipschitz property of
f |Bk (x,1) therefore follows immediately from Bk (x, 1) ⊆ Bk (x, 1).

Lemma H.10. If f : Rm → Rn is locally Lipschitz and K ⊆ Rm is compact, then f (K) is compact.
Proof. Follows from continuity of f and [47, Theorem 2-7.2].
We will need the following composition property of locally Lipschitz mappings.
Lemma H.11. If f : Rk → Rm and g : Rm → Rn are locally Lipschitz, then h = g ◦ f : Rk → Rn is
locally Lipschitz.
Proof. Suppose that f : Rk → Rm and g : Rm → Rn are both locally Lipschitz. To prove that h = g ◦ f
is locally Lipschitz, by Lemma H.9, it is sufficient to show that h|K is Lipschitz for all compact sets

March 20, 2018

DRAFT

59

K ⊆ Rk . Let K ⊆ Rk be an arbitrary but fixed compact set and note that Q = f (K) is compact owing

to Lemma H.10. Thus, by Lemma H.9, f |K and g|Q are both Lipschitz with Lipschitz constants, say, L
and M , respectively. It follows that
kh(u) − h(v)k2 ≤ M kf (u) − f (v)k2

(347)

≤ LM ku − vk2

(348)

for all u and v in K, which implies that h|K is Lipschitz. As K was arbitrary, we conclude that h is
locally Lipschitz.
Definition H.6. (Differentiable mapping) [48, Definition 1.2] Let U be an open set in Rm . A function
f : U → R is

i) C 0 if it is continuous.
ii) C r with r ∈ N if, for all possible choices of r1 , . . . , rm ∈ N0 with

Pk

i=1 ri

= r, the partial

derivatives
∂r
f (x)
∂xr11 . . . ∂xrmm

(349)

exist and are continuous on U .

iii) C ∞ if it is C r for all r ∈ N.

For r ∈ N0 ∪ {∞}, a mapping f : U → Rn , x 7→ (f1 (x) . . . fn (x))T is C r if every component fi ,
i = 1, . . . , n, is C r .

It follows from the mean value theorem [49, Theorem 3.4] that C 1 mappings are locally Lipschitz.
Conversely, by Rademacher’s Theorem [36, Theorem. 5.1.11], every locally Lipschitz mapping f : Rm →

Rn has a L (Rm )-measurable (but not necessarily continuous) differential Df , which is defined λm -a.e.
Theorem H.2. (Sard’s theorem) [50] Let f : Rm → Rn , x 7→ (f1 (x) . . . fn (x))T be C r and set A =
{x : Jf (x) = 0}. The following statements hold.

i) If m ≤ n, then H m (f (A)) = 0.
ii) If m > n and r ≥ m − n + 1, then λn (f (A)) = 0.
Next, we state two fundamental results from geometric measure theory that are used frequently in the
paper, namely, the area and the coarea formula for locally Lipschitz mappings f : Rm → Rn .

March 20, 2018

DRAFT

60

Theorem H.3. (Area formula) [36, Theorem 5.1.1] If A ∈ B(Rm ), f : Rm → Rn is Lipschitz, and
g : A → R is nonnegative and Lebesgue measurable, and m ≤ n, then
Z
Z

m
Jf (x)dλ (x) =
card A ∩ f −1 ({y}) dH m (y).
A

(350)

Rn

Corollary H.3. (Area formula) If A ∈ B(Rm ), f : Rm → Rn is locally Lipschitz and one-to-one on A,
and m ≤ n, then
Z

Jf (x)dλm (x) = H m (f (A)).

(351)

A

Proof. For i ∈ N, let gi = 1Bm (0,i) . It follows that
Z
Z
m
Jf (x)dλ (x) = lim
gi (x)Jf (x)dλm (x)
i→∞ A
A
Z
= lim
J(f |Bm (0,i) )(x)dλm (x)
i→∞ A
Z


({y})
dH m (y)
= lim
card A ∩ f |−1
Bm (0,i)
i→∞ Rn

= lim H m f A ∩ Bm (0, i)



i→∞

(352)
(353)
(354)
(355)

!
=Hm

[
i∈N


f A ∩ Bm (0, i)

= H m (f (A)),

(356)
(357)

where (352) is by the Lebesgue Monotone Convergence Theorem [44, Theorem 4.6] upon noting that
(gi )i∈N is an increasing sequence of nonnegative Borel measurable functions converging to 1Rm , in (354)

we applied Theorem H.3 to f |Bm (0,i) , which is Lipschitz by Lemma H.9 as Bm (0, i) ⊆ Bm (0, i) and

Bm (0, i) is compact for all i ∈ N, in (355) we used that f is one-to-one, by assumption, which implies


1 if y ∈ f A ∩ Bm (0, i)

 
−1
(358)
card A ∩ f |Bm (0,i) ({y}) =

0 else,

and (356) is by Property ii) in Lemma H.1.
Theorem H.4. (Coarea formula) [36, Theorem 5.2.1] If f : Rm → Rn is Lipschitz, A ∈ B(Rm ), and
m ≥ n, then

Z

m

Z

Jf (x)dλ (x) =
A

Rn


H m−n A ∩ f −1 ({y}) dλn (y).

(359)

Corollary H.4. (Coarea formula) If f : Rm → Rn is locally Lipschitz, A ∈ B(Rm ), and m ≥ n, then
Z
Z

m
Jf (x)dλ (x) =
H m−n A ∩ f −1 ({y}) dλn (y).
(360)
A

March 20, 2018

Rn

DRAFT

61

Proof. We have
Z

Z

m

Jf (x)dλ (x) = lim

i→∞ A

A

J(f |Bm (0,i) )(x)dλm (x)

(361)

Z



H m−n A ∩ f |−1
({y})
dλn (y)
Bm (0,i)
i→∞ Rn
!
Z
[
n
A ∩ f |−1
=
H m−n
Bm (0,i) ({y}) dλ (y)
= lim

Rn

Z
=
Rn

(362)
(363)

i∈N


H m−n A ∩ f −1 ({y}) dλn (y),

(364)

where (361) follows from (352)–(353), in (362) we applied Theorem H.4 to f |Bm (0,i) , which is Lipschitz
by Lemma H.9 as Bm (0, i) ⊆ Bm (0, i) and Bm (0, i) is compact for all i ∈ N, and (363) is by the
Lebesgue Monotone Convergence Theorem [44, Theorem 4.6] upon noting that, for every i ∈ N, the

function
gi : Rn → R

(365)

y 7→ H m−n




A ∩ f |−1
({y})
Bm (0,i)

(366)

is Lebesgue measurable [36, Lemma 5.2.5] and, therefore, (gi )i∈N is a sequence of nonnegative increasing
Lebesgue measurable functions, with
!
lim gi (y) = H

m−n

i→∞

[
i∈N

A∩

f |−1
Bm (0,i) ({y})

for all y ∈ Rn

(367)

by Property ii) in Lemma H.1.
Lemma H.12. Main properties of modified Minkowski dimension:
i) A smooth s-dimensional submanifold U of Rm has dimMB (U) = s.
ii) dimMB (·) and dimMB (·) are monotonic with respect to ⊆.
iii) dimMB (U) ≤ dimB (U) and dimMB (U) ≤ dimB (U) for all nonempty sets U .
iv) If f is locally Lipschitz, then
dimMB (f (U)) ≤ dimMB (U)

(368)

dimMB (f (U)) ≤ dimMB (U)

(369)

for all nonempty subsets U in the domain of f .
v) dimMB is countably stable, i.e.,
!
dimMB

[
i∈N

Ui

= sup dimMB (Ui )

(370)

i∈N

for all countable collections of nonempty sets Ui , i ∈ N.
March 20, 2018

DRAFT

62

H d (U)
∞

0

dimH (U)

m

d

Figure 4. ([32, Figure 2.3]) Graph of H d (U) as a function of d ∈ [0, m] for a set U ⊆ Rm .

Proof. Properties i)–iv) follow from the definitions of lower and upper modified Minkowski dimension
and the properties of lower and upper Minkowski dimension listed in [32, Section 3.2]. Property v)
follows from [32, Equation 3.26] and [32, Proposition 3.8].
Definition H.7. (Hausdorff measures) [43, Definition 2.46] Let d ∈ [0, ∞) and U ⊆ Rm . The ddimensional Hausdorff measure of U , denoted by H d (U), is limδ→0 Hδd (U), where
(
)
X
[
V
(d,
1)
inf
diam(Ui )d : diam(Ui ) < δ, U ⊆
Ui
Hδd (U) =
2d
i∈N

(371)

i∈N

for all δ > 0, with
diam(U) :=



sup{ku − vk2 : u, v ∈ U}

if U 6= ∅


0

if U = ∅.

(372)

Definition H.8. (Hausdorff dimension) [43, Definition 2.51] The Hausdorff dimension of U ⊆ Rm ,
denoted by dimH (U), is sup{d ≥ 0 : H d (U) = ∞} = inf{d ≥ 0 : H d (U) = 0}, i.e., dimH (U) is the
value of d for which the sharp transition from ∞ to 0 in Figure 4 occurs.
Lemma H.13. Main properties of Hausdorff measures:
i) If a > b ≥ 0, then H a (E) > 0 implies H b (E) = ∞ for all E ⊆ Rm (cf. Fig. 4).

ii) If f : Rm → Rn is Lipschitz with Lipschitz constant L, then
H d (f (E)) ≤ Ld H d (E)

for all E ⊆ Rm .

(373)

iii) H m (E) = λm (E) for all E ∈ B(Rm ).
Proof. See [43, Proposition 2.49] and [43, Theorem 2.53].

March 20, 2018

DRAFT

63

Lemma H.14. Let xi > 0 for all i ∈ I and set
M=

sup

X

xi .

(374)

J ⊆I : |J |<∞ i∈J

If M < ∞, then I is at most countable.
Proof. Suppose that M is finite. For every k ∈ N0 , set Ik = {i ∈ I : 1/(k + 1) ≤ xi < 1/k} and
Mk =

sup

X

xi .

(375)

J ⊆Ik :|J |<∞ i∈J

Since M < ∞ and Mk ≤ M , we must have Mk < ∞ for all k ∈ N0 . But for every k ∈ N0 , by the
S
definition of Ik , Mk can only be finite if |Ik | < ∞. Thus, |Ik | < ∞ for all k ∈ N0 . Since I = k∈N Ik ,
we conclude that I is at most countable.
A PPENDIX I
P ROPERTIES OF S ET-VALUED M APPINGS
A set-valued mapping Φ : T → 2R

m

associates to each x ∈ T a set Φ(x) ⊆ Rm . Many properties of

ordinary mappings such as, e.g., measurability, can be extended to set-valued mappings. In this appendix,
we first briefly review properties of set-valued mappings and then state a result for set-valued mappings
needed in the existence proof of a measurable decoder in Section V-A.
Definition I.1. (Closed-valuedness of set-valued mappings) [51, Section 5] A set-valued mapping Φ : T →
m

2R

is closed-valued if, for every t ∈ T , the set Φ(t) is closed.

Definition I.2. (Inverse image of a set-valued mapping) [51, Section 14] For a set-valued mapping
m

Φ : T → 2R , the inverse image Φ−1 (A) of A ⊆ Rm is
Φ−1 (A) = {t ∈ T : Φ(t) ∩ A =
6 ∅}.

(376)

Definition I.3. (Measurable set-valued mapping) [51, Section 14] Let (T , S (T )) be a measurable space.
A set-valued mapping Φ : T → 2R
image Φ−1 (O) ∈ S (T ).

m

is S (T )-measurable if, for every open set O ⊆ Rm , the inverse

m

Lemma I.1. [51, Theorem 14.3] Let (T , S (T )) be a measurable space and Φ : T → 2R closed-valued.
Then, Φ is S (T )-measurable if and only if Φ−1 (K) ∈ S (T ) for all compact sets K ⊆ Rm .

m

Lemma I.2. [51, Corollary 14.6] Let (T , S (T )) be a measurable space and Φ : T → 2R

a S (T )-

measurable closed-valued mapping. Then, there exists a S (T )-measurable mapping f : Φ−1 (Rm ) → Rm
such that f (t) ∈ Φ(t) for all t ∈ Φ−1 (Rm ).
March 20, 2018

DRAFT

64

Definition I.4. (Normal integrand) [51, Definition 14.27] Let (T , S (T )) be a measurable space. An
extended real-valued function f : T × Rm → R ∪ {∞} ∪ {−∞} is a normal integrand with respect to
S (T ) if its epigraphical mapping
m

Sf : T → 2R

×R

(377)

t 7→ {(x, α) ∈ Rm × R : f (t, x) ≤ α}

(378)

is closed-valued and S (T )-measurable.
Lemma I.3. [51, Example 14.31] Let T = Rn×m × Rn and suppose that f : T × Rm → R ∪{∞}∪{−∞}
is continuous. Then, f is a normal integrand with respect to B(T ).
Lemma I.4. [51, Proposition 14.33] Let (T , S (T )) be a measurable space. An extended real-valued
function f : T × Rm → R ∪ {∞} ∪ {−∞} is a normal integrand with respect to S (T ) if and only if,
for every α ∈ R ∪ {∞} ∪ {−∞}, the level-set mapping
m

Lα : T → 2 R

(379)

t 7→ {x ∈ Rm : f (t, x) ≤ α}

(380)

is S (T )-measurable and closed-valued.
We can now state the result on set-valued mappings needed to prove the existence of a measurable
decoder in Section V-A.
Lemma I.5. Let (T , S (T )) be a measurable space, α ∈ R, and f : T × Rm → R ∪ {∞} ∪ {−∞}.

Suppose that f is a normal integrand with respect to S (T ) and K ⊆ Rm is compact and nonempty.
Then, the following properties hold.
i) The set-valued mapping
m

PK : T → 2R

t 7→ {x ∈ K : f (t, x) ≤ α}

(381)
(382)

is S (T )-measurable and closed-valued.
ii) PK−1 (Rm ) = {t ∈ T : ∃x ∈ K with f (t, x) ≤ α} ∈ S (T ).
iii) There exists a S (T )-measurable mapping
pK : PK−1 (Rm ) → Rm
t 7→ pK (t) ∈ PK (t).

March 20, 2018

(383)
(384)

DRAFT

65

Proof. We start with the proof of i). For each t ∈ T , we can write PK (t) = Lα (t) ∩ K, where Lα is
the S (T )-measurable closed-valued level-set mapping from Lemma I.4. Since Lα is closed-valued and
the intersection of a closed set with a compact set is closed, PK is closed-valued. To prove that PK is
S (T )-measurable it suffices, thanks to Lemma I.1, to show that PK−1 (A) ∈ S (T ) for all compact sets

A ⊆ Rm . To this end, let A ⊆ Rm be an arbitrary but fixed compact set. Since the intersection of two

compact sets is compact it follows that K ∩ A is compact. As Lα is S (T )-measurable and K ∩ A is

−1
−1
compact, L−1
α (K ∩ A) ∈ S (T ) by Lemma I.1. Therefore, as Lα (K ∩ A) = PK (A), we can conclude

that PK−1 (A) ∈ S (T ). Since A was arbitrary, this proves i). Now, S (T )-measurability of PK implies

PK−1 (Rm ) ∈ S (T ), and thereby ii). Finally, the existence of the S (T )-measurable mapping pK in iii)

follows from i) and Lemma I.2.
A PPENDIX J
P ROPERTIES OF S EQUENCES OF F UNCTIONS IN S EVERAL VARIABLES
In this appendix, we summarize properties of sequences of functions in several variables needed in
the proof of Theorem III.2. We start with a result that establishes a sufficient condition for uniform
convergence.
Theorem J.1. (Weierstrass M -test) [39, Theorem 7.10] Consider a sequence {fn }n∈N of functions
fn : Rk → R and suppose that there exists a sequence {Mn }n∈N of nonnegative real numbers Mn

such that
for all x ∈ Rk and n ∈ N

|fn (x)| ≤ Mn

and

P

n∈N Mn

(385)

< ∞. Then, the sequence {sn }n∈N of partial sums
sn =

n
X

fi

(386)

i=1

converges uniformly to a function f :

Rk

→ R.

Next, we state a result that allows us to interchange the order of summation and differentiation for
certain sequences of differentiable functions. We start with the corresponding statement for differentiable
functions in one variable.
Theorem J.2. [39, Theorem 7.17] Consider a sequence {fn }n∈N of functions fn : R → R, each of

which is differentiable on the closed interval [a, b] ⊆ R, such that limn→∞ fn (x0 ) exists and is finite for

March 20, 2018

DRAFT

66

at least one x0 ∈ [a, b]. Let fn0 denote the derivative of fn , n ∈ N. If {fn0 }n∈N converges uniformly on
[a, b], then {fn }n∈N converges uniformly on [a, b] to a function f : R → R satisfying
df (x)
= lim fn0 (x)
n→∞
dx

for all x ∈ [a, b].

(387)

Corollary J.1. Consider a sequence {fn }n∈N of functions fn : Rk → R converging uniformly to f : Rk →
R. Suppose that there exists an i ∈ {1, . . . , k} such that the partial derivatives ∂fn (x)/∂xi , denoted by

fn0 (x), exist and are finite for all x ∈ Rk and n ∈ N. If the sequence {fn0 }n∈N converges uniformly, then
∂f (x)
= lim fn0 (x)
n→∞
∂xi

for all x ∈ Rk .

(388)

Proof. Suppose that the sequence {fn0 }n∈N converges uniformly. Let x = (x1 . . . xk )T ∈ Rk be arbitrary
but fixed and denote by {gn }n∈N the sequence of functions gn (t) = fn ((x1 . . . xi−1 t xi+1 . . . xk )T ).

Since {fn }n∈N converges uniformly to f by assumption, and gn (xi ) = fn (x) for all n ∈ N, it follows

that
lim gn (xi ) = lim fn (x)

n→∞

n→∞

= f (x).

(389)
(390)

For each n ∈ N, let gn0 denote the derivative of gn . Since {fn0 }n∈N converges uniformly, so does {gn0 }n∈N .
In particular, {gn0 }n∈N converges uniformly on a closed interval [a, b] ⊆ R containing xi . Therefore,
Theorem J.2 implies that {gn }n∈N converges uniformly on [a, b] to a function g : R → R satisfying
dg(t)
= lim gn0 (t)
n→∞
dt

for all t ∈ [a, b].

(391)

But g(xi ) = f (x) and gn0 (xi ) = fn0 (x) for all n ∈ N, which implies ∂f (x)/∂xi = limn→∞ fn0 (x). As x
was arbitrary, this finishes the proof.
A PPENDIX K
P ROPERTIES OF R EAL A NALYTIC M APPINGS AND C ONSEQUENCES T HEREOF
In this appendix, we review material on real analytic mappings our strong converse established in
Sections IV and VII is based on. We start with the definition of a real analytic mapping.
Definition K.1. (Real analytic mapping) [52, Definition 2.2.1] Let U be an open set in Rm .
i) A function f : U → R is real analytic on U if, for each x ∈ U , f may be represented by a convergent
power series in some open neighborhood of x; if U = Rm , then f is real analytic.

ii) A mapping f : U → Rn , x 7→ (f1 (x) . . . fn (x))T is real analytic on U if every component fi ,
i = 1, . . . , n, is real analytic on U ; if U = Rm , then f is real analytic.

March 20, 2018

DRAFT

67

Lemma K.1. [52, Corollary 1.2.4] If a power series
f (x) =

∞
X
j=0

aj (x − α)j

(392)

converges on an open interval I ⊆ R, then f is real analytic on I .
Lemma K.2. [52, Proposition 2.2.2] Let U and V be open sets in Rm . If f : U → R is real analytic on

U and g : V → R is real analytic on V , then f + g and f · g are both real analytic on U ∩ V . Furthermore,

if g(x) 6= 0 for all x ∈ U ∩ V , then f /g is real analytic on U ∩ V .
Corollary K.1. All polynomials on Rm are real analytic.
Lemma K.3. [52, Proposition 2.2.3] Let U be an open set in Rm and suppose that f : U → R is real
analytic on U . Then, the partial derivatives—of arbitrary order—of f are real analytic on U .
Lemma K.4. [52, Proposition 2.2.8] Let U be an open set in Rm and V an open set in Rn . Suppose

that f : U → Rn is real analytic on U and g : V → Rk is real analytic on V . Then, for every x ∈ U with

f (x) ∈ V , there exists an open set W ⊆ Rm such that x ∈ W and (g ◦ f )|W : W → Rk is real analytic

on W .
Corollary K.2. If f : Rm → Rn and g : Rn → Rk are both real analytic, then g ◦ f : Rm → Rk is real
analytic.
Lemma K.5. [52, p. 83] A real analytic function f : Rm → R vanishes either identically or on a set of
Lebesgue measure zero.
The following definition extends the notion of a diffeomorphism of class C r [34, Definition 3.1.18]
to a real analytic diffeomorphism.
Definition K.2. (Real analytic diffeomorphism) Let U ⊆ Rn be an open set and ρ : U → Rn real analytic.

The mapping ρ is a real analytic diffeomorphism if V = ρ(U) is an open set and the inverse ρ−1 of ρ
exists on V and is real analytic on V .
Theorem K.1. [52, Theorem 2.5.1] Let U ⊆ Rm be open and f : U → Rm real analytic. If Jf (x0 ) > 0
for some x0 ∈ U , then f −1 exists on an open set V ⊆ Rm containing f (x0 ) and is real analytic on V .

Corollary K.3. Let U be an open set in Rm and suppose that f : U → Rm is real analytic on U . If there
exists an x0 ∈ U such that Jf (x0 ) > 0, then there exists an r > 0 such that f |Bm (x0 ,r) is a real analytic
diffeomorphism.

March 20, 2018

DRAFT

68

Proof. Suppose that there exists an x0 ∈ U such that Jf (x0 ) > 0. Since Jf (x0 ) > 0, Theorem K.1

implies that there exists an open set V ⊆ Rm such that f (x0 ) ∈ V , and f −1 exists on V and is real
analytic on V . Since V is open and f (x0 ) ∈ V , there must exist an ε > 0 such that Bm (f (x0 ), ε) ⊆ V . By
continuity of f , which follows from real analyticity, there must exist an r > 0 such that f (Bm (x0 , r)) ⊆
Bm (f (x0 ), ε) ⊆ V . We set W = f (Bm (x0 , r)). Summarizing, f is real analytic on Bm (x0 , r) and f −1

exists on W = f (Bm (x0 , r)) and is real analytic on W . It remains to show that W is open. This follows

by noting that thanks to W = (f −1 )−1 (Bm (x0 , r)), W is the inverse image of an open set under a real
analytic (and therefore continuous) mapping, and is hence open. We conclude that f |Bm (x0 ,r) is a real
analytic diffeomorphism.
Corollary K.4. Let U be an open set in Rm and suppose that f : U → Rn with n ≥ m is real analytic on
U . If there exists an x0 ∈ U such that Jf (x0 ) > 0, then there exists an r > 0 such that f is one-to-one

on Bm (x0 , r).
Proof. Suppose that there exists an x0 ∈ U such that Jf (x0 ) > 0. Then, Jf (x0 ) > 0 and n ≥ m imply
rank(Df (x0 )) = m. Thus, the n × m matrix Df (x0 ) has m linearly independent row vectors. Denote

the indices of m such linearly independent row vectors by {i1 , . . . , im } and consider the mapping
g : U → Rm

(393)

x 7→ (fi1 (x) . . . fim (x))T .

(394)

Since f is real analytic on U , so is g . Furthermore, rank(Dg(x0 )) = m and hence Jg(x0 ) > 0. Corollary
K.3 therefore implies the existence of an r > 0 such that g|Bm (x0 ,r) is a real analytic diffeomorphism. In
particular, g is one-to-one on Bm (x0 , r), which in turn implies that f is one-to-one on Bm (x0 , r).
Next, we show that the square root is a real analytic diffeomorphism on the set of positive real numbers.
Lemma K.6. The function

√

: R+ → R+ , x 7→

√

x, where R+ = {x ∈ R : x > 0}, is a real analytic

diffeomorphism.
Proof. The function (·)2 : R+ → R+ , x 7→ x2 is real analytic by Corollary K.1. Let y ∈ R+ be arbitrary
√
but fixed and set x = y . Since dx2 /dx = 2x > 0, Theorem K.1 implies that there exists an r > 0
√
such that the inverse of (·)2 , given by ·, exists on (y − r, y + r) and is real analytic on (y − r, y + r).
√
√
As y was arbitrary, it follows that · is real analytic on R+ . Finally, since (·)2 is the inverse of · and
p
√
R+ = R+ is open, · is a real analytic diffeomorphism.

March 20, 2018

DRAFT

69

Lemma K.7. If f : Rm → Rn is real analytic, so is Jf . In particular, Jf vanishes either identically or
on a set of Lebesgue measure zero.
p
Proof. Suppose that f : Rm → Rn is real analytic. Recall that Jf (x) = g(x), where g : Rm → R,


det(Df (x)(Df (x))T ) if n < m
g(x) =
(395)

det((Df (x))T Df (x)) else.
√
Lemmata K.2 and K.3 imply that g is real analytic. As · is real analytic on R+ by Lemma K.6, real
analyticity of Jf follows from Lemma K.4. Finally, as Jf is real analytic, it vanishes by Lemma K.5
either identically or on a set of Lebesgue measure zero.
We have the following important properties of real analytic mappings.
Lemma K.8. Let h : Rs → Rm be a real analytic mapping of s-dimensional Jacobian Jh 6≡ 0. Then, the
following properties hold.
i) The set O = {z ∈ Rs : Jh(z) > 0} is open and satisfies λs (Rs \O) = 0.

ii) For each set A ∈ B(Rs ) of positive Lebesgue measure there exists a set B ∈ B(Rs ) of positive
Lebesgue measure such that B ⊆ A and the mapping h|B is an embedding, i.e., Jh(z) > 0 for all
z ∈ B and h is one-to-one on B .

Proof. Openness of O follows from continuity of Jh, and Lemma K.7 together with Jh 6≡ 0 implies
λs (Rs \O) = 0. To prove ii), consider A ∈ B(Rs ) of positive Lebesgue measure. As λs (Rs \O) = 0,

with O from i), it follows that λs (A ∩ O) > 0. Thus, by Lemma H.7, there must exist a z0 ∈ A ∩ O
such that
λs (Bs (z0 , r) ∩ A ∩ O) > 0

for all r > 0.

(396)

Since Jh(z0 ) > 0, which follows from z0 ∈ O, Corollary K.4 implies that there must exist an r0 > 0
such that h is one-to-one on Bs (z0 , r0 ). Setting B = Bs (z0 , r0 ) ∩ A ∩ O concludes the proof.
Definition K.3. (Real analytic submanifold) [52, Definition 2.7.1] A subset M ⊆ Rn is an m-dimensional
real analytic submanifold of Rn if, for each y ∈ M, there exist an open set U ⊆ Rm and a real analytic

immersion f : U → Rn such that y ∈ f (U) and open subsets of U are mapped onto relatively open
subsets in M. Here, a subset W ⊆ M is called relatively open in M if there exists an open set V ⊆ Rn

such that W = V ∩ M.

March 20, 2018

DRAFT

70

Lemma K.9. Let M ⊆ Rs be a t-dimensional real analytic submanifold of Rs and z0 ∈ M. Then, there
exist a real analytic embedding ζ : Rt → Rs and an η > 0 such that
ζ(0) = z0 ,

(397)


Bs (z0 , η) ∩ M ⊆ ζ Rt ,

(398)



and ζ Rt is relatively open in M, i.e., there exists an open set V ⊆ Rs such that ζ Rt = V ∩ M.
Proof. Since M ⊆ Rs is a t-dimensional real analytic submanifold of Rs , Definition K.3 implies the
existence of an open set U ⊆ Rt and a real analytic immersion ξ : U → Rs that maps open subsets of U
onto relatively open subsets in M and satisfies z0 = ξ(u0 ) with u0 ∈ U . As ξ is an immersion,
rank(Dξ(v)) = t

for all v ∈ U.

(399)

Since U is open and u0 ∈ U , there exists a ρ > 0 such that Bt (u0 , ρ) ⊆ U , which implies in turn

ξ Bt (u0 , ρ) ⊆ ξ(U).

(400)

Using Corollary K.4 and Jξ(u0 ) > 0 (recall that ξ is an immersion) we may choose ρ sufficiently small
for ξ to be one-to-one on Bt (u0 , ρ). As ξ(Bt (u0 , ρ)) is relatively open in M, there must exist an open

set V ⊆ Rs such that


ξ Bt (u0 , ρ) = V ∩ M.

(401)

Now, as V is open and z0 = ξ(u0 ) ∈ V , we can find an η > 0 such that Bs (z0 , η) ⊆ V , which, together
with (401), yields

Bs (z0 , η) ∩ M ⊆ ξ Bt (u0 , ρ) .

(402)

Let κ : Rt → Bt (0, ρ) be the real analytic diffeomorphism constructed in Lemma K.10 below and set
ζ : Rt → Rs

(403)

v 7→ ξ(κ(v) + u0 ).

(404)

The mapping ζ is a real analytic mapping by Lemmata K.2 and K.4. Clearly, ζ is one-to-one on Rt as κ is

a diffeomorphism and ξ is one-to-one on Bt (u0 , ρ). Since ζ Rt = ξ(Bt (u0 , ρ)), (402) establishes (398)

and (401) proves that ζ Rt is relatively open in M. Finally, (397) follows from ζ(0) = ξ(κ(0) + u0 ) =
ξ(u0 ) = z0 , where in the second equality we used (408) in Lemma K.10 below. It remains to show that
ζ is an immersion, which is effected by proving that rank(Dζ(v)) = t for all v ∈ Rt . The chain rule

implies
Dζ(v) = (Dξ)(κ(v) + u0 )Dκ(v)

March 20, 2018

for all v ∈ Rt .

(405)

DRAFT

71

It now follows
i) from (410) in Lemma K.10 below that rank(Dκ(v)) = t for all v ∈ Rt , and

ii) from (399) and κ(v) + u0 ∈ Bt (u0 , ρ) ⊆ U that rank((Dξ)(κ(v) + u0 )) = t for all v ∈ Rt .
Applying Lemma K.12 to (Dξ)(κ(v) + u0 ) ∈ Rs×t and Dκ(v) ∈ Rt×t , and using i) and ii) above yields
rank(Dζ(v)) ≥ t for all v ∈ Rt , which in turn implies Jζ(v) > 0 for all v ∈ Rt , thereby concluding

the proof.
Lemma K.10. For ρ > 0, the mapping
κ : Rk → Bk (0, ρ)

(406)

x 7→ p

(407)

is a real analytic diffeomorphism on Rk satisfying

ρx

1 + kxk22

κ(0) = 0,

(408)

κ(Rk ) = Bk (0, ρ),
rank(Dκ(x)) = k

(409)

for all x ∈ Rk .

(410)

Proof. It follows immediately from the definition of κ that κ(0) = 0. The mapping κ is real analytic
thanks to Lemmata K.2, K.4, and K.6. Now, consider the mapping
σ : Bk (0, ρ) → Rk
y 7→ p

ρ2

(411)
y
− kyk22

.

(412)

Again, σ is real analytic thanks to Lemmata K.2, K.4, and K.6. Since (κ◦σ)(y) = y for all y ∈ Bk (0, ρ),
it follows that κ(Rk ) = Bk (0, ρ). Moreover, as (σ ◦ κ)(x) = x for all x ∈ Rk , σ is the inverse of κ,

which establishes that κ is a real analytic diffeomorphism on Rk . Finally, since (σ ◦ κ)(x) = x for all
x ∈ Rk , the chain rule implies Ik = D(σ ◦ κ)(x) = (Dσ)(κ(x))Dκ(x) for all x ∈ Rk , which yields

(410).
Proposition K.1. [52, Proposition 2.7.3] Let M ⊆ Rn . The following statements are equivalent:
i) M is a m-dimensional real analytic submanifold of Rn .

ii) For each z ∈ M there exist an open set U ⊆ Rn with z ∈ U , a real analytic diffeomorphism
ρ : U → Rn , and a m-dimensional linear subspace L ⊆ Rn , such that
ρ(M ∩ U) = ρ(U) ∩ L.

March 20, 2018

(413)

DRAFT

72

Proposition K.1 allows us to state the following sufficient condition on the inverse image of a point
under a real analytic function to result in a real analytic submanifold.
Lemma K.11. Let ψ : Rs → R be a real analytic function, y0 ∈ ψ(Rs ), and set My0 = ψ −1 ({y0 }).
Suppose that Jψ(z) > 0 for all z ∈ My0 . Then, My0 is a (s − 1)-dimensional real analytic submanifold

of Rs .

Proof. We may assume, w.l.o.g., that y0 = 0 (if y0 6= 0, we set ψ̃(z) = ψ(z) − y0 and prove the lemma
with ψ̃ in place of ψ , noting that My0 = ψ̃ −1 ({0}) and J ψ̃(z) = Jψ(z) for all z ∈ Rs .) The proof

is effected by verifying that M0 satisfies Statement ii) of Proposition K.1. Let z0 ∈ M0 be arbitrary
but fixed and set aT
1 = Dψ(z0 ). Since Jψ(z0 ) > 0 by assumption, we must have a1 6= 0. Choose
a2 , . . . , as ∈ Rs such that A = (a1 . . . as )T is a regular matrix and consider the mapping
ρ : Rs → Rs
T
z 7→ ψ(z) aT
2 z . . . as z

(414)
T

.

(415)

Note that Dρ(z0 ) = A. Since rank(A) = s by construction, Jρ(z0 ) > 0. It therefore follows from
Corollary K.3 that there exists an r > 0 such that ρ|Bs (z0 ,r) is a real analytic diffeomorphism. Finally,
we can write
ρ(M0 ∩ Bs (z0 , r)) = ρ({z ∈ Bs (z0 , r) : ψ(z) = 0})

(416)

= ρ({z ∈ Bs (z0 , r) : eT
1 ρ(z) = 0})

(417)

= ρ(Bs (z0 , r)) ∩ L,

(418)

where (416) follows from M0 = ψ −1 ({0}), (417) is by (415), and in (418) we set L = {(w1 . . . ws )T ∈
Rs : w1 = 0}.

Lemma K.12. [37, Property (c), Chapter 0.4.5] If A ∈ Rm×k and B ∈ Rk×n , then
rank(AB) ≥ rank(A) + rank(B) − k.

(419)

R EFERENCES
[1] G. Alberti, H. Bölcskei, C. De Lellis, G. Koliander, and E. Riegler, “Lossless linear analog compression,” in Proc. IEEE
Int. Symp. Inf. Theory, 2016, pp. 2789–2793.
[2] D. L. Donoho and P. B. Stark, “Uncertainty principles and signal recovery,” SIAM J. Appl. Math., vol. 49, no. 3, pp.
906–931, Jun. 1989.
[3] D. L. Donoho, “Compressed sensing,” IEEE Trans. Inf. Theory, vol. 52, no. 4, pp. 1289–1306, Apr. 2006.

March 20, 2018

DRAFT

73

[4] E. J. Candès, J. Romberg, and T. Tao, “Robust uncertainty principles: Exact signal reconstruction from highly incomplete
frequency information,” IEEE Trans. Inf. Theory, vol. 52, no. 2, pp. 489–509, Feb. 2006.
[5] E. J. Candès, Y. C. Eldar, D. Needell, and P. Randall, “Compressed sensing with coherent and redundant dictionaries,”
Appl. Comp. Harm. Anal., vol. 31, no. 1, pp. 59–73, Jul. 2011.
[6] P. Kuppinger, G. Durisi, and H. Bölcskei, “Uncertainty relations and sparse signal recovery for pairs of general signal
sets,” IEEE Trans. Inf. Theory, vol. 58, no. 1, pp. 263–277, Jan. 2012.
[7] R. Gribonval and M. Nielsen, “Sparse representations in unions of bases,” IEEE Trans. Inf. Theory, vol. 49, no. 12, pp.
3320–3325, Jan. 2003.
[8] M. Elad and A. M. Bruckstein, “A generalized uncertainty principle and sparse representation in pairs of bases,” IEEE
Trans. Inf. Theory, vol. 48, no. 9, pp. 2558–2567, Sep. 2002.
[9] D. L. Donoho and M. Elad, “Optimally sparse representation in general (nonorthogonal) dictionaries via `1 minimization,”
in Proc. Natl. Acad. Sci. USA, vol. 100, no. 5, 2003, pp. 2197–2002.
[10] J. A. Tropp, “Greed is good: Algorithmic results for sparse approximation,” IEEE Trans. Inf. Theory, vol. 50, no. 10, pp.
2231–2242, Oct. 2004.
[11] L. R. Welch, “Lower bounds on the maximum cross correlation of signals,” IEEE Trans. Inf. Theory, vol. 20, no. 3, pp.
397–399, May 1974.
[12] E. J. Candès and T. Tao, “Near-optimal signal recovery from random projections: Universal encoding strategies?” IEEE
Trans. Inf. Theory, vol. 52, no. 12, pp. 5406–5425, Dec. 2006.
[13] J. A. Tropp, “On the conditioning of random subdictionaries,” Appl. Comp. Harm. Anal., vol. 25, pp. 1–24, 2008.
[14] G. Pope, A. Bracher, and C. Studer, “Probabilistic recovery guarantees for sparsely corrupted signals,” IEEE Trans. Inf.
Theory, vol. 59, no. 5, pp. 3104–3116, May 2013.
[15] R. G. Baraniuk, M. Davenport, R. DeVore, and M. Wakin, “A simple proof of the restricted isometry property for random
matrices,” Constructive Approximation, vol. 28, no. 3, pp. 253–263, Dec. 2008.
[16] Y. Wu and S. Verdú, “Rényi information dimension: Fundamental limits of almost lossless analog compression,” IEEE
Trans. Inf. Theory, vol. 56, no. 8, pp. 3721–3748, Aug. 2010.
[17] ——, “Optimal phase transitions in compressed sensing,” IEEE Trans. Inf. Theory, vol. 58, no. 10, pp. 6241–6263, Oct.
2012.
[18] D. Stotz, E. Riegler, E. Agustsson, and H. Bölcskei, “Almost lossless analog signal separation and probabilistic uncertainty
relations,” IEEE Trans. Inf. Theory, vol. 63, no. 9, pp. 5445–5460, Sep. 2017.
[19] G. Koliander, G. Pichler, E. Riegler, and F. Hlawatsch, “Entropy and source coding for integer-dimensional singular random
variables,” IEEE Trans. Inf. Theory, vol. 62, no. 11, pp. 6124–6154, 2016.
[20] Y. C. Eldar and M. Mishali, “Robust recovery of signals from a structured union of subspaces,” IEEE Trans. Inf. Theory,
vol. 55, no. 11, pp. 5302–5316, Nov. 2009.
[21] R. G. Baraniuk, V. Cevher, M. F. Duarte, and C. Hegde, “Model-based compressive sensing,” IEEE Trans. Inf. Theory,
vol. 56, no. 4, pp. 1982–2001, Apr. 2010.
[22] P. Feng and Y. Bresler, “Spectrum-blind minimum-rate sampling and reconstruction of multiband signals,” in Proc. IEEE
Int. Conf. Acoust. Speech Signal Process., 1996, pp. 1688–1691.
[23] 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, Mar. 2009.
[24] R. G. Baraniuk and M. B. Wakin, “Random projections of smooth manifolds,” Found. Comput. Math., vol. 9, no. 1, pp.
51–77, Feb 2009.

March 20, 2018

DRAFT

74

[25] M. Stojnic, F. Parvaresh, and B. Hassibi, “On the reconstruction of block-sparse signals with an optimal number of
measurements,” IEEE Trans. Signal Process., vol. 57, no. 8, pp. 3075–3085, Aug. 2009.
[26] Y. C. Eldar, P. Kuppinger, and H. Bölcskei, “Block-sparse signals: Uncertainty relations and efficient recovery,” IEEE
Trans. Signal Process., vol. 58, no. 6, Jun. 2010.
[27] J. Huang and T. Zhang, “The benefit of group sparsity,” Ann. Stat., vol. 38, no. 4, pp. 1978–2004, 2010.
[28] E. J. Candès and B. Recht, “Exact matrix completion via convex optimization,” Found. Comput. Math., vol. 9, no. 6, pp.
717–772, 2009.
[29] E. J. Candès and Y. Plan, “Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random
measurements,” IEEE Trans. Inf. Theory, vol. 4, no. 57, pp. 2342–2359, Apr. 2011.
[30] E. Riegler, D. Stotz, and H. Bölcskei, “Information-theoretic limits of matrix completion,” in Proc. IEEE Int. Symp. Inf.
Theory, Jun. 2015, pp. 1836–1840.
[31] J. C. Robinson, Dimensions, Embeddings, and Attractors.
[32] K. Falconer, Fractal Geometry, 1st ed.

Cambridge, NY: Cambridge University Press, 2011.

New York, NY: Wiley, 1990.

[33] T. Kawabata and A. Dembo, “The rate-distortion dimension of sets and measures,” IEEE Trans. Inf. Theory, vol. 40, no. 5,
pp. 1564–1572, Sep. 1994.
[34] H. Federer, Geometric Measure Theory.

New York, NY: Springer, 1969.

[35] P. Mattila, Geometry of Sets and Measures in Euclidean Space: Fractals and Rectifiability. Cambridge, UK: Cambridge
Univ. Press, 1999.
[36] S. G. Krantz and H. R. Parks, Geometric Integration Theory.
[37] R. A. Horn and C. R. Johnson, Matrix Analysis, 2nd ed.

Princeton, NJ: Birkhäuser, 2008.

Cambridge, U.K.: Cambridge Univ. Press, 2013.

[38] K. Stromberg, “An elementary proof of Steinhaus’s theorem,” in Proc. of the American Mathematical Society, vol. 36,
no. 1, 1976, p. 308.
[39] W. Rudin, Principles of Mathematical Analysis, 3rd ed.
[40] J. M. Lee, Introduction to Smooth Manifolds, 2nd ed.

New York, NY: McGraw-Hill, 1976.
New York, NY: Springer, 2013.

[41] G. Folland, Real Analysis: Modern Techniques and Their Applications, 2nd ed.
[42] H. H. Sohrab, Basic Real Analysis, 2nd ed.

New York, NY: Wiley, 2013.

New York, NY: Birkhäuser, 2014.

[43] L. Ambrosio, N. Fusco, and D. Pallara, Functions of Bounded Variation and Free Discontinuity Problems.

New York,

NY: Oxford Univ. Press, 2000.
[44] R. G. Bartle, The Elements of Integration and Lebesgue Measure.
[45] T. Tao, An Introduction to Measure Theory.

New York, NY: Wiley, 1995.

Providence RI: AMS, 2011.

[46] L. Gasiński and N. S. Papageorgiou, Exercises in Analysis-Part 2: Nonlinear Analysis, ser. Problem Books in Mathematics.
Cham, Switzerland: Springer, 2016.
[47] T.-W. Ma, Classical Analysis on Normed Spaces.

Singapore: World Scientific Pub. Co., 1995.

[48] F. W. Warner, Foundations of Differentiable Manifolds and Lie Groups.
[49] C. H. Edwards, Advanced Calculus of Several Variables.

New York, NY: Springer, 1971.

New York, NY: Academic Press, Inc., 1973.

[50] A. Sard, “The measure of the critical values of differentiable maps,” Bull. Amer. Math. Soc., vol. 48, no. 12, pp. 883–890,
1942.
[51] R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, 3rd ed.

Heidelberg, Germany: Springer, 2009.

[52] S. G. Krantz and H. R. Parks, A Primer of Real Analytic Functions, 2nd ed.

March 20, 2018

Basel, Switzerland: Birkhäuser, 2002.

DRAFT

