1 Introduction↩︎

This paper is a followup to the recent author’s paper [1]. In this paper we continue to study approximation of the multivariate functions \(K(\mathbf{x},\mathbf{y})\), \(\mathbf{x}=(x_1,\dots,x_d)\), \(\mathbf{y}=(y_1,\dots,y_d)\) by linear combinations of functions of the form \(u(\mathbf{x})v(\mathbf{y})\). In the case, when we can choose arbitrary functions \(u\) and \(v\), it is a classical problem of best bilinear approximation. In the paper [1] it was pointed out that the problem of optimal linear recovery on function classes defined by an integral operator with the kernel \(K(\mathbf{x},\mathbf{y})\) is closely related to the problem of approximation of \(K\) by linear combinations of functions of the form \(u(\mathbf{x})v(\mathbf{y})\) with functions \(v(\mathbf{y})\) defined by the kernel \(K(\mathbf{x},\mathbf{y})\), namely, \(v(\mathbf{y}) = K(\mathbf{z},\mathbf{y})\) with some \(\mathbf{z}\). This means that we approximate \(K(\mathbf{x},\mathbf{y})\) with respect to a dictionary, which is determined by the function \(K(\mathbf{x},\mathbf{y})\) itself. We call such a process – approximation with adaptive dictionaries (see below for more details). In the paper [1] mostly the case \(d=1\), i.e. the case of functions \(K(x,y)\) of two variables, was studied. In this paper we focus on the general case \(d\ge 1\).

We now proceed to the detailed presentation. Let \((\Omega,\mu)\) be a probability space. By the \(L_p\), \(1\le p< \infty\), norm we understand \[\|f\|_p:=\|f\|_{L_p(\Omega,\mu)} := \left(\int_\Omega |f|^p\,d\mu\right)^{1/p}.\] By the \(L_\infty\)-norm we understand the uniform norm of continuous functions \[\|f\|_\infty := \sup_{\omega\in\Omega} |f(\omega)|\] and with some abuse of notation we occasionally write \(L_\infty(\Omega)\) for the space \({\mathcal{C}}(\Omega)\) of continuous functions on \(\Omega\). We define the vector \(L_{\mathbf{p}}\)-norm, \(\mathbf{p}=(p_1,\dots,p_v)\), of functions of \(v\) variables \(\mathbf{x}=(x_1,\dots,x_v)\) as \[\|f(\mathbf{x})\|_{\mathbf{p}} :=\|f(\mathbf{x})\|_{(p_1,\dots,p_v)} :=\|f(\mathbf{x})\|_{p_1,\dots,p_v} := \|\cdots\|f(\cdot,x_2,\dots,x_v)\|_{p_1}\cdots\|_{p_v}.\]

We now introduce some concepts from nonlinear sparse approximation.

The first example of sparse approximation with respect to redundant dictionaries was considered by E. Schmidt in [2], who studied the approximation of functions \(f(x,y)\) of two variables by bilinear forms, \[\sum_{i=1}^mu_i(x)v_i(y),\] in \(L_2([0,1]^2)\). In this case we use the following dictionary (bilinear dictionary) \[\label{Bi1} \Pi := \{u(x)v(y)\,:\, u,v\in L_2([0,1])\},\tag{1}\] where the functions \(u\) and \(v\) are functions of a single variable. This problem is closely connected with properties of the integral operator \[(J_fg)(x) := \int_0^1 f(x,y)g(y) dy\] with the kernel \(f(x,y)\). E. Schmidt ([2]) gave an expansion (known as the Schmidt expansion) \[\label{Bi2} f(x,y) = \sum_{j=1}^\infty s_j(J_f) \phi_j(x)\psi_j(y),\tag{2}\] where \(\{s_j(J_f)\}\) is a nonincreasing sequence of singular numbers of \(J_f\), i.e. \(s_j(J_f) := \lambda_j(J^*_fJ_f)^{1/2}\), where \(\{\lambda_j(A)\}\) is a sequence of eigenvalues of an operator \(A\), and \(J^*_f\) is the adjoint operator to \(J_f\). The two sequences \(\{\phi_j(x)\}\) and \(\{\psi_j(y)\}\) form orthonormal sequences of eigenfunctions of the operators \(J_fJ_f^*\) and \(J_f^*J_f\), respectively. He also proved that \[\left\|f(x,y) -\sum_{j=1}^m s_j(J_f) \phi_j(x)\psi_j(y)\right\|_{L_2}\] \[\label{Bi3} = \inf_{u_j,v_j\in L_2, \quad j=1,\dots,m}\left\|f(x,y) -\sum_{j=1}^m u_j(x)v_j(y)\right\|_{L_2}.\tag{3}\] The reader can find a detailed discussion of this connection in [3], Ch.2.

