On a new orthonormal basis for RBF native spaces and its fast computation

On a new orthonormal basis for RBF native spaces and its fast

computation

Stefano De Marchi and Gabriele Santin Torino: June 11, 2014

Outline

1 Introduction 2 Change of basis 3 WSVD Basis 4 The new basis 5 Numerical Results 6 Further work 7 References

2 of 33

Introduction

RBF Approximation

1 Data:

Ω ⊂ R

^{n, X}

⊂ Ω

, test function f X = {x1, . . . , xN} ⊂Ω

f1, . . . , fN, where fi = f (xi)

2 Approximation setting: kernel K_ε,

N

_K

(Ω)

,

N

_K

(

X

) ⊂ N

_K

(Ω)

kernelK = K_ε, positive definite and radial

native spaceN_K(Ω)(where K is the reproducing kernel) finite subspaceN_K(X )= span{K (·, x) : x ∈ X } ⊂ N_K(Ω)

Aim

Finds_f

∈ N

_K

(

X

)

s.t. s_f

≈

f

Introduction

RBF Approximation

1 Data:

Ω ⊂ R

^{n, X}

⊂ Ω

, test function f X = {x1, . . . , xN} ⊂Ω

f1, . . . , fN, where fi = f (xi)

2 Approximation setting: kernel K_ε,

N

_K

(Ω)

,

N

_K

(

X

) ⊂ N

_K

(Ω)

kernelK = K_ε, positive definite and radial

native spaceN_K(Ω)(where K is the reproducing kernel) finite subspaceN_K(X )= span{K (·, x) : x ∈ X } ⊂ N_K(Ω)

Aim

Finds_f

∈ N

_K

(

X

)

s.t. s_f

≈

f

3 of 33

Introduction

RBF Approximation

1 Data:

Ω ⊂ R

^{n, X}

⊂ Ω

, test function f X = {x1, . . . , xN} ⊂Ω

f1, . . . , fN, where fi = f (xi)

2 Approximation setting: kernel K_ε,

N

_K

(Ω)

,

N

_K

(

X

) ⊂ N

_K

(Ω)

kernelK = K_ε, positive definite and radial

native spaceN_K(Ω)(where K is the reproducing kernel) finite subspaceN_K(X )= span{K (·, x) : x ∈ X } ⊂ N_K(Ω)

Aim

Finds_f

∈ N

_K

(

X

)

s.t. s_f

≈

f

Introduction

Problem setting and questions

Problem:the standard basis of translates (data-dependent) of

N

_K

(

X

)

is unstable and not flexible

Question 1

Is it possible to find a “better” basisUofN_K(X)?

Question 2

How to embed information about K andΩin the basisU?

Question 3

Can we extractU⁰ ⊂ Us.t. s⁰

f is as good as s_f?

4 of 33

The “natural” basis

The “natural” (data-independent) basis for Hilbert spaces (Mercer’s theorem,1909)

Let K be a continuous, positive definite kernel on a bounded Ω ⊂ Rⁿ. Then K has an eigenfunction expansion with non-negative coefficients, the eigenvalues, s.t.

K (x, y) =

∞

X

j=0

λjϕj(x)ϕj(y), ∀ x, y ∈ Ω .

Moreover,

λjϕj(x) = Z

Ω

K (x, y)ϕj(y)dy := T [ϕj](x), ∀x ∈ Ω, j ≥ 0

{ϕj}_j>0 orthonormal∈ N_K(Ω)

{ϕj}_j>0 orthogonal∈ L2(Ω), kϕjk²

L2(Ω)=λj

−→ 0,∞

X

j>0

λ_j = K (0, 0) |Ω|, (the operator is oftrace-class)

Change of basis

Notation

Letting

Ω ⊂ R

^{nand X}

= {

x₁

, . . . ,

x_N

} ⊂ Ω

T

_X

= {

K

(·,

x_i

),

x_i

∈

X

}

: the standard basis of translates;

U = {

u_i

∈ N

_K

(Ω),

i

=

1

, . . . ,

N

}

: another basis s.t.

span

(U) =

span

(T

_X

) := N

_K

