PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 96 (110) (2014), 41–48 DOI: 10.2298/PIM1410041B

FEKETE TYPE POINTS FOR RIDGE FUNCTION INTERPOLATION AND HYPERBOLIC POTENTIAL THEORY

Len Bos, Stefano De Marchi, and Norm Levenberg

Abstract. We apply hyperbolic potential theory to the study of the asymptotics of Fekete type points for univariate ridge function interpolation.

1. Introduction

Suppose that f : ℂ → ℂ and g : ℂ^{d} → ℂ is defined by g(x) = f(t · x) where t ∈ ℂ^{d} is fixed and t · x = t_{1}x_{1} + ⋯+ t_{d}x_{d}. In the case of t = iω with ω ∈ ℝ^{d} and f(z) = e^{z}, g(x) = e^{iω·x} and hence we refer to t as a (generalized) “frequency”. Such an g is called a ridge function (or sometimes a planar wave). If we have n such frequencies t_{1}, …, t_{n} ∈ ℂ^{d} then the span of the associated ridge functions

V_{n} := span({f(t_{1} · x), f(t_{2} · x), …, f(t_{n} · x)})

form a linear “frequency space” and may be used as the basis of a multivariate interpolation scheme for data in ℂ^{d} in the following way. Suppose that the “sites” s_{i} ∈ K ⊂ ℂ^{d}, 1 ⩽ i ⩽ n, where K is compact, are given together with values z_{i} ∈ ℂ, 1 ⩽ i ⩽ n. We look for an interpolant of the form

p(x) = ∑_{j=1}^{n} a_{j} f(t_{j} · x),

i.e., a p ∈ V_{n} such that

(1.1)  p(s_{i}) = z_{i}, 1 ⩽ i ⩽ n.

Applying the conditions (1.1) to the equation for p results in a linear system with coefficient matrix M_{n}(s, t) := [f(t_{j} · s_{i})]_{1⩽i,j⩽n} .

If the frequencies t_{j} or the sites s_{i}, or both, may freely be adjusted within K, then it is reasonable to ask for those points which produce “best” or at least “good” interpolants. Of course, the numerical conditioning of the matrix M_{n} will play an important role in the answer to such questions and hence it would be useful to know which frequencies t_{j} and/or points s_{i} produce the best conditioned matrix M_{n}. Unfortunately, this is likely a forbiddingly difficult problem, and hence, as a first step, it is reasonable to ask for those frequencies t_{j} and/or points s_{i} in K for which which det(M_{n}) is as large as possible. M_{n} is an analogue of the classical Vandermonde matrix and so in analogy with this case, we refer to such optimal points as ridge Fekete points. In [4], specifying to ℝ^{d} and two particular classes of ridge functions, we proved the following theorem.

2010 Mathematics Subject Classification: Primary 41A05; Secondary 31C15.

Key words and phrases: ridge function, interpolation, Fekete type points, hyperbolic capacity.

We dedicate this paper to Prof. Giuseppe Mastroianni on the occasion of his retirement.

Theorem 1.1. Suppose that f(x) = exp(αx) or f(x) = exp(−βx^{2}) for some α, β > 0. Suppose further that ŝ_{1} < ŝ_{2} < ⋯< ŝ_{n} ∈ [a, b] are points which maximize either

(1) det(M_{n}(s, t)), s ∈ [a, b]^{n}, where t ∈ [a, b]^{n} are fixed but distinct
(2) det(M_{n}(s, s)), s ∈ [a, b]^{n}.

Then the discrete measures μ(n) ; ŝ := \frac{1}{n} ∑ _{i=1}^{n} δŝ_{i} tend weak-* to the arcsine measure μ^{∗} given by

dμ^{∗} = \frac{1}{π} \frac{1}{\sqrt{(b − x)(x − a)}} dx.

See [10] for error estimates of such interpolants. We also remark that, in contrast, for radial basis interpolation by basis functions of the form g(|x|) with g′(0) ≠ 0, the optimal points are asymptotically uniformly distributed; see [5] or [3].