In a general setting we are working in a Banach space \(X\) with a redundant system of elements \({\mathcal{D}}\) (dictionary \({\mathcal{D}}\)). An element (function, signal) \(h\in X\) is said to be \(m\)-sparse with respect to \({\mathcal{D}}\) if it has a representation \(h=\sum_{i=1}^mc_ig_i\), \(g_i\in {\mathcal{D}}\), \(i=1,\dots,m\), where \(\{c_i\}\) are real or complex numbers. The set of all \(m\)-sparse elements is denoted by \(\Sigma_m({\mathcal{D}})\). For a given element \(f\) we introduce the error of best \(m\)-term approximation \[\sigma_m(f,{\mathcal{D}})_X := \inf_{h\in\Sigma_m({\mathcal{D}})} \|f-h\|_X.\] We now make a comment on terminology. In the greedy approximation literature we define a dictionary \({\mathcal{D}}\) as a system \(\{g\}\) of elements \(g\in X\) with the following two properties \[\|g\|_X\le 1 \quad\text{for all} \quad g\in {\mathcal{D}}\quad \text{and the closure of}\, \operatorname{span}({\mathcal{D}}) =X.\] The normalization condition \(\|g\|_X\le 1\) is imposed for convenience. Clearly, the characteristic \(\sigma_m(f,{\mathcal{D}})_X\) does not depend on normalization. In this paper we mostly use this characteristic. Let us discuss the second condition. Suppose that a system \({\mathcal{S}}\subset X\) does not satisfy this condition. Then, instead of the Banach space \(X\) we consider a subspace \(X_{\mathcal{S}}\) of \(X\), which is the closure (in \(X\)) of \(\operatorname{span}({\mathcal{S}})\). This makes the system \({\mathcal{S}}\) to be a dictionary in the Banach space \(X_{\mathcal{S}}\). For this reason, we sometimes with a little abuse of exactness freely use both terms system and dictionary for a general system. In the greedy approximation theory there are theorems, which guarantee convergence of certain greedy algorithms with respect to any dictionary \({\mathcal{D}}\) for any element \(f\in X\). Clearly, in the case, when we deal with a system, we can only apply those theorems to \(f\in X_{\mathcal{S}}\).

We stress that the bilinear dictionary \(\Pi\) does not depend on a function under approximation. In this sense it is not adaptive – we use it for approximation of all functions. It turns out that in some problems we need to study approximation of a given kernel \(K(\mathbf{x},\mathbf{y})\) with respect to a dictionary, which is determined by \(K\). We now give a more general definition of the bilinear dictionary (system) and define three adaptive systems. Let \(\mathbf{p}=(p_1,p_2)\), \(1\le p_1,p_2 \le \infty\) be given. In the case \(\mathbf{p}=(p,p)\) for brevity we write \(p\) instead of \(p,p\) in the notations. Sometimes, we drop \(\mathbf{p}\) from the notation.

Bilinear dictionary \(\Pi(\mathbf{p})\). Define \[\Pi(\mathbf{p}):={\mathcal{L}}{\mathcal{L}}(\mathbf{p}) :=\{g: g(\mathbf{x},\mathbf{y}) = u(\mathbf{x})v(\mathbf{y}),\, u\in L_{p_1}(\Omega^1),\, v\in L_{p_2}(\Omega^2) \}.\]

\({\mathcal{L}}{\mathcal{K}}(\mathbf{p})\)-system. Assume that \(K \in L_\mathbf{p}(\Omega^1\times \Omega^2)\) satisfies the following property. For any \(\mathbf{z}\in \Omega^1\) we have \(K(\mathbf{z},\cdot) \in L_{p_2}(\Omega^2)\). Define \[{\mathcal{L}}{\mathcal{K}}(\mathbf{p}) :=\{g: g(\mathbf{x},\mathbf{y}) = u(\mathbf{x},\mathbf{z})K(\mathbf{z},\mathbf{y}),\, \forall \mathbf{z}\in \Omega^1\,\,\text{we have}\,\, u(\cdot,\mathbf{z}) \in L_{p_1}(\Omega^1) \}.\]

\({\mathcal{K}}{\mathcal{L}}(\mathbf{p})\)-system. Assume that \(K \in L_\mathbf{p}(\Omega^1\times \Omega^2)\) satisfies the following property. For any \(\mathbf{z}\in \Omega^2\) we have \(K(\cdot,\mathbf{z}) \in L_{p_1}(\Omega^1)\). Define \[{\mathcal{K}}{\mathcal{L}}(\mathbf{p}) :=\{g: g(\mathbf{x},\mathbf{y}) = K(\mathbf{x},\mathbf{z})v(\mathbf{z},\mathbf{y}),\, \forall \mathbf{z}\in \Omega^2\,\,\text{we have}\,\, v(\mathbf{z},\cdot) \in L_{p_1}(\Omega^2) \}.\]

