Tchakaloﬀ polynomial meshes

(1)

Len Bos

Department of Computer Science University of Verona

Italy

E-mail: leonardpeter.bos@univr.it

Marco Vianello

Department of Mathematics University of Padova

Italy

E-mail: marcov@math.unipd.it

Abstract

We construct polynomial meshes from Tchakaloff quadrature points for measures on compact domains with certain boundary regularity, via estimates of the Christoffel function and its reciprocal.

1 Introduction

A norming set for P^d_n(K), the polynomials of degree not exceeding n restricted to a compact set K ⊂ R^d, is a subset Xn⊂ K such that

(1.1) kpk^K ≤ Cⁿkpk^Xⁿ , ∀p ∈ P^dn(K) ,

where kfk^Y denotes the sup-norm of a bounded function on the compact set Y .

Sequences of finite norming sets such that both Cn and card(Xn) grow algebraically in n are of primary interest in multivariate polynomial approximation, and are usually called weakly admissible polynomial meshes. If

2010 Mathematics Subject Classification: Primary 41A17; Secondary 41A63.

Key words and phrases: norming sets, polynomial meshes, equilibrium measure, Christoffel function, quadrature formulas, Tchakaloff Theorem.

1

(2)

Cn ≡ C is constant, the mesh is termed admissible. Notice that necessar- ily card(Xn) ≥ Nⁿ = Nn(K) = dim(P^d_n(K)), since Xn is determining for P^d

n(K) (i.e., polynomials vanishing there vanish everywhere on K). Admis- sible meshes with card(Xn) = O(Nⁿ) are termed optimal.

Observe that Nn= O(n^β) with β ≤ d, in particular Nⁿ= ^n+d_d ∼ n^d/d!

on polynomial determining compact sets (i.e., polynomials vanishing there vanish everywhere in R^d), but we can have β < d for example on compact algebraic varieties, like the sphere in R^d where Nn= ^n+d_d − ^n−2+d_d .

In case m ∈ R is not an integer, we will let P^dm(K) denote the space P^d

n(K) for n ≤ m the largest integer less than or equal to m, and similarly for Nm etc..

We recall among their properties that polynomial meshes are invariant under affine transformations, can be extended by algebraic transformations, finite union and product and are stable under small perturbations. They give good discrete models of a compact set for polynomial approximation, since they are nearly optimal for polynomial least squares, contain extremal subsets of Fekete and Leja type for polynomial interpolation, have been applied in polynomial optimization and in pluripotential numerics; cf., e.g., [5, 6, 9, 16, 18, 19, 21, 22].

2 Tchakaloff points and polynomial meshes

In the present paper we’ll make use of the notion of Tchakaloff quadrature points, to construct polynomial meshes on compact sets with certain boundary regularity (see Corollary 2.4 for the details). It is then worth recalling the celebrated Tchakaloff Theorem on the existence of positive algebraic quadrature formulas, originally proved in [26] for the Lebesgue measure, and later extended to general measures (cf., e.g., [23]).

