## Description

## Problems

Theory

1. Let (ℋ, ‖ · ‖,⟨·, ·⟩) be an RKHS of functions from a set 𝒳 → R, with kernel 𝐾. Given a pointset

𝑋 = {𝑥1, . . . , 𝑥𝑚} ⊂ 𝒳 consider the interpolation problem

{︃

minimize𝑢∈ℋ ‖𝑢‖

subject to 𝑢(𝑋) = y.

Suppose the 𝑥𝑚 are distinct and that 𝐾(𝑋, 𝑋) is invertible. Prove that the minimizer 𝑢

⋆

is given by

the formula

𝑢

⋆ = 𝐾(·, 𝑋)𝐾(𝑋, 𝑋)

−1y. (1)

2. Let (ℋ, ‖ · ‖,⟨·, ·⟩) be an RKHS of functions from a set 𝒳 → R, with kernel 𝐾.

(a) Let 𝜑 ∈ ℋ*

, be a bounded linear functional on ℋ. Show that the function 𝐾𝜑 : 𝑥 ↦→ 𝜑(𝐾(·, 𝑥))

(this simply means the functional 𝜑 is applied to 𝐾(·, 𝑥) as a function from 𝒳 → R for each fixed

𝑥) is the Riesz representer of 𝜑 with respect to the RKHS inner product. That is,

𝜑(𝑓) = ⟨𝐾𝜑, 𝑓⟩. (2)

Hint: (i) First consider the case of 𝑓 belonging to the pre-Hilbert space ℋ0; (ii) Observe that

by taking 𝜑 to be the pointwise evaluation functional (2) is nothing more than the reproducing

property.

(b) Consider the setting of Problem 2. Let 𝜑1, . . . , 𝜑𝑚 ∈ ℋ* be a sequence of bounded linear functionals

on ℋ. Show that the orthogonal complement of span{𝐾𝜑1, . . . , 𝐾𝜑𝑚} is precisely the subspace

{𝑓 ∈ ℋ | 𝜑𝑗 (𝑓) = 0, 𝑗 = 1, . . . , 𝑚}.

(c) Define the bounded linear operator

𝜑 : ℋ → R

𝑚, 𝜑(𝑓) := (𝜑1(𝑓), . . . , 𝜑𝑚(𝑓))𝑇

,

and consider the (generalized) interpolation problem

{︃

minimize𝑢∈ℋ ‖𝑢‖

subject to 𝜑(𝑢) = y.

Consider the matrix Θ ∈ R

𝑚×𝑚 with entries Θ𝑖𝑗 = 𝜑𝑖(𝐾𝜑𝑗 ). Prove that whenever Θ is invertible

then the minimizer 𝑢

⋆

is given by the formula

𝑢

⋆ =

∑︁𝑚

𝑗=1

𝛼

⋆

𝑗𝐾𝜑𝑗 , where 𝛼

⋆ = Θ−1

.

Hint: Observe that if the 𝜑𝑗 = 𝛿𝑥𝑗 were pointwise evaluation functionals at a set of points

𝑋 = {𝑥1, . . . , 𝑥𝑚} then the above result coincides with formula (1).

3. Let 𝐿 = 𝐷 − 𝑊 ∈ R

𝑛×𝑛 be the unnormalized Laplacian and let 𝐿˜ = 𝐷−1/2

(𝐷 − 𝑊)𝐷−1/2 be the

normalized Laplacian.

Show that

(a) (𝜆, v) is an eigenpair of 𝐿˜ iff v = 𝐷1/2u where u solves the generalized eigenvalue problem

𝐿u = 𝜆𝐷u.

(b) Show that if 𝐺 is a disconnected graph without isolated vertices and with 𝑀-connected components

then 𝐿˜ has an 𝑀-dimensional null-space spanned by the weighted set functions 𝐷1/21𝐺𝑗 where

1𝐺𝑗

is the indicator vector of the 𝑗-th connected component 𝐺𝑗 .

(c) Show that 𝜆𝑗 ≤ 2 for all 𝑗 ≤ 𝑛, i.e., the eigenvalues of 𝐿˜ are uniformly bounded. Can you say

the same about the eigenvalues of 𝐿? Hint: Look up the Courant-Fisher-Weyl characterization of

eigenvalues.

## Computation

Prepare a report of a maximum of four pages for this computational exercise addressing the

tasks outlined below as well as pertinent mathematical background, algorithmic details, and

your findings.

In this problem you will use a specific construction of the graph Laplacian operator to approximate the

Laplacian differential operator on arbitrary domains. In parts 1–4 you work on the unit box and verify that

the eigenvectors of the graph Laplacian converge to those of the differential operator. In part 5, you modify

the domain to an L-shaped domain.

In correspondence with the literature on graph Laplacians here we

assume the eigenvalues of matrices are ordered in increasing order. Some of the calculations here can be

expensive and the matrices can become quite large. Make sure you take advantage of sparse matrices and

benchmark your code with small data sets.

1. Let Ω = [0, 1]2 ⊂ R

2 and let 𝑥1, . . . , 𝑥𝑚 be uniformly distributed random points in Ω. We define

𝑋 = {𝑥1, . . . , 𝑥𝑚} to be our set of scattered data points and define the weighted graph 𝐺 = {𝑋, 𝑊}

with the weight matrix 𝑊 ∈ R

𝑚×𝑚 as

𝑤𝑖𝑗 = 𝜅𝜀(‖x𝑖 − x𝑗‖2), where 𝜅𝜀(𝑡) :=

{︃

(𝜋𝜀2

)

−1

𝑡 ≤ 𝜀,

0 𝑡 > 𝜀.

The parameter 𝜀 > 0 controls the bandwidth of the kernel 𝜅 and in turn the local connectivity of the

graph 𝐺. Throughout this assignment we choose

𝜀 = 𝐶

log(𝑚)

3/4

𝑚1/2

,

where 𝐶 > 0 is a constant (you should find that 𝐶 = 1 is sufficient but feel free to tune this number).

Let 𝐿 = 𝐷 − 𝑊 be the unnormalized graph Laplacian matrix of 𝐺 and fix 𝑚 = 2048. Then compute

the first four eigenvectors of 𝐿, i.e., those corresponding to the four smallest eigenvalues of 𝐿.

Present

a plot of these four eigenvectors as functions over Ω; you may use 3D scatter plots or contour plots.

2. Now consider the differential operator

ℒ𝑓 ↦→ −(︃

∂

2𝑓

∂𝑥2

1

+

∂

2𝑓

∂𝑥2

2

)︃

,

that is well-defined for functions 𝑓 : Ω ↦→ R that are twice continuously differentiable, i.e., 𝑓 ∈ 𝐶

2

(Ω).

Observe that for integers 𝑛, 𝑘 ≥ 0, the functions

𝜓(x) = cos(𝑛𝜋𝑥1) cos(𝑘𝜋𝑥2),

solve the Neumann eigenvalue problem for the operator ℒ, i.e.,

ℒ𝜓 = 𝜆(𝑛, 𝑘)𝜓, in Ω,

∇𝜓 · n = 0, on Boundary of Ω.

where n denotes the outward unit normal vector on the boundary of Ω.

Now let q1, . . . q4 ∈ R

𝑚 be the eigenvectors of the graph Laplacian 𝐿 as computed in part 1, and define

the vectors 𝜓1, . . . ,𝜓4 ∈ R

𝑚 as follows

𝜓𝑗 =

𝜓˜

𝑗

‖𝜓˜

𝑗‖2

,

where the entries of 𝜓˜

𝑗

contain the point values of the first four eigenfunctions 𝜓(𝑥), at the vertices 𝑋.

Once again fix 𝑚 = 2048 and present a plot of the vectors 𝜓1, . . .𝜓4 akin to part 1. Inspect the plots

visually and comment on similarities and differences between q𝑗 and the 𝜓𝑗 .

3. We now wish to show that span{q1, . . . , q4} ≈ span{𝜓1, . . . ,𝜓4}. Choose 𝑚 = 27

, 2

5

, . . . , 2

10.

For each

value of 𝑚 proceed as in part 1 to generate the random points 𝑋, compute the corresponding value

of 𝜀(𝑚), and compute the four eigenvectors q1, . . . , q4. Also compute the vectors 𝜓1, . . . ,𝜓4 as above.

Then define the matrices

𝑄 := [q1| . . . |q4] ∈ R

𝑚×4

, Ψ := [𝜓1, . . . ,𝜓4] ∈ R

𝑚×4

,

and the projectors

𝑃𝑄 := 𝑄𝑄𝑇

, 𝑃Ψ := ΨΨ𝑇

.

Then compute the error

error(𝑚) := ‖𝑃𝑄𝑃Ψ − 𝑃𝜓𝑃𝑄‖𝐹 .

For each value of 𝑚, compute this error over at least 30 trials where the points in 𝑋 are redrawn at

random. Present a loglog plot of the average error as a function of 𝑚.

4. Hopefully the above results have convinced you that the spectrum of 𝐿 converges to that of ℒ as

𝑚 → ∞, albeit slowly. We now use this observation to approximate the spectrum of ℒ on non-standard

domains Ω. Let Ω be the L-shaped domain

Ω = (︁

[0, 1]2

)︁

∪ ([1, 2] × [0, 1]) ∪ ([0, 1] × [1, 2]),

i.e, the [0, 2]2 box with the top right quadrant removed. Take 𝑚 = 213, generate uniformly random

points 𝑋 on Ω and proceed as in part 1 to plot the q7, . . . , q10 eigenvectors of 𝐿.