\({\mathcal{K}}{\mathcal{K}}(\mathbf{p})\)-system. Assume that \(K \in L_\mathbf{p}(\Omega^1\times \Omega^2)\) satisfies the following property. For any \(\mathbf{a}\in \Omega^1\) we have \(K(\mathbf{a},\cdot) \in L_{p_2}(\Omega^2)\) and for any \(\mathbf{b}\in \Omega^2\) we have \(K(\cdot,\mathbf{b}) \in L_{p_1}(\Omega^1)\). Define \[{\mathcal{K}}{\mathcal{K}}(\mathbf{p}) :=\{g: g(\mathbf{x},\mathbf{y}) = K(\mathbf{x},\mathbf{b})K(\mathbf{a},\mathbf{y}), \quad (\mathbf{a},\mathbf{b})\in \Omega^1\times \Omega^2 \}.\] Note that in the literature (see [4]) the functions \(K_{ab}(x,y) := K(x,b)K(a,y)\), \((x,y),(a,b) \in [0,1]^2\) are called cross-functions of the function \(K(x,y)\) and the system \({\mathcal{K}}{\mathcal{K}}(\infty)\) is called the system of cross-functions.

In Section 6 we prove the following general inequalities (see Theorem 20): For any \(b\in(1,2]\) there exists a positive constant \(B=B(b)\) such that for any continuous \(K\) we have \[\label{In1} \sigma_m(K,{\mathcal{L}}{\mathcal{K}}(\infty))_\infty \le Bm^{1/2} \sigma_{\theta (m-1)}(K,\Pi(\infty))_\infty\tag{4}\] with \(\theta =1/b\) in the real case and \(\theta =1/(2b)\) in the complex case. Also, we prove there that the extra factor \(m^{1/2}\) in the inequality (4 ) is sharp (see Proposition 3).

A number of results (upper bounds, lower bounds, and sometimes the right orders) are obtained in the paper [1] in the case \(d=1\) for the following setting: Estimate \[\sup_{K\in {\mathbf{F}}} \sigma_m(K,{\mathcal{L}}{\mathcal{K}}(\mathbf{p}))_\mathbf{p}\] for a certain function class \({\mathbf{F}}\).

In this paper we extend some of those results from the case \(d=1\) to the general case \(d\ge 1\). For that we apply here the same general strategy, which was used in [1]. It is a three step strategy. First, we relate \(\sigma_m(K,{\mathcal{L}}{\mathcal{K}}(\mathbf{p}))_\mathbf{p}\) to the optimal linear recovery characteristic \(\varrho_m({\mathbf{W}}^K_q,L_\mathbf{p})\). Second, we relate \(\sigma_m(K,\Pi(\mathbf{p}))_\mathbf{p}\), \(\mathbf{p}= (p,\infty)\), to the Kolmogorov width \(d_m({\mathbf{W}}^K_1,L_p)\). Third, we use known results, which provide an upper bound on \(\varrho_m({\mathbf{W}},L_p)\) in terms of the Kolmogorov width \(d_n({\mathbf{W}},L_\infty)\). Note that the first inequality of that type, namely, the inequality \[\varrho_{bn}({\mathbf{W}},L_2) \le Bd_n({\mathbf{W}},L_\infty)\] was obtained in [5] (see Theorem 2 below). Later, some generalizations of that inequality to the case \(p\in (2,\infty]\) were proved in [6] and [7]. Here we use Theorem 8.

In Section 6 we prove the following bound (see Corollary 5). Assume that we have \(r_1>1/2\), \(r_2>0\). Then (see the definition of classes \({\mathbf{W}}^\mathbf{r}_2\) in Section 2 below) \[\sup_{K\in {\mathbf{W}}^\mathbf{r}_2} \sigma_m(K,{\mathcal{L}}{\mathcal{K}})_{2} \ll m^{-r_1-r_2}(\log m)^{(d-1)(r_1+r_2)+1/2} .\]

As we already pointed out above the study of linear recovery is closely related to the Kolmogorov widths. Namely, to the Kolmogorov widths in the uniform norm \(L_\infty\). In Section 5 we focus on the case of the uniform norm and complement the results known in the case of \(L_p\), \(p\in [2,\infty)\), by the case \(p=\infty\). The following bound (see Theorem 18 below) is a step in that direction. Assume that we have \(r_1>1/2\), \(r_2>0\). Then (see the definition of classes \({\mathbf{W}}^\mathbf{r}_2\) in Section 2 below) \[\sup_{K\in {\mathbf{W}}^\mathbf{r}_2} d_m({\mathbf{W}}^K_2)_\infty \ll m^{-r_1-r_2-1/2}(\log m)^{(d-1)(r_1+r_2)+1/2} .\]

