- Kolmogorov n -Widths of Function Classes Induced by a Non-Degenerate Differential Operator: A Convex Duality. - The problem of computing the asymp- totic order of the Kolmogorov n-width d n (U 2 [P. - In the present paper, we use convex analytical tools to solve it in the case when P(D) is non-degenerate.. - asymptotic order · Kolmogorov n-widths · non-degenerate differential operator · convex duality. - The aim of the present paper is to study Kolmogorov n-widths of classes of multivariate periodic functions induced by a differential operator. - In order to describe the exact setting of the problem let us introduce some notation.. - Let X be a normed space, let F be a nonempty subset of X such that F = −F , and let G n be the class of all vector subspaces of X of dimension at most n. - This notion quantifies the error of the best approximation to the elements of F by elements in a vector subspace of X of dimension at most n . - T d ) is the distribution f (α. - Now let A ⊂ N d be a nonempty finite set, let (c α ) α∈A be nonzero real numbers, and define a polynomial by. - Our main contribution is to solve it for a non-degenerate differential operator P(D) (see Definition 2.4).. - was computed in the case when U 2 A is the closed unit ball of the space W 2 A of functions with several bounded mixed derivatives (see Subsection 4.4 for a precise definition).. - The remainder of the paper is organized as follows. - In Section 3, we present the main result of the paper, namely the asymptotic order of d n U 2 [P. - in the case when P(D) is non-degenerate. - for non-degenerate differential operators.. - such that (∀θ ∈ Θ) γ 1 Φ(θ. - For every j ∈ {1. - Definition 2.1 Let B be a nonempty finite subset of N d . - Assumption 2.2 A is a nonempty finite subset of N d and (c α ) α∈A are nonzero real numbers. - Definition 2.4 The Newton diagram of P is ∆(A) and the Newton polyhedron of P is conv(A). - The differential operator P(D) is non-degenerate if P and, for every σ ∈ Σ(A), P σ : R d → R : x 7→ P. - Remark 2.5 Suppose that P is non-degenerate and let α ∈ ϑ(A). - Lemma 2.6 Let t ∈ R. - Corollary 2.7 Let t ∈ ]τ. - Lemma 2.8 Let t ∈ ]τ. - We start with a characterization of the compactness of the unit ball defined in (1.12).. - Lemma 2.9 The set U 2 [P] is a compact subset of L 2 ( T d ) if and only if the following hold:. - (iii) For every ǫ ∈ R. - By Lemma 2.8, U e. - Lemma 2.10 P(D) is non-degenerate if and only if. - As proved in [12, 17], P(D) is non-degenerate if and only if. - such that (∀x ∈ R d ) γ 2 max. - Lemma 2.11 Let B be a nonempty finite subset of N d and let t ∈ R. - d } such that. - Theorem 2.12 Suppose that P(D) is non-degenerate. - such that. - by Carathéodory’s theorem [20, Theorem 17.1], α is a convex combina- tion of points (β j ) 1¶ j¶d+1 in ϑ(B), say. - Hence, Lemma 2.10 asserts that there exists γ 2 ∈ R. - Consequently, by Lemma 2.9, U 2 [P] is a compact set in L 2 ( T d ) if and only if, for every t ∈ R. - In view of Lemma 2.11, the first condition is equivalent to (2.21) and the second to 0 ∈ A. - Corollary 3.1 Suppose that P(D) is non-degenerate. - Combine (2.28) and Lemma 2.10.. - Let C be a subset of R d . - Lemma 3.2 Let B be a nonempty finite subset of R d. - R d , let µ(B) be the optimal value of the problem. - ι B ⊙ [4, Propositions 14.12 and 7.14(vi)] and the conjugate of ψ is ψ. - To illustrate the duality principles underlying Lemma 3.2, we consider two examples.. - Example 3.3 We consider the case when d = 2 and B see Figure 1).. - Then (3.4) is satisfied, µ(B. - The set of solutions to (3.5) is the set S represented by the solid red segment: S. - Example 3.4 In this example we consider the case when B . - Lemma 3.5 Let B be a nonempty finite subset of R d. - Let µ(B) be the optimal value of the problem. - and let ν (B) be the dimension of its set of solutions. - Figure 1: Graphical illustration of Example 3.3: In gray, the Newton polyhedron (top) and its polar (bottom). - The dashed lines are the hyperplanes delimiting the polar set B ⊙ and the dotted line rep- resents the optimal level curve of the objective function x 7. - Figure 2: Graphical illustration of Example 3.4: In gray, the Newton polyhedron (top) and its polar (bottom). - Then, as in the proof of Lemma 2.11, one can see that Λ B (t) is a bounded subset of R + d . - Theorem 3.6 Suppose that P (D) is non-degenerate and that. - Let µ be the optimal value of the problem. - let ν be the dimension of its set of solutions, and set. - We also note that the equivalence between (3.17) and (3.18) follows from (1.1) and (1.2). - Applying Lemma 3.5 to ϑ(A) yields. - It therefore follows from (1.1) and Corollary 2.7 that d n U 2 [P. - which establishes the upper bound in (3.17). - By Lemma 2.8, U (t. - Consequently, it follows from and (3.23) that d n U 2 [P. - which concludes the proof of (3.17). - such that 0 <. - Remark 3.7 We have actually proven a bit more than Theorem 3.6. - Namely, suppose that P(D) satis- fies the conditions of compactness for U 2 [P] stated in Lemma 2.9 and, for every n ∈ N , let t(n) be the largest number such that card K( t(n. - for non-degenerate and degenerate differential operators.. - Theorem 4.1 Suppose that P (D) is non-degenerate and set Q : x 7→ X. - (4.2) Moreover, the seminorms in (4.2) are norms if and only if 0 ∈ A.. - Now let (Z d (α)) α∈ϑ(A) be a partition of Z d such that. - Hence, appealing to Corollary 3.1 and (2.10), we obtain. - Therefore, we derive from (4.2) that the seminorms in (4.2) are norms if and only if 0 ∈ A.. - If s is even, it follows directly from Lemma 2.10 that the differential operator P(D) is non-degenerate, and consequently, by Theorem 4.1, k · k H s is equivalent to one of the norms appearing in (4.2) with ϑ(A. - Therefore, we retrieve from Theorem 3.6 the well-known result. - This result is a direct generalization of the first result on n-widths established by Kolmogorov in [14].. - If the coordinates of β are even, the differential operator P(D) is non-degenerate. - Consequently, by Theorem 4.1, k · k H β is equivalent to one of the norms in (4.2) with ϑ(A. - 0, and therefore, from Theorem 3.6 we retrieve the known result [13]. - The space W 2 α is the Hilbert space of functions f ∈ L 2 equipped with the norm. - If the coordinates of α are even, the differential operator P(D) is non-degenerate and hence, by Theorem 4.1, k · k W α. - 2 is equivalent to one of the norms in (4.2) with ϑ(A. - ν , and therefore, from Theorem 3.6 we recover the result proven in [1], namely that for n sufficiently large. - Suppose that (3.14) is satisfied. - Let W 2 A be the Hilbert space of functions f ∈ L 2 ( T d ) equipped with the norm. - If the coordinates of every α ∈ ϑ(A) are even, the differential operator P(D) is non-degenerate and it follows from Theorem 4.1 that k · k W A. - 2 is equivalent to one of the norms in (4.2). - we again retrieve from Theorem 3.6 the result proven in [6], namely that for n sufficiently large. - 4.5 Classes of functions induced by a differential operator. - It is easy to verify that P 1 (D) and P 2 (D) are non-degenerate and that (3.14) holds. - In view of Lemma 2.9, this is equivalent to the conditions:. - (i) For every t ∈ R. - As mentioned in (3.30), for every n ∈ N sufficiently large, if t (n. - In view of (3.20), we know that the conjecture is true when P satisfies conditions (2.7) and (3.9).. - Wakin, A simple proof of the restricted isometry property for random matrices, Constr