As is well known, the arcsine measure μ^{∗} is also the so-called equilibrium measure of complex potential theory, a theory fundamental for the study of the asymptotics of good points for univariate polynomial interpolation; see, for example [1] or [2]. This theorem may be paraphrased to say that for the exponential basis functions optimal points for ridge function interpolation behave (asymptotically) exactly like those for polynomial interpolation. In this paper we show that, depending on the basis function f(x), this is not always the case. Indeed, for a different family of functions, it is hyperbolic potential theory that plays a central role. In particular, this shows that the asymptotic distribution of ridge Fekete points, in general, depends on the function f.

2. A first example and hyperbolic potential theory

Consider the function f(z) := 1/(1 − z) and the corresponding ridge function g(x) = f(tx) where d = 1 so that t, x ∈ ℂ. Then, for sites s_{i}, 1 ⩽ i ⩽ n and frequencies t_{i}, 1 ⩽ i ⩽ n distinct, the matrix M_{n}(s, t) = [1/(1 − s_{i}t_{j})]_{1⩽i,j⩽n} is a variant of the so-called Cauchy matrix (see [6, p. 268]) and its determinant may be explicitly calculated.

Proposition 2.1. We have

det(M_{n}(s, t)) = \frac{V (s)V (t)}{∏ _{i,j=1}^{n} (1 − s_{i}t_{j})}

where V (x) := ∏ _{i>j} (x_{i} − x_{j}) is the classical Vandermonde determinant.

Proof. We may write

\frac{1}{1 − s_{i}t_{j}} = \frac{1}{s_{i}} \frac{1}{a_{i} + b_{j}}

where a_{i} := 1/s_{i} and b_{j} := −t_{j}. Hence

det(M_{n}(s, t)) = ( ∏_{i=1}^{n} \frac{1}{s_{i}} ) ^{n} det([1/(a_{i} + b_{j})]).

This latter determinant is the Cauchy determinant for which Davis [6, p. 268] gives the formula

det([1/(a_{i} + b_{j})]) = \frac{V (a)V (b)}{∏ _{i,j=1}^{n} (a_{i} + b_{j})} .

Elementary algebra then gives us the result. □

Take now t = s ∈ ℝ^{n}. Then
det(M_{n}(s, s)) = \frac{(V (s))^{2}}{∏ _{i,j=1}^{n} (1 − s_{i}s_{j})} = \frac{( ∏ _{i>j} (s_{i} − s_{j}))^{2}}{∏ _{i≠j} (1 − s_{i}s_{j})} \frac{1}{∏ _{i=1}^{n} (1 − s_{i}^{2})}

= ( \frac{∏ _{i>j} (s_{i} − s_{j})}{∏ _{i>j} (1 − s_{i}s_{j})} ) ^{2} \frac{1}{∏ _{i=1}^{n} (1 − s_{i}^{2})} = ( ∏_{i>j} [s_{i}, s_{j}]_{h}) ^{2} \frac{1}{∏ _{i=1}^{n} (1 − s_{i}^{2})} (2.1)

where

[α, β]_{h} := | \frac{α − β}{1 − \overline{α}β} |

is the pseudohyperbolic distance between α, β ∈ ℂ.

Remark 2.1. Let 𝔻 = {z ∈ ℂ : |z| < 1} be the open unit disk. Equipped with the hyperbolic distance

\{α, β\}_{h} := inf_{γ} ∫_{γ} \frac{|dz|}{1 − |z|^{2}} , α, β ∈ 𝔻

where the inf is taken over all rectifiable curves in 𝔻 connecting α to β, 𝔻 becomes the hyperbolic plane. It can be shown that [α, β]_{h} = tanh({α, β}_{h}).

We then define the hyperbolic Vandermonde determinant to be

H(s) := ∏_{i>j} [s_{i}, s_{j}]_{h}.

Suppose that K ⊂ 𝔻 is compact. A set of points t^{(n)} = {t_{1}^{(n)} , …, t_{n}^{(n)} } ⊂ K that maximize H(s) for s ∈ K^{n} form a hyperbolic analogue of classical Fekete points. As they were first studied by Tsuji they are often referred to as Tsuji points. Hyperbolic potential theory, as introduced in Tsuji [9, p. 94], may be thought of as classical complex potential theory with the euclidean distance |α − β| replaced by the pseudohyperbolic distance; see also the survey by Kirsch [8, § 6.2]. In particular, for a probability measure μ with support in K, its energy is