Thus, the new results of the paper are contained in Sections 5 and 6. In Section 2 we present the definitions of function classes that we discuss in the paper. In Section 3 we formulate results on inequalities between the error of optimal linear sampling recovery and the Kolmogorov widths. In Section 4 we collect some of the known results on the Kolmogorov widths and their relation to the sparse approximation with respect to the bilinear dictionary \(\Pi\).

2 Function classes↩︎

We begin with the definition of classes \({\mathbf{W}}^\mathbf{a}_\mathbf{q}\) (see, for instance, [8], p.31, in the case of scalar \(q\)).

The classes \({\mathbf{W}}^\mathbf{a}_\mathbf{q}\) are classical classes of functions with dominating mixed derivative (Sobolev-type classes of functions with mixed smoothness).

We now proceed to the definition of the classes \({\mathbf{H}}^\mathbf{a}_\mathbf{q}:= {\mathbf{H}}^{\mathbf{a},v}_\mathbf{q}\) of periodic functions of \(v\) variables, which is based on the mixed differences (see, for instance, [8], p.31, in the case of scalar \(q\)).

We now formulate a result, which gives an equivalent description of classes \({\mathbf{H}}^\mathbf{a}_{\mathbf{q},l}\). We need some classical trigonometric polynomials. The univariate Fejér kernel of order \(j - 1\): \[\mathcal{K}_{j} (x) := \sum_{|k|\le j} \bigl(1 - |k|/j\bigr) e^{ikx} =\frac{(\sin (jx/2))^2}{j (\sin (x/2))^2}.\] The Fejér kernel is an even nonnegative trigonometric polynomial of order \(j-1\). It satisfies the obvious relations \[\label{FKm} \| \mathcal{K}_{j} \|_1 = 1, \qquad \| \mathcal{K}_{j} \|_{\infty} = j.\tag{5}\] Let \({\mathcal{K}}_\mathbf{j}(\mathbf{x}):= \prod_{i=1}^v {\mathcal{K}}_{j_i}(x_i)\) be the \(v\)-variate Fejér kernels for \(\mathbf{j}= (j_1,\dots,j_d)\) and \(\mathbf{x}=(x_1,\dots,x_v)\).

The univariate de la Vallée Poussin kernels are defined as follows \[{\mathcal{V}}_m := 2{\mathcal{K}}_{2m} - {\mathcal{K}}_m.\] We also need the following special trigonometric polynomials. Let \(s\) be a nonnegative integer. We define \[\mathcal{A}_0 (x) := 1, \quad \mathcal{A}_1 (x) := \mathcal{V}_1 (x) - 1, \quad \mathcal{A}_s (x) := \mathcal{V}_{2^{s-1}} (x) -\mathcal{V}_{2^{s-2}} (x), \quad s\ge 2,\] where \(\mathcal{V}_m\) are the de la Vallée Poussin kernels defined above. For \(\mathbf{s}=(s_1,\dots,s_v)\in {\mathbb{N}}^v_0\) define \[{\mathcal{A}}_\mathbf{s}(\mathbf{x}) := \prod_{j=1}^v {\mathcal{A}}_{s_j}(x_j),\qquad \mathbf{x}=(x_1,\dots,x_v)\] and \[A_\mathbf{s}(f) := {\mathcal{A}}_\mathbf{s}\ast f.\]

The following result is known (see, for instance, [8], p.32, for the scalar \(q\) and [9] for the vector \(\mathbf{q}\)).

The reader can find results on approximation properties of these classes in the books [8], [10], and [11].

Notations for the function classes. In this paper we consider the case, when \(v=2d\), \(d\in {\mathbb{N}}\), \(\mathbf{1}\le \mathbf{q}\le \infty\), and \(\mathbf{a}\) has a special form: \(a_j = r_1\), \(a_{j+d}= r_2\) for \(j=1,\dots,d\). In this case we write \({\mathbf{W}}^{\mathbf{r}}_\mathbf{q}= {\mathbf{W}}^{(\mathbf{r}^1,\mathbf{r}^2)}_\mathbf{q}= {\mathbf{W}}^{r_1,r_2}_\mathbf{q}\) and \({\mathbf{H}}^{\mathbf{r},2d}_\mathbf{q}= {\mathbf{H}}^{(\mathbf{r}^1,\mathbf{r}^2),2d}_\mathbf{q}= {\mathbf{H}}^{r_1,r_2,2d}_\mathbf{q}\), where \(\mathbf{r}^i := (r_i,\dots,r_i) \in {\mathbb{R}}^d\), \(i=1,2\). Sometimes for brevity we omit \(2d\) in the notation for the \({\mathbf{H}}\) classes and write, for instance, \({\mathbf{H}}^{r_1,r_2}_\mathbf{q}\) instead of \({\mathbf{H}}^{r_1,r_2,2d}_\mathbf{q}\).

