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 𝐿.
