{'fraction_non_alphanumeric': 0.07496038900726656, 'fraction_numerical': 0.020925531333661148, 'mean_word_length': 3.0361631753031975, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 35, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 24, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the entropy numbers and the Kolmogorov widths

Direct estimates between linear or nonlinear Kolmogorov widths and entropy numbers are presented. These estimates are derived using the recently introduced Lipschitz widths. Applications for m-term approximation are obtained.


Introduction
We consider a Banach space (X, · X ) (or a Hilbert space H) equipped with a norm · X and a compact subset K ⊂ X of X. Typically, K is a finite ball in smoothness spaces like the Lipschitz, Sobolev, or Besov spaces.
A well known classical result, called the Carl's inequality, see [2] or [7], compares a certain characteristic of the set K, called entropy numbers e k (K) X , with its approximability by linear spaces, measured by its Kolmogorov width d k (K) X . The Carl's inequality states that for each r > 0, there is a constant C(r) such that for all n ∈ N, Inequality (1.1) has been generalized in [10], where the nonlinear Kolmogorov widths d n (K, N ) X have been used instead of the linear Kolmogorov widths d k (K) X . More precisely, it has been shown there that for each r > 0, there is a constant C(r, λ) such that for all n ∈ N, k r e k (K) X ≤ C(r, λ) max 1≤m≤n m r d m−1 (K, λ m ) X , with λ > 1 a fixed constant. In addition, it was also proven that for each r > 0, there is a constant C(r, a) such that for all n ∈ N, k r e (a+r)k log k (K) X ≤ C(r, a) max where a > 0 is a fixed constant and k log k cannot be replaced by a slower growing function of k. All these inequalities are primarily useful when the linear or nonlinear Kolmogorov widths decay as a power of m. In this paper, we give finer extensions of the (generalized) Carl's inequalities (1.1), (1.2) and (1.3), using the recently introduced in [8] Lipschitz widths. We start with some definitions, presented in §2, and continue, see §3, with a comparison between the nonlinear Kolmogorov widths and the Lipschitz widths. Our main results are presented in §4, where we give a direct comparison between the entropy numbers of K and its linear and nonlinear Kolmogorov widths. Finally, in §5, we derive what these estimates mean for the m-term approximation in Hilbert spaces.

Preliminaries
We start this section with the definition of Kolmogorov widths. If we fix the value of n ≥ 0, the Kolmogorov n-width d n (K) X of K is defined as where the infimum is taken over all linear spaces X n ⊂ X of dimension n. These are the classical Kolmogorov widths introduced in [6], or consult [7] for their modern exposition. To distinguish them from the introduced later nonlinear Kolmogorov widths, we call them linear Kolmogorov n-widths. They describe the optimal performance possible for the approximation of the model class K using linear spaces of dimension n. However, they do not tell us how to select a (near) optimal space Y of dimension n for this purpose. Let us also note that in the definition of Kolmogorov width, we are not requiring that the mapping which sends f ∈ K into an approximation to f is a linear map. A generalization of this concept was introduced in [10], where the so called nonlinear Kolmogorov (n, N )-width d n (K, N ) X was defined for N ≥ 1 as where the last infimum is over the sets L N of at most N linear spaces X n ⊂ X of dimension n. Note that here the choice of the linear subspace X n ∈ L N from which we choose the best approximation to f depends on f . Clearly, d n (K, 1) X = d n (K) X , and the bigger the N is, the more flexibility we have to approximate f . These nonlinear Kolmogorov widths are used in estimating from below the best m-term approximation, see e.g. [3,10]. The cases considered in [10] are the cases when N = λ n , and N = n an , where λ > 1 and a > 0 are fixed constants, respectively. A useful observation that we are going to utilize is that both Kolmogorov widths are homogenous. Namely, if K ⊂ X and t ∈ R, we have (2.1) d n (tK, N ) X = |t|d n (K, N ) X and d n (tK) X = |t|d n (K) X , In going further, we introduce first the minimal ǫ-covering number N ǫ (K) of a compact set K ⊂ X. A collection {g 1 , . . . , g m } ⊂ X of elements of X is called an ǫ-covering of K if An ǫ-covering of K whose cardinality is minimal is called minimal ǫ-covering of K. We denote by N ǫ (K) the cardinality of the minimal ǫ-covering of K. Minimal inner ǫ-covering numberÑ ǫ (K) of a compact set K ⊂ X is defined exactly as N ǫ (K) but we additionally require that the centers {g 1 , . . . , g m } of the covering are elements from K.
Entropy numbers e n (K) X , n ≥ 0, of the compact set K ⊂ X are defined as the infimum of all ǫ > 0 for which 2 n balls with centers from X and radius ǫ cover K. If we put the additional restriction that the centers of these balls are from K, then we define the so called inner entropy numbersẽ n (K) X . Formally, we write An ǫ-packing of K whose size is maximal is called maximal ǫ-packing of K. We denote byP ǫ (K) the cardinality of the maximal ǫ-packing of K. We have the following inequalities for every ǫ > 0 and every compact set K Finally, we introduce the Lipschitz widths d γ n (K) X , γ ≥ 0, n ≥ 1, of the compact set K ⊂ X, see [8]. We denote by (R n , . Yn ), n ≥ 1, the n-dimensional Banach space with a fixed norm · Yn . For γ ≥ 0, we first define the fixed Lipschitz width d γ (K, Y n ) X , where the infimum is taken over all Lipschitz mappings Φ n : (B Yn , · Yn ) → X, B Yn := {y ∈ R n : y Yn ≤ 1}, that satisfy the Lipschitz condition with constant γ. We then define the Lipschitz width where the infimum is taken over all norms · Y k in R k and all k ≤ n. We observe the following analog to (2.1)

Comparison between nonlinear Kolmogorov widths and Lipschitz widths
In this section, we derive direct inequalities between the nonlinear Kolmogorov widths and the Lipschitz widths. We then use known relations between entropy numbers and Lipschitz widths to derive improvements of the (generalized) Carl's inequalities.
We first note the following comparison between the linear Kolmogorov widths and the Lipschitz widths, proven in [8], see Corollary 5.2.
Theorem 3.1. For every n ≥ 1 and every compact set K ⊂ X we have We next proceed with estimates between the nonlinear Kolmogorov width and the Lipschitz widths. Clearly, it follows from the definition that where we have used in the last inequality the above theorem. Better estimates in the case of K being a subset of a Hilbert space H or a general Banach space X are described in the following lemmas.
Let (B X j , · H ) be the unit ball of the space X j ⊂ H. We fix an orthonormal basis {ϕ j 1 , . . . , ϕ j n } in X j and consider the isometry We use these mappings to construct Φ n+1 : We want to derive an upper bound for A. Note that ψ j (x n+1 ) = 0 if and only if x n+1 ∈ I j .We consider the following two cases: • if x n+1 , x ′ n+1 ∈ I j for some j = 0, . . . , N − 1, then ψ j (x n+1 ) = 0, We can assume without loss of generality that , where we have used arguments similar to the first case. In both cases we have that , and therefore Φ n+1 is an (N + 1)-Lipschitz mapping. Since To show the second part of (3.1), we determine ℓ ∈ N such that x := (x 1 , . . . , x n ), y := (y 1 , . . . , y ℓ ). The unit ball with respect to this norm is We denote by c j := (c j 1 , . . . , c j ℓ ) ∈ R ℓ the center of Q j , j = 1, . . . , 2 ℓ , and define the functions φ j : whereψ j are the mappings defined in (3.2). Using the fact that for any two numbers a, b, we have |a . Moreover, the supports of the φ j 's are disjoint, with Q j being the support of φ j , and |φ j (y)| ≤ 1 for all j. Now, following similar arguments as the ones for Φ n+1 , and denoting we derive that: • if y, y ′ ∈ Q j for some j = 1, . . . , 2 ℓ , • if y ∈ Q j and y ′ ∈ Q k , k = j, we consider the line segment , and similarly to the estimate for A, one obtains Therefore, Ψ n+ℓ is a 3-Lipschitz mapping. As before, since sup f ∈K f H = 1, we obtain d 3 where we have used the fact that ℓ = ⌈log 2 N ⌉ and φ j (c j ) = 1, j = 0, . . . , N . The proof is completed.
The case of arbitrary Banach space X is based on the following lemma.
In addition, if X = L p , then the Lipschitz constant ofψ is at most n |1/2−1/p| .
Proof: It follows from the Fritz John theorem, see Chapter 3 in [9] or [1], that there exists an invertible linear operator φ : Let us fix an orthonormal basis ϕ 1 , . . . , ϕ n for Z and consider the coordinate mapping κ Z : Z → R n defined as This mapping is isometry when R n is equipped with the norm We now define the linear mapping The first inclusion gives thatψ has a norm (Lipschitz constant) ≤ 1, and thusψ := √ nψ has a Lipschitz constant √ n. The second inclusion shows that B Y ⊂ψ(B Z ), and thereforeψ is the desired mapping. It follows from [5,Cor. 5] that in the case of X = L p , we can replace √ n in (3.3) by Note that sinceψ is linear, we have thatψ(0) = 0, and for every z ∈ B Z , where we can replace √ n by n |1/2−1/p| in the case when X = L p .
Lemma 3.5. For every n ≥ 1, N > 1, and every compact set K subset of a Banach space X with sup f ∈K f X = 1, we have We fix n, N > 1, and consider the n dimensional linear spaces X 1 , . . . , X N , X j ⊂ X, j = 1, . . . , N , with (B X j , · X ) being the unit ball of X j . For a fixed j = 1, . . . , N , we apply Lemma 3.3 with Y = X j and Z = ℓ 2 (R n ) to find an M -Lipschitz mappingΨ j , where M = √ n or n |1/p−1/2| , depending on whether X is a general Banach space or L p , such that We show (3.5) by proceeding as in the proof of Lemma 3.2 and defining a mapping Θ n+1 : and therefore Θ n+1 is a 2M (N + 1)-Lipschitz mapping.
Note that if f j is the approximant to f from X j , then where we have used that sup f ∈K f X = 1. Thus f j ∈ 2B X j . It follows from To show the second part of (3.5), we define Ξ n+ℓ : where φ j and (B Y n+ℓ , · Y n+ℓ ) are the same as in Lemma 3.2 andΨ j is defined in (3.6). For fixed (x, y), (x ′ , y ′ ) ∈ B Y n+ℓ , we denote by and consider the following cases • if y, y ′ ∈ Q j for some j = 1, . . . , 2 ℓ , we have • if y ∈ Q j and y ′ ∈ Q k , k = j, similarly to the estimate for C, we obtain The latter estimate implies that Ξ n+ℓ is a 6M -Lipschitz mapping, and since sup f ∈K f X = 1, we obtain Remark 3.6. Note that Lemma 3.5 with X = L 2 can be used instead of Lemma 3.2. However, we have decided to present both lemmas since better Lipschitz constants are obtained when working directly with a Hilbert space H.

Main results
In this section, we provide estimates from above and below that connect the behavior of the linear and nonlinear Kolmogorov widths of K with its entropy numbers. In what follows we assume that sup f ∈K f H = 1 in the case of Hilbert space, or sup f ∈K f X = 1 in the case of a general Banach space. Similar results hold if this supremum is not 1.
Our approach of deriving estimates from below utilizes some known results for Lipschitz widths stated below, see Theorem 4.7 in [8].
Theorem 4.1. Let K ⊂ X be a compact subset of a Banach space X, n ∈ N , and d γ n (K) X be the Lipschitz width for K with Lipschitz constant γ ≥ 2rad(K). Then the following holds: (1) If for α > 0, β ∈ R and a constant C > 0, we have for n = 1, 2, . . ., where C ′ > 0 is a fixed constant.    Proof: To show (4.1), we apply Lemma 3.2, Theorem 4.1 with a value γ = max{2rad(K), 3}, and use the monotonicity of the Lipschitz width as a function of γ to derive that We omit the proof of the rest of the theorem since it is similar to the case already discussed. Note that the above theorem holds for any value of N . In the cases when N = λ n , with λ > 1, or N = n an , with a > 0, we obtain two corollaries. • If e n (K) H ≥ C [log 2 n] β n α , n = 1, 2, . . ., then • If e n (K) H ≥ C 1 [log 2 n] α , n = 1, 2, . . ., then • If e n (K) H ≥ C2 −cn α , n = 1, 2, . . ., then

Proof:
We outline the proof of only the first statement. It follows from (4.1) with N = n an that where we have used that for n big enough log 2 n ≤ log 2 (n + an log 2 n) ≤ 2 log 2 n.

Proof:
Since we have that the ball with center σ j e j and radius r j := σ 2 j + σ 2 j+1 contains 0 and all points σ j ′ e j ′ with j ′ > j, but none of the points σ j ′ e j ′ with j ′ < j. Thus, if we look for 2 n balls with centers in K σ , covering K σ , and with smallest radius, these are the balls B(σ j e j , r 2 n ), j = 1, 2, . . . , 2 n , with centers σ j e j and radius r 2 n . The j-th ball does not contain the first (j − 1) points σ j ′ e j ′ , 1 ≤ j ′ ≤ j −1, from K σ , but contains the rest of the points {σ i e i } ∞ i=j ∪ {0}. Therefore, we have thatẽ To prove the second statement, we define the n-dimensional spaces X s := span{e j } sn (s−1)n+1 , s = 1, 2, . . . , N.

4.3.
Estimates from below for the nonlinear Kolmogorov width, the Banach space case. To prove an estimate from below in the Banach space case, we use the following statement from [8], see Theorem 7.3 in [8].

Proof:
We apply Lemma 3.5, Theorem 4.8 with γ = 2(λ n + 1) √ n and use the monotonicity of the Lipschitz width as a function of γ to derive that

4.4.
Estimates from above for the entropy numbers. The next proposition provides us with a tool to derive estimates for the entropy numbers of K if we have a knowledge about the behavior of the nonlinear Kolmogorov widths d n (K, N ) X . Proposition 4.10. Let K ⊂ X with rad(K) < 1 be a compact subset of a Banach space X and d n (K, N ) X , N > 1, n ∈ N, be the nonlinear Kolmogorov width for K. If for some 1 > ǫ > 0 we have d n (K, N ) X < ǫ, then there exists an absolute constant c > 0 such thatP 3ǫ (K) ≤ N (c/ǫ) n and e ⌈log 2 µ⌉ (K) X ≤ 3cN 1/n µ −1/n , with µ =P 3ǫ (K).
Proof: Since d n (K, N ) X < ǫ, it follows from the definition of the nonlinear Kolmogorov width that there exist n-dimensional subspaces X j ⊂ X, j = 1, . . . , N , for which Let {k j } µ j=1 ⊂ K be a maximal 3ǫ-packing in K, i.e. µ =P 3ǫ (K). Then, for each k i there exists x i ∈ X j(i) ⊂ N j=1 X j such that k i − x i X < ǫ, i = 1, . . . , µ, and we can estimate the difference The condition rad(K) < 1 implies that there exists y ∈ X such that and therefore Let y j be the closest to y element from X j(i) ⊂ N j=1 X j . Then for any x i ∈ {x 1 , . . . , x N } (x 1 , . . . , x N may not be necessary all different) we have which leads to It follows from (4.5) that the set {x i } µ i=1 is an ǫ-packing for N j=1 B X j(i) (y j , 4). We next use (2.2) to derive where c > 0 is an absolute constant. Note that we have applied the inequality N ǫ/2 (B X j(i) (y j , 4)) ≤ (c/ǫ) n , j = 1, . . . , N, from [7,Chp. 15 Prop.1.3]. In terms of entropy numbers we can write e ⌈log 2 µ⌉ (K) X ≤ 3ǫ ≤ 3cN 1/n µ −1/n .
We use Proposition 4.10 to obtain estimates from above for the entropy numbers e m (K) X of K. A similar estimate but for a different range of m and some specific values of N has been recently presented in [11]. Lemma 4.11. Let K ⊂ X be a compact subset of a Banach space X with rad(K) < 1. If for α > 0, β ∈ R, λ > 1, and c 0 > 0 we have that for some n > n 0 (c 0 , α, β, λ), then where C is a fixed constant depending only on λ, α, β, c 0 .
Proof: It follows from Proposition 4.10 with ǫ = c 0 for n > n 0 where n 0 depends only c 0 , λ, α and β. For such n's we have Setting m = 2αn log 2 n gives Since for n sufficiently large, 2 −1 log 2 n < log 2 m < 3 log 2 n, the proof is completed. The results in Lemma 4.11 and Remark 4.12 hold also for sequences. Namely, using the monotonicity of the quantities involved, the following is true.

Applications
In this section, we describe how some of the above results can translate to estimates about m-term approximation. We follow the framework outlined in Theorem 4.1 from [10].
We assume that we have a system D = {g j } ∞ j=1 ⊂ X and de la Vallee-Poussin linear operators V k associated with the sequences n k , {(V k , n k )} ∞ k=1 , satisfying the conditions: (1) There is a constant A 2 > 1 such that (2) The norms of V k as operators from X to X are uniformly bounded, i.e. there is a constant A 3 > 0 such that V k X→X ≤ A 3 , k = 1, 2, . . ..
We denote by S n k (f ) the best approximation to f ∈ K by elements from span{g 1 , . . . , g n k }, Then the following lemma holds.
Lemma 5.1. If the Banach space X admits de la Vallee-Poussin linear operators V k that satisfy (1)-(2), with constants A 2 > 1, A 3 > 0, then we have for 1 < m < A 2 n k , where b > 1 is an absolute constant.
Proof: Clearly, we have the inequality If we denote by D A 2 n k := {g 1 , . . . , g A 2 n k }, then it follows from the properties of V k that for any index set Λ with |Λ| = m and any coefficients {c j } m j=1 , and therefore Since Taking a supremum over f ∈ K in the latter inequality gives Note that the total number of m-dimensional subspaces, 1 < m < A 2 n k , of the linear space span{g 1 , . . . , g A 2 n k } is A 2 n k m . Using the Stirling formula, one can show that there is an absolute constant b > 1 such that Then the definition of nonlinear Kolmogorov width and its monotonicity with respect to N gives The latter inequality combined with (5.4) leads to where 1 < m < A 2 n k , and the proof is completed. . We next state a theorem that follows from Lemma 5.1 and our inequalities for nonlinear Kolmogorov widths in Hilbert spaces. Note that our theorem does not require the additional assumptions on the error E n (K, D) H that are needed in Theorem 4.1 from [10] and describes the behavior of the errors in cases not covered by this theorem. Note that we have utilized the fact that the constants in Theorem 4.3 do not depend on N . We can derive several corollaries from the above theorem, one of which we state below. If we take m = n k /2 in Theorem 5.2, we obtain the following statement. • If e n k (K) H ≥ C 1 [log 2 n k ] α , k = 1, 2, . . ., then there is an absolute constant C ′′ > 0 such that max{E n k (K, D) H , σ n k /2 (K, D) H } ≥ C ′′ [log 2 n k ] α , k = 1, 2, . . . .
Note that since A 2 > 1, we can take m = n k in Lemma 5.1, use the fact that E n k (K, D) H ≥ σ n k (K, D) H , and obtain from this lemma that if the Banach space X admits de la Vallee-Poussin linear operators satisfying (1)-(2), then d n k (K, (A 2 b) n k ) H ≤ (1 + 2A 3 )E n k (K, D) H .
We can now use Corollary 4.4 and the monotonicity of the nonlinear Kolmogorov width with respect to N to conclude that d n k K, (A 2 b) n k +1 H ≤ d n k (K, (A 2 b) n k ) H , and derive the following statement.