(Ω) .

At x

∈ Ω

,

T

_Xand

U

can be expressed as the row vectors T

(

x

) = [

K

(

x

,

x₁

), . . . ,

K

(

x

,

x_N

)] ∈ R

^N

U

(

x

) = [

u₁

(

x

), . . . ,

u_N

(

x

)] ∈ R

^N

.

we need also the scalar products

(

f

,

g

)

²_L

2(Ω)

:=

Z

Ω

f

(

x

)

g

(

x

)

dx

≈

N

X

j=1

w_jf

(

x_j

)

g

(

x_j

) =: (

f

,

g

)

²_`w 2(X )

.

6 of 33

Change of basis

General idea

Some useful results [Pazouki,Schaback 2011]

Change of basis

Let A_ij = K (x_i, x_j) ∈ R^N×N. Any basis U arises from a factorization A = V_U· C_U⁻¹, whereV_U = (u_j(x_i))_16i,j6NandC_U is the matrix of change of basis s.t. U(x) = T (x) · C_U.

Some consequences of this factorization

1. The interpolant P_f,X at x can be written as

Pf,X(x) =

N

X

j=1

Λj(f )uj(x) = U(x)Λ(f ), ∀x ∈ Ω

where Λ(f ) = [Λ1(f ), . . . , ΛN(f )]^T ∈ R^Nis a column vector of values of linear functionals defined by

Λ(f ) = C_U⁻¹· A⁻¹· fX= V_U⁻¹· fX,

where f_Xis the column vector given by the evaluations of f at X .

Change of basis

General idea

Some useful results [Pazouki,Schaback 2011]

Change of basis

Let A_ij = K (x_i, x_j) ∈ R^N×N. Any basis U arises from a factorization A = V_U· C_U⁻¹, whereV_U = (u_j(x_i))_16i,j6NandC_U is the matrix of change of basis s.t. U(x) = T (x) · C_U.

Some consequences of this factorization 1. The interpolant P_f,X at x can be written as

Pf,X(x) =

N

X

j=1

Λj(f )uj(x) = U(x)Λ(f ), ∀x ∈ Ω

where Λ(f ) = [Λ1(f ), . . . , ΛN(f )]^T ∈ R^Nis a column vector of values of linear functionals defined by

Λ(f ) = C_U⁻¹· A⁻¹· fX= V_U⁻¹· fX,

where f_Xis the column vector given by the evaluations of f at X .

7 of 33

Change of basis

Consequences

2. If U is a N_K(Ω)-orthonormal basis, we get thestability estimate 

Pf,X(x) 6

qK (0, 0) kfkK ∀x ∈ Ω. (1)

In particular, for fixed x ∈ Ω and f ∈ NKthe values kU(x)k2and kΛ(f )k₂, are the same for all N_K(Ω)-orthonormal bases

independently on X kU(x)k26

qK (0, 0), kΛ(f)k26 kfkK. (2)

Change of basis

Other results [Pazouki,Schaback 2011]

Change of basis

Each

N

_K

(Ω)

-orthonormal basis

U

arises from an orthornormal decompositionA =B^T ·B with B

=

C_U⁻¹

,

V_U

=

B^T

= (

C_U⁻¹

)

^T.

Each

`

₂

(

X

)

-orthonormal basis

U

arises from a decomposition A =Q·B with Q

=

V_U,Q^TQ =I, B

=

C_U⁻¹

=

Q^TA .

Notice: the best bases in terms of stability are the

N

_K

(Ω)

-orthonormal ones!

Q1:It is possible to find a “better” basis?Yes, we can!

9 of 33

Change of basis

Other results [Pazouki,Schaback 2011]

Change of basis

Each

N

_K

(Ω)

-orthonormal basis

U

arises from an orthornormal decompositionA =B^T ·B with B

=

C_U⁻¹

,

V_U

=

B^T

= (

C_U⁻¹

)

^T.

Each

