Entropy numbers of finite-dimensional

Lorentz space embeddings

Joscha Prochno∗, Mathias Sonnleitner∗,†and Jan Vybı́ral‡
arXiv:2404.06058v2 [[Link]] 14 Oct 2024

October 15, 2024

Dedicated to the memory of Albrecht Pietsch.

Abstract
The sequence of entropy numbers quantifies the degree of compactness of a lin-
ear operator acting between quasi-Banach spaces. We determine the asymptotic
behavior of entropy numbers in the case of natural embeddings between finite-
dimensional Lorentz spaces ℓnp,q in all regimes; our results are sharp up to constants.
This generalizes classical results obtained by Schütt (in the case of Banach spaces)
and Edmunds and Triebel, Kühn, as well as Guédon and Litvak (in the case of
quasi-Banach spaces) for entropy numbers of identities between finte-dimensional
Lebesgue sequence spaces ℓnp . We employ techniques such as interpolation, volume
comparison as well as techniques from sparse approximation and combinatorial ar-
guments. Further, we characterize entropy numbers of embeddings between finite-
dimensional symmetric quasi-Banach spaces in terms of best s-term approximation
numbers.
Keywords. Entropy numbers, Lorentz spaces, natural embeddings, quasi-Banach
spaces, sparse approximation
MSC 2020. Primary: 47B06, 46B06 Secondary: 41A46, 46B07, 46A16

1 Introduction and main result

The fundamental notion of covering numbers and with it Pietsch’s inverse concept of
entropy numbers [45] quantify to what extent a bounded linear operator is compact.
∗
Faculty of Computer Science and Mathematics, University of Passau, Dr.-Hans-Kapfinger-Str. 30,
94032 Passau, Germany, [Link]@[Link]
†
Institute of Mathematical Stochastics, University of Münster, Orléans-Ring 10, 48149 Münster, Ger-
many, [Link]@[Link]
‡
Department of Mathematics, Faculty of Nuclear Sciences and Physical Engineering, Czech Technical
University, Trojanova 13, 12000 Praha, Czech Republic, [Link]@[Link]