I(μ) := ∫_{K} ∫_{K} log( \frac{1}{[α, β]_{h}} ) dμ(α) dμ(β)

and its hyperbolic conductor potential is

U_{μ}^{h}(α) := ∫_{K} log( \frac{1}{[α, β]_{h}} ) dμ(β).

Let V_{h}(K) := inf_{μ} I(μ). It is known that

lim_{n→∞} H(t^{(n)} )^{1/\binom{n}{2}} = exp(−V_{h}(K)) =: cap_{h}(K),

the hyperbolic capacity of K. If cap_{h}(K) > 0 then there exists a unique minimizing measure, μ_{K}^{h}, called the hyperbolic equilibrium measure. For μ = μ_{K}^{h}, the potential function U_{μ} is harmonic in 𝔻∖K and has the properties that U_{μ}(α) = 0 for α ∈ ∂𝔻, U_{μ}(α) ⩽ V_{h}(K) on 𝔻 and U_{μ}(α) = V_{h}(K) q.e. on K; i.e., for α ∈ K ∖ P where P is a (possibly empty) polar set (a set P is polar if there exists a subharmonic function u ≢ −∞ with P ⊂ {u = −∞}). Points of K ∖ P are called regular points of K.

If we define the discrete measures supported on the Tsuji points,

μ_{n} := \frac{1}{n} ∑_{i=1}^{n} δ_{t_{i}^{(n)}} ,

then μ_{n} → μ_{K}^{h}, weak−∗. More generally we have (cf. the proof of Thm. 1.5 in [1])

Theorem 2.1. Suppose that s^{(n)} ∈ K^{n} is a sequence of sets of points such that

lim_{n→∞} H(s^{(n)} )^{1/\binom{n}{2}} = cap_{h}(K).

Then for the discrete measures μ_{n} := \frac{1}{n} ∑ _{i=1}^{n} δ_{s_{i}^{(n)}} , we have lim_{n→∞} μ_{n} = μ_{K}^{h}, weak-*.

From this we may conclude

Theorem 2.2. Suppose that for K ⊂ 𝔻 compact, s^{(n)} ∈ K^{n} is such that

| det(M_{n}(s^{(n)} , s^{(n)} ))| = max_{s∈K^{n}} |det(M_{n}(s, s))| , n = 1, 2, …,

i.e., s^{(n)} is a set of ridge Fekete points, and μ_{n} := \frac{1}{n} ∑ _{i=1}^{n} δ_{s_{i}^{(n)}} . Then

lim_{n→∞} μ_{n} = μ_{K}^{h} , weak-∗ .

Proof. By Theorem 2.1 it is sufficient to prove that

lim_{n→∞} H(s^{(n)} )^{1/\binom{n}{2}} = cap_{h}(K).

First note that since K ⊂ 𝔻, there exists a constant δ > 0 such that 0 < δ ⩽ |1 − s_{i}^{2}| ⩽ 2, for all s ∈ K. If we let, as before, t^{(n)} ∈ K^{n} denote the Tsuji points for K, we have immediately that H(s^{(n)} ) ⩽ H(t^{(n)} ). Further, by the definition of s^{(n)} , |det(M_{n}(t^{(n)} , t^{(n)} ))| ⩽ |det(M_{n}(s^{(n)} , s^{(n)} ))| so that from (2.1) applied to s = t^{(n)} and to s = s^{(n)} we have

H^{2}(t^{(n)} )\frac{1}{∏ _{i=1}^{n} |1 − (t_{i}^{(n)} )^{2}|} = |det(M_{n}(t^{(n)} , t^{(n)} ))|

⩽ |det(M_{n}(s^{(n)} , s^{(n)} ))| = H^{2}(s^{(n)} )\frac{1}{∏ _{i=1}^{n} |1 − (s_{i}^{(n)} )^{2}|} .

It follows that

H^{2}(t^{(n)} )( ∏_{i=1}^{n} \frac{|1 − (s_{i}^{(n)} )^{2}|}{|1 − (t_{i}^{(n)} )^{2}|} ) ⩽ H^{2}(s^{(n)} ) ⩽ H^{2}(t^{(n)} )