`

₂

(

X

)

-orthonormal basis

U

arises from a decomposition A =Q·B with Q

=

V_U,Q^TQ =I, B

=

C_U⁻¹

=

Q^TA .

Notice: the best bases in terms of stability are the

N

_K

(Ω)

-orthonormal ones!

Q1:It is possible to find a “better” basis?Yes, we can!

Change of basis

Other results [Pazouki,Schaback 2011]

Change of basis

Each

N

_K

(Ω)

-orthonormal basis

U

arises from an orthornormal decompositionA =B^T ·B with B

=

C_U⁻¹

,

V_U

=

B^T

= (

C_U⁻¹

)

^T.

Each

`

₂

(

X

)

-orthonormal basis

U

arises from a decomposition A =Q·B with Q

=

V_U,Q^TQ =I, B

=

C_U⁻¹

=

Q^TA .

Notice: the best bases in terms of stability are the

N

_K

(Ω)

-orthonormal ones!

Q1:It is possible to find a “better” basis?Yes, we can!

9 of 33

WSVD Basis

Main idea: I

Q2:How to embed information on K and

Ω

in

U

?

Symmetric Nystr ¨om method [Atkinson,Han 2001]

The main idea for the construction of our basis is to discretize the

“natural” basis introduced in Mercer’s theorem.

To this aim, consider onΩacubature rule(X, W),that is a set of distinct points X= {x_j}^N_j=1 ⊂Ωand a set ofpositive weights W= {w_j}^N_j=1, N∈ N, such that

Z

Ω

f(y)dy ≈ XN

j=1

f(x_j)w_j ∀f ∈ N_K(Ω). (3)

WSVD Basis

Main idea: II

Thus, the operator

T

_K can be evaluated on X as

λ

_j

ϕ

_j

(

x_i

) =

Z

Ω

K

(

x_i

,

y

)ϕ

_j

(

y

)

dy i

=

1

, . . . ,

N

, ∀

j

>

0

,

and then discretized using the cubature rule by

λ

_j

ϕ

_j

(

x_i

) ≈ X

N

h=1

K

(

x_i

,

x_h

)ϕ

_j

(

x_h

)

w_h i

,

j

=

1

, . . . ,

N

.

(4)

Letting W

= diag(

w_j

)

, it suffices to solve the followingdiscrete eigenvalue problemin order to find the approximation of the eigenvalues and eigenfunctions (evaluated on X ) of

T

_K

[

f

]

:

λ

v

= (

A

·

W

)

v (5)

11 of 33

WSVD basis

Main idea: III

A solution is to rewrite (4) using the fact that the weights are positive as

λ

_j

( √

w_i

ϕ

_j

(

x_i

)) = X

N

h=1

( √

w_i

Φ(

x_i

,

x_h

) √

w_h

)( √

w_h

ϕ

_j

(

x_h

)) ∀

i

,

j

=

1

, . . . ,

N

,

(6) and then to consider the correspondingscaled eigenvalue problem

λ  √

W

·

v



=  √

W

·

A

·

√

W

  √

W

·

v



which is equivalent to the previous one, now involving the symmetric and positive definite matrix A_W := √

W·A · √ W .

WSVD Basis

Definition

{λ

_j

, ϕ

_j

}

_j>0 are then approximated by eigenvalues/eigenvectors of A_W

:= √

W

·

A

· √

W . This matrix is normal, then a singular value decomposition of A_W is a unitary diagonalization.

Definition:

A weighted SVD basisUis a basis forN_K(X)s.t.

V_U =

√

W⁻¹·Q·Σ, C_U =

√

W·Q·Σ⁻¹ since A =V_UC_U⁻¹, then A_W =Q·Σ²·Q^T is the SVD .

Here

Σ

_jj

= σ

_j

,

j

=

1

, . . . ,

N and

σ

²₁

≥ · · · ≥ σ

²_N

>

0 are the singular values of A_W.

13 of 33

WSVD Basis

Properties

This basis is in fact an approximation of the “natural” one (provided w_i

>

0,

P

N

i=1w_i

= |Ω|

)

Properties of the new basis U (cf. [De Marchi-Santin 2013])

u_j

(

x

) =

¹

σ

²_j

X

N

i=1

w_iu_j

(

x_i

)

K

(

x

,

x_i

) ≈

¹

σ