3 Some known results on sampling recovery↩︎

In this paper we study the case, when the asymptotic characteristic is the error of sampling recovery. Recall the setting of the optimal linear recovery introduced in [12]. For a fixed \(m\) and a set of points \(\xi:=\{\xi^j\}_{j=1}^m\subset \Omega\), let \(\Phi\) be a linear operator from \({\mathbb{C}}^m\) into \(L_p(\Omega,\mu)\). Denote for a class \({\mathbf{F}}\) (usually, centrally symmetric and compact subset of \(L_p(\Omega,\mu)\)) \[\varrho_m({\mathbf{F}},L_p) := \inf_{\xi} \inf_{\text{linear}\, \Phi } \sup_{f\in {\mathbf{F}}} \|f-\Phi(f(\xi^1),\dots,f(\xi^m))\|_p.\] The above described recovery procedure is a linear procedure.

Most of the known results on optimal sampling recovery deal with the linear recovery methods. We now give some very brief comments on recent results in this direction and refer the reader to the books [11], [10] and to the survey paper [6] for a discussion of the previous results in this direction. We are interested in results, which relate the errors of sampling recovery with the Kolmogorov widths for general function classes. We begin with a result from [5].

The following generalization of Theorem 2 to the case \(2<p\le \infty\) was obtained in [7].

In our applications the following analog of the inequality (?? ), which is contained in Theorem 3, \[\label{kr3} \varrho_{bn}({\mathbf{F}},L_\infty) \le Bn^{1/2}d_n({\mathbf{F}},L_\infty)\tag{6}\] plays a fundamental role. For this reason, we now present a detailed discussion of this inequality.

Let as above \(\Omega\) be a compact subset of \({\mathbb{R}}^d\) and \(X_N\) be an \(N\)-dimensional subspace of the space of continuous functions \({\mathcal{C}}(\Omega)\). Given a fixed \(m\) and a set of points \(\xi^1,\ldots,\xi^m\in\Omega\), we associate with a function \(f\in {\mathcal{C}}(\Omega)\) a vector (sample vector) \[S(f,\xi) := (f(\xi^1),\dots,f(\xi^m)) \in {\mathbb{C}}^m.\] We also consider the discrete norms \[\|S(f,\xi)\|_p:= \left(\frac{1}{m}\sum_{j=1}^m |f(\xi^j)|^p\right)^{1/p},\quad 1\le p<\infty,\] and \(\|S(f,\xi)\|_\infty := \max_{j}|f(\xi^j)|\).

For a positive weight \(\mathbf{w}:=(w_1,\dots,w_m)\in {\mathbb{R}}^m\) consider the following seminorm \[\|S(f,\xi)\|_{p,\mathbf{w}}:= \left(\sum_{j=1}^m w_j |f(\xi^j)|^p\right)^{1/p},\quad 1\le p<\infty.\] Define the best approximation of \(f\in L_p(\Omega,\mu)\), \(1\le p\le \infty\), by elements of \(X_N\) as follows \[d(f,X_N)_p := \inf_{u\in X_N} \|f-u\|_p.\]

Theorem 4 below was proved in [5] under the following assumptions.

A1. Discretization. Let \(1\le p\le \infty\). Suppose that \(\xi:=\{\xi^j\}_{j=1}^m\subset \Omega\) provides the following discretization property: For any \(u\in X_N\) in the case \(p<\infty\) we have \[\|u\|_p \le D \|S(u,\xi)\|_{p,\mathbf{w}}\] and in the case \(p=\infty\) we have \[\|u\|_\infty \le D \|S(u,\xi)\|_{\infty}\] with some positive constant \(D\).

A2. Weights. Suppose that there is a positive constant \(W\) such that \(\sum_{j=1}^m w_j \le W\).

Consider the following well known recovery operator (algorithm) \[\ell p\mathbf{w}(\xi)(f) := \ell p\mathbf{w}(\xi,X_N)(f):=\text{arg}\min_{u\in X_N} \|S(f-u,\xi)\|_{p,\mathbf{w}},\quad 1\le p<\infty,\] \[\ell \infty(\xi)(f) := \ell \infty(\xi,X_N)(f):=\text{arg}\min_{u\in X_N} \|S(f-u,\xi)\|_{\infty}.\] Note that the above algorithm \(\ell p\mathbf{w}(\xi)\) only uses the function values \(f(\xi^j)\), \(j=1,\dots,m\). In the case \(p=2\) it is a linear algorithm – orthogonal projection with respect to the seminorm \(\|\cdot\|_{2,\mathbf{w}}\). Therefore, in the case \(p=2\) the approximation error in the \(L_q\) norm by the algorithm \(\ell 2\mathbf{w}(\xi)\) gives an upper bound for the recovery characteristic \(\varrho_m(\cdot, L_q)\).