and hence (δ/2)^{n}H^{2}(t^{(n)} ) ⩽ H^{2}(s^{(n)} ) ⩽ H^{2}(t^{(n)} ). Clearly then

lim_{n→∞} H(s^{(n)} )^{1/\binom{n}{2}} = lim_{n→∞} H(t^{(n)} )^{1/\binom{n}{2}} = cap_{h}(K)

and we are done. □

Now let us return to the case when K is a real interval. For simplicity let us take K = [−a, a] ⊂ 𝔻. We first note that μ_{K}^{h} is not the same as the classical equilibrium measure

μ^{∗} = \frac{1}{π} \frac{1}{\sqrt{a^{2} − x^{2}}} dx.

For if μ_{K}^{h} = μ^{∗} then it would have to be the case that

(2.2)  ∫_{−a}^{a} log( \frac{1}{|α − β|} ) dμ^{∗}(β) − ∫_{−a}^{a} log( \frac{1}{[α, β]_{h}} ) dμ^{∗}(β)

is constant q.e. for α ∈ [−a, a] as, from the classical theory, the first term in (2.2) is also constant on [−a, a]. Hence we would have that

∫_{−a}^{a} log( \frac{[α, β]_{h}}{|α − β|} ) dμ^{∗}(β) = −\frac{1}{π} ∫_{−a}^{a} log(1 − αβ)\frac{dβ}{\sqrt{a^{2} − β^{2}}}

is constant q.e. on [−a, a]. However, a direct calculation shows that

\frac{1}{π} ∫_{−a}^{a} log(1 − αβ)\frac{dβ}{\sqrt{a^{2} − β^{2}}} = log( \frac{1 + \sqrt{1 − a^{2}α^{2}}}{2} )

which is clearly not constant in α, a contradiction.

Alternatively, we may note that in this case

U_{μ}^{h}(α) = ∫_{−a}^{a} log | \frac{1 − \overline{α}β}{α − β} | dμ(β)

and for |α| = 1,

| \frac{1 − \overline{α}β}{α − β} | = | \frac{\overline{α}(α − β)}{α − β} | = |\overline{α}| = 1

so that U_{μ}^{h}(α) = 0, |α| = 1. Then, from the fact that, for μ = μ_{K}^{h}, U_{K}^{h} (α) ≡ V_{h}(K) on [−a, a], it follows that U_{K}^{h} is a multiple of the relative extremal function

ω(α, K, 𝔻) := sup{u(α) : u shm in 𝔻, u < 0 on 𝔻, u ⩽ −1 on K},

so that μ_{K}^{h} = c Δω(α, K, 𝔻) for some constant c. In particular,

μ_{K}^{h} ≠ \frac{1}{π} \frac{dβ}{\sqrt{a^{2} − β^{2}}} ,

since the right-hand side is the classical equilibrium measure of [−a, a], which is a multiple of the laplacian of the global extremal function

sup{u(α) : u shm in ℂ, u(z) − log|z| = 0(1) (|z| → ∞), u ⩽ 0 on [−a, a]}
= log |α/a − \sqrt{(α/a)^{2} − 1} | .

3. A generalized family of functions

Consider now the family of functions f_{c}(z) := c^{2}/(c^{2} − z), c ⩾ 1 with g_{c}(x) = f_{c}(tx). These functions are analytic in the disks 𝔻_{c} := {z ∈ ℂ : |z| < c^{2}} ⊃ 𝔻. The matrices M_{n}(s, t) for s, t ∈ ℝ^{n} then become M_{n}(s, t) = [c^{2}/(c^{2}−s_{i}t_{j})] ∈ ℝ^{n×n} . It is easy to verify, using Proposition 2.1, that

Proposition 3.1. We have

det(M_{n}(s, t)) = \frac{V (s′)V (t′)}{∏ _{i,j=1}^{n} (1 − s′_{i}t′_{j})}

where s′:= s/c, t′ = t/c and V (x) := ∏ _{i>j} (x_{i} − x_{j}) is the classical Vandermonde determinant.