²_j

T

_K

[

u_j

](

x

)

,

∀

1

6

^j

6

^N

, ∀

x

∈ Ω

;

N

_K

(Ω)

-orthonormal

`

^w₂

(

X

)

-orthogonal,

k

u_j

k

²_`w

2(X )

= σ

²_j

∀

u_j

∈ U X

N

j=1

σ

²_j

=

K

(

0

,

0

) |Ω|

WSVD Basis

Properties

This basis is in fact an approximation of the “natural” one (provided w_i

>

0,

P

N

i=1w_i

= |Ω|

)

Properties of the new basis U (cf. [De Marchi-Santin 2013])

u_j

(

x

) =

¹

σ

²_j

N

X

i=1

w_iu_j

(

x_i

)

K

(

x

,

x_i

) ≈

¹

σ

²_j

T

_K

[

u_j

](

x

)

,

∀

1

6

^j

6

^N

, ∀

x

∈ Ω

;

N

_K

(Ω)

-orthonormal

`

^w₂

(

X

)

-orthogonal,

k

u_j

k

²_`w

2(X )

= σ

²_j

∀

u_j

∈ U X

N

j=1

σ

²_j

=

K

(

0

,

0

) |Ω|

14 of 33

WSVD Basis

Approximation

Interpolant:s_f

(

x

) = P

N

j=1

(

f

,

u_j

)

Ku_j

(

x

) ∀

x

∈ Ω

WDLS:s^M

f

:= argmin

 k

f

−

g

k

`w2(X )

:

g

∈ span{

u₁

, . . . ,

u_M

}



Weighted Discrete Least Squares as truncation:

Let f

∈ N

_K

(Ω)

, 1

6

^M

6

^{N. Then}

∀

x

∈ Ω

s_f^M(x) =

M

X

j=1

(f, uj)_`^w

2(X)

(uj, u_j)_`w 2(X)

uj(x) =

M

X

j=1

(f, uj)_`^w

2(X)

σ²_j uj(x) =

M

X

j=1

(f, uj)Kuj(x)

Q3:Can we extract

U

⁰

⊂ U

s.t. s⁰

f is as good as s_f?Yes we can: takeU⁰ = {u₁, . . . ,u_M}.

WSVD Basis

Approximation

Interpolant:s_f

(

x

) = P

N

j=1

(

f

,

u_j

)

Ku_j

(

x

) ∀

x

∈ Ω

WDLS:s^M

f

:= argmin

 k

f

−

g

k

`w2(X )

:

g

∈ span{

u₁

, . . . ,

u_M

}



Weighted Discrete Least Squares as truncation:

Let f

∈ N

_K

(Ω)

, 1

6

^M

6

^{N. Then}

∀

x

∈ Ω

s_f^M(x) =

M

X

j=1

(f, uj)_`^w

2(X)

(uj, u_j)_`w 2(X)

uj(x) =

M

X

j=1

(f, uj)_`^w

2(X)

σ²_j uj(x) =

M

X

j=1

(f, uj)Kuj(x)

Q3:Can we extract

U

⁰

⊂ U

s.t. s⁰

f is as good as s_f?Yes we can:

takeU⁰ = {u₁, . . . ,u_M}.

15 of 33

WSVD Basis

Approximation II

If we define the pseudo-cardinal functions as`˜i = s<sub>`</sub>^M

i, we get s^M_f (x) =

N

X

i=1

f (xi)˜`i(x), ˜`i(x) =

M

X

j=1

uj(xi) σ²_j uj(x).

Generalized Power Function and Lebesgue constant:

If f ∈ N_K(Ω), 

f (x) − s^M

f (x) 

 6P_K,X^(M)(x)kf k_N

K(Ω) ∀x ∈ Ω, where hP_K,X^(M)(x)i²

= K (0, 0) −

M

X

j=1

[uj(x)]².

Moreover,ks^Mk 6 ˜Λ kf k .

WSVD Basis

Sub-basis

How can we extractU⁰⊂ Us.t. s⁰

f is as good as s_f?Idea.

0 100 200 300 400 500 600 700 800 900