The following version of Theorem 4 for the error of \(\|f-\ell p\mathbf{w}(\xi)(f)\|_{\infty}\) under an extra condition on the Nikol’skii inequality for the \(X_N\) was proved in [13]. For completeness we present that proof here. For the reader’s convenience we recall the classical definition of the Nikol’skii inequality.

Nikol’skii-type inequalities. Let \(1\le p\le q\le\infty\) and \(X_N\subset L_q(\Omega, \mu)\). The inequality \[\label{I4} \|f\|_q \leq M\|f\|_p,\; \;\forall f\in X_N\tag{7}\] is called the Nikol’skii inequality for the pair \((p,q)\) with the constant \(M\). We will also use the brief form of this fact: \(X_N \in NI(p,q,M)\). Typically, \(M\) depends on \(N\), for instance, \(M\) can be of order \(N^{\frac{1}{p}-\frac{1}{q}}\).

We now explain how to derive inequality (6 ) from Theorem 5. For a given function class \({\mathbf{F}}\subset {\mathcal{C}}(\Omega)\) and any \(\delta>0\) find a subspace \(X_N := X_N^\delta\) such that for any \(f\in {\mathbf{F}}\) we have \[\label{kr4} d(f, X_N)_\infty \le d_N({\mathbf{F}},L_\infty) +\delta.\tag{8}\] We want to apply Theorem 5 to the subspace \(X_N\). We will do that for \(p=2\). For that we need to check that the conditions of that theorem are satisfied. Namely, assumptions A1, A2, and the assumption \(X_N\in NI(p,\infty,M)\). To satisfy those conditions we can choose the measure \(\mu\), points \(\xi^1, \dots, \xi^m\), and weights \(\mathbf{w}\). We begin with the measure \(\mu\). We use the following fundamental result of J. Kiefer and J. Wolfowitz [14], which guarantees that for any finite dimensional subspace \(X_N\) of \({\mathcal{C}}(\Omega)\) there exists a probability measure \(\mu\) on \(\Omega\) such that for all \(f\in X_N\) we have \[\label{KW} \|f\|_\infty \le N^{1/2}\|f\|_{L_2(\Omega,\mu)}.\tag{9}\] In other words, for any subspace \(X_N\) of \({\mathcal{C}}(\Omega)\) we have \(X_N \in NI(2,\infty, N^{1/2})\) with some probability measure \(\mu\). We take this measure \(\mu\) and solve the discretization problem for the \(L_2(\Omega,\mu)\) norm on the subspace \(X_N\).

We use a result on discretization from [15] (see Theorem 3.3 there), which is a generalization to the complex case of an earlier result from [16] established for the real case.

For our application we need to satisfy the assumption A2 on weights. We use the following remark from [5].

We apply Theorem 5 with \(p=2\), \(M=N^{1/2}\), \(D= c_0^{-1/2}\), \(\mathbf{w}=(\lambda_1,\dots,\lambda_m)\), \(W=C_0^{1/2}\) and obtain \[\label{kr6} \varrho_{C_1(N+1)}({\mathbf{F}},L_\infty) \le (2N^{1/2}(C_0/c_0)^{1/2}+1)(d_N({\mathbf{F}},L_\infty) +\delta),\tag{10}\] which implies (6 ).

In the inequality (6 ) we only say that the parameter \(b\) can be chosen as an absolute constant. There are results on the inequality (?? ) with \(b\) being arbitrarily close to \(1\). The first result in that direction was proved in [15].

In the same way as we obtained above an analog (6 ) of the original inequality (?? ) we can obtain the following analog of Theorem 7.

We complete this section with a brief historical comment.

Historical comments on weighted discretization. In the case of weighted discretization, namely, when instead of \(\frac{1}{m}\sum_{j=1}^m |f(\xi^j)|^2\) we use the weighted sum \(\sum_{j=1}^m\lambda_j |f(\xi^j)|^2\), the problem of discretization is solved in the sense of order in the case of real subspaces \(X_N\). It is pointed out in [17] that the paper by J. Batson, D.A. Spielman, and N. Srivastava [18] basically solves the discretization problem with weights. We present an explicit formulation of this important result in our notation.

As observed in [19] Theorem 2.13, this last theorem with a general probability space \((\Omega, \mu)\) in place of the discrete space \((\Omega_M, \mu_M)\) remains true (with other constant in the right hand side) if \(X_N\subset L_4(\Omega,\mu)\). It was proved in [16] that the additional assumption \(X_N\subset L_4(\Omega,\mu)\) can be dropped as well.

4 Some connections between the Kolmogorov widths and bilinear approximations↩︎