Suppose that K ⊂ 𝔻. It follows that the points that maximize the determinant of M_{n}(s, s), s ⊂ K, have a limiting measure given by that of the dilation by c of that for K/c. Specifically, if we denote this measure by dμ_{c}^{∗} it is such that

∫_{K} f(β) dμ_{c}^{∗}(β) = ∫_{K/c} f(cβ) dμ_{K/c}^{h} (β).

In particular

∫_{K} log | \frac{1 − \overline{α}β}{α − β} | dμ_{c}^{∗}(β) = ∫_{K/c} log | \frac{1 − \overline{α}cβ}{α − cβ} | dμ_{K/c}^{h} (β).

Now, we claim that μ_{c}^{∗} cannot (in general) be equal to the hyperbolic equilibrium measure dμ_{K}^{h}. For suppose that they were equal and suppose that 0 ∈ K and that α = 0 ∈ K ∩ (K/c) is a regular point. It would follow that, evaluating at α = 0,

V_{h}(K) = ∫_{K} log | \frac{1}{β} | dμ_{c}^{∗}(β) = ∫_{K/c} log | \frac{1}{cβ} | dμ_{K/c}^{h} (β) = V_{h}(K/c) − log(c)

so that cap_{h}(K) = c cap_{h}(K/c). However, cap_{h} does not in general have this scaling property. In fact, Kirsch [8, p. 278], reports that

cap_{h}([0, r]) = exp\{ − \frac{π}{2} \frac{K(\sqrt{1 − r^{2}} )}{K(r)}\}

where

K(r) := ∫_{0}^{1} \frac{dx}{\sqrt{(1 − x^{2})(1 − r^{2}x^{2})}}

is the complete elliptic integral of the first kind.

In summary, the limiting measure seems to depend on the domain of analyticity of the basis function. To illustrate this further, we consider in the next section a family of functions with the same domain of analyticity.

4. The family of functions f^{c}(z) := (1 − z)^{−c} , c ⩾ 1
We again take K = [−a, a] ⊂ 𝔻 with 0 < a < 1. For s ∈ K^{n}, the matrix

M_{n}(s, s) = [(1 − s_{i}s_{j})^{−c} ] ∈ ℝ^{n×n} . For c = 1 we recover the matrix of the first section. Gross and Richards [7, (3.21)] give the remarkable formula

(4.1)  det(M_{n}(s, s)) = c_{n}(V (s))^{2} ∫_{U(n)} det(I − susu^{−1} )^{−(c+n−1)} du

where U(n) is the group of n × n complex unitary matrices. We remark that on the right-hand side, we may take s ∈ ℝ^{n×n} the diagonal matrix with diagonal the vector s of the left-hand side. The measure is Haar measure on U(n). The constant c_{n} depends on the parameter c but its exact value will not play a role for us.

In particular this formula allows them to conclude that the matrices M_{n}(s, s) are positive definite and hence have positive determinant.

First note that ∥susu^{−1} ∥_{2} ⩽ ∥s∥_{2}^{2} = (max_{1⩽i⩽n} |s_{i}|)^{2} ⩽ a^{2} so that the spectral radius ρ(susu^{−1} ) ⩽ a^{2}. It follows that 1 − a^{2} ⩽ |λ| ⩽ 1 + a^{2} for any eigenvalue λ of I − susu^{−1} , and hence

(1 − a^{2})^{n} ⩽ det(I − susu^{−1} ) ⩽ (1 + a^{2})^{n}.

Now consider the formula (4.1). We have

det([(1 − s_{i}s_{j})^{−c} ])

= c_{n}(V (s))^{2} ∫_{U(n)} det(I − susu^{−1} )^{−(c+n−1)} du

= c_{n}(V (s))^{2} ∫_{U(n)} \frac{det(I − susu^{−1} )^{−(c+n−1)}}{det(I − susu^{−1} )^{−(1+n−1)}} det(I − susu^{−1} )^{−(1+n−1)} du

= c_{n}(V (s))^{2} ∫_{U(n)} det(I − susu^{−1} )^{−(c−1)} det(I − susu^{−1} )^{−n} du.

Consequently, since by assumption c ⩾ 1,