10⁻²⁰ 10⁻¹⁵ 10⁻¹⁰ 10⁻⁵ 10⁰ 10⁵

← ε = 1 ← ε = 4

← ε = 9

Figure: Gaussian kernel,σ²_j on equispaced points of the square

recall that

k

u_j

k

_`^w

2(X )

= σ

²_j

→

0 we can choose M s.t.

σ

²_M+1

< tol

we don’t need u_j, j

>

M

17 of 33

WSVD Basis

An Example: I

−0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8

−0.8

−0.6

−0.4

−0.2 0 0.2 0.4 0.6 0.8

−1 −0.5 0 0.5 1

−1

−0.5 0 0.5 1

0 0.2 0.4 0.6 0.8 1

0 0.2 0.4 0.6 0.8 1

Figure:The domains used in the numerical experiments with an example of the corresponding sample points.

Fromleft to right: the lens Ω1(trigonometric-gaussian points), the disk Ω2

(trigonometric-gaussian points) and the square Ω3(product Gauss-Legendre points).

WSVD Basis

An Example: II

ε =

1

ε =

4

ε =

9

Gaussian 100 340 500

IMQ 180 580 580

Matern3 460 560 580

Table:Optimal Mfor different kernels and shape parameter that correspond to the indexes such that the weighted least-squares approximant s_f^M provides the best approximation of the function f (x, y) = cos(20(x + y)) on the disk with center C = (1/2, 1/2) and radius R = 1/2

19 of 33

WSVD Basis

An Example: III

0 100 200 300 400 500 600 700 800 900 1000

10⁻⁶ 10⁻⁴ 10⁻² 10⁰ 10²

0 100 200 300 400 500 600 700 800 900 1000

10⁻⁶ 10⁻⁵ 10⁻⁴ 10⁻³ 10⁻² 10⁻¹ 10⁰ 10¹ 10²

10³ RMS error

WSvd Std

0 100 200 300 400 500 600 700 800 900 1000

10⁻⁶ 10⁻⁴ 10⁻² 10⁰ 10²

0 100 200 300 400 500 600 700 800 900 1000

10⁻⁷ 10⁻⁶ 10⁻⁵ 10⁻⁴ 10⁻³ 10⁻² 10⁻¹ 10⁰ 10¹ 10²

10³ RMS error

WSvdStd

Figure:Franke’s test function, lens, IMQ Kernel,ε = 1 and RMSE.

Left: complete basis.Right:σ²_M+1< 10⁻¹⁷.

Problem:We have to compute the whole basis before truncation! Solution:Krylov methods.

WSVD Basis

An Example: III

0 100 200 300 400 500 600 700 800 900 1000

10⁻⁶ 10⁻⁴ 10⁻² 10⁰ 10²

0 100 200 300 400 500 600 700 800 900 1000

10⁻⁶ 10⁻⁵ 10⁻⁴ 10⁻³ 10⁻² 10⁻¹ 10⁰ 10¹ 10²

10³ RMS error

WSvd Std

0 100 200 300 400 500 600 700 800 900 1000

10⁻⁶ 10⁻⁴ 10⁻² 10⁰ 10²

0 100 200 300 400 500 600 700 800 900 1000

10⁻⁷ 10⁻⁶ 10⁻⁵ 10⁻⁴ 10⁻³ 10⁻² 10⁻¹ 10⁰ 10¹ 10²

10³ RMS error

WSvdStd

Figure:Franke’s test function, lens, IMQ Kernel,ε = 1 and RMSE.

Left: complete basis.Right:σ²_M+1< 10⁻¹⁷.

Problem:We have to compute the whole basis before truncation!

Solution:Krylov methods.

20 of 33

The new basis

Arnoldi iteration

Consider Aij = K (x_i, xj) (which is symmetric), b_i = f (x_i), 1 6 i, j 6 N define theKrylov subspaceK_M(A, b) = span{b, Ab, . . . , A^M−1b}, M  N.

compute an o.n. basis {φ₁, . . . , φ_M} of K_M(A, b) and form Φ_M = [φ₁, . . . , φ_M], N × M

define the (tridiagonal) matrix H_M= Φ^T_MA Φ_M which represents the projection of A into KM(A, b)

Arnoldi iterationgivesA Φ_M= Φ_M+1H_Mwhere H_M=

"

HM

hM+1,Me^T_M

# is (M + 1) × M. In practice hM+1,M ≈ 0 so that KM+1(A, b) = KM(A, b).

The new basis

Approximation of the SVD

Consider a SVDH_M =U_MΣ²_MV_M^T, where U_M

∈ R

(M+1)×(M+1)

, V_M

∈ R

^M×M,

Σ

²_M

= h ˜ Σ

²_M

,

0

i

T

and

Σ ˜

²_M

= diag(σ

²_M,1

, . . . , σ

²_M,M

)

.

Approximate SVD (Novati-Russo 2013:)

Let U_M

= Φ

M+1U_M, V_M

= Φ

MV_M, then A V_M

=

U_M

Σ

²_M

,

A U_M

=

V_M

(Σ

²_M

)

^T

the first M singular values of A are well approx. by

σ

²_M,j If M

=

N, in exact arithmetic the triplet



Φ

_M+1U

˜

_M

, ˜ Σ

_M

, Φ

_MV_M



is a SVD of A , where_U

˜

_{M is UM} without the last column.

22 of 33

The new basis

Definition

Recall:

A

Φ

_M

= Φ

_M+1H_M H_M

=

U_M

Σ

²_MV_M^T

Σ

²_M

= h ˜ Σ

²_M

,

0

i

T

U

˜

_M is U_M without the last column.

Definition:

The sub-basisU_M is a set{u₁, . . . ,u_M} ⊂ N_K(X)defined by V_U = Φ_M+1U˜_MΣ˜_M, C_U = Φ_MV_MΣ˜⁻¹_M .

The new basis

Properties

Properties [De Marchi, Santin 2014]:

The sub-basis

U

_M has the following properties for each 1

6

^M

6

^N:

1 it is

`

