On a new orthonormal basis for RBF native spaces

On a new orthonormal basis for RBF native spaces

Stefano De Marchi and Gabriele Santin San Diego: July 8, 2013

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

Problem setting

Problem:the standard (data-dependent) basis 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ΩinU?

Question 3

Can we extractU⁰ ⊂ Us.t. s⁰

f is as good as s_f?

Q1:It is possible to find a “better” basis?

Change of basis ([Pazouki-Schaback 2011]):

Let A_ij

=

K

(

x_i

,

x_j

) ∈ R

^N×N. Any basis

U

arises from a

factorizationA

=

V_U

·

C_U⁻¹, whereC_U is the matrix of change of basis,V_U

= (

u_j

(

x_i

))

_16i,j6N.

Each

N

_K

(Ω)

-orthonormal basis

U

arises from a 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 .

The best bases in terms of stability are theN_K(Ω)-o.n. ones.

Motivation

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

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) |Ω|

Definition

Q2:How to embed information on K and

Ω

in

U

?

Idea:Approximate the integral equation

λ

_j

ϕ

_j

(

x

) = T [ϕ

_j

](

x

)

with thesymmetric Nystr ¨om method, with a cubature formula

(

X

, W)

:

{λ

_j

, ϕ

_j

}

_j>0 are approximated by eigenvalues/eigenvectors of A_W

:= √

W

·

A

· √

W , with W

= diag(

w_j

)

, i.e. the solution of the scaled eigenvalue problem

λ( √

W

·

v

) =

A_W

(

√

W

·

v

)

.

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 (and unitary diagonalization).

Properties

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

>

0,

P

_N

i=1w_i

= |Ω|

):

Properties (cf. [De Marchi-Santin 2013])

σ

²_j u_j

(

x

) = T

_KN

[

u_j

](

x

)

where T_KN

[

u_j

](·) := (

u_j

,

K

(·,

x

))

_`w

2(X )

∀

j

, ∀

x

∈ Ω N

_K

(Ω)

-orthonormal

`

^w₂

(

X

)

-orthogonal,

k

u_j

k

²_`w

2(X )

= σ

²_j

∀

j

P

_N

j=1

σ

²_j

=

K

(

0

,

0

) |Ω|

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

}



WDLS as truncation:

Let f

∈ N

_K

(Ω)

, 1

6

^M

6

^{N. Then}

∀

x

∈ Ω

s^M

f

(

x

) =

X

M

j=1

(

f

,

u_j

)

_`^w

2(X )

(

u_j

,

u_j

)

_`w 2(X )

u_j

(

x

) = X

M

j=1

(

f

,

u_j

)

_Ku_j

(

x

)

Q3:Can we extract

U

⁰

⊂ U

s.t. s⁰

f is as good as s_f?We can take

U

⁰

= {

u₁

, . . . ,

u_M

}

.

Approximation II

If we define the pseudo-cardinal functions as

` ˜

_i

=

s^M_`

i, we get

˜ `

_i

(

x

) = P

_M

j=1 uj(xi)

σ²_j u_j

(

x

),

s^M

f

(

x

) = P

_N

i=1f

(

x_i

)˜ `

_i

(

x

).

Generalized Power Function and Lebesgue constant:

If f

∈ N

_K

(Ω)

,

  



^f

(

x

) −

s^M

f

(

x

)     6

^P

(M) K,X

(

x

)k

f

k

_N

K(Ω)

∀

x

∈ Ω

, where



P_K,X^(M)

(

x

)



2

=

K

(

0

,

0

) − X

M

j=1

[

u_j

(

x

)]

²

.

Moreover,

k

s^M

f

k

_∞

6 ˜ Λ

_X

k

f

k

_X.

Sub-basis

Q3:Can we extract

U

⁰

⊂ U

s.t. s⁰

f is as good as s_f?We can take

U

⁰

= {

u₁

, . . . ,

u_M

}

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

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. From left to right: the lens Ω1

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

An Example: II

ε =

1

ε =

4

ε =

9

Gaussian 100 340 500

IMQ 180 580 580

Matern3 460 560 580

Table:Optimal M for 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

An Example: III

0 100 200 300 400 500 600 700 800 900 1000

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

N

RMSE

WSvd Std

0 100 200 300 400 500 600 700 800 900 1000

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

N

RMSE

WSvd Std

Figure:Franke’s 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.

Arnoldi iteration

Consider Aij = K (x_i, xj), b_i = f (x_i), 1 6 i, j 6 N

define the Krylov subspace KM(A, b) = span{b, Ab, . . . , A^M−1b}, M  N.

compute an o.n. basis {φ₁, . . . , φ_M} of K_M(A, b)

define the (tridiagonal) matrix H_Mwhich represents the projection of A into K_M(A, b) (since Φ^T_MA Φ_M = H_M, with

ΦM = [φ1, . . . , φM], N × M)

Arnoldi’s algorithm givesA Φ_M= Φ_M+1H_M where H_M =

"

HM

hM+1,Me_M^T

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

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.

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 .

Properties

Properties:

The sub-basis

U

_M has the following properties for each 1

6

^M

6

^N:

it is

N

_K

(Ω)

-orthonormal

it is

`

₂

(

X

)

-orthogonal with

k

u_j

k

_{`2(X )}

= σ

²_M,j 1

6

^j

6

^M if M

=

N it is the SVD basis

U

(

Φ

_M

=

I)

Using this basis we get

∀

f

∈ N

_K

(Ω)

s⁰

f

(

x

) =

M

X

j=1

(

f

,

u_j

)

_{`2(X )}

σ

²_M,j ^uj

(

x

) =

M

X

j=1

(

f

,

u_j

)

_Ku_j

(

x

) ∀

x

∈ Ω

(and P_K,X^(M)

(

x

)

,

˜ Λ

_X as before)

Stopping rule



H_M



M+1,M

≈ σ

²_M,j

<

10⁻¹³

0 50 100 150

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

M

hM+1,M σM,M

2 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, f ∈ N_K(Ω), with f (x) = K (x, y1) + 2K(x, y2) − 2K(x, y3) + 3K(x, y4),

y1 = (0, −1.2), y2 = (−0.4, 0.5), y3 = (−0.4, 1.1), y4 = (1.2, 1.3).

Comparison with the SVD basis

0 200 400 600 800 1000 1200 1400 1600

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

Time

Lanc.

WSVD

0 200 400 600 800 1000 1200 1400 1600

10⁻¹⁰ 10⁻⁹ 10⁻⁸ 10⁻⁷ 10⁻⁶

RMSE

Lanc.

WSVD

Figure:Gaussian kernel,ε = 1, disk, trig.-gauss. points, f ∈ N_K(Ω)

An 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

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:

power function

Further investigation is needed:

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

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.

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.

preprint, 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.