Theorem 2.1. Let µ be a positive measure with compact support in R^d. Then there are s ≤ Nⁿ= dim(P^d_n(supp(µ)) points Tⁿ= {t^j} ⊆ supp(µ) and positive real numbers w = {w^j} such that

Z

R^d

p(x) dµ =

s

X

j=1

wjp(tj) , ∀p ∈ P^dn(supp(µ)) .

The points Tⁿ may be termed a set of Tchakaloff quadrature points of degree n for the measure µ.

(3)

Assume now that supp(µ) is determining for P^d(K) (the space of d- variate real polynomials restricted to K; for a fixed degree n, we could even assume that supp(µ) is determining for P^d_n(K)). We recall two functions that will play a relevant role in our construction. The first is the reproducing kernel for µ in P^d_n(K), namely

(2.1) Kn(x, y) = K_n^µ(x, y) =

Nn

X

j=1

pj(x)pj(y) ,

where {pj} is any µ-orthonormal basis of P^dn(K), for example that obtained from the standard monomial basis by applying the Gram-Schmidt orthonor- malization process (it can be shown that Kn(x, y) does not depend on the choice of the orthonormal basis). The diagonal of the reproducing kernel, Kn(x, x), has the important property that

(2.2) kpk^K ≤q

maxx∈K Kn(x, x) kpk^L²µ(K) , ∀p ∈ P^dn(K) .

The second function is the reciprocal of Kn(x, x), usually called the Christoffel function of µ, that has the following relevant characterization (2.3) λn(x) = 1

Kn(x, x) = min

p∈P^d_n(K), p(x)=1

Z

K

p²(x) dµ ;

cf., e.g., [12, 13] for the definition and properties of the Christoffel function λn(x) and its reciprocal Kn(x, x).

We are now ready to state and prove our main result.

Proposition 2.2. Let K ⊂ R^d be a compact set and µ a measure on K whose support is determining for P^d(K) and fix α > 1. Then Tchakaloff quadrature points T2αn for µ of degree at most 2αn, are norming sets for P^d

n(K), with cardinality not exceeding N2αn and norming constant

(2.4) C_n=q

maxx∈K{Kαn(x, x)} max

x∈K{λ(α−1)n(x)} .

Proof. Let p ∈ P^dn(K) and ξ ∈ K such that |p(ξ)| = kpk^K. The proof exploits the auxiliary polynomial r(x) = p(x)q(x) ∈ P^dαn(K), using the peaking polynomial q(x) = K(α−1)n(x, ξ)/K(α−1)n(ξ, ξ) ∈ P^d(α−1)n(K). It is easily seen to be such that

q(ξ) = 1 , Z

K

q²(x) dµ = Z

K

K(α−1)n(x, ξ) K(α−1)n(x, ξ) (K(α−1)n(ξ, ξ))² dµ

(4)

= K(α−1)n(ξ, ξ)

(K(α−1)n(ξ, ξ))² = 1

K(α−1)n(ξ, ξ) = λ(α−1)n(ξ) . By (2.2) we can write

kpk^K = |r(ξ)| ≤q

maxx∈K Kαn(x, x) krk^L²µ(K) ,

and by Theorem 1 for degree 2αn we have (with s = card(T^2αn) ≤ N^2αn)

krk²L²µ(K) = Z

K

r²(x) dµ =

s

X

j=1

w_jr²(t_j) =

s

X

j=1

w_jp²(t_j) q²(t_j)

≤ kpk²T_2αn s

X

j=1

wjq²(tj) = kpk²T_2αn

Z

K

q²(x) dµ

= kpk²T_2αnλ_(α−1)n(ξ) ≤ kpk²T_2αn max

x∈K λ_(α−1)n(x) , from which we get

kpk^K ≤q

maxx∈K{K^αn(x, x)} max

x∈K{λ^(α−1)n(x)} kpk^T2αn .

We can now give some corollaries on the construction of Tchakaloff polynomial meshes on compact sets satisfying certain geometric regularity conditions on the boundary. All the asymptotic bounds are intended as n → ∞ for fixed d. The first concerns the sphere, where a similar result has been proved by means of Fekete points, cf. [2, 17].

Corollary 2.3. Let K = S^d−1 be the unit sphere in R^d. Then, the sequence of Tchakaloff point sets {T^2αn} for the standard surface measure dσ is an optimal admissible polynomial mesh.

Proof. The proof is immediate recalling that Nn = ^n+d_d − ^n−2+d_d ∼ _(d−1)!²ⁿ^d−1 and the well-known property K_n(x, x) = N_n/ω_d−1for every x ∈ S^d−1, where ωd−1 is the surface area of the sphere (cf. [24]). By Theorem 1 and Propo- sition 1 give card(T^2αn) ≤ N^2αn = O(Nⁿ) and Cn = pNαn/N_(α−1)n = O(1).

The following result, which concerns dµ = dx (the Lebesgue measure) and fat compact sets with some geometric regularity, is substantially based

(5)

on the upper and lower bounds for Christoffel functions obtained in [12], see also [8] for a general discussion of the functional inequalities involved.

We say that K satisfies a UIBC (Uniform Interior Ball Condition) if every point of K belongs to a ball of fixed radius contained in K. This is equivalent to saying that there is a ball of fixed radius that can roll along the boundary of K remaining in K. This holds for example on smooth convex bodies, by the celebrated Rolling Ball Theorem, cf. [15]. We stress however that such a property does not require convexity or smoothness, for example inward corners or even inward cusps are allowed (consider e.g. the union of two overlapping disks or a cardioid in R²).

On the other hand, K satisfies a UICC (Uniform Interior Cone Condi- tion) if every point of K belongs to a fixed suitably rotated cone contained in K. This property is equivalent to having a Lipschitz boundary and holds for example for any convex body; for such geometric properties of compact sets we refer the reader, e.g., to [10].

Corollary 2.4. Let K ⊂ R^d be a fat compact set (the closure of a bounded open set) and {T^2αn} a sequence of Tchakaloff point sets for the Lebesgue measure on K (whose cardinality does not exceed N2αn = O(n^d) by Theorem 1). Then

• if K satisfies a UIBC (Uniform Interior Ball Condition), {T^2αn} is a weakly-admissible polynomial mesh with Cn= O(√

n);

• if K satisfies a UICC (Uniform Interior Cone Condition), {T^2αn} is a weakly-admissible polynomial mesh with C_n= O(n^d/2).

Proof. First, we recall that with the Lebesgue measure, on any compact set we have maxx∈Kλn(x) = O(n^−d), by Theorem 6.3 in [12]. On one hand, in [12] it is proved that on compact sets satisfying a UIBC the bound maxx∈KKn(x, x) = O(n^d+1) holds, which by Proposition 1 gives Cn = pO(n) = O(√

n). On the other hand, on compact sets satisfying a UICC maxx∈KKn(x, x) = O(n^2d) holds, which gives Cn = pO(n^d) = O(n^d/2).

It is worth recalling that the existence of weakly-admissible Tchakaloff- like polynomial meshes with Cn = O(n^d/2) and O(n^d) cardinality was proved in [27] by a fully discrete version of the Tchakaloff Theorem, on any compact set admitting an optimal admissible polynomial mesh. The existence of

(6)

optimal polynomial meshes on UICC compact sets is not known in general, and has been proved only in special cases and conjectured for convex bodies;

cf. [16].

On the other hand, in some sense the result for UIBC compact sets is weaker than what is known for example on general smooth compact bodies, where it is proved constructively that an optimal admissible polynomial mesh always exists (cf. [18]). However the effective computation of such a mesh does not appear to be an easy task, whereas the computation of Tchakaloff quadrature points is much easier, whenever a starting algebraic quadrature formula is known (as happens with the Lebesgue measure for many classes of compact sets). Indeed, the computation of Tchakaloff points of degree n starting from a known quadrature formula with M > N2αnnodes can be treated as a Quadratic or even as a Linear Programming problem with N2αn constraints and M variables, which (taking for example α = 2) can be solved effectively by standard algorithms at least in low dimension d and for moderate degrees n. We refer the reader, e.g., to [20, 25] for the computational aspects concerning Tchakaloff points.

3 The Pluripotential Equilibrium Measure

For any (regular) compact set K ⊂ C there is a distiguished measure for which the associated K_n(x, x) (and hence also λ_n(x)) has a special be- haviour. Indeed, it is known ([3, Thm. B]) that (under certain conditions), for dµ a probabilty measure supported on K,

n→∞lim 1 Nn

Kn(x, x)dµ(x) = dµK(x), weak-*,

where dµK is the so-called pluripotential equilibrium measure for K (see e.g.

the monograph [14] more an introduction to this subject). Of special note is the fact that for K = [−1, 1] ⊂ C, it is known that

dµK = 1 π

√ 1

1 − x²dx, the so-called Chebyshev measure.

In particular if dµ is chosen dµ = dµK to be itself the equilibrium measure, then it follows that

(3.1) lim

n→∞

1 Nn

Kn(x, x)dµK(x) = dµK(x), weak-*, and hence

n→∞lim 1 Nn

Kn(x, x) = 1, weak-*.

(7)

In special cases (see e.g. [4]) it is known that the limit (3.1) is actually pointwise (for x in the interior of K). Moreover, when K ⊂ R^d is a ball, simplex or cube, the equilibrium measure is explicitly known and this can be exploited to show that, for dµ = dµK, there are constants C1, C2 > 0 such that

(3.2) C1Nn≤ Kⁿ(x, x) ≤ C²Nn, x ∈ K.

From (3.2) and Proposition 2.2 we then immediately obtain

Corollary 3.1. Let K ⊂ R^d be either a ball, simplex or cube. Then, the sequence of Tchakaloff point sets {T^2αn} for the equilibrium measure dµ^K is an optimal admissible polynomial mesh.

We now proceed to prove the bounds (3.2) for K a ball, simplex or cube.

3.1 The Ball

Here K = B^d = {x ∈ R^d : kxk² ≤ 1} and its equilibrium measure is dµK = cd

1 p1 − kxk2

dx

where the constant cd is chosen so that dµK is a probability measure.

Lemma 3.2. There are constants C1, C2 > 0 so that (for the equilibrium measure)

C1Nn≤ Kⁿ(x, x) ≤ C²Nn, x ∈ B^d.

Proof. We will make use of the intimate connection between B^d and the sphere S^d:= {x ∈ R^d+1 : kxk2 = 1}, of which B^dis the principal diameter.

Indeed, any function f : B^d → R can be “lifted” to a function on S^d by setting, for x ∈ B^dand z ∈ [−1, 1] such that kxk²2+|z|² = 1, f (x, z) := f (x).

Further,

Z

B^d

f (x)dµ_K(x) = 1 2

Z

S^d

f (x, z)dσ(x, z)

where dσ is surface area on S^d, normalized to be a probability measure.

Hence, if {p¹(x), · · · , pNn(B^d)(x)} is an orthonormal basis, with respect to the measure dµK, for P^d_n(B^d), it is also an orthogonal set, considered as a subset of P^d_m(S^d), with respect to the measure dσ with

kp^jk^L²^(S^d⁾ =√ 2.

(8)

It follows that, for x ∈ B^d,

K_n(x, x) =

Nn(B^d)

X

j=1

p²_j(x) ≤ 2Kn((x, z), (x, z)) = 2N_n(S^d) ≤ 4Nn(B^d)

where, by an abuse of notation, Kn((x, z), (x, z)) denotes the diagonal of the reproducing kernel for S^d. Hence the upper bound in (3.2) follows with (the non-optimal) C2 = 4.

The proof of the lower bound is a bit more delicate. We use the optimality property of Kn,

Kn(x, x) = max

p∈P^d_n(K), p(x)=1

1 R

Kp²(x)dµ(x) so that, for any particular p ∈ P^dn(K) with p(x) = 1,

(3.3) K_n(x, x) ≥ 1

R

Kp²(x)dµK(x).

Indeed, by Lemma 3 of [7], for every a ∈ B^d and integer n > 0, there exists a “peaking” polynomial pa(x) of degree at most n with the properties that

1. pa(a) = 1,

2. there is a constant c1 so that max_x∈B^d|p^a(x)| ≤ c¹, 3. there is a constant c2 so that

|pa(x)| ≤ c₂

n^d+1dist(a, x)^−(d+1).

Here, for a, b ∈ B^d, dist(a, b) is the geodesic distance on the sphere S^d between the lifted points ˜a := (a,p1 − kak²2) ∈ S^d and ˜b := (b,p1 − kbk²2) ∈ S^d. Using this pa(x) in (3.3) results in

K_n(a, a) ≥ 1 R

B^dp²_a(x)dµK(x) = 2 R

S^dp²_a(x)dσ(x). We claim that there is a constant C₂^′ so that

Z

S^d

p²_a(x)dσ(x) ≤ C2^′n^−d, from which the lower bound follows.

Now to see this we split the domain into two parts: where dist(˜a, x) ≤ 1/n and where dist(˜a, x) > 1/n. Firstly, we have

(3.4) Z

dist(˜a,x)≤1/n

p²_a(x)dσ(x) ≤ c²1vol({x ∈ S^d : dist(˜a, x) ≤ 1/n) ≤ c³n^−d

(9)

for some constant c3.

The second part is more delicate, yet completely elementary. We use spherical coordinates with “north pole” at ˜a and let φ ∈ [0, π] denote the angle between x ∈ S^d and the axis through the pole, so that

dist(˜a, x) = φ, with cos(φ) = ˜a · x.

We claim that there is a constant c4 such that Z

dist(˜a,x)≥1/n

p²_a(x)dσ(x) ≤ c⁴n^−d.

To see this, first notice that, by property 3 of pa(x) it is sufficient to prove

that Z

ǫ≥dist(˜a,x)≥1/n

p²_a(x)dσ(x) ≤ c⁴n^−d

for any fixed ǫ > 0. Then, as dσ(x) = sin(φ)^d−1dσ^′(θ), where dσ^′(θ) repre- sents the part of dσ(x) due to the angles other than φ,

Z

ǫ≥dist(˜a,x)≥1/n

p²_a(x)dσ(x) ≤ c⁴ 1 n^2d+2

Z ǫ 1/n

1

φ^2d+2φ^d−1dφ

= c4

1 n^2d+2

Z ǫ 1/n

φ^−(d+3)dφ

= c4

1 n^2d+2

1

d + 2n^d+2− ǫ^−(d+2)

≤ c4n^−d

(where the meaning of c4 changes slightly on the last line).

3.2 The Simplex

Here K = T^d= {x ∈ R^d : xi ≥ 0,Pd

i=1xi ≤ 1} and its equilibrium measure is

dµK = cd

1 q

x1· · · x^d(1 −Pd i=1xi)

dx

where the constant cd is chosen so that dµK is a probability measure.

This case is also intimately related to the sphere S^dby setting, for x ∈ T^d,

˜ x :=



√ x1,√

x2, · · · ,√ xd,

v u u t1 −

d

X

i=1

xi



∈ S^d and its inverse, for ˜x ∈ S^d⊂ R^d+1,

x = (˜x²₁, ˜x²₂, · · · , ˜x²d) ∈ T^d.

(10)

We remark that the equilibrium measure for T^dis just the pullback of surface area on S^d under the mapping x 7→ ˜x. We claim that

Lemma 3.3. There are constants C₁, C₂ > 0 so that (for the equilibrium measure)

C1Nn≤ Kⁿ(x, x) ≤ C²Nn, x ∈ T^d.

Proof. To see the upper bound just note that if {p1(x), · · · , pNn(T^d)(x)} is an orthonormal basis for P^d_n(T^d), with respect to the measure dµK, then, defining

qj(˜x) := pj(x) = pj(˜x²₁, · · · , ˜x²d),

{q¹(˜x), · · · , qNn(T^d)(˜x)} is an orthogonal set, considered as a subset of P^d+12n (S^d), with respect to the measure dσ with norm a certain dimensional constant.

It follows that, for x ∈ T^d, K_n(x, x) =

Nn(T^d)

X

j=1

p²_j(x) =

Nn(T^d)

X

j=1

q_j²(˜x) ≤ cK2n(˜x, ˜x) = cN_2n(S^d) ≤ c^′N_n(T^d) for some constant c^′. Here, by an abuse of notation, K2n(˜x, ˜x) denotes the diagonal of the reproducing kernel for S^d.

The proof of the lower bound is very similar to the proof of the case of the ball. Indeed Lemma 4 of [7] provides, for each a ∈ T^d, a “peaking”

polynomial pa(x) with the same properties as that for the ball. We suppress the details.

3.3 The Cube

Here K = [−1, 1]^dfor which the equilibrium measure is the product measure dµK(x) = 1

π^d

d

Y

i=1

1 p1 − x²i

dx.

We claim that also in this case

Lemma 3.4. There are constants C1, C2 > 0 so that (for the equilibrium measure)

C1Nn ≤ Kⁿ(x, x) ≤ C²Nn, x ∈ [−1, 1]^d. Proof. This follows easily from the fact that

d

Y

i=1

Kn/d(xi) ≤ Kⁿ(x, x) ≤

d

Y

i=1

Kn(xi)

where Km(xi) denotes the univariate kernel of degree m for the univariate equilibrium measure for [−1, 1].

(11)

Remark 3.5. It is an interesting problem to determine for which compact sets K the property (7) holds. Given the weak convergence indicated in (6) we suspect that it holds for quite a general class of K, but even a proof for K (centrally symmetric and) convex would be meaningful.

Acknowledgements

Work partially supported by the DOR funds of the University of Padova, and by the GNCS-INdAM. This research has been accomplished within the RITA “Research ITalian network on Approximation”.

References

[1] L. Bos, Asymptotics for the Christoffel function for Jacobi like weights on a ball in Rⁿ, New Zealand J. Math. 23 (1994), no. 2, 99–109.

[2] L. Bos, Fekete Points as Norming Sets, Dolomites Res. Notes Ap- prox. DRNA 11 (2018), to appear.

[3] R. Berman, S. Bouksom and D. W. Nystrom, Fekete points and convergence towards equilibrium measures on complex manifolds, Acta Math. 207 (2011), no. 1, 1–27.

[4] L. Bos, B. Della Vecchia and G. Mastroianni, On the asymptotics of Christoffel functions for centrally symmetric weight functions on the ball in R^d, Rend. Circ. Mat. Palermo (2) Suppl. No. 52, Vol. I (1998), 277–290.

[5] L. Bos, J.P. Calvi, N. Levenberg, A. Sommariva and M. Vianello, Geometric Weakly Admissible Meshes, Discrete Least Squares Ap- proximations and Approximate Fekete Points, Math. Comp. 80 (2011), 1601–1621.

[6] L. Bos, S. De Marchi, A. Sommariva and M. Vianello, Comput- ing multivariate Fekete and Leja points by numerical linear algebra, SIAM J. Numer. Anal. 48 (2010), 1984–1999.

[7] L. Bos, N. Levenberg and S. Waldron, On the Spacing of Fekete Points for a Sphere, Ball or Simplex, Indag. Math. (N.S.) 19 (2008), no. 2, 163–176.

(12)

[8] L. Bos and P. Milman, Sobolev-Gagliardo-Nirenberg and Markov type inequalities on subanalytic domains, Geom. Funct. Anal. 5 (1995), no. 6, 853–923.

[9] J.P. Calvi and N. Levenberg, Uniform approximation by discrete least squares polynomials, J. Approx. Theory 152 (2008), 82–100.

[10] M.C. Delfour and J.-P. Zolesio, Shapes and Geometries, SIAM, Philadelphia, 2001.

[11] S. De Marchi, A. Sommariva and M. Vianello, Multivariate Christoffel functions and hyperinterpolation, Dolomites Res. Notes Approx. DRNA 7 (2014), 26–33.

[12] Z. Ditzian and A. Prymak, On Nikol’skii inequalities for domains in R^d, Constr. Approx. 44 (2016), 23–51.

[13] C.F. Dunkl and Y. Xu, Orthogonal Polynomials of Several Vari- ables, Encyclopedia of Mathematics and its Applications 81, Cam- bridge University Press, 2001.

[14] M. Klimek, Pluripotential Theory, Oxford U. Press, 1991.

[15] D. Koutroufiotis, On Blaschke’s rolling theorems, Arch. Math. 23 (1972), 655–670.

[16] A. Kroó, On optimal polynomial meshes, J. Approx. Theory 163 (2011), 1107–1124.

[17] J. Marzo and J. Ortega-Cerdà, Equidistribution of Fekete Points on the Sphere, Constr. Approx. 32 (2010), 513–521.

[18] F. Piazzon, Optimal Polynomial Admissible Meshes on Some Classes of Compact Subsets of R^d, J. Approx. Theory 207 (2016), 241–264.

[19] F. Piazzon, Pluripotential Numerics, Constr. Approx., published online 21 June 2018.

[20] F. Piazzon, A. Sommariva and M. Vianello, Caratheodory- Tchakaloff Subsampling, Dolomites Res. Notes Approx. DRNA 10 (2017), 5–14.

(13)

[21] F. Piazzon and M. Vianello, Small perturbations of polynomial meshes, Appl. Anal. 92 (2013), 1063–1073.

[22] F. Piazzon and M. Vianello, Markov inequalities, Dubiner distance, norming meshes and polynomial optimization on convex bodies, Optim. Lett., under revision (preprint at Optimization Online:

http://www.optimization-online.org/DB_HTML/2018/08/6758.html).

[23] M. Putinar, A note on Tchakaloff ’s theorem, Proc. Amer. Math.

Soc. 125 (1997), 2409–2414.

[24] M. Reimer, Multivariate polynomial approximation, International Series of Numerical Mathematics, 144, Birkhauser, Basel, 2003.

[25] A. Sommariva and M. Vianello, Compression of multivariate discrete measures and applications, Numer. Funct. Anal. Optim. 36 (2015), 1198–1223.

[26] V. Tchakaloff, Formules de cubatures mécaniques à coefficients non négatifs. (French) Bull. Sci. Math. 81 (1957), 123–134.

[27] M. Vianello, Compressed sampling inequalities by Tchakaloff ’s theorem, Math. Inequal. Appl. 19 (2016), 395–400.