1
They are important elements in both pure and applied mathematics, for instance,
in the geometry of Banach spaces [8, 12, 24, 34], signal processing and compressed
sensing [10, 17, 22], or the theory of random processes [38, 39, 52]. In particular,
they are useful measures for complexity in approximation theory [13, 20] and a
powerful tool in the flourishing field of statistical machine learning, explaining, for
instance, the effect of the choice of kernel function on the generalization performance
of support vector machines [54] (see also [15]). The origin of these notions can in
fact be traced back to Kolmogorov, who, motivated by ideas and definitions in
information theory, introduced the so-called ε-entropy already in the 1950s [33].
From the point of view of geometric functional analysis, entropy numbers are
quite well understood in a number of fundamental and important situations, but
before presenting explicit examples, let us further motivate the interest in them by
looking at their relation to a specific sequence of singular numbers (s-numbers) of
operators and the problem of optimal recovery. Via a famous inequality of Carl
[12], entropy numbers are related to the most important scales of s-numbers and,
specifically, can provide lower bounds on the so-called Gelfand numbers, which
bound from below the error of optimal reconstructions using linear measurements
(see, e.g., [44] for background information on the related field of information-based
complexity); one should note that, in general, it is significantly more delicate to
determine the asymptotic behavior of Gelfand numbers than of entropy numbers.
Let n ∈ N and consider continuous linear functionals L1 , . . . , Ln on a quasi-normed
space F . The problem is to approximate in the quasi-norm of a quasi-normed space
G into which F continuously embeds an unknown element f from the unit ball of
F purely based on the measurements L1 (f ), . . . , Ln (f ). Then the worst-case error
of any such approximation A(f ) = ϕ(L1 (f ), . . . , Ln (f )), where ϕ : Rn → G is an
algorithm using the linear information, is bounded from below by the n-th Gelfand
number of the natural identity id : F → G (see, e.g., [21, Proposition 1.2]). In the
context of compressed sensing, where one is interested in recovery of (nearly) sparse
signals, this has been used by Donoho [17] in the case of the embedding id : ℓnp → ℓn2
with the claimed extension of Carl’s inequality to quasi-Banach spaces only proven
later by Hinrichs, Kolleck, and Vybı́ral [27]. The lower bound for the associated
Gelfand numbers has been proven earlier by Foucart, Pajor, Rauhut, and Ullrich
[21].
Of specific interest, as indicated above, are often finite-dimensional embeddings,
also because they can serve as a discrete model for operators between function
spaces, such as differential operators between Sobolev spaces [20, 34]. Arguably
most fundamental in this respect are the natural embeddings of Lebesgue sequence
spaces, i.e., of id : ℓnp → ℓnq , and in this situation the behavior of entropy numbers is
in fact well understood. Indeed, in the case of Banach spaces, this is a classical result
of Schütt [49] (who actually obtained more general results for entropy numbers of

2
diagonal operators between symmetric Banach sequence spaces), while its extension
to the quasi-Banach space setting has been obtained by Edmunds and Triebel [20,
Sec. 3.2.2], Kühn [36], and independently by Guédon and Litvak [26]; we refer to
the survey [35] by Kossaczká and Vybı́ral (see also [43, Remark 3]) for an account
on the history of this result.
Before we state the result, let us recall that the k-th (dyadic) entropy number
of a continuous linear map T : X → Y between quasi-Banach spaces with unit balls
BX and BY , respectively, is given by
( k−1
2[
)
ek (T : X → Y ) := inf ε > 0 : ∃ y1 , . . . , y2k−1 ∈ Y : T (BX ) ⊂ (yi + εBY ) .
i=1

Moreover, entropy numbers are almost s-numbers and satisfy

1. (norming property) 21−1/p kT k ≤ e1 (T ) ≤ kT k, whenever Y is a p-Banach
space,
2. (monotonicity) e1 (T ) ≥ e2 (T ) ≥ · · · ≥ 0,
3. (sub-multiplicativity) en+m−1 (ST ) ≤ en (S)·em (T ) for n, m ∈ N and S : Y → Z
is a linear and continuous map to a quasi-Banach space Z.
These properties can be deduced, e.g., from [20, Lemma [Link]] and its proof; see
also Section 2 for more information on quasi- and p-Banach spaces.
For a sequence x = (xi )i∈N ∈ RN , we denote
 ∞ 1/p
 X

 |xi |p
: 0 < p < ∞,
kxkp := i=1


max |xi | : p = ∞,
i∈N

and write ℓp := {x ∈ RN : kxkp < ∞} and ℓnp for (Rn , k · kp ).

We now present the asymptotics for the entropy numbers of embeddings between
ℓp -spaces. For 0 < p ≤ r ≤ ∞, one has


 1 : k ≤ log n,

 1/p−1/r
ek (id : ℓnp → ℓnr ) ≍ log(n/k+1)
k : log n ≤ k ≤ n, (1)



2−k/n n1/r−1/p : k ≥ n,

and if 0 < r ≤ p ≤ ∞, then

ek (id : ℓnp → ℓnr ) ≍ 2−k/n n1/r−1/p . (2)

Here, the relation ≍ denotes equivalence up to implicit constants independent of k

and n (while they may depend on the parameters p or r), and we interpret 1/∞ = 0;
for the non-commutative counterpart to the previous result, we refer to [28].

3
 As mentioned above, for various reasons it is of interest to understand the asymp-
totic behavior of entropy numbers of finite-dimensional embeddings. In the case of
embeddings between Orlicz sequence spaces, an asymptotic characterization similar
to the one presented before was obtained by Kaewtem and Netrusov [31, Theorem
4.2].
The main aim of our paper is to give a complete asymptotic characterization of
entropy numbers of embeddings of Lorentz sequence spaces. Before we come to that,
we introduce the necessary notation and provide some historical remarks. Lorentz
spaces of measurable functions were introduced by G. G. Lorentz [41, 42] and since
then they have become an indisposable tool in mathematical analysis [51]. Lorentz
spaces arise from Lebesgue spaces via interpolation and we shall give more details on
this later in Section 2.1. Moreover, beyond being studied in the functional analysis
literature, Lorentz spaces also play fundamental roles in applied mathematics, for
instance, in signal processing [11]. In particular, the weak ℓp -spaces ℓnp,∞ are used
in the theory of compressed sensing [22].
The theory of Lorentz function spaces includes as a special case also the Lorentz
sequence spaces, which we consider in this paper. We give their definition using the
notion of non-increasing rearrangement. If x = (xi )i∈N ∈ RN is an infinite sequence,
we define its non-increasing rearrangement x∗ = (x∗i )i∈N , where x∗i := inf{λ >
0 : |{k ∈ N : |xk | > λ}| ≤ i − 1}. For 0 < p, u ≤ ∞ the Lorentz ℓp,u -quasi-norm of
x = (xi )i∈N ∈ RN is defined as

kxkp,u := ki1/p−1/u x∗i ku ,

(see, e.g., [25, (1.4.9)] or [37, Lemma 2.9] for the fact that this is a quasi-norm).
Lorentz sequence spaces (at least in the case 1 ≤ u ≤ p) appear already in [40,
Section I.3.a] as an example of Banach spaces with a symmetric basis. We shall
write ℓp,u := {x ∈ RN : kxkp,u < ∞} for the corresponding Lorentz sequence space
and ℓnp,u for the space (Rn , k · kp,u ). The finite-dimensional unit ball is then given
n := {x ∈ Rn : kxk
by Bp,u p,u ≤ 1}.
For general background on Lorentz sequence spaces, we refer the reader to [3, 14]
and the original work of Lorentz [42]. From the point of view of geometric functional
analysis, Lorentz sequence spaces form a generalization of ℓp -spaces belonging to
the important class of 1-symmetric Banach spaces. Various analytic and geometric
properties of Lorentz spaces have been studied in the local theory of Banach spaces
and geometric functional analysis (see, e.g., [4, 16, 23, 29, 32, 37, 46, 47, 50]).
Let us now elaborate on the relation of Lorentz spaces and entropy numbers,
bringing both concepts together. Using finite-dimensional Lorentz space embed-
dings, Edmunds and Netrusov [19] disproved a conjecture regarding the interpo-
lation behavior of entropy numbers. More precisely, they showed that entropy
numbers are not compatible with respect to interpolation on both sides, while in-

4
terpolation on either side is indeed possible. Let us give some explanation (we refer
to Section 2.1 below for more details). Given pairs (X0 , X1 ) and (Y0 , Y1 ) of Banach
spaces which are each embedded into a common Hausdorff topological space, a lin-
ear operator T : X0 + X1 → Y0 + Y1 , and parameters θ ∈ (0, 1) and 1 ≤ u ≤ ∞, it
was disproved in [19] that there is C ∈ (0, ∞) such that, for all k0 , k1 ∈ N,

ek0 +k1 −1 (T : (X0 , X1 )θ,u → (Y0 , Y1 )θ,u ) ≤ Cek1−θ

0
(T : X0 → Y0 )eθk1 (T : X1 → Y1 ).

A counterexample is provided by a diagonal operator between Lorentz spaces with

logarithmically decaying diagonal.
Having mentioned or referred to a number of results concerning entropy numbers
and/or Lorentz spaces, as it turns out, until now, there was no complete picture
regarding entropy numbers for Lorentz space embeddings. The main contribution
of this work is to close this gap with the following theorem.

Theorem 1. Let 0 < p, q, u, v ≤ ∞ and n ∈ N. Define the quantity

k
ℓ(k, n) := , log n ≤ k ≤ n.
log(n/k + 1)

Then the following asymptotics hold:

(0) For p 6= q < ∞, we have

ek (id : ℓnp,u → ℓnq,v ) ≍ ek (id : ℓnp → ℓnq ), k ∈ N.

(I) For q < p = ∞, we have

ek (id : ℓn∞,u → ℓnq,v ) ≍ 2−k/n n1/q (log n)−1/u , k ∈ N.

(II) For p < q = ∞, we have




1

: k ≤ log n,
ek (id : ℓnp,u → ℓn∞,v ) ≍ ℓ(k, n)−1/p log(ℓ(k, n))1/v : log n ≤ k ≤ n,



2−k/n n−1/p (log n)1/v : k ≥ n.

(III) For p = q < ∞, we have

(III.1) whenever u ≤ v

ek (id : ℓnp,u → ℓnp,v ) ≍ 2−k/n , k ∈ N,

(III.2) and whenever u > v


log(n/k + 1)1/v−1/u : k ≤ n,
ek (id : ℓnp,u → ℓnp,v ) ≍
2−k/n : k ≥ n.

5
(IV) For p = q = ∞, we have
(IV.1) whenever u ≥ v

ek (id : ℓn∞,u → ℓn∞,v ) ≍ 2−k/n (log n)1/v−1/u , k ∈ N,

(IV.2) and whenever u < v



 1 : k ≤ log n,


ek (id : ℓn∞,u → ℓn∞,v ) ≍ log(ℓ(k, n))1/v−1/u : log n ≤ k ≤ n,



2−k/n (log n)1/v−1/u : k ≥ n.

All implicit constants are independent of k and n, but may depend on p, u, q, or v.

Theorem 1 shows that, asymptotically, entropy numbers of embeddings between

Lorentz spaces exhibit a rich behavior with additional logarithms appearing if p = q
or if p or q are infinite.

Remark 1. Let us elaborate on previously known results in order to contextualize

our contribution.

1. The case p = u and q = v reduces to id : ℓnp → ℓnq , see (1) and (2) above.
2. The case 0 < p 6= q < ∞ was already stated in [16, Eq. (29)] and also in
[19], where the authors actually refer to [18]. Since we could not locate a
proof in the literature, we provide one ourselves using interpolation. Note
that Kaewtem [30, Corollary 4.3] proved the special case of p < q and k ≥ n.
3. The case 0 < p = q = v < ∞ and u = ∞ was proven in [16, Theorem 10].

The following result provides asymptotics for the norm of the natural embedding
between Lorentz sequence spaces. Using the equivalence between e1 (T ) and kT k
given through the norming property of entropy numbers, it coincides with the choice
of k = 1 in Theorem 1. As we shall need it in the proof of Theorem 1, we state (and
prove) it separately. Here and in what follows, we write (x)+ := max{0, x} for the
positive part of x ∈ R.

Proposition 2. Let n ∈ N and 0 < p, q, u, v ≤ ∞. We have



 n(1/q−1/p)+ : p 6= q < ∞,




n1/q (log n)−1/u : q < p = ∞,
k id : ℓnp,u → ℓnq,v k ≍


1

: p < q = ∞,


(log n)(1/v−1/u)+ : p = q,

where the implicit constants are independent of the dimension n.

6
 In the remainder of this work, we shall present the proof of Theorem 1 and gen-
eralize techniques developed for ℓp -spaces to our Lorentz space setting. As a general
rule, bounds for k ≥ n and bounds with no case distinction on k are proven with
volume techniques, prepared in Section 2 more generally for embeddings between
quasi-Banach spaces. Upper bounds in the remaining cases are proven via sparse
approximation, and monotonicity arguments. Whenever convenient, we shall use
interpolation (see Section 2.1). Finally, in Section 5 we state a characterization of
entropy numbers of embeddings between finite-dimensional symmetric quasi-Banach
spaces in terms of best s-term approximation numbers and present an alternative
proof of Theorem 1.
Notation. Given sequences (ak )k∈N and (bk )k∈N of non-negative real numbers,
we write ak . bk if there exists an implicit constant C ∈ (0, ∞) such that ak ≤ Cbk
for all k ∈ N. Similarly, we use ak & bk if bk . ak and ak ≍ bk if additionally
ak . bk holds. In the following, implicit constants will never depend on k and n
and may depend on parameters p, q, u or v. With respect to this notation and due
to log 1 = 0, we want to point out that sometimes it may be necessary to replace
log n by log(n + 1). We omit this for the sake of readability.

2 Entropy numbers of embeddings between

quasi-Banach spaces
Here and in the following, we provide some background information on quasi-normed
spaces. Let X be a linear space. A mapping k · k : X → [0, ∞) is called a quasi-norm
if it satisfies the axioms of a norm except that the triangle inequality is weakened
to
kx + yk ≤ C(kxk + kyk) for all x, y ∈ X, (3)

where C ≥ 1 is some constant. If (3) is replaced by

kx + ykp ≤ kxkp + kykp for all x, y ∈ X (4)

for some 0 < p ≤ 1, then k · k is called a p-norm. It follows from Hölder’s inequality
that every p-norm is a quasi-norm with constant C = 21/p−1 . In fact, by the Aoki-
Rolewicz theorem [2, 48] every quasi-norm with constant C ≥ 1 is equivalent to a
p-norm with 0 < p ≤ 1 chosen to satisfy C = 21/p−1 . We say that two quasi-norms
k · kX and k · kY on X are equivalent if and only if there exist c, C ∈ (0, ∞) such
that
ckxkX ≤ kxkY ≤ CkxkX for all x ∈ X.

Note that in this case we may replace k · kX by k · kY in entropy estimates at the

cost of multiplicative constants. Whenever we endow X with a quasi-norm (p-norm)

7
and X is complete with respect to the induced distance, it is called a quasi-Banach
space (p-Banach space). It is useful to note that every p-Banach space is also an
r-Banach space whenever 0 < r < p ≤ 1, simply because (ap + bp )1/p ≤ (ar + br )1/r
for a, b ≥ 0.
A basis {e1 , e2 , . . . } of a quasi-Banach space (X, k · kX ) is called 1-unconditional
P∞
(or just unconditional) if, for all x = i=1 ai ei ∈ X and all sequences of signs
ε1 , ε2 , · · · ∈ {−1, 1} it holds that
∞
X ∞
X
ai ei = εi ai ei
X X
i=1 i=1

and 1-symmetric (or just symmetric) if, moreover, for all permutations π of N it
holds that
∞
X X∞
ai ei = εi aπ(i) ei .
X X
i=1 i=1
The associated fundamental function is defined by
n
X
ϕX (n) := ei , n ∈ N.
X
i=1

We shall say that a quasi-Banach space is symmetric if it admits a symmetric basis.

In the following, we shall study entropy numbers of embeddings between n-
dimensional symmetric quasi-Banach spaces. For this purpose we will need the
following monotonicity/lattice property which also holds in the case of an uncondi-
tional basis. Its proof was kindly provided to us by G. Schechtman.

Lemma 3. For every quasi-Banach space X with an unconditional basis {ei }i∈N ,
any n ∈ N and all scalars a1 , . . . , an and b1 , . . . , bn satisfying |bi | ≤ |ai | for all
1 ≤ i ≤ n, we have
Xn X n
bi ei ≤ KX ai ei ,
X X
i=1 i=1
where KX ≥ 1 depends only on the quasi-norm constant.

Proof. By the Aoki-Rolewicz theorem there exists 0 < p ≤ 1 and a corresponding p-

norm k·k on X which is equivalent to k·kX . For n ∈ N let a1 , . . . , an and b1 , . . . , bn be
scalars such that |bi | ≤ |ai | for all 1 ≤ i ≤ n. Because of the quasi-norm equivalence,
it is sufficient to show that
n
X n
X
bi ei ≤ Cp ai ei , (5)
i=1 i=1

where Cp ∈ (0, ∞) depends only on p. For any i ∈ {1, . . . , n}, let us write
∞
X
|bi | = |ai | δij 2−j
j=1

8
for some suitable sequence δij ∈ {0, 1}, j ∈ N. Then, for all j ∈ N,
n
X 1 1 1/p X
n
2−j ai δij ei ≤ 2−j + ai ei ,
2p 2p
i=1 i=1

where we used that δij = 12 εij + 21 for some εij ∈ {−1, 1} and that k · k can also be
assumed to be unconditional (see e.g. the proof of [34, Proposition 1.c.5]). Therefore,
we obtain
n
X ∞
X n
X
bi ei = 2−j ai δij ei
i=1 j=1 i=1
1−p X
∞ 1/p X
n
−jp
≤2 p 2 ai ei ,
j=1 i=1

 1/p
1 2
which yields (5) with Cp := 2 2p −1 . This completes the proof.

Remark 2. If X is a Banach space, then Lemma 3 holds with KX = 1. This follows

from [5, Theorem 2] or [1, Proposition 3.1.3]. We further remark that Lemma 3 is
closely related to the so-called lattice property of (quasi-)Banach spaces, which is
widely used in functional analysis, see, e.g., [9, Section 13.1] or [6, (P2) in Definition
1.1.1].

Let n ∈ N and X, Y be n-dimensional quasi-Banach spaces with normalized

symmetric bases {ei }ni=1 and {fi }ni=1 , respectively. We will study the behavior of
the entropy numbers of the embedding
X
n  Xn
id : X → Y, id xi ei = xi f i , (x1 , . . . , xn ) ∈ Rn .
i=1 i=1

For this we will use the following elementary lemma relating the operator norm of
the natural identity between ℓn∞ and a symmetric quasi-Banach space X with the
fundamental function of the space.

Lemma 4. Let n ∈ N and X be an n-dimensional quasi-Banach space with a

symmetric basis {ei }ni=1 . Then

ϕX (n) ≤ k id : ℓn∞ → Xk ≤ KX ϕX (n),

where we identify ℓn∞ = (span{e1 , . . . , en }, k · k∞ ) and KX ≥ 1 is as in Lemma 3.

Proof. By Lemma 3 it holds that

n
X n
X
k id : ℓn∞ → Xk = sup xi ei ≤ KX ei ,
n
x∈B∞ X X
i=1 i=1

and for the lower bound we specify x = (1, . . . , 1).

9
 The following proposition taken from [30, Theorem 4.2] generalizes [49, Lemma
4] to quasi-Banach spaces.

Proposition 5. Let n ∈ N and X, Y be n-dimensional quasi-Banach spaces with

quasi-norm constants CX , CY ≥ 1 and normalized symmetric bases {ei }ni=1 and
{fi }ni=1 , respectively. Then

ϕY (n)
ek (id : X → Y ) ≍ 2−k/n , k ≥ n, (6)
ϕX (n)

where the implicit constants depend only on max{CX , CY }.

Proof. In order to derive the statement from [30, Theorem 4.2], which is in terms of
p-Banach spaces, we note that by the Aoki-Rolewicz theorem, we find 0 < p, q ≤ 1,
a p-norm ||| · |||p and a q-norm ||| · |||q equivalent to k · kX and k · kY , respectively.
Then both ||| · |||p and ||| · |||q are r-norms with r = min{p, q} depending only on
max{CX , CY } and we can apply [30, Theorem 4.2]. Switching back to the original
quasi-norms incurs additional implicit constants depending only on r.

We note that the proof of [30, Theorem 4.2] implicitly uses the statement of
Lemma 3. Moreover, it essentially involves the following asymptotic inequality
from [18, Section 4, Lemma 3 (ii)] which states that

en (id : X → ℓn∞ ) . ϕX (n)−1 , (7)

where X is as in the assumption of Proposition 5 and the implicit constant depends

only on CX . Note that in the proof of (7) the authors of [18] crucially use symmetry.
We can use (7) to prove the following generalization of Schütt’s result [49, Lemma
3] to quasi-Banach spaces, which was used in [49] to prove (6) in the case of Banach
spaces.

Proposition 6. Let n ∈ N and X an n-dimensional quasi-Banach space with nor-

malized symmetric basis {ei }ni=1 . Then

ϕX (n)−1 ≍ vol(BX )1/n ,

where vol denotes Lebesgue measure on Rn , which is identified with span{e1 , . . . , en }.

The implicit constants depend only on the quasi-norm constant.

Proposition 6 allows us to rewrite the bounds in Proposition 5 to

ek (id : X → Y ) ≍ 2−k/n rv(X, Y ), k ≥ n, (8)

where
vol(BX )1/n
rv(X, Y ) := .
vol(BY )1/n

10
Here, we identify BX with id(BX ) ⊂ Y and Y with Rn using a suitable basis. Note
that rv(X, Y ) is the normalized ratio of volumes of the unit balls of X and Y ,
respectively, and that it differs from the notion of volume ratio, used in the local
theory of Banach spaces.
For the proof of Proposition 6, we shall use volume comparison arguments and
volume bounds such as the following lower bound on entropy numbers by the nor-
malized ratio of volumes.

Lemma 7. Let n ∈ N and X, Y be n-dimensional quasi-Banach spaces. Then, for

any k ∈ N,
k−1
ek (id : X → Y ) ≥ 2− n rv(X, Y ).

Proof. Suppose that BX is covered by 2k−1 balls of radius r > 0 in the space Y for
some k ∈ N. Then a union bound immediately gives

vol(BX ) ≤ 2k−1 r n vol(BY ).

Thus, r ≥ 2−(k−1)/n rv(X, Y ), and the result follows.

Proof of Proposition 6. In the following, ℓn∞ is taken with respect to the basis
{ei }ni=1 . We conclude from Lemma 7 and the inequality (7) that
1
vol(BX )1/n = rv(X, ℓn∞ ) ≤ 2en (id : X → ℓn∞ ) . ϕX (n)−1 ,
2
which completes the proof of the lower bound.
For the upper bound, we shall use a volume comparison argument. Consider the
vectors Pn
j=1 εj ej
yε = , ε = (εj )nj=1 ∈ {−1, 1}n .
ϕX (n)
Then kyε kX = 1 and kyε − yε′ k∞ ≥ ϕX2(n) for each ε 6= ε′ . Therefore, the balls
n , ε ∈ {−1, 1}n , are disjoint, and if z ∈ y + ϕ (n)−1 B n for some
yε + ϕX (n)−1 B∞ ε X ∞
ε, then, by Lemma 4,

kzkX ≤ CX (kyε kX + kz − yε kX ) ≤ CX (1 + k id : ℓ∞ → Xkkz − yε k∞ ) ≤ cX ,

where cX = CX (1 + KX ) ≤ 2CX KX with CX being the quasi-norm constant of

n , ε ∈ {−1, 1}n ,
k · kX and KX as in Lemma 4. So the disjoint balls yε + ϕX (n)−1 B∞
are contained in cX BX . Hence, a comparison of volumes shows that

2n ϕX (n)−n vol(B∞
n
) ≤ cnX vol(BX ),

which is equivalent to

ϕX (n)−1 (4/cX ) ≤ vol(BX )1/n .

This concludes the proof.

11
 We show that under some additional assumption, (8) may in fact be extended
to all k’s.

Proposition 8. Let n ∈ N and X, Y be n-dimensional quasi-Banach spaces with

symmetric bases. If
k id : X → Y k . rv(X, Y ), (9)

then
ek (id : X → Y ) ≍ 2−k/n rv(X, Y ), k ∈ N.

The implicit constants do not depend on k or n.

Proof. If k ≥ n, this follows from (8). If k ≤ n, then by monotonicity

ek (id : X → Y ) ≤ k id : X → Y k ≤ 2 · 2−k/n k id : X → Y k.

Together with (9), this gives the upper bound. Finally, the lower bound follows
from Lemma 7.

Note that we always have

k id : X → Y k ≥ rv(X, Y ). (10)

In particular, we can replace (9) by k id : X → Y k ≍ rv(X, Y ). For convenience of

the reader, we provide a proof.

Proof of (10). Write

k id : X → Y k = sup kykY = inf{r > 0 : BX ⊂ rBY }.

kykX ≤1

If BX ⊂ rBY for some r > 0, then we have vol(BX ) ≤ r n vol(BY ), that is,
rv(X, Y ) ≤ r. So if k id : X → Y k ≤ r, then rv(X, Y ) ≤ r + ε for every ε > 0,
which proves the statement.

Remark 3. For completeness we remark that the conclusion of Proposition 8 under

(9) can be shown directly for all k ∈ N. For this, note that by [27, Lemma 2.1], for
an n-dimensional p-Banach space X and for k ∈ N, we have

ek (id : X → X) ≤ 41/p 2−(k−1)/n . (11)

By factorization and (11), we have for an n-dimensional p-Banach space X and a

quasi-Banach space Y that

ek (id : X → Y ) ≤ ek (id : X → X)k id : X → Y k

k−1
≤ 41/p 2− n k id : X → Y k.

Using (9), Lemma 7 and the Aoki-Rolewicz theorem completes the proof.

12
2.1 Interpolation
We already mentioned that the Lorentz sequence space ℓp,u arises from real inter-
polation of ℓp -spaces. For convenience of the reader, we give more details on this
procedure and refer to [7] for more information.
Let (X0 , X1 ) be a pair of quasi-normed spaces such that there is a quasi-normed
space X , in which both spaces are continuously embedded. Let X0 + X1 be the
space of all x ∈ X with x = x0 + x1 for xi ∈ Xi , i ∈ {0, 1}. Define for x ∈ X0 + X1
the K-functional by

K(t, x) := inf kx0 kX0 + tkx1 kX1 : x = x0 + x1 with xi ∈ Xi , i ∈ {0, 1} , t > 0.

Let 0 < θ < 1 and 0 < u ≤ ∞. Then (X0 , X1 )θ,u is the space of all x ∈ X0 + X1
such that  R 
 ∞ (t−θ K(t, x))u dt 1/u : u < ∞,
0 t
kxk(θ,u) :=
sup t−θ K(t, x) : u = ∞,
t>0

is finite. The space is endowed with the quasi-norm k · kθ,u . Note that if one of the
spaces X0 or X1 is continuously embedded into the other, they automatically form
a pair as above. This is the case with ℓp -spaces and also ℓp,u -spaces. The following
result is taken from [7, Theorem 5.3.1].

Proposition 9. Let 0 < p0 , p1 , u0 , u1 , p, u ≤ ∞. If p0 6= p1 and 1/p = (1 − θ)/p0 +

θ/p1 for some θ ∈ (0, 1), then

(ℓp0 ,u0 , ℓp1 ,u1 )θ,u = ℓp,u .

Moreover, the quasi-norms k · k(θ,u) and k · kp,u are equivalent. This statement
remains true if p0 = p1 = p, provided that 1/u = (1 − θ)/u0 + θ/u1 .

Entropy numbers behave well with respect to interpolation on either side, but
not on both (as we mentioned before). The following result is adapted from [20,
Theorem 1.3.2].

Proposition 10. Let Y be a quasi-Banach space and (X0 , X1 ) be a pair as above,

θ ∈ (0, 1) and 0 < u ≤ ∞.
1. If T : Y → X0 ∩ X1 is linear and continuous with respect to kxk = max{kxkX0 , kxkX1 },
x ∈ X0 ∩ X1 , then, for all k0 , k1 ∈ N, we have

ek0 +k1 −1 (T : Y → (X0 , X1 )θ,u ) ≤ Ce1−θ θ

k0 (T : Y → X0 )ek1 (T : Y → X1 ).

2. If T : X0 + X1 → Y is linear such that its restrictions to X0 and X1 are

continuous, then, for all k0 , k1 ∈ N, we have

ek0 +k1 −1 (T : (X0 , X1 )θ,u → Y ) ≤ Ce1−θ θ

k0 (T : X0 → Y )ek1 (T : X1 → Y ).

13
Here, the constant C ∈ (0, ∞) depends only on the quasi-norm constants of X0 and
X1 .

We shall apply the statements of this section to prove case (0) in Theorem 1.
Note that with regard to Proposition 9, the restriction to the first n coordinates
does not change results and that it is sufficient to consider equivalent quasi-norms.

3 The size of the unit ball of a Lorentz space

As a preparation for the proof of Theorem 1, we prove asymptotics for the volume
of the unit ball of a Lorentz space (Lemma 11) and for its size when measured in the
quasi-norm of another Lorentz space (Proposition 2); such results are of independent
interest.
The fundamental function of ℓp,u with 0 < p, u ≤ ∞ satisfies

n1/p : p < ∞,
ϕℓp,u (n) ≍ (12)
(log n)1/u : p = ∞.

Combined with Proposition 6 this yields the following asymptotics for the volume
of Lorentz balls. The case p < ∞ can be found in [16, Theorem 7] and is proven
using interpolation methods. In the case of p = 1, the volume of Bp,u n can be

computed explicitly and precise asymptotics become available, see [16, Theorem 5]
and [29, Corollary 1].

Lemma 11. For all 0 < p, u ≤ ∞, we have


n−1/p : p < ∞,
n 1/n
vol(Bp,u ) ≍
(log n)−1/u : p = ∞.

For convenience of the reader we give a direct proof in the case of p = ∞.

Proof of Lemma 11 for p = ∞ and u < ∞. Let us denote

n
X
Hn := k−1 . (13)
k=1

−1/u
Then Hn grows logarithmically in n and Hn · [−1, 1]n ⊂ B∞,u
n , which gives the

lower bound.
To show the upper bound, we fix some c > 1 and denote by K ≤ n the maximal
n , where |x | > cH −1/u . Then
number of indices of x ∈ B∞,u j n

n
X K
X
1≥ k−1 (x∗k )u ≥ (x∗K )u k−1 ≥ cu · Hn−1 · HK .
k=1 k=1

14
Letting c := 61/u and using the elementary estimate log n ≤ Hn ≤ 3 log n, we obtain
√
K ≤ n.
n n

We can now cover B∞,u by the union of K cubes having sides [−1, 1] in exactly
−1/u −1/u
K coordinates and [−cHn , cHn ] in the remaining ones. By volume compari-
son, we obtain
 
n n
vol(B∞,u ) ≤ vol([−1, 1]K × [−cHn−1/u , cHn−1/u ]n−K )
K
and
 1/n
n n
vol(B∞,u )1/n ≤ · 2K/n · (2cHn−1/u )1−K/n
K
≤ 2 · 2 · (2cHn−1/u ) · (2c)−K/n · HnK/(un)
≤ 8cHn−1/u · HnK/(un) .

K/(un) √
Finally, we observe that Hn is bounded due to K ≤ n.

We shall need the following decay estimates for the largest entries. These are
essentially sharp as shown by x = 1 for p < ∞ and x = ((log i)−1/u )ni=1 for p = ∞.

Lemma 12. Let n ∈ N. For all x ∈ Rn and i ∈ {1, . . . , n}, we have


i−1/p : p < ∞,
∗
xi . kxkp,u
(log i)−1/u : p = ∞.

Proof. If p = u = ∞, then this trivially holds. If p < u = ∞, then

x∗i = i−1/p i1/p x∗i ≤ i−1/p max j 1/p x∗j = i−1/p kxkp,∞ .
1≤j≤n

If u < ∞, then we proceed as follows. There are z1 , . . . , zn ≥ 0 such that (x∗i )u =

Pn
ℓ=i zℓ for every i ∈ {1, . . . , n}. If p < ∞, then for β = u/p,

n
X n
X n
X ℓ
X n
X n
X
iβ zℓ ≤ zℓ ℓβ . zℓ j β−1 = j β−1 zℓ = kxkup,u .
ℓ=i ℓ=1 ℓ=1 j=1 j=1 ℓ=j

If p = ∞, i.e., β = 0, then this remains valid if we replace iβ and ℓβ by log i and

log ℓ, respectively.

Next, we prove Proposition 2. We shall use that for 0 < p ≤ ∞ and 0 < u ≤
v ≤ ∞ there exists a constant cp,u,v ∈ (0, ∞) such that

kxkp,v ≤ cp,u,v kxkp,u x ∈ Rn . (14)

This is a well known fact, see [6, Proposition 4.2] and also [16, Proposition 6] and
its proof.

15
Proof of Proposition 2. In what follows, we let x ∈ Rn .

Case 1. Let p 6= q < ∞. The lower bound follows by choosing x = e1 ∈ Bp,u n if

n with x =
P n
p < q and x/kxkp,u ∈ Bp,u i=1 ei if q < p.
To show the upper bound, we observe that by (14) it is enough to consider only
u = ∞. In this case, we estimate
n
X n
X
kxkvq,v = v/q−1
i ·i−v/p
·iv/p
· (x∗i )v ≤ max j v/p
(x∗j )v · iv/q−v/p−1
1≤j≤n
i=1 i=1

. kxkvp,∞ ·n v(1/q−1/p)+

if v < ∞ and

kxkq,∞ = max j 1/q x∗j = max j 1/q−1/p · j 1/p x∗j ≤ kxkp,∞ · nv(1/q−1/p)+
1≤j≤n 1≤j≤n

if v = ∞.

Case 2. Let q < p = ∞ and 0 < u, v ≤ ∞. The lower bound is obtained by choosing
P
n
x/kxk∞,u ∈ B∞,u with x := ni=1 ei . For the upper bound, we first assume that
v < ∞. Then, by Lemma 12,
n
X n
X
kxkvq,v = i v/q−1
(x∗i )v ≤ kxk∞,u iv/q−1 (log i)−v/u .
i=1 i=1

To complete the proof of the upper bound in this case, we use the known asymptotics
n
X
iλ−1 (log i)β ≍ nλ (log n)β ,
i=1

valid for λ > 0 and β ∈ R with implicit constants independent of n. Now assume
that v = ∞. Then

kxkq,∞ = max i1/q x∗i ≤ kxk∞,u max i1/q (log i)−1/u . n1/q (log n)−1/u kxk∞,u .
1≤i≤n 1≤i≤n

Case 3. Let p < q = ∞ and 0 < u, v ≤ ∞. The lower bound is obtained by choosing
n . First, let v < ∞. Then
the vector x = e1 ∈ Bp,u
n
X n
X
kxkv∞,v = i−1
(x∗i )v ≤ kxkp,u i−v/p−1 . kxkp,u .
i=1 i=1

Now let v = ∞. Then, by the estimate in (14), we have kxk∞ . kxk∞,v . This
completes the proof of the upper bound.
Case 4. Let p = q ≤ ∞. This case splits into two cases.
u ≤ v: Then we conclude the upper bound from (14), while the lower bound
n .
simply follows by choosing x = e1 ∈ Bp,u

16
 u > v: Then we deduce from Hölder’s inequality applied with conjugate indices
r := u/v > 1 and r ∗ := u/(u − v) that
X
n 1/v
kxkp,v = (k1/p x∗k )v k−v/u · k−1+v/u
k=1
X
n 1/u  X
n (u−v)/uv
≤ (k1/p x∗k )u k−1 k−1 ,
k=1 k=1

where the first factor on the right-hand side is just kxkp,u , while the second fac-
1/v−1/u
tor equals Hn with Hn having been introduced in (13). Therefore, Hölder’s
inequality immediately gives

k id : ℓnp,u → ℓnp,v k ≤ sup kxkp,u Hn1/v−1/u = Hn1/v−1/u .

kxkp,u ≤1

For the corresponding lower bound, we just observe that x := (k−1/p )nk=1 satisfies
1/u 1/v −1/u
kxkp,u = Hn as well as kxkp,v = Hn , and so, because kHn xkp,u = 1, it follows
that
k id : ℓnp,u → ℓnp,v k ≥ kHn−1/u xkp,v = Hn1/v−1/u .

Thus, we have

k id : ℓnp,u → ℓnp,v k = Hn1/v−1/u ≍ (log n)1/v−1/u ,

where the latter asymptotic follows directly from the definition of Hn .

4 Proof of Theorem 1
We first give a proof of the case 0 < p 6= q < ∞, where we follow the general
strategy set out in [16, Section 4]. Essentially, it relies on interpolation properties
of Lorentz spaces and entropy numbers, as detailed in Section 2.1.

Proof of case (0). We only present the proof in the case 0 < p < q < ∞ and note
that the case 0 < q < p < ∞ can be proven in a similar way. For the upper bound,
let 0 < r < p < s < q < ∞ with 1s = 12 ( p1 + 1q ) and 1p = 21 ( 1r + 1s ). Then, by
Proposition 9,
ℓnp,u = (ℓnr , ℓns ) 1 ,u and ℓnq,v = (ℓns , ℓn∞ )θ,v
2

s
with θ = 1 − q ∈ (0, 1). Therefore, by Proposition 10, for every k ∈ N,

e4k−3 (id : ℓnp,u → ℓnq,v ) . e2k−1 (id : ℓnr → ℓnq,v )1/2 e2k−1 (id : ℓns → ℓnq,v )1/2
. ek (id : ℓnr → ℓns )(1−θ)/2 ek (id : ℓnr → ℓn∞ )θ/2
× ek (id : ℓns → ℓns )(1−θ)/2 ek (id : ℓns → ℓn∞ )θ/2 .

17
Using the upper bounds in (1), we see that

e4k−3 (id : ℓnp,u → ℓnq,v ) . 2−k/n n1/q−1/p ,

and using monotonicity completes the proof of the upper bound.

For the lower bound in the case 0 < p < q < ∞ choose p2 , q2 such that 0 <
p < p2 < q < q2 < ∞, as well as p11 = 12 ( 1p + p12 ) and q11 = 12 ( 1q + q12 ) such that
0 < p < p1 < p2 < q < q1 < q2 < ∞. Then, by Proposition 9,

ℓnp1 = (ℓnp,u , ℓnp2 ) 1 ,p1 and ℓnq1 = (ℓnq,v , ℓnq2 ) 1 ,q1 .

2 2

Again by Proposition 10, we have, for every k ∈ N, that

e4k−3 (id : ℓnp1 → ℓnq1 ) . e2k−1 (id : ℓnp,u → ℓnq1 )1/2 e2k−1 (id : ℓnp2 → ℓnq1 )1/2
. ek (id : ℓnp,u → ℓnq,v )1/4 ek (id : ℓnp,u → ℓnq2 )1/4
× ek (id : ℓnp2 → ℓnq,v )1/4 ek (id : ℓnp2 → ℓnq2 )1/4 .

Using the upper bound we just proved, we obtain

e4k−3 (id : ℓnp1 → ℓnq1 ) . ek (id : ℓnp,u → ℓnq,v )1/4 ek (id : ℓnp → ℓnq2 )1/4
× ek (id : ℓnp2 → ℓnq )1/4 ek (id : ℓnp2 → ℓnq2 )1/4

since p 6= q2 and q 6= p2 . Plugging in the upper bounds from (1) and using mono-
tonicity gives the lower bound.

We now give the proofs of the cases (I), (II), (III) and (IV).
We first treat the cases which follow from volume estimates.

Proof of (I), (III.1), (IV.1) for k ∈ N and of (II), (III.2), (IV.2) for k ≥ n. In all of
these cases Theorem 1 follows for k ≥ n from Proposition 5 and (12).
For the proof of (I), (III.1) and (IV.1) also for k ≤ n, we note that by Proposi-
tion 2 and Lemma 11 in each case it holds that

k id : ℓnp,u → ℓnq,v k ≍ rv(ℓnp,u , ℓnq,v ).

Therefore, Lemma 7 and Proposition 8 imply

ek (id : ℓnp,u → ℓnq,v ) ≍ 2−k/n rv(ℓnp,u , ℓnq,v ), k ∈ N.

We now prove the bounds for small k ≤ n in the remaining cases (II), (III.2), and
(IV.2). To this end, we will employ [18, Section 4, Theorem 2]. Roughly speaking,

18
 it characterizes the behavior of ek (id : X → Y ), k < n/2, for n-dimensional quasi-
Banach spaces X and Y with common symmetric basis {b1 , . . . , bn } in terms of
n
X
u(X, Y, s) = sup u(x, Y, s) = sup min{x∗s , x∗i }bi , (15)
x∈BX x∈BX Y
i=1

where s = s(n, k) ∈ N is defined by

k k
<s ≤1+ . (16)
log(n/k + 1) log(n/k + 1)

The characterization via u(X, Y, s) has been applied, for instance, by Kaewtem [30],
and Mayer and Ullrich [43], who proved results for entropy numbers of embeddings
between mixed-norm spaces, but apparently has been largely overlooked. For ex-
ample, Kühn’s lower bound [36] for ek (id : ℓnp → ℓnq ) with 0 < p < q ≤ ∞ is a direct
P
consequence (choose x = s−1/p si=1 ei in the supremum). The quantity u(X, Y, s)
is related to the best s-term approximation in the worst case. The latter concept
is traditionally used in upper bounds for log n ≤ k ≤ n and will be discussed in
Section 5.
We need the following formulation of [18, Section 4, Theorem 2].

Proposition 13. Let n ∈ N. For k < n/2, we have

ek (id : ℓnp,u → ℓnq,v ) ≍ u(ℓnp,u , ℓnq,v , s),

where s ∈ N is as in (16) and the implicit constants are independent of k and n.

We shall deduce the following result; note that s < n/ log(3) if k < n/2.

Proposition 14. Let 0 < p, q, u, v ≤ ∞ and s ∈ N such that 1 ≤ s < n/ log(3).

Then we have the following asymptotics:
(II) For p < q = ∞, we have

u(ℓnp,u , ℓn∞,v , s) ≍ s−1/p log(s)1/v .

(III.2) For p = q < ∞ and u > v, we have

u(ℓnp,u , ℓnp,v , s) ≍ log(n/s + 1)1/v−1/u .

(IV.2) For p = q = ∞ and u < v, we have

u(ℓn∞,u , ℓn∞,v , s) ≍ log(s + 1)1/v−1/u .

All implicit constants are independent of s, n ∈ N.

19
 n be such that x∗ > · · · > x∗ > 0. It is easy to
Proof. Let 0 < p, u ≤ ∞ and x ∈ Bp,u 1 n
see that the supremum remains the same if we only consider such x’s. For v < ∞,
we have
n
X s
X n
X
v
min{x∗s , x∗i }ei = (x∗s )v v/q−1
i + (x∗i )v iv/q−1 , (17)
q,v
i=1 i=1 i=s+1

whereas for v = ∞, we have

n
X
min{x∗s , x∗i }ei = max{x∗s s1/q , sup x∗i i1/q }.
q,∞ s+1≤i≤n
i=1

We will use Lemma 12, i.e., that


i−1/p : p < ∞,
x∗i . (18)
(log i)−1/u : p = ∞.

We distinguish several cases and carry out the computations only for v < ∞
(they are in fact easier for v = ∞).
Case (II)
Let p < q = ∞. If v < ∞, we estimate (17) by
s
X n
X n
X
(x∗s )v −1
i + (x∗i )v i−1 .s −v/p
log s + i−v/p−1 . s−v/p log s.
i=1 i=s+1 i=s+1

The upper bound for v = ∞ is a direct consequence of (18).

P
The lower bound is achieved by x = s−1/p si=1 ei , which by (12) satisfies

kxkp,u ≍ 1 and kxk∞,v ≍ s−1/p (log s)1/v .

Case (III.2)
Let 0 < p = q < ∞ and 0 < v < u ≤ ∞. We first prove the upper bound.
By means of (17) and (18) we have
n
X
u(ℓnp,u , ℓnp,v , s)v . 1 + (x∗i )v iv/p−1 . (19)
i=s+1

v
In the case of u < ∞, we use Hölder’s inequality with β = p − uv , ϕ = u/v > 1 and
ϕ∗ = u/(u − v), to obtain
n
X  X
n 1/ϕ  X n  ∗
∗ 1/ϕ
(x∗i )v iβ i−β iv/p−1 ≤ ∗ vϕ βϕ
(xi ) i · i(−β+v/p−1)ϕ
i=s+1 i=s+1 i=s+1
 Xn v/u  X n (u−v)/u
= (x∗i )u iu/p−1 · i−1 (20)
i=s+1 i=s+1

. log(n/s)1−v/u .

20
For u = ∞, we use x∗i . i−1/p and obtain
n
X
(x∗i )v iv/p−1 . log(n/s).
i=s+1

Combined with (19), this shows that

u(ℓnp,u , ℓnp,v , s) . log(n/s)1/v−1/u .

P P
The lower bound is achieved by x = s−1/p si=1 ei + ni=s+1 i−1/p ei , which satisfies

kxkp,u ≍ (1 + log(n/s))1/u and kxkp,v ≍ (1 + log(n/s))1/v .

Case (IV.2)
Let p = q = ∞ and 0 < u < v ≤ ∞. We proceed as in the proof of case (II) and
replace s−1/p by (log s)−1/u .

We can now complete the proof of Theorem 1 using Propositions 13 and 14.

Proof of (II), (III.2) and (IV.2) for k ≤ n. We combine Propositions 13 and 14 to

obtain the asymptotics of
ek (id : ℓnp,u → ℓnq,v )
k
for k < n/2 in terms of s ≍ log(n/k+1) . For n/2 ≤ k ≤ n, we use monotonicity. All
implicit constants are independent of n and k. Further note that, for k ≤ log n, we
have
log n
s≤ ≤ C,
log(1 + n/ log n)
where C ∈ (0, ∞) is some absolute constant. Therefore, after looking at Proposi-
tion 2, monotonicity yields

ek (id : ℓnp,u → ℓnq,v ) ≍ k id : ℓnp,u → ℓnq,v k.

Case (II) (p < ∞ and q = ∞)

For k < n/2, we have

ek (id : ℓnp,u → ℓn∞,v ) ≍ s−1/p log(s),

which proves the theorem in this case.

Case (III.2) (p = q < ∞ and u > v)
For k < n/2, we have

ek (id : ℓnp,u → ℓn∞,v ) ≍ log(n/s + 1)1/v−1/u ≍ log(n/k + 1)1/v−1/u ,

which proves the theorem in this case.

Case (IV.2) (p = q = ∞ and u < v)
For k < n/2, we have

ek (id : ℓnp,u → ℓn∞,v ) ≍ log(s + 1)1/v−1/u ,

which proves the theorem in this case.

21
5 Sparse Approximation
Since the proof of Theorem 1 in the cases (II), (III.2), and (IV.2) in the intermediate
range log n ≤ k ≤ n, and in particular Proposition 13 (taken from [18, Section 4,
Theorem 2]), is very much related to ideas of sparse approximation, we provide
some background and an alternative proof.
In general, for positive integers s ≤ n the error of best s-term approximation of
a vector x ∈ Rn in a quasi-norm k · kY is given by

σs (x)Y = inf kx − zkY : z ∈ Rn with |{i : zi 6= 0}| ≤ s .

It measures (with respect to k · kY ) how far x is from being s-sparse, i.e., how
far from being supported on s coordinates. In contrast, for obtaining the quantity
u(x, Y, s) in (15) only truncation of the entries of x is permitted. However, assuming
symmetry, both quantities are suitable for characterizing the behavior of entropy
numbers.
Proposition 15. Let n ∈ N and let X, Y be n-dimensional quasi-Banach spaces
with quasi-norm constants CX , CY ≥ 1 and a common symmetric basis {e1 , . . . , en }.
For k < n/2, we have

ek (id : X → Y ) ≍ sup σs (x)Y ,

x∈BX
k
where s ∈ N is the minimal integer with s > log(n/k+1) and the implicit con-
stants depends only on max{CX , CY }. Note that sparsity is with respect to the
basis {e1 , . . . , en }.

Proof. By [18, Section 4, Theorem 2] the statement holds with supx∈BX σs (x)Y
replaced by u(X, Y, s). We will show that in fact for s < n/2

sup σs (x)Y ≍ u(X, Y, s), (21)

x∈BX

where the implicit constants are independent of s. Then it remains to note that for
k < n/2 we also have s < n/2. Using symmetry and Lemma 3, the upper bound in
(21) follows from
n
X n
X
σs (x)Y = x∗i ei ≤ KY min{x∗s , x∗i }ei = KY u(x, Y, s),
i=s+1 Y i=1 Y
Pn
and taking the supremum over x = i=1 xi ei ∈ BX .
For the lower bound in (21) we write
s
X 2s
X n
X
u(x, Y, 2s) = x∗2s ei + x∗2s ei + x∗i ei
i=1 i=s+1 i=2s+1 Y

 X
s n
X 
≤ CY x∗2s ei + KY x∗i ei ≤ 2 CY KY σs (x)Y ,
 
i=1 Y i=s+1 Y

22
take the supremum, and note that by [18, Section 4, Lemma 4 (i)] we have, for
s < n/2,
u(X, Y, 2s) & u(X, Y, s) (22)

with an implicit constant only depending on max{CX , CY }.

Remark 4. Proposition 15 can be seen as a complement to Theorem 3.1 in [53]

by Temlyakov who proves an upper bound on the entropy numbers under polyno-
mial decay assumption on the best s-term approximation numbers uniformly over
compact sets.

We note the following consequence of (21) and (22), which shows that best
s-term approximation numbers exhibit regular decay.

Corollary 16. Assume X and Y are as in Proposition 15. Then, for s < n/2,

sup σ2s (x)Y ≍ sup σs (x)Y ,

x∈BX x∈BX

where the implicit constants depend only on max{CX , CY }.

In the following, we will give the above mentioned alternative proof of Theorem 1.
Since x∗s+1 = σs (x)∞ holds, Lorentz quasi-norms can be understood via best s-term
approximation. We believe the following estimates to be of independent interest.
The case u = ∞ and v = q > p is for example covered in [22, Prop. 2.11].

Proposition 17. Let 0 < p, q, u, v ≤ ∞ and s ≤ n be positive integers and assume

that x ∈ Rn . For q = ∞, we have

s−1/p (log s)1/v : p < ∞,
σs (x)∞,v . kxkp,u
(log s)1/v−1/u : p = ∞ and u < v,

and, for p = q < ∞ and v < u, we have

σs (x)p,v . kxkp,u (log(n/s) + 1)1/v−1/u .

All implicit constants are independent of n and s.

For the proof of Proposition 17 we need the following.

Lemma 18. Let s ≤ n be positive integers. Then the following estimates hold:
(i) For λ > 0, we have
n
X
(i − s)−1 i−λ . s−λ log s.
i=s+1

23
(ii) For λ > 1, we have
n
X
(i − s)−1 (log i)−λ . (log s)−λ+1 .
i=s+1

The implicit constants depend only on the parameter λ.

We postpone its proof and first use it to deduce Proposition 17.

Proof of Proposition 17. We first prove the case q = ∞. If v = ∞, then we obtain

from Lemma 12 that

s−1/p : p < ∞,
σs (x)∞ = x∗s+1 . (23)
(log s)−1/u : p = ∞.

If v < ∞, then
n
X
σs (x)v∞,v = (i − s)−1 (x∗i )v .
i=s+1

Combining (23) with Lemma 18 (i) for λ = v/p if p < ∞ and (ii) for λ = v/u > 1
if p = ∞ completes the proof of the case q = ∞.
If p = q < ∞ and v < u, then
n
X n
X
σs (x)vp,v = (i − s) v/p−1
(x∗i )v ≤ iv/p−1 (x∗i )v .
i=s+1 i=s+1

The conclusion now follows by Hölder’s inequality used as in the proof of Theorem 1
(III.2), cf. (20).

Proof of Lemma 18. We can assume that n ≥ 2s, otherwise we increase n. We start
with (i) and let λ > 0. First, we decompose the sum as follows,
n
X 2s
X n
X
−1 −λ −1 −λ
(i − s) i = (i − s) i + (i − s)−1 i−λ . (24)
i=s+1 i=s+1 i=2s+1

In the first sum on the right-hand side of (24), due to monotonicity, we have i−λ ≤
s−λ . Therefore,
2s
X 2s
X s
X
(i − s)−1 i−λ ≤ s−λ (i − s)−1 = s−λ i−1 . s−λ log s.
i=s+1 i=s+1 i=1

In the second sum on the right-hand side of (24), we have (i − s)−1 ≤ 2i−1 . Thus,
n
X n
X
(i − s)−1 i−λ ≤ 2 i−1−λ . s−λ .
i=2s+1 i=2s+1

Together, this completes the proof of (a).

24
 For the proof of (b) let λ > 1. We can decompose similarly to (24) and due
to monotonicity of (log i)−λ the bound on the first sum is analogous. In order to
bound the second sum we note that
n
X n
X
(i − s)−1 (log i)−λ ≤ 2 i−1 (log i)−λ . s−1 (log s)−λ+1 .
i=2s+1 i=2s+1

This proves (b).

Combined, Propositions 15 and 17 can be used to replace Propositions 13 and 14

in the proof of Theorem 1 in the cases (II), (III.2) and (IV.2) for the upper bounds.
The lower bounds in the proof of Theorem 1 in the cases (II), (III.2) and (IV.2)
can be proven via the following combinatorial lemma, which has been used for
bounds on entropy numbers, in coding theory and compressed sensing (see, e.g.,
[16, Lemma 9] and the references given there).

Lemma 19. Let s ≤ n be positive integers. There are T1 , . . . , TM ⊂ {1, . . . , n} with

(i) M ≥ (n/4s)s/2 ,
(ii) |Ti | = s for i = 1, . . . , M ,
(iii) |Ti ∩ Tj | < s/2 for i 6= j.

In the cases (II) and (IV.2) we can use indicators 1T1 , . . . , 1TM based on the sets
T1 , . . . , TM in Lemma 19 with s = ℓ(n, k) as in Theorem 1. Renormalizing these
indicators gives us a large set of well-separated unit vectors and thus a lower bound
on the entropy numbers for log n ≤ k ≤ n (see Step 4 in the proof of [35, Theorem
2]).
In the case (III.2) we can use appropriately rescaled indicators of different sizes,
adapting the arguments used in the proof of [16, Theorem 10] which are similar
to the more elaborate approach used in the proof of [18, Section 4, Theorem 2].
For convenience of the reader we sketch the argument. First, let us note that if
E1 , . . . , En are disjoint subsets of N with cardinality #Eℓ ≍ 4ℓ and α1 , . . . , αn ∈ R,
then, for 0 < p, u ≤ ∞, we have
 1/u
 Pn
X n  4ℓu/p |α |u
ℓ : u < ∞,
ℓ=1
αi 1Eℓ ≍ (25)
p,u 
 max 4ℓ/p |αℓ | : u = ∞,
i=1
1≤ℓ≤n

where for p = ∞ we use a/∞ = 0 for any a ∈ R (see [19, Lemma 6]).
Following the proof of [16, Theorem 10], let n ∈ N be sufficiently large and
ν ≥ 1 be the largest integer such that 12 · 4ν ≤ n and µ be the smallest integer
such that k ≤ 4µ /2. We obtain from Lemma 19 that, for n ∈ N sufficiently large,
µ
M ≥ (n/4µ+1 )4 /2 families {Tejℓ : µ ≤ ℓ ≤ ν}, 1 ≤ µ ≤ ν, of such sets such that
2 ℓ
4 ≤ |Tejℓ | ≤ 4ℓ , µ ≤ ℓ ≤ ν, 1 ≤ j ≤ M,
3

25
the sets Tejℓ , µ ≤ ℓ ≤ ν are mutually disjoint, and
1
|Teiℓ ∩ Tejℓ | ≤ 4ℓ , µ ≤ ℓ ≤ ν, i 6= j.
2
Defining the vectors
ν
X
j
x := 4−ℓ/p 1Teℓ , j = 1, . . . , M,
j
ℓ=µ

we obtain from (25) that

kxj kp,u ≍ (ν − µ + 1)1/u

and
kxi − xj kp,v & (ν − µ + 1)1/v , i 6= j.
By rescaling, we can ensure that the points xj are in Bp,u
n and are pairwise separated

in the quasi-norm of ℓnp,v by & (ν −µ+1)1/v−1/u . Noting that ν −µ+1 & log(n/k+1)
the proof can be concluded as in Step 4 of the proof of Theorem 10 in [16].

Acknowledgement
We would like to thank G. Schechtman for providing us with the proof of Lemma 3
and the anonymous referee for the valuable comments, which helped to improve
the manuscript. Joscha Prochno’s research is supported by the German Research
Foundation (DFG) under project 516672205 and by the Austrian Science Fund
(FWF) under project P-32405. This research was funded in whole or in part by
the Austrian Science Fund (FWF) [Grant DOI: 10.55776/P32405; 10.55776/J4777].
The work of Jan Vybı́ral has been supported by the grant P202/23/04720S of the
Grant Agency of the Czech Republic. For open access purposes, the authors have
applied a CC BY public copyright license to any author-accepted manuscript version
arising from this submission.

References
[1] F. Albiac and N. J. Kalton. Topics in Banach space theory, volume 233 of
Graduate Texts in Mathematics. Springer, New York, 2006.
[2] T. Aoki. Locally bounded linear topological spaces. Proc. Imp. Acad. Tokyo,
18:588–594, 1942.
[3] M. Ariño, R. Eldeeb, and N. T. Peck. The Lorentz sequence spaces d(w, p)
where w is increasing. Math. Ann., 282(2):259–266, 1988.
[4] S. V. Astashkin. On lattice properties of the Lorentz spaces Lp,q . Math. Notes,
113(1):10–17, 2023.

26
 [5] F. L. Bauer, J. Stoer, and C. Witzgall. Absolute and monotonic norms. Numer.
Math., 3:257–264, 1961.
[6] C. Bennett and R. Sharpley. Interpolation of operators, volume 129 of Pure
and Applied Mathematics. Academic Press, Inc., Boston, MA, 1988.
[7] J. Bergh and J. Löfström. Interpolation spaces. An introduction, volume No.
223 of Grundlehren der Mathematischen Wissenschaften. Springer-Verlag,
Berlin-New York, 1976.
[8] J. Bourgain, J. Lindenstrauss, and V. Milman. Approximation of zonoids by
zonotopes. Acta Math., 162(1-2):73–141, 1989.
[9] A. Calderón. Intermediate spaces and interpolation, the complex method. Stu-
dia Math., 24(2):113–190, 1964.
[10] E. J. Candès, J. K. Romberg, and T. Tao. Robust uncertainty principles: ex-
act signal reconstruction from highly incomplete frequency information. IEEE
Trans. Inf. Theory, 52(2):489–509, 2006.
[11] E. J. Candes and T. Tao. Near-optimal signal recovery from random pro-
jections: universal encoding strategies? IEEE Trans. Inform. Theory,
52(12):5406–5425, 2006.
[12] B. Carl. Entropy numbers, s-numbers, and eigenvalue problems. J. Funct.
Anal., 41:290–306, 1981.
[13] B. Carl and I. Stephani. Entropy, compactness and the approximation of oper-
ators, volume 98 of Cambridge Tracts in Mathematics. Cambridge University
Press, Cambridge, 1990.
[14] M. Ciesielski and G. Lewicki. Sequence Lorentz spaces and their geometric
structure. J. Geom. Anal., 29(3):1929–1952, 2019.
[15] F. Cucker and S. Smale. On the mathematical foundations of learning. Bull.
Amer. Math. Soc. (N.S.), 39(1):1–49, 2002.
[16] A. Doležalová and J. Vybı́ral. On the volume of unit balls of finite-dimensional
Lorentz spaces. J. Approx. Theory, 255:105407, 20, 2020.
[17] D. L. Donoho. Compressed sensing. IEEE Trans. Inform. Theory, 52(4):1289–
1306, 2006.
[18] D. E. Edmunds and Yu. Netrusov. Entropy numbers of embeddings of Sobolev
spaces in Zygmund spaces. Studia Math., 128(1):71–102, 1998.
[19] D. E. Edmunds and Yu. Netrusov. Entropy numbers and interpolation. Math.
Ann., 351(4):963–977, 2011.
[20] D. E. Edmunds and H. Triebel. Function spaces, entropy numbers, differen-
tial operators, volume 120 of Cambridge Tracts in Mathematics. Cambridge
University Press, Cambridge, 1996.

27
[21] S. Foucart, A. Pajor, H. Rauhut, and T. Ullrich. The Gelfand widths of ℓp -balls
for 0 < p ≤ 1. J. Complexity, 26(6):629–640, 2010.
[22] S. Foucart and H. Rauhut. A mathematical introduction to compressive sensing.
Applied and Numerical Harmonic Analysis. Birkhäuser/Springer, New York,
2013.
[23] D. J. Fresen. Random Euclidean embeddings in finite-dimensional Lorentz
spaces. Studia Math., 269(2):121–138, 2023.
[24] Y. Gordon, H. König, and C. Schütt. Geometric and probabilistic estimates for
entropy and approximation numbers of operators. J. Approx. Theory, 49:219–
239, 1987.
[25] L. Grafakos. Classical Fourier analysis. Springer, 2008.
[26] O. Guédon and A. E. Litvak. Euclidean projections of a p-convex body. In Ge-
ometric aspects of functional analysis, volume 1745 of Lecture Notes in Math.,
pages 95–108. Springer, Berlin, 2000.
[27] A. Hinrichs, A. Kolleck, and J. Vybı́ral. Carl’s inequality for quasi-Banach
spaces. J. Funct. Anal., 271(8):2293–2307, 2016.
[28] A. Hinrichs, J. Prochno, and J. Vybı́ral. Entropy numbers of embeddings of
Schatten classes. J. Funct. Anal., 273(10):3241–3261, 2017.
[29] Z. Kabluchko, J. Prochno, and M. Sonnleitner. A probabilistic approach to
Lorentz balls ℓnq,1 . J. Funct. Anal., 288(1):110682, 2025.
[30] T. Kaewtem. Entropy numbers in γ-Banach spaces. Math. Nachr., 290(17-
18):2879–2889, 2017.
[31] T. Kaewtem and Y. Netrusov. Entropy numbers of diagonal operators on Orlicz
sequence spaces. Math. Nachr., 294(7):1350–1373, 2021.
[32] A. Kamińska and L. Maligranda. Order convexity and concavity of Lorentz
spaces Λp,w , 0 < p < ∞. Studia Math., 160(3):267–286, 2004.
[33] A. N. Kolmogorov. On certain asymptotic characteristics of completely
bounded metric spaces. Dokl. Akad. Nauk SSSR, 108:385–388, 1956.
[34] H. König. Eigenvalue distribution of compact operators, volume 16 of Oper.
Theory: Adv. Appl. Birkhäuser, Cham, 1986.
[35] M. Kossaczká and J. Vybı́ral. Entropy numbers of finite-dimensional embed-
dings. Expo. Math., 38(3):319–336, 2020.
[36] T. Kühn. A lower estimate for entropy numbers. J. Approx. Theory,
110(1):120–124, 2001.
[37] J. Lang and A. Nekvinda. Embeddings between Lorentz sequence spaces are
strictly but not finitely strictly singular. Studia Math., 272(1):35–57, 2023.

28
[38] M. Ledoux and M. Talagrand. Probability in Banach spaces. Isoperimetry and
processes, volume 23 of Ergeb. Math. Grenzgeb., 3. Folge. Berlin etc.: Springer-
Verlag, 1991.
[39] M. A. Lifshits and W. Linde. Approximation and entropy numbers of Volterra
operators with application to Brownian motion, volume 745 of Mem. Am. Math.
Soc. Providence, RI: American Mathematical Society (AMS), 2002.
[40] J. Lindenstrauss and L. Tzafriri. Classical Banach spaces, volume 338 of Lecture
Notes in Math. Springer, 1973.
[41] G. G. Lorentz. Some new functional spaces. Ann. Math., 51(1):37–55, 1950.
[42] G. G. Lorentz. On the theory of spaces Λ. Pac. J. Math., 1:411–429, 1951.
[43] S. Mayer and T. Ullrich. Entropy numbers of finite dimensional mixed-norm
balls and function space embeddings with small mixed smoothness. Constr.
Approx., 53(2):249–279, 2021.
[44] E. Novak and H. Woźniakowski. Tractability of multivariate problems. Vol.
1: Linear information, volume 6 of EMS Tracts in Mathematics. European
Mathematical Society (EMS), Zürich, 2008.
[45] A. Pietsch. Operator ideals. Mathematische Monographien, Bd. 16. Berlin:
VEB Deutscher Verlag der Wissenschaften. 451 p. M 83.00 (1978)., 1978.
[46] J. Prochno. Embeddings of Orlicz-Lorentz spaces into L1 . St. Petersbg. Math.
J., 32(1):59–70, 2021.
[47] S. Reisner. On the duals of Lorentz function and sequence spaces. Indiana
Univ. Math. J., 31:65–72, 1982.
[48] S. Rolewicz. On a certain class of linear metric spaces. Bull. Acad. Polon. Sci.
Cl. III., 5:471–473, XL, 1957.
[49] C. Schütt. Entropy numbers of diagonal operators between symmetric Banach
spaces. J. Approx. Theory, 40(2):121–128, 1984.
[50] C. Schütt. Lorentz spaces that are isomorphic to subspaces of L1 . Trans. Am.
Math. Soc., 314(1):583–595, 1989.
[51] E. M. Stein and G. Weiss. Introduction to Fourier analysis on Euclidean spaces,
volume 1. Princeton university press, 1971.
[52] M. Talagrand. The generic chaining. Upper and lower bounds of stochastic
processes. Springer Monogr. Math. Berlin: Springer, 2005.
[53] V. N. Temlyakov. An inequality for the entropy numbers and its application.
J. Approx. Theory, 173:110–121, 2013.
[54] R. C. Williamson, A. J. Smola, and B. Schölkopf. Generalization performance
of regularization networks and support vector machines via entropy numbers
of compact operators. IEEE Trans. Inf. Theory, 47(6):2516–2532, 2001.

29