₂

(

X

)

-orthogonal with

k

u_j

k

_{`2(X )}

= σ

²_M,j 1

6

^j

6

^M

2 it is near-orthonormal in

N

_K

(Ω)

3 if M

=

N it is the SVD basis

U

(

Φ

_M

=

I)

About point 2: it means that

(

u_i

,

u_j

) = δ

_ij

+

r_ij^(M)where

(

R^(M)

)

ij

:=

r_ij^(M)is a rank one matrix for 1

6

^M

6

^{N, and r}_ij^(M)

=

0 if M

=

N;

24 of 33

The new basis

Properties

Using this basis we get

∀

f

∈ N

_K

(Ω)

s⁰

f(x) = XM

j=1

(f,u_j)_{`2(X )}

σ²_M,j ^uj(x) = XM

j=1

(f,u_j)_Ku_j(x) ∀x∈Ω

(and P_K,X^(M)

(

x

)

,

˜ Λ

_X as before)

Numerical Results

Stopping rule: I

Fix

τ >

0

H_M

M+1,M ≈σ²_M,j < τ

ora better choiceis the following



      

X

M

j=1

(

H_M

)

_jj

−

N

       

< τ,

(7)

that works for functions lying in the native space of the kernel.

26 of 33

Numerical Results

Stopping rule: II

The decay of the residual described in (7) compared to the

corresponding RMSE goes as in the Figure below withτ = 1.e − 15

0 50 100 150

10⁻¹⁶ 10⁻¹⁴ 10⁻¹² 10⁻¹⁰ 10⁻⁸ 10⁻⁶ 10⁻⁴ 10⁻² 10⁰ 10²

m

hm+1,m σ_m,m² svd(A)

0 50 100 150

10⁻¹⁰ 10⁻⁹ 10⁻⁸ 10⁻⁷ 10⁻⁶ 10⁻⁵ 10⁻⁴ 10⁻³ 10⁻² 10⁻¹ 10⁰

m

RMSE

Figure:Gaussian kernel,ε = 1, square [−1, 1]², N = 200 e.s. points,

Numerical Results

CPU time comparison

For each N we compute theoptimal Musing the new algorithm with toleranceτ = 1e − 14.