In this section we discuss the best \(m\)-term bilinear approximations in \(L_\mathbf{p}({\mathbb{T}}^{2d})\) of functions from different classes. Our standard notation for the best \(m\)-term bilinear approximations is the following (see Section 1) \[\sigma_m({\mathbf{F}},\Pi)_\mathbf{p}:= \sup_{f\in {\mathbf{F}}}\sigma_m(f,\Pi)_\mathbf{p}.\] Note, that in a number of papers on this topic the following notation is used as well \[\tau_m({\mathbf{F}})_\mathbf{p}:= \sigma_m({\mathbf{F}},\Pi)_\mathbf{p},\qquad \tau_m(K)_\mathbf{p}:= \sigma_m(K,\Pi)_\mathbf{p}.\] In the formulation of the known results we use the \(\tau\) notation, which is used in the corresponding papers.

We begin with a simple lemma, which was proved (in a particular case) in [9]. For completeness we present a proof here.

Some useful tricks. For bounded linear operators \(P\,:\, X\to Y\) and \(Q\,:\, Y\to Z\) acting in Banach spaces \(X\), \(Y\), \(Z\) we have the following simple inequality \[\label{KB6} d_{2n}(QP(B_X),Z) \le d_n(P(B_X),Y)d_n(Q(B_Y),Z).\tag{15}\]

Let \(H\) be a Hilbert space and \(J\,:\, H\to H\) be a compact linear operator. Then \[\label{KB7} d_n(J(B_H),H) = s_{n+1}(J).\tag{16}\]

Let \(K\in L_2(\Omega^1\times\Omega^2)\). Then the following Schmidt’s formula holds \[\label{KB8} \tau_n(K)_2 = \left(\sum_{i=n+1}^\infty s_i(J_K)^2\right)^{1/2},\tag{17}\] which implies that \[\label{KB9} s_{2n}(J_K) \le n^{-1/2}\tau_n(K)_2.\tag{18}\]

Some known results on bilinear approximation and singular numbers.

The case \(d\ge 1\). Here is the result from [20].

Here are the corresponding results for the \({\mathbf{H}}\) classes form [20].

The case \(d=1\). The case \(d=1\) is better studied than the general case. We now formulate the corresponding results. The following results are from [9]. We use the following notation for \(1\le q,p\le\infty\) \[\label{ksi} \xi(q,p):= \left(\frac{1}{q} - \max\left(\frac{1}{2},\frac{1}{p}\right)\right)_+, \quad (a)_+ :=\max(a,0).\tag{19}\]

Some known results on the Kolmogorov widths of classes \({\mathbf{W}}^K_q\).

We begin with the case of univariate functions (\(d=1\)), in which case the kernel \(K\) is a function on two variables. The following results are proved in [9].

For \(\mathbf{q}=(q_1,q_2)\), \(\mathbf{p}=(p_1,p_2)\), \(1\le q_1 \le p_1 \le \infty\), \(1\le q_2,p_2 \le \infty\) denote \[\mathbf{r}(\mathbf{q},\mathbf{p}) := \begin{cases} (1/q_1-1/p_1,(1/q_2-1/p_2)_+), & 1\le q_1\le p_1 \le 2, \\ (1/q_1,1/q_2), & 2\le q_1\le p_1\le \infty, p_1>2,\\ (1/q_1,\max(1/2,1/q_2)), & 1\le q_1<2< p_1 \le \infty. \end{cases}\]

Note that in the case \(\mathbf{r}> \mathbf{1}\) Theorem 15 follows from Lemma 1 and Theorem 13 (see also Remark 3).

In the above Theorem 14 we consider the case of classes \({\mathbf{F}}^\mathbf{r}_1\). Some results on the classes \({\mathbf{F}}^\mathbf{r}_\mathbf{q}\) are obtained in [20] (see Theorem 3.1’ there). We formulate that result as Theorem 16 and refer the reader to the paper [9] for further results and historical comments on bilinear approximation of functions on two variables with mixed smoothness. Denote \[\mathbf{r}(\mathbf{q}) := ((1/q_1-1/2)_+,(1/q_2-1/2)_+).\]

Here is an analog of Theorem 14, which holds for \(d=1\), in the case \(d>1\).

5 Some new results on the Kolmogorov widths↩︎

Theorems 2 and 3 show that in the study of linear recovery the Kolmogorov widths in the uniform norm \(L_\infty\) play an important role. In this section we focus on the case of the uniform norm and complement the results known in the case of \(L_p\), \(p\in [2,\infty)\), by the case \(p=\infty\). The following Theorem 18 is a step in that direction from the above Theorem 17.

For the future use we formulate the inequality (29 ) proved above as a separate statement.

We now prove an analog of Theorem 18 for the \({\mathbf{H}}\) classes.

6 Some relations between different asymptotic characteristics↩︎

6.1 Connections between linear recovery and nonlinear approximations↩︎

Sampling recovery. We begin with a simple inequality for the linear recovery \(\varrho_m({\mathbf{W}}^K_q,L_p)\).