det([(1 − s_{i}s_{j})^{−c} ]) ⩽ (1 − a^{2})^{−n(c−1)} c_{n}(V (s))^{2} ∫_{U(n)} det(I − susu^{−1} )^{−n} du

= (1 − a^{2})^{−n(c−1)} det([(1 − s_{i}s_{j})^{−1} ]) (4.2)

and similarly

det([(1 − s_{i}s_{j})^{−c} ]) ⩾ (1 + a^{2})^{−n(c−1)} c_{n}(V (s))^{2} ∫_{U(n)} det(I − susu^{−1} )^{−n} du

= (1 + a^{2})^{−n(c−1)} det([(1 − s_{i}s_{j})^{−1} ]). (4.3)

Let now s^{⋆} denote the points in K^{n} which maximize det([(1−s_{i}s_{j})^{−c} ]) and t^{⋆} those points in K^{n} which maximize det([(1 − s_{i}s_{j})^{−1} ]). By the definition of t^{⋆} we have directly that

det([(1 − s_{i}^{⋆}s_{j}^{⋆})^{−1} ]) ⩽ det([(1 − t_{i}^{⋆}t_{j}^{⋆})^{−1} ]).

Furthermore,

det([(1 − s_{i}^{⋆}s_{j}^{⋆})^{−1} ]) ⩾ (1 − a^{2})^{n(c−1)} det([(1 − s_{i}^{⋆}s_{j}^{⋆})^{−c} ]) by (4.2)

⩾ (1 − a^{2})^{n(c−1)} det([(1 − t_{i}^{⋆}t_{j}^{⋆})^{−c} ])

⩾ (1 − a^{2})^{n(c−1)} (1 + a^{2})^{−n(c−1)} det([(1 − t_{i}^{⋆}t_{j}^{⋆})^{−1} ]) by (4.3)

= ( \frac{1 − a^{2}}{1 + a^{2}} )^{n(c−1)} det([(1 − t_{i}^{⋆}t_{j}^{⋆})^{−1} ]).

We conclude that

lim_{n→∞} H(s^{⋆})^{1/\binom{n}{2}} = lim_{n→∞} H(t^{⋆})^{1/\binom{n}{2}}

and hence, by Theorem 2.2, that the optimal points for f^{c} also are asymptotically distributed according to the hyperbolic equilibrium measure, μ_{K}^{h}.

References

1. T. Bloom, L. Bos, C. Christensen, N. Levenberg, Polynomial interpolation of holomorphic functions in ℂ and ℂ^{n}, Rocky Mountain J. Math. 22(2) (1992), 441–470.

2. T. Bloom, L. Bos, J.-P. Calvi, N. Levenberg, Polynomial interpolation and approximation in ℂ^{d}, Ann. Polon. Math. 106 (2012), 53–81.

3. L. Bos, S. De Marchi, Univariate radial basis functions with compact support cardinal functions, East J. Approx. 14(1) (2008), 69–80.

4. , On optimal points for interpolation by univariate exponential functions, Dolomites Res. Notes Approx. DRNA 4 (2011), 8–12.

5. L. Bos, U. Maier, On the asymptotics of Fekete-type points for univariate radial basis functions, J. Approx. Theory 119(2) (2002), 252–270.

6. P. Davis, Interpolation and Approximation, Dover, New York, 1975.

7. K. Gross, D. St. P. Richards, Total positivity, spherical series, and hypergeometric functions of matrix argument, J. Approx. Theory 59(2) (1989), 224–246.

8. S. Kirsch, Transfinite Diameter, Chebyshev Constant and Capacity, Chapter 6 of Handbook of Complex Analysis, Volume 2: Geometric Function Theory, North Holland, 2005.

9. M. Tsuji, Potential Theory in Modern Function Theory, Maruzen, Tokyo, 1958.

10. D. Yarotsky, Univariate interpolation by exponential functions and Gaussian RBFs for generic sets of nodes, J. Approx. Theory 166 (2013), 163–175.

Department of Computer Science University of Verona, Verona, Italy

   leonardpeter.bos@univr.it

Department of Mathematics

University of Padova, Padova, Italy

   demarchi@math.unipd.it

Department of Mathematics

Indiana University, Bloomington, Indiana, U.S.A.

   nlevenbe@indiana.edu