N 121 225 361 529 729 961 1225 1521

optimal M 100 110 113 114 114 115 115 116

RMSE 5.0e-08 3.4e-10 1.0e-10 6.7e-11 6.4e-11 5.5e-11 4.7e-11 3.4e-11 new

RMSE 5.0e-08 3.3e-09 1.3e-09 1.1e-09 1.1e-09 8.3e-10 7.8e-10 7.9e-10 WSVD

Time 1.7e-01 3.4e-01 6.1e-01 1.0e+00 1.6e+00 2.6e+00 3.7e+00 6.5e+00 new

Time 3.3e-01 7.2e-01 1.5e+00 4.2e+00 1.0e+01 2.5e+01 5.5e+01 1.1e+02 WSVD

Table:Comparison between the WSVD basis and the new basis.

Computational time in seconds and corresponding RMSE, restricted to n = 49, . . . , 1600 equally spaced points.

28 of 33

Approximated Power function and Lebesgue function

Figure:Approximated power function (left, logarithmic plot) and approximated Lebesgue function (right) Ω

Numerical Results

Another example

−1 −0.5 0 0.5 1

−0.8

−0.6

−0.4

−0.2 0 0.2 0.4 0.6 0.8

−1

−0.5 0

0.5 1

−1

−0.5 0 0.5 1 0 0.5 1 1.5 2 2.5 3 3.5

−7

−6

−5

−4

−3

−2

Figure:IMQ kernel,ε = 1, cutted-disk, N = 1600 random points, M = 260, f (x, y) = exp(|x − y|) − 1

30 of 33

Numerical Results

Lebesgue Constant and Power Function

−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1

−1

−0.8

−0.6

−0.4

−0.2 0 0.2 0.4 0.6 0.8 1

Λ_X = 160.2017

0.6 0.8 1 1.2 1.4 1.6 1.8 2 2.2

−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1

−1

−0.8

−0.6

−0.4

−0.2 0 0.2 0.4 0.6 0.8 1

4 5 6 7 8 9 x 10⁻⁶

Figure:IMQ kernel,ε = 1, cutted-disk, N = 1600 random points, M = 260, f (x, y) = exp(|x − y|) − 1. Left: Lebesgue function. Right:

Further work

More analysis has to be done a better stopping rule

understand the decay rate of P_K,X^(M) understand the growing rate of

Λ ˜

_X understand how X ,

ε

influence s⁰

f

Thank you for your attention!

32 of 33

Further work

More analysis has to be done a better stopping rule

understand the decay rate of P_K,X^(M) understand the growing rate of

Λ ˜

_X understand how X ,

ε

influence s⁰

f

Thank you for your attention!

References

R. K. Beatson, J. B. Cherrie, C. T. Mouat .

Fast fitting of radial basis functions: methods based on preconditioned GMRES iteration.

Adv. Comp. Math., 11 : 253–270, 1999.

S. De Marchi, G. Santin.

A new stable basis for radial basis function interpolation.

J. Comput. Appl. Math., 253 : 1–13, 2013.

S. De Marchi, G. Santin.

Fast computation of orthonormal bases for RBF spaces through Krylov spaces methods preprint., 2014.

G. Fasshauer, M. J. McCourt.

Stable evaluation of Gaussian radial basis functions interpolants.

SIAM J. Sci. Comput., 34: A737–A762, 2012.

A. C. Faul, M. J. D. Powell.

Krylov subspace methods for radial basis function interpolation.

Chapman & Hall/CRC Res. Notes Math., 420 : 115–141, 1999.

P. Novati, M. R. Russo.

A GCV based Arnoldi-Tikhonov regularization method.

BIT Numerical Analysis, DOI: 10.1007/S10543-013-0447-Z, 2013.

M. Pazouki, R. Schaback.

Bases for kernel-based spaces.

J. Comput. Appl. Math., 236 : 575–588, 2011.

M. Vianello and G. Da Fies.

Algebraic cubature on planar lenses and bubbles.

Dolomites Res. Notes Approx. DRNA 15, 7–12, 2012.

33 of 33