Best approximation by ridge functions in $L_p$-spaces
We study the approximation of the classes of functions by the manifold $R_n$ formed by all possible linear combinations of $n$ ridge functions of the form $r(a · x))$. It is proved that, for any $1 ≤ q ≤ p ≤ ∞$, the deviation of the Sobolev class $W^r_p$ from the set $R_n$ of ridge functions in the...
Gespeichert in:
| Datum: | 2010 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Englisch |
| Veröffentlicht: |
Institute of Mathematics, NAS of Ukraine
2010
|
| Online Zugang: | https://umj.imath.kiev.ua/index.php/umj/article/view/2875 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Ukrains’kyi Matematychnyi Zhurnal |
| Завантажити файл: |  |
Institution
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860508866720038912 |
|---|---|
| author | Maiorov, V. E. Майоров, В. Є. |
| author_facet | Maiorov, V. E. Майоров, В. Є. |
| author_sort | Maiorov, V. E. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2020-03-18T19:39:19Z |
| description | We study the approximation of the classes of functions by the manifold $R_n$ formed by all possible linear combinations of $n$ ridge functions of the form $r(a · x))$. It is proved that, for any $1 ≤ q ≤ p ≤ ∞$, the deviation of the Sobolev class $W^r_p$ from the set $R_n$ of ridge functions in the space $L_q (B^d)$ satisfies the sharp order $n^{-r/(d-1)}$. |
| first_indexed | 2026-03-24T02:32:01Z |
| format | Article |
| fulltext |
UDC 517.5
V. E. Maiorov (Technion, Haifa, Israel)
BEST APPROXIMATION BY RIDGE FUNCTIONS
IN Lp-SPACES
НАЙКРАЩЕ НАБЛИЖЕННЯ ХРЕБТОВИМИ ФУНКЦIЯМИ
В Lp-ПРОСТОРАХ
We study the approximation of function classes by the manifold Rn formed by all possible linear combinations
of n ridge functions of the form r(a ·x)). We prove that for any 1 ≤ q ≤ p ≤ ∞, the deviation of the Sobolev
class W r
p from the set Rn of ridge functions in the space Lq(Bd) satisfies the sharp order n−r/(d−1).
Дослiджено наближення класiв функцiй многовидом Rn, що утворений усiма можливими лiнiйними
комбiнацiями n хребтових функцiй вигляду r(a · x)). Доведено, що для будь-яких 1 ≤ q ≤ p ≤ ∞ вiд-
хилення класу Соболєва W r
p вiд множини Rn хребтових функцiй у просторi Lq(Bd) характеризується
точним порядком n−r/(d−1).
1. Introduction. In this work we continue the study of approximation of multivariate
functions by classes consisting of linear combinations of ridge functions started in
[9, 10, 11, 5]. Ridge functions are defined as functions on Rd of the form r(a · x),
with the parameters a ∈ Rd, r : R → R and a · x is the usual inner product. Let
Lq = Lp(B
d), 1 ≤ q ≤ ∞, be Banach space of all q-integrable functions on the unite
ball Bd = {|x| ≤ 1}, where |x|2 = x2
1 + . . .+ x2
d, with the norm
‖f‖q =
∫
Bd
|f(x)|q dx
1/q
.
Let A be a set on the unit sphere Sd−1 = {|x| = 1} in Rd. Introduce the set of ridge
functions
R(A) =
{
ra := r(a · x) : r ∈ L2,loc(R), a ∈ A
}
,
where r runs over the class L2,loc(R) of square integrable functions on all compact
subsets of R, and a runs over A. We denote R = R(Sd−1). Let n be a natural number.
Consider the class of functions
Rn = R+ . . .+R,
consisting of all possible linear combinations of n functions from the set R.
Approximation by ridge functions has been studied by several authors. In the works
[26] and [6] necessary and sufficient conditions are found on a set A in order that the
closure of the set R(A) coincides with the space of continuous functions. In addition,
Lin and Pinkus [7] proved that for any fixed n the set Rn is not dense in the spaces of
continuous functions on a compact sets. The approximation properties of ridge manifolds
were studied by Barron [1], DeVore, Oskolkov and Petrushev [2], Maiorov [9], Maiorov
and Meir [12]. Makovoz [14], Mhaskar and Micchelli [16], Mhaskar [15], Oskolkov
[17], Petrushev [18], Pinkus [19], Temlyakov [21]. In Gordon, Maiorov, Meyer and
Reisner [5] the results about best approximation by ridge functions in the Banach space
Lp are considered.
c© V. E. MAIOROV, 2010
396 ISSN 1027-3190. Укр. мат. журн., 2010, т. 62, № 3
BEST APPROXIMATION BY RIDGE FUNCTIONS IN Lp-SPACES 397
In this work we consider the problems of best approximation of multivariate functions
from the Sobolev classes W r
p by the class Rn in the space Lq, where the parameters
p, q satisfy 1 ≤ q ≤ p ≤ ∞. Earlier, the asymptotical estimates of approximation by Rn
were studied in [5, 9], but only for 2 ≤ q ≤ p ≤ ∞.
Let ρ = (ρ1, . . . , ρd) be a multiindex vector, that is, ρ is the vector with nonnegative
integer coordinates, |ρ| = ρ1 + . . . + ρd. Introduce the differential operator Dρ =
= ∂|ρ|/∂ρ1x1 . . . ∂
ρdxd.
Let r be any natural number. We consider in the space Lp = Lp(B
d) the Sobolev
[23] class of functions
W r
p :=
f : ‖f‖W r
p
:= ‖f‖p +
∑
|ρ|=r
‖Dρf‖p ≤ 1
.
For subsets W,V ⊂ Lq we define the deviation of W from V by
e(W,V )q = sup
f∈W
e(f, V )q,
where e(f, V )q = inf
v∈V
‖f − v‖q.
Theorem 1. Let d ≥ 2, r > 0 and 1 ≤ p ≤ q ≤ ∞ be any numbers. Then for the
deviation of the Sobolev class W r
p from the class Rn the asymptotic inequality holds
e(W r
p , Rn)q � n−r/(d−1).
We describe briefly the proof of the Theorem 1. In order to obtain the lower bound
in Theorem 1, we construct for any n a function f ∈ W r
p depending on n such that
the distance of f from the class Rn is greater than cn−r/(d−1). The construction of the
function f will be done in the following way. In Section 2 we introduce an orthonormal
system
{
Pk(x)
}∞
k=1
of polynomials on the ball Bd and study the Fourier coefficients
〈ra, Pk〉 of ridge function r(a ·x) respect to the system
{
Pk(x)
}
. In particular, we show
that the coefficients allow the separation of variables r and a (see [13, 9, 10]), namely for
any k the identity holds 〈ra, Pk〉 = u(a)v(r), where u and v are some function of a and
linear functional of r, respectively. In Section 3 we estimate the Vapnik – Chervonenkis
dimension of the projection PrsRn of the class of ridge functions Rn to the polynomial
space Pds . In Section 4 we prove Theorem 1 using the results of Sections 2, 3. In the
Appendix we present well-known results from the theory of orthogonal polynomials on
the segment and from the theory of harmonic analysis on the sphere, which we use in
the proofs of Theorem 1.
In the rest of this paper notations like c, c′, c0, c1, . . . , etc. denote positive constants
which do not depend on the parameter n and may depend only on r, d, p, or q. For two
positive sequences {an} and {bn}, n = 0, 1, . . . we write an � bn if there exist positive
constants c1 and c2 such that c1 ≤ an/bn ≤ c2 for all n = 0, 1, . . . .
2. Projection of Rn to the polynomial space. In this section we construct speci-
al orthonormal systems of polynomials on the unit ball Bd. Orthogonal systems of
polynomials on the ball play the important part in problems of approximations of multi-
variable functions by manifolds of linear combinations of ridge functions (the plane
waves) (see [2, 18, 9, 10]). In the works [2, 18] these methods were developed for the
construction of orthogonal projections on polynomial subspaces and approximation by
ISSN 1027-3190. Укр. мат. журн., 2010, т. 62, № 3
398 V. E. MAIOROV
ridge functions. The system of Gegenbauer orthogonal polynomials is the main tool used
in the construction of orthogonal systems of polynomials on the ball [8]. Note, in parti-
cular, that in the case d = 2, these Gegenbauer polynomials coincide with Chebyshev
polynomials of second kind.
In our work the system of orthogonal polynomials on the unit ball is obtained, in a
sense, by the convolution of two orthogonal systems. These are the system of Gegenbauer
polynomials on the segment [−1, 1], and the system of spherical harmonics on the unit
sphere Sd−1. We describe this construction.
Let L2(Sd−1) be the Hilbert space consisting of all the complex-valued square-
integrable functions h(ξ) on the sphere Sd−1 with the inner product
(h1, h2) =
∫
Sd−1
h1(ξ)h̄2(ξ)dξ, h1, h2 ∈ L2(Sd−1),
where by dξ we denote the normalized Lebesgue measure on the sphere Sd−1.
Consider (see the Appendix) in the space L2(Sd−1) the subspace H consisting of
the restrictions on Sd−1 of the harmonic functions on Rd. Let Hs be the subspace in H
generated by all spherical harmonics of degree at most s, i.e., all harmonic polynomials
of degree at most s. Let Hhom
s be the subspace of Hs formed by all homogeneous
spherical harmonics of degree s. The functions {hsk}k∈Ks (see Appendix) generate a
basis in the space Hhom
s .
The space Hs = Hhom
0 ⊕ Hhom
1 ⊕ . . . ⊕ Hhom
s is the direct sum of the orthogonal
subspaces of the spherical harmonics of degrees 0, 1, . . . , s. Denote by Ns the dimension
of the space Hs. We have Ns � sd−1. Indeed, using the relation dim Hhom
s � sd−2
(see (A.2)) we obtain
Ns = dim Hs = dim Hhom
0 + dim Hhom
1 + . . .+ dim Hhom
s � sd−1.
We introduce in the space H the family of functions B(Sd−1) := {hi}∞i=0 consisting
(see (A.2)) of all ordered spherical harmonics, that is, the functions
∞⋃
s=0
{hs,k}k∈Ks ,
where Ks is defined in Appendix. The set B(Sd−1) is an orthonormal basis in the space
H, i.e., for indices i 6= i′ we have (hi, hi′) = δii′ , where δii′ = 0 for i 6= i′, and δii = 1.
Now we consider (see Appendix) the Gegenbauer polynomials Cd/2n (t), t ∈ R, of
degree n associated with d/2. We norm the polynomial Cd/2n by a factor, i.e., we set
un(t) = v−1/2
n Cd/2n (t), vn =
π1/2(d)nΓ ((d+ 1)/2)
(n+ d/2)n!Γ(d/2)
,
where (a)0 = 1, and (a)n = a(a+ 1) . . . (a+ n− 1).
Let i and j be two arbitrary indices from Z+. Construct on Rd the function
Pij(x) = νj
∫
Sd−1
hi(ξ)uj(x · ξ)dξ, νj =
(
(j + 1)d−1
2(2π)d−1
)1/2
. (1)
ISSN 1027-3190. Укр. мат. журн., 2010, т. 62, № 3
BEST APPROXIMATION BY RIDGE FUNCTIONS IN Lp-SPACES 399
From (1) we see that for any i, j ∈ Z+ the function Pij is a polynomial on Rd of degree
j. Note that if the indices i and j are such that the degrees of the polynomials hi and uj
satisfy the inequality deg hi > deg uj = j, then Pij(x) ≡ 0 (see (A.8)). Let the set I
consists of the couples of nonnegative integers (i, j) such that deg hi ≤ j and a parity
of numbers deg hi and j are equal. Let Is be the subset in I consisting of the couples
(i, j) with deg hi ≤ j ≤ s. Construct the system of polynomials
Π := Π(Bd) := {Pij}(i,j)∈I . (2)
We consider in the system Π the finite subsystem Πs = {Pij}(i,j)∈Is consisting of
polynomials of degree at most s.
Lemma 1 (see [10]). a) The polynomial set Πs is an orthonormal basis in the space
of polynomials Pds .
b) The set of polynomials Π(Bd) is a complete orthonormal system of functions in
the space L2(Bd).
Let a ∈ Sd−1 be any unit vector and let A be an orthogonal matrix such that a = Ae,
where e = (1, 0, . . . , 0). Let A∗ be the adjoint matrix to A. We denote a∗ = A∗e.
Lemma 2. Let ra = r(a · x) be any ridge function from the class R. Then any
Fourier coefficient of the function ra with respect to the orthonormal system Πs = {Pij}
admits separation of the variables a and r, that is can be represented as
〈ra, Pij〉 = hi(a
∗) r̂j ,
where
r̂j =
∫
I
r(t)uj(t)wd/2(t) dt
is the j-th coefficient of Fourier – Gegenbauer of the function r.
Proof. By the invariance of the measures dx and dξ relative to the rotation in Rd
and Sd we have∫
Bd
r(a · x)Pij(x) dx = νj
∫
Bd
r(a · x) dx
∫
Sd−1
hi(ξ)uj(ξ · x) dξ =
= νj
∫
Bd
r(e · x) dx
∫
Sd−1
hi(A
∗ξ)uj(ξ · x) dξ =
= νj
∫
Sd−1
hi(A
∗ξ) dξ
∫
Bd
r(e · x)uj(ξ · x) dx.
Decompose the function r to the Fourier – Gegenbauer serious r(t) =
∑∞
k=0
r̂kuk(t) in
the space L2(I, w). Using the properties (A.2) and (A.3) from Appendix we obtain∫
Bd
r(e · x)uj(ξ · x) dx =
∞∑
k=0
r̂k
∫
Bd
uk(e · x)uj(ξ · x) dx =
= r̂j
∫
Bd
uj(e · x)uj(ξ · x) dx = r̂j
uj(e · ξ)
uj(1)
.
ISSN 1027-3190. Укр. мат. журн., 2010, т. 62, № 3
400 V. E. MAIOROV
It follows from the property (A.4) that
νj
∫
Sd−1
hi(A
∗ξ) dξ
∫
Bd
r(e · x)uj(ξ · x) dξ =
=
νj r̂j
uj(1)
∫
Sd
hi(A
∗ξ)uj(e · ξ) dx = r̂jhi(A
∗e).
The lemma is proved.
Denote bym = dimPds the dimension of the space Pds . Let r(x) =
∑n
k=1
rk(ak ·x)
be any function from the ridge functions classRn. Consider the projection of the function
r to the space Pds
Prsr(x) :=
∑
Pij∈Πs
〈r, Pij〉Pij(x). (3)
According to Lemma 2 we can write
Prsr(x) =
n∑
k=1
∑
Pij∈Πs
hi(a
∗
k) r̂kjPij(x), (4)
where r̂kj is the j-th coefficient of Fourier – Gegenbauer of the function gk.
3. Vapnik – Chervonenkis dimension of the class PrsRn. We recall the notions of
Vapnik – Chervonenkis dimension (in details see [24]). Consider the function sgn a = 1,
if a ≥ 0, and sgn a = −1, if a < 0. For a vector h = (h1, . . . , hn) in Rn, we denote
by sgnh the vector (sgnh1, . . . , sgnhn). Let H = {h} be a set of real-valued functions
defined on Rd. By sgnH we denote the set of all vectors {sgnh}, h ∈ H.
Definition. The Vapnik – Chervonenkis dimension dimV C H of a functions set
H = {h} is defined as the maximal natural number m such that there exists a
collection {ξ1, . . . , ξm} in Rd such that the cardinality of the sgn vectors set S =
= {(sgnh(ξ1), . . . , sgnh(ξm)) : h ∈ H} is equal to 2m. That is, the set S coincides
with the set of all vertices of the unit cube in the space Rm.
Let {ξ1, . . . , ξm} be any collection of points in Rd. Consider the set of vectors in Rd
Πm,s,n =
{
(P (ξ1 + t), . . . , P (ξm + t)) : P ∈ PrsRn, t ∈ Rd
}
.
We will need to estimate the cardinality |sgn Πm,s,n| of the sign vectors set sgn Πm,s,n.
To this end we use the following result.
Lemma 3 ([9], Lemma 3). Let m, s, l and q be any natural numbers such that
l + q ≤ m/2. Let παβ(σ), α = 1, . . . ,m, β = 1, . . . , q be any fixed polynomials with
real coefficients in the variables σ ∈ Rl, each of degree 2s. Construct m polynomials in
the l + q variables b ∈ Rq and σ ∈ Rl
πα(b, σ) =
q∑
β=1
bβπαβ(σ), α = 1, . . . ,m. (5)
Construct in Rm a polynomial manifold
Π∗m,s,l,q =
{
(π1(b, σ), . . . , πm(b, σ)) : (b, σ) ∈ Rq × Rl
}
.
ISSN 1027-3190. Укр. мат. журн., 2010, т. 62, № 3
BEST APPROXIMATION BY RIDGE FUNCTIONS IN Lp-SPACES 401
Then for the cardinality of the set sgn Π∗m,s,p,q the following estimate holds:
∣∣sgn Π∗m,s,l,q
∣∣ ≤ (4s)l(l + q + 1)l+2
(
2em
l + q
)l+q
.
Lemma 4. There exist absolute constants c0, c1 and c2 such that
c0n ≤ sd−1 ≤ 2c0n, c1s
d ≤ m ≤ c2sd,
and the cardinality of the set sgn Πm,s,n satisfies the inequality
|sgn Πm,s,n| ≤ 2cm,
where c ≤ 1/4 is some absolute constant.
Proof. Consider the polynomial space Pds with the orthonormal basis Πs =
= {Pi,j}(i,j)∈Is Let P ∈ PrsRn be any polynomial. Then
P (x) =
∑
(i,j)∈Is
〈r, Pij〉Pij(x), (6)
where the function r(x) =
∑n
k=1
rk(ak · x) belongs to the manifold Rn. We will
show that for every point ξ ∈ Rd the polynomial P (ξ + t) can be represented as a
linear combination of polynomials on the variables a∗1, . . . , a
∗
n and t. It follows from the
identity (4)
P (x) =
n∑
k=1
∑
(i,j)∈Is
hi(a
∗
k)r̂kjPij(x). (7)
Recall that the set Is consists of the couples (i, j) from the set I satisfying deg hi ≤
≤ j ≤ s. For every j introduce the set Ijs consisting of all numbers i such that
deg hi = j. Then the polynomial P (x) can be written as
P (x) =
n∑
k=1
s∑
j=1
r̂kj
∑
i∈Ijs
hi(a
∗
k)Pij(x). (8)
Since {Pi,j}(i,j)∈Is is an orthonormal basis in the space Pds then for every t there is a
nondegenerate matrix
Γ(t) =
{
γi
′j′
ij (t)
}
(i,j),(i′,j′)∈Is
,
where (i, j) and (i′, j′) are the column and row indexes, respectively, of the matrix Γ(t),
such that
Pij(ξ + t) =
m∑
(i′,j′)∈Is
γi
′j′
ij (t)Pi′j′(ξ). (9)
Note that all the functions γi
′j′
ij (t) are polynomials from the space Pds . Hence, from (8)
and (9) we obtain
P (ξ + t) =
n∑
k=1
s∑
j=1
r̂kj
∑
i∈Ijs
∑
(i′,j′)∈Is
γi
′j′
ij (t)hi(a
∗
k)Pi′j′(ξ). (10)
ISSN 1027-3190. Укр. мат. журн., 2010, т. 62, № 3
402 V. E. MAIOROV
We enumerate the set
{
(k, j) : 1 ≤ k ≤ n, 1 ≤ j ≤ s
}
in {β = 1, . . . , q}, where q = ns
and we put bβ = r̂kj . For every point ξα, α = 1, . . . ,m and index β = 1, . . . , ns we
define the function on R(d+1)n
παβ(a∗1, . . . , a
∗
n, t) =
∑
i∈Ijs
∑
(i′,j′)∈Is
γi
′j′
ij (t)hi(a
∗
k)Pi′j′(ξα).
Then the identity (10) can be written as
P (ξ + t) =
q∑
β=1
bβπαβ(a∗1, . . . , a
∗
n, t), α = 1, . . . ,m.
Introduce the variables σ = (a∗1, . . . , a
∗
n, t) which belong to the polynomial space P l2s
with l = (d+ 1)n. Thus the vector set Πm,s,n belongs to the set Π∗m,2s,l,q with q = sn.
From here and Lemma 3 we obtain
|sgn Πm,2s,n| ≤ (8s)l(l + q + 1)l+2
(
2em
l + q
)l+q
. (11)
Let c0 and c1 < c2 be a positive numbers with we will choose below. We assume the
numbers m, s, l satisfy the conditions
c0n ≤ sd−1 ≤ 2c0n, c1s
d ≤ m ≤ c2sd and l = (d+ 1)n. (12)
Substituting these conditions to the inequality (11) we complete Lemma 4.
From Lemma 4 we directly obtain the following consequence.
Consequence 1. The Vapnik – Chervonenkis dimension of the polynomial class
PrsRn satisfies the estimate
dimV C PrsRn ≤ l log2(4s) + (l + 2) log2(l + q + 1) + (l + q) log2
(
2em
l + q
)
.
4. Approximation of the class Pd
s by ridge functions. Let Ω =
[
− 1√
d
,
1√
d
]d
be
the cube which belongs to the unit ball Bd. We define the function on Rd
ω(x) =
1, x ∈ 1
2
Ω,
0, x ∈ Rd \ Ω,
and continue it on the space Rd such that ω belongs to the classW r
∞(Rd) and 0 ≤ ω(x) ≤
≤ 1 for all x ∈ Rd. Let λ and m be any natural numbers such that m1/d ≤ λ ≤ 2m1/d.
Consider the lattice subset in the cube Ω consisting of m points
Ξm =
{(
i1 + 1/2√
d λ
, . . . ,
id + 1/2√
d λ
)
: i1, . . . , id = −λ, . . . , λ− 1
}
.
Let ξ1, . . . , ξm be the points of the set Ξm. Introduce the set
Em =
{
ε = (ε1, . . . , εm) : εi = ±1, i− 1, . . . ,m
}
of sign vectors in Rm. Consider the collection of function
ISSN 1027-3190. Укр. мат. журн., 2010, т. 62, № 3
BEST APPROXIMATION BY RIDGE FUNCTIONS IN Lp-SPACES 403
Fm =
{
fε(x) := (2λ)−r
m∑
i=1
εiω (2λ(x− ξi)) : ε ∈ Em
}
.
Obviously, every function fε from Fm belongs to the Sobolev class W r
∞. Denote by gε
the polynomial of best approximation of the function fε by the space Pds in L∞-norm,
that is satisfying
‖fε − gε‖∞ = min
g∈Pd
s
‖fε − g‖∞.
We know [22] that the error of the best approximation of any function f ∈ W r
∞ from
the polynomial space Pds in the L∞-norm is bounded above as follows,
‖fε − gε‖∞ ≤ cs−r.
Hence we have the next result.
Proposition 1. Consider the set of polynomials
Gms = {gε : ε ∈ Em}.
Then the deviation of the set Fm from the space Gms satisfies
e(Fm, Gms )∞ ≤ cs−r.
Let Q be a set of functions in the space L(Bd). Denote by PrsQ = {Prsq : q ∈ Q}
the projection of a set Q to the subspace Pds .
Lemma 5. Let 1 ≤ q ≤ ∞ be any number and P ∈ Pds be any polynomial. Then
e(P,Rn)q ≥ e(P,PrsRn)q.
Proof. We have
e(P,Rn)q = inf
ri∈L2,loc(R), ai∈Rd
∥∥∥∥∥P (x)−
n∑
i=1
ri(ai · x)
∥∥∥∥∥
q
. (13)
We fix the set of vectors a = {a1, . . . , an} and consider the linear subspace of functions
Un(a) :=
{
u =
n∑
i=1
ui(ai · x) : ui ∈ L2,loc(R)
}
.
Let Un(a)⊥ =
{
v ∈ Lq : 〈v, u〉 = 0 for all u ∈ Un(a)
}
be the annihilator subspace in
Lq for the subspace Un(a). Define the number q′ such that 1/q + 1/q′ = 1. Using the
duality in the space Lq we have
inf
u∈Un(a)
‖P − u‖q = sup
v∈Un(a)⊥, ‖v‖q′≤1
〈P, v〉 ≥ sup
v∈Un(a)⊥∩Pd
s , ‖v‖q′≤1
〈P, v〉.
Since
Un(a)⊥ ∩ Pds =
{
v ∈ Pds : 〈v, Un(a)〉 = 0
}
=
{
v : 〈v,Prs Un(a))〉 = 0
}
,
then using once more the duality in the space Pds , we obtain
ISSN 1027-3190. Укр. мат. журн., 2010, т. 62, № 3
404 V. E. MAIOROV
e(P,Un(a))q ≥ sup
v∈PrsUn(a)⊥∩Pd
s , ‖v‖q′≤1
〈P, v〉 = inf
h∈Prs Un(a)
‖P − h‖q. (14)
It follows from (13) and (14) that
e(P,Rn)q = inf
a1,...,an
e(P,Un(a))q ≥
≥ inf
a1,...,an
inf
h∈PrsUn(a)
‖P − h‖q = e(P,PrsRn)q.
Lemma 5 is proved.
5. Proof of Theorem 1. Consider the space lm1 consisting of vectors x ∈ Rm
equipped with the norm ‖x‖lm1 = |x1| + . . . + |xm|. In the space lm1 we consider
the subset Em =
{
ε : ε1, . . . , εm = ±1
}
. The following lemma is proved in [9]. For
completeness we cite its proof.
Lemma 6. Assume that all conditions of Lemma 4 are satisfied. Then there is a
vector ε∗ ∈ Em such that
e(ε∗,Πm,s,n)lm1 := inf
x∈Πm,s,n
‖ε∗ − x‖lm1 ≥ am,
where a is an absolute and strictly positive constant.
Proof. Let a < 1 be the absolute constant satisfying the equation 1 − 1
2
(1 −
− 2a)2 log2 e =
47
64
(i.e., a = 0.19 . . .). Set Π = sgn Πm,s,n. Let π be any vector from
Π. Consider the subset in Em
Eπ =
{
ε ∈ Em :
m∑
i=1
|εi − πi| ≤ 2am
}
.
Since πi = ±1 we have the estimate for cardinality of the set Eπ
|Eπ| =
∣∣∣∣∣
{
ε ∈ Em :
m∑
i=1
(εi + 1) ≤ 2am
}∣∣∣∣∣ =
=
∣∣∣∣∣
{
ε :
∑
i : εi=1
1 ≤ am
}∣∣∣∣∣ =
[am]∑
i=0
(
m
i
)
.
From the well-known estimate (see, for example, [3], Chapter 8) we have
[am]∑
i=0
(
m
i
)
≤ 2me−2m(1/2−β)2 ≤ 2bm,
where β = m−1[am], and b = 1 − 1
2
(1 − 2a)2 log2 e =
47
64
. Hence |Eπ| ≤ 247m/64.
Consider in Em the subset E′ =
⋂
π∈Π(Em \ Eπ). We estimate the cardinality of E′
via
|E′| =
∣∣∣∣∣Em \ ⋃
π∈H
Eπ
∣∣∣∣∣ ≥ 2m − |Π|max
π∈Π
|Eπ| ≥ 2m − |Π|2(47/64)m. (15)
By Lemma 4 we have |Π| ≤ 2m/4. From this and (15) we obtain |E′| ≥ 2m−2(63/64)m >
> 0. Therefore there exists a vector ε∗ such that for every vector π ∈ Π the following
inequality holds:
ISSN 1027-3190. Укр. мат. журн., 2010, т. 62, № 3
BEST APPROXIMATION BY RIDGE FUNCTIONS IN Lp-SPACES 405
‖ε∗ − π‖lm1 ≥ 2am.
From here we obtain the inequality
e(ε∗,Πm,s,n)lm1 ≥
1
2
e(ε∗, sgn Πm,s,n)lm1 ≥ am.
Lemma 6 is proved.
Lemma 7. Assume the natural numbers m, s and n satisfy the conditions of
Lemma 4. Then there is a fε∗ ∈ Fm such that
e(fε∗ ,PrsRn)1 ≥ c3n−r/(d−1),
where c3 is an absolute and strictly positive constant.
Proof. Let fε and P be any functions from the sets Fm and PrsRn, respectively.
We have
‖fε − P‖1 ≥
∫
Ω
|fε(x)− P (x)|dx =
∫
Ω/(2λ)
m∑
i=1
∣∣fε(ξi + t)− P (ξi + t)
∣∣dt.
Define the function ω̄(t) = (2λ)−rω(2λ t). Since fε(ξi + t) = ω̄(t)εi for every vector
ε, then for any t from the cube Ω/(2λ) we have
m∑
i=1
∣∣fε(ξi + t)− P (ξi + t)
∣∣ ≥ inf
P∈PrsRn, τ∈Rd
m∑
i=1
∣∣ω̄(t)εi − P (ξi + τ)
∣∣ =
= inf
P∈PrsRn, τ∈Rd
ω̄(t)
m∑
i=1
∣∣εi − P (ξi + τ)
∣∣.
Thus we obtain
‖fε − P‖1 ≥
1
m
inf
t∈Ω/(2λ)
∣∣ω̄(t)
∣∣ inf
P∈PrsRn, τ∈Rd
m∑
i=1
∣∣εi − P (ξi + τ)
∣∣ ≥
≥ c3
(2λ)rm
e(ε,Πm,s,n, l
m
1 ).
Recall (see (12)) that the numbers m, s, n satisfy the conditions c0n ≤ sd−1 ≤ 2c0n,
c1s
d ≤ m ≤ c2s
d and m1/d ≤ λ ≤ 2m1/d. Applying Lemma 6 we obtain that there is
a function fε∗ ∈ Fm satisfying
‖fε∗ − P‖1 ≥
c3a
(2λ)r
≥ c4n−r/(d−1), c4 =
c3a
c
r/d
2 (2c0)r
,
for any polynomial P ∈ PrsRn.
Lemma 7 is proved.
Lemma 8. The deviation of the set Fm from the class Rn satisfies
e(Fm, Rn)1 ≥ c4n−r/(d−1).
Proof. Let f ∈ Fm be any function. According to Proposition 1 there is a polynomial
g ∈ Gms that
‖f − g‖∞ ≤ cs−r. (16)
ISSN 1027-3190. Укр. мат. журн., 2010, т. 62, № 3
406 V. E. MAIOROV
Using Lemma 5 and twice the inequality (16) we obtain
e(Fm, Rn)1 ≥ e(Gms , Rn, L1)− cs−r ≥
≥ e(Gms ,PrsRn)1 − cs−r ≥ e(Fm,PrsRn)1 − 2cs−r.
We choose c2 and c0 such that c4 > 2c. Then it follows from Lemma 7 that
e(Fm, Rn)1 ≥ c4n−r/(d−1) − 2cs−r � n−r/(d−1).
Lemma 8 is proved.
Now we prove Theorem 1. We know that the collection of functions Fm belongs to
the class W r
∞. Therefore, using Hölder’s inequality for 1 ≤ q ≤ p ≤ ∞ and Lemma 8,
we obtain
e(W r
p , Rn)q ≥ e(W r
∞, Rn)1 ≥ e(Fm, Rn)1 ≥ cn−r/(d−1).
The upper bound
e(W r
p , Rn)q ≤ cn−r/(d−1)
was proved in the paper [9].
Theorem 1 is completely proved.
6. Appendix. We discuss some well-known results connected with orthogonal
polynomials, which we use in this present work.
The Gegenbauer polynomials. The Gegenbauer polynomials are usually defined
via the generating function
(1− 2tz + z2)−λ =
∞∑
k=0
Cλk (t)zk,
where |z| < 1, |t| < 1, and λ > 0. The coefficients Cλk (t) are algebraic polynomials of
degree k and are termed the Gegenbauer polynomials associated with λ.
The Gegenbauer polynomials possess the following properties:
1. The family of polynomials {Cλk } is a complete orthogonal system for the wei-
ghted space L2(I, w), I = [−1, 1], w(t) := wλ(t) := (1− t2)λ−1/2, and∫
I
Cλm(t)Cλn(t)w(t)dt =
{
0, m 6= n,
vn,λ, m = n,
with vn,λ :=
π1/2(2λ)nΓ(λ+ 1/2)
(n+ λ)n!Γ(λ)
,
(A.1)
where we use the usual notation (a)0 := 0, (a)N := a(a+ 1) . . . (a+N − 1).
2. Let Pn denote the set of all algebraic polynomials of total degree n in d real vari-
ables. Set un(t) = v
−1/2
n C
d/2
n (t), where vn =
π1/2(d)nΓ ((d+ 1)/2)
(n+ d/2)n!Γ(d/2)
. The polynomials
un(ξ · x), ξ ∈ Sd−1, are in Pn and the un(ξ · x) are orthogonal to Pn−1 in L2(Bd)
(see [18]): ∫
Bd
un(ξ · x)p(x)dx = 0 ∀ξ ∈ Sd−1 and ∀p ∈ Pn−1. (A.2)
ISSN 1027-3190. Укр. мат. журн., 2010, т. 62, № 3
BEST APPROXIMATION BY RIDGE FUNCTIONS IN Lp-SPACES 407
3. For each ξ, η ∈ Sd−1 we have (see [18])∫
Bd
un(ξ · x)un(η · x)dx =
un(ξ · η)
un(1)
. (A.3)
4. For each polynomial h(x) ∈ Pn such that h(x) = (−1)nh(−x) for all x ∈ Rd
we have (see [18])∫
Sd−1
h(ξ)un(ξ · η)dξ =
un(1)
νn
h(η), where νn =
(n+ 1)d−1
2(2π)d−1
. (A.4)
An orthogonal system of polynomials on the sphere. We state some facts (see
[4, 25, 20]) from the theory of harmonic analysis on the sphere. Let s be any positive
integer. Consider a space Hs consisting of the homogeneous harmonic polynomials of
degree s in the d variables x1, . . . , xd. Any polynomial from Hs is decomposable by a
linear combination of polynomials of the form
hsk(x) = Ask
d−2∏
j=o
r
kj−kj−1+1
d−j C
d−j−2
2 +kj+1
kj−kj+1
(
xd−j
rd−j
)
(x2 ± ix1)kd−2 , (A.5)
where r2
d−j = x2
1 + . . .+ x2
d−j . The vector k with integer coordinates belongs to the set
Ks =
{
k = (k0, k1, . . . , kd−3, εkd−2) : 0 ≤ kd−2 ≤ . . . ≤ k1 ≤ k0 = s, ε = ±1
}
,
and Ask is the normalization factor. It is known that the dimension of the space Hs is
given by
dimHs = |Ks| =
(
s+ d− 1
s
)
−
(
s+ d− 3
s− 2
)
, (A.6)
if s ≥ 2, and dimH0 = 1, dimH1 = d. It is easy to verify that the dimension of Hs is
asymptotically given by
dimHs =
(
2 +
2
(d− 2)!
+ c(s, d)
)
s(s+ 1) . . . (s+ d− 3) � sd−2, (A.7)
where 0 ≤ c(s, d) ≤ 1 is some function depending only on s and d.
The family of functions {hsk}k∈Ks is an orthonormal system in the spaceL2(Sd−1),
i.e., for any multiindices k, k′ ∈ Ks, the following holds:
(hsk, hsk′) =
∫
Sd−1
hsk(ξ)hsk′(ξ)dξ = δkk′ . (A.8)
Note that the spaces Hs and Hs′ for s 6= s′ are orthogonal with respect to the inner
product (A.8). The family of functions
⋃∞
s=0{hsk}k∈Ks is a complete orthonormal
system in the space L2(Sd−1).
The set of polynomials on the sphere {p : p ∈ Pn} of degree ≤ n is contained in
the space H0 ⊕ H1 ⊕ . . . ⊕ Hn, which is the direct sum of the orthogonal subspaces
H0,H1, . . . ,Hn. From the above it follows that for any polynomial p ∈ Pn and for any
function h ∈ Hn+1 ⊕Hn+2 ⊕ . . . the equality
ISSN 1027-3190. Укр. мат. журн., 2010, т. 62, № 3
408 V. E. MAIOROV∫
Sd−1
p(ξ)h(ξ)dξ = 0
holds.
1. Barron A. R. Universal approximation bounds for superposition of a sigmoidal function // IEEE Trans.
Inform. Theory. – 1993. – 39. – P. 930 – 945.
2. DeVore R. A., Oskolkov K., Petrushev P. Approximation by feed-forward neural networks // Ann. Numer.
Math. – 1997. – 4. – P. 261 – 287.
3. Devroye L., Györfy L., Lugosi G. A probabilistic theory of pattern recognition. – New York: Springer
Verlag, 1996.
4. Erdelyi A., ed. Higher transcendental functions. Vol. 2. Bateman manuscript project. – New York, N. Y.:
McGraw Hill, 1953.
5. Gordon Y., Maiorov V., Meyer M., Reisner S. On best approximation by ridge functions in the uniform
norm // Constr. Approxim. – 2002. – 18. – P. 61 – 85.
6. Lin V. Ya., Pinkus A. Fundamentality of ridge functions // J. Approxim. Theory. – 1993. – 75. – P. 295 –
311.
7. Lin V. Ya., Pinkus A. Approximation of multivariate functions // Adv. Comput. Math. – World Sci.
(Singapore), 1994. – P. 257 – 265.
8. Logan B., Shepp L. Optimal reconstruction of functions from its projections // Duke Math. J. – 1975. –
42. – P. 645 – 659.
9. Maiorov V. On best approximation by ridge functions // J. Approxim. Theory. – 1999. – 99. – P. 68 – 94.
10. Maiorov V. On best approximation of classes by radial functions // Ibid. – 2003. – 120. – P. 36 – 70.
11. Maiorov V., Meir R., Ratsaby J. On the approximation of functional classes equipped with a uniform
measure using ridge functions // Ibid. – 1999. – 99. – P. 95 – 111.
12. Maiorov V., Meir R. On the near optimality of the stochastic approximation of smooth functions by
neural networks // Adv. Comput. Math. – 2000. – 13. – P. 79 – 103.
13. Maiorov V., Oskolkov K. I., Temlyakov V. N. Gridge approximation and Radon compass // Approxim.
Theory (a Volume dedicated to Blagovest Sendov / Ed. B. Bojanov. – Sofia: DARBA, 2002. – P. 284 – 309.
14. Makovoz Y. Random approximation and neural networks // J. Approxim. Theory. – 1996. – 85. –
P. 98 – 109.
15. Mhaskar H. N. Neural networks for optimal approximation of smooth and analytic functions // Neural
Comput. – 1996. – 8. – P. 164 – 177.
16. Mhaskar H. N., Micchelli C. A. Dimension independent bounds on the degree of approximation by
neural networks // IBM J. Research and Development. – 1994. – 38. – P. 277 – 284.
17. Oskolkov K. I. Ridge approximation, Chebyshev – Fourier analysis and optimal quadrature formulas //
Proc. Steklov Inst. Math. – 1997. – 219. – P. 265 – 280.
18. Petrushev P. P. Approximation by ridge functions and neural networks // SIAM J. Math. Anal. – 1998.
– 30. – P. 291 – 300.
19. Pinkus A. Approximation by ridge functions, some density problems from neutral networks // Surface
Fitting and Multiresolution Method. – 1997. – 2. – P. 279 – 292.
20. Stein E. M., Weiss G. Introduction to Fourier analysis on Euclidean spaces. – Princeton, New Jersey,
1971.
21. Temlyakov V. On approximation by ridge functions. – Preprint.
22. Timan A. F. Theory of approximation of function of the real variable. – New York: Macmillan Co., 1963.
23. Tribel H. Interpolation theory function spaces, differential operators. – Berlin: Veb Deutscher Verlag
Wissenschaften, 1978.
24. Vapnik V., Chervonkis A. Necessary and sufficient conditions for the uniform convergence of empirical
means to their expectations // Theory Probab. Appl. – 1981. – 3. – P. 532 – 553.
25. Vilenkin N. Ya. Special functions and a theory of representation of group. – Moscow: Fizmatgiz, 1965.
26. Vostrecov B. A., Kreines M. A. Approximation of continuous functions by superpositions of plane
waves // Dokl. Akad. Nauk SSSR. – 1961. – 140. – P. 1237 – 1240 (Soviet Math. Dokl. – 1961. – 2. –
P. 1320 – 1329).
Received 26.05.09
ISSN 1027-3190. Укр. мат. журн., 2010, т. 62, № 3
|
| id | umjimathkievua-article-2875 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | English |
| last_indexed | 2026-03-24T02:32:01Z |
| publishDate | 2010 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/70/2ad5e7992c07e163e9587e988b092a70.pdf |
| spelling | umjimathkievua-article-28752020-03-18T19:39:19Z Best approximation by ridge functions in $L_p$-spaces Найкраще наближення хребтовими функціями в $L_p$-просторах Maiorov, V. E. Майоров, В. Є. We study the approximation of the classes of functions by the manifold $R_n$ formed by all possible linear combinations of $n$ ridge functions of the form $r(a · x))$. It is proved that, for any $1 ≤ q ≤ p ≤ ∞$, the deviation of the Sobolev class $W^r_p$ from the set $R_n$ of ridge functions in the space $L_q (B^d)$ satisfies the sharp order $n^{-r/(d-1)}$. Досліджено наближення класів функцій многовидом $R_n$, що утворений усіма можливими лінійними комбінаціями $n$ хребтових функцій вигляду $r(a · x))$. Доведено, що для будь-яких $1 ≤ q ≤ p ≤ ∞$ відхилення класу Соболева $W^r_p$ від множини $R_n$ хребтових функцій у просторі $L_q (B^d)$характеризується точним порядком $n^{-r/(d-1)}$. Institute of Mathematics, NAS of Ukraine 2010-03-25 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/2875 Ukrains’kyi Matematychnyi Zhurnal; Vol. 62 No. 3 (2010); 396–408 Український математичний журнал; Том 62 № 3 (2010); 396–408 1027-3190 en https://umj.imath.kiev.ua/index.php/umj/article/view/2875/2501 https://umj.imath.kiev.ua/index.php/umj/article/view/2875/2502 Copyright (c) 2010 Maiorov V. E. |
| spellingShingle | Maiorov, V. E. Майоров, В. Є. Best approximation by ridge functions in $L_p$-spaces |
| title | Best approximation by ridge functions in $L_p$-spaces |
| title_alt | Найкраще наближення хребтовими функціями в $L_p$-просторах |
| title_full | Best approximation by ridge functions in $L_p$-spaces |
| title_fullStr | Best approximation by ridge functions in $L_p$-spaces |
| title_full_unstemmed | Best approximation by ridge functions in $L_p$-spaces |
| title_short | Best approximation by ridge functions in $L_p$-spaces |
| title_sort | best approximation by ridge functions in $l_p$-spaces |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/2875 |
| work_keys_str_mv | AT maiorovve bestapproximationbyridgefunctionsinlpspaces AT majorovvê bestapproximationbyridgefunctionsinlpspaces AT maiorovve najkraŝenabližennâhrebtovimifunkcíâmivlpprostorah AT majorovvê najkraŝenabližennâhrebtovimifunkcíâmivlpprostorah |