For the next simple relation we need a new notation. Define for \(p_1,p_2\) \[\|f(\mathbf{x},\mathbf{y})\|_{L^*_{p_1,p_2}}:=\|f(\mathbf{x},\mathbf{y})\|^*_{p_1,p_2} := \|\|f(\mathbf{x},\cdot)\|_{p_2}\|_{p_1},\] which means that first we take the norm with respect to \(\mathbf{y}\) and after that the norm with respect to \(\mathbf{x}\).

6.2 Some inequalities↩︎

In the Section 1 we defined the systems \(\Pi={\mathcal{L}}{\mathcal{L}}\), \({\mathcal{L}}{\mathcal{K}}\), \({\mathcal{K}}{\mathcal{L}}\), and \({\mathcal{K}}{\mathcal{K}}\). In this section we only discuss the best \(m\)-term approximations with respect to some of these systems and therefore normalization of elements of these systems does not play any role. Obviously, we have the following inclusions for any \(\mathbf{p}\) \[{\mathcal{K}}{\mathcal{K}}(\mathbf{p}) \subset {\mathcal{L}}{\mathcal{K}}(\mathbf{p}) \subset \Pi(\mathbf{p}).\] These inclusions immediately imply the following trivial inequalities \[\sigma_m(K,\Pi(\mathbf{p}))_\mathbf{p}\le \sigma_m(K,{\mathcal{L}}{\mathcal{K}}(\mathbf{p}))_\mathbf{p}\le \sigma_m(K,{\mathcal{K}}{\mathcal{K}}(\mathbf{p}))_\mathbf{p}.\]

In this section we discuss the following fundamental problems.

Problem \({\mathcal{L}}{\mathcal{K}}-\Pi\). Find an upper bound for \(\sigma_m(K,{\mathcal{L}}{\mathcal{K}}(\mathbf{p}))_\mathbf{p}\) in terms of \(\sigma_n(K,\Pi(\mathbf{p}))_\mathbf{p}\) with \(n\) close to \(m\).

General Problem \({\mathcal{L}}{\mathcal{K}}-\Pi\). Find an upper bound for \(\sigma_m(K,{\mathcal{L}}{\mathcal{K}}(\mathbf{p}))_\mathbf{p}\) in terms of \(\sigma_n(K^*,\Pi(\mathbf{p}))_\mathbf{p}\) with \(n\) close to \(m\), where \(K^*\) is a new function build from \(K\). Certainly, we would like the operator mapping \(K\) to \(K^*\) to be as simple as possible. For instance, it might be a differentiation operator, which is popular in approximation theory.

We begin with a result on the Problem \({\mathcal{L}}{\mathcal{K}}-\Pi\).

We now proceed to the General Problem \({\mathcal{L}}{\mathcal{K}}-\Pi\) in the case of scalar \(p=2\).

Here is a direct corollary of Theorem 23.

Proof of Theorem 23. By Proposition 2 with \(q=2\) we find that \[\label{RI3} \sigma_m(K,{\mathcal{L}}{\mathcal{K}})_{L^*_{\infty,2}} = \varrho_m({\mathbf{W}}^K_2,L_\infty).\tag{36}\] By Theorem 3 with \({\mathbf{F}}= {\mathbf{W}}^K_2\) and \(p=\infty\) we obtain \[\label{RI4} \varrho_m({\mathbf{W}}^K_2,L_\infty) \le Cm^{1/2} d_{m/4}({\mathbf{W}}^K_2, L_\infty).\tag{37}\] By Lemma 2 we get \[\label{RI5} d_{m/4}({\mathbf{W}}^K_2,L_\infty) \le d_{m/8}({\mathbf{W}}^\mathbf{u}_2,L_\infty) d_{m/8}({\mathbf{W}}^g_2,L_2), \quad g:= K^{(u)}.\tag{38}\] By (20 ) we find \[\label{RI6} d_{m/8}({\mathbf{W}}^u_{2},L_\infty) \ll m^{-u}(\log m)^{(d-1)u+1/2}, \qquad u>1/2.\tag{39}\] Next by (16 ) and (18 ) we conclude \[\label{RI7} d_{m/8}({\mathbf{W}}^g_2,L_2) \le (m/8)^{-1/2} \sigma_{m/16}(g,\Pi)_2.\tag{40}\] Combining (36 ) – (40 ), we complete the proof of Theorem 23.

6.3 Some upper bounds↩︎

We formulate corollaries of Proposition 2, Theorems 18, 19, and Theorem 8.

V.N. Temlyakov, University of South Carolina, USA,
Steklov Mathematical Institute of Russian Academy of Sciences, Russia;
Lomonosov Moscow State University, Russia;
Moscow Center of Fundamental and Applied Mathematics, Russia.
E-mail: temlyakovv@gmail.com

References↩︎