Laplace Operator
Table of Contents
YT: Lecture 18 - The Laplace Operator (Discrete Differential Geometry) by Keenan Crane
1. Definition
Figure 1: # Many Defintions of Laplace Operator
1.1. In \(\mathbb{R}^n\)
Laplacian in \(\mathbb{R}^n\) is defined as:
\begin{align*} \Delta u = \sum_{i=1}^{n} \frac {\partial^2}{\partial x_i^2} u \end{align*}So, laplacian gives the sum of second derivatives.
Second derivative gives the convexity of a function.
Curvature at a point is:
\begin{equation*} \kappa = \frac{u''} {(1+u'^2)^{3/2}} \end{equation*}At the points where first derivatives is zero (i.e. maximum and minimum) the second derviative is equal to curvature. At other places it is not the same but gives a sense of the curvature.
1.2. Graph Laplacian
\(L\) at a node gives deviation from average value of all neighbours \(j\) of the node \(i\)
\begin{align*} (Lu)_i = \left( \frac 1 {deg(i)} \sum_{ij \in E} u_j \right) - u_i \end{align*}# In \(\mathbb{R}^n\) too, we can think of laplacian as the deviation from the average.
\begin{align*} \Delta u (x_0) \propto \lim_{\epsilon \to 0} \frac 1 {\epsilon^2} \left( \frac 1 {|S_{\epsilon} (x_0)|} \int_{S_{\epsilon} (x_0)} u(x) dx - u(x_0) \right) \end{align*}The expression in brackets is the value of \(u(x_0)\) subtracted from average value of \(u\) over an Spherical region \(S\) around \(x_0\).
1.3. Interms of Random Walks
We can express the solution of laplace equation in terms of the heat kernel.
If we are solving the heat equation \(\frac d {dt} u = \Delta u\) with the initial condition that \(u_{t = 0} = \phi\) then the solution at any time \(t\) is given by convolution of initial solution with the heat kernel over the domain:
\begin{align*} u(t,x) &= \int_{\Omega} k_t(x,y) \phi(y) dy \end{align*}Heat kernel is named so because it is the fundamental solution to heat equation.
# Turns out that the average location of many random walks (Brownian Motion \(X_t\)) approaches the Heat kernel \(k_t(x, y)\). Thus the integral above is the expected value of the initial function evaluated at the location of random walker at time \(t\):
\begin{align*} u(t,x) &= \int_{\Omega} k_t(x,y) \phi(y) dy \\ &= \mathbb{E} [\phi(X_t)] \end{align*}Now we can connect this to the laplacian by using the heat equation and its solution as follows:
\begin{align*} \Delta u &= \frac d {dt} u\\ &= \frac d {dt} \mathbb{E} [\phi(X_t)]\\ \end{align*}2. Properties
# Some properties of Laplacian are:
- Constant and linear functions in kernel i.e \(u(x) = c \implies \Delta u = 0\)
Invariant to rigit motions and more generaly invariant to isometries.
As a practical example: If you bend you arms the distance between the surface points doesn't change much, and thus although the geometry changes in non-rigid way, the laplacian remains same. Thus some parameters like eigenvectors and eigenvalues don't change which we can exploit in our algorithms.
- Self-Adjoint: \(\int_M u \Delta v = \int_M v \Delta u\)
- Elliptic (similar to positive definite)
- i.e. \(-\left<\Delta u, u\right>\) are convex/bowl shaped. (Similar to \(x^T A x\))
- have a unique mnimizer
In summary, we can think that Laplacian behaves like a positive-semidefnite matrix
# Since laplace operator is Self adjoint and Elliptic, it has a discrete set of eigenvalues and orthogonal eigenfunctions.
This forms the basis for fourier analysis/signal processing.
3. Harmonic Function
# Solutions to the Laplace Equation (\(\Delta u = 0\)) are called Harmonic Functions.
The eigenfunctions for the laplacian equation which form the basis for solving for laplace equation are also harmonic functions.
4. Laplace Beltrami Operator
- Generalization of Laplace Operator to curved domains
- Denoted by \(\Delta\) or at someplaces as \(\nabla^2\) (but not in this document)
- Laplacian shows up in geometry & physics because it models many physical behavior:
- Heat Equation \(\frac{du}{dt} u = \Delta u\)
- Steady state heat equation: \(0 = \Delta u\)
- Wave equation: \(\frac{d^2}{dt^2} u = \Delta u\)
- Discrete laplacian shows up in algorithms because it changes many problems to solving a sparse linear system.
- physics simulation
- graph theory
- machine learning
- geometry processing
- Laplacian in Geometry
- Gives mean curvature of surface
- Is ismetry invariance (i.e. when we transform without changing point to point distance)
- Frequency decomposition
5. Use in Interpolation
# Interpolation is useful in many problems:
- Statistics: Scattered data interpolation
- ML: Semi-supervised learning (Laplacian Learning)
- Physics: Steady-state solutoin (e.g. heat flow, soap bubbles)
- Geometry processing: Shape editing, surface parameterization
Say we are given a region and the value of a function at the boundary of the region. If we want to interpolate the function within the regions as smoothly as possible. The smoothest possible function is a constant function but it cannot satisfy any general boundary condition. We might use the Dirichlet Energy to measure smoothness of a function as:
\begin{align*} E_D(u) = \frac 1 2 \int_{\Omega} \left|\nabla u\right|^2 dA \end{align*}Dirichlet energy measure the total deviation/failure of the function to be a constant function.
So, we want to find the function that minimizes Dirichlet Energy. Solution to Laplace equation gives the solution.
6. Feasible Boundary Conditions
Dirichlet - Fixed values at boundary
For any boundary condition we can solve the laplace equation. Just think that the heat equation has to have a solution for any physically valid boundary condition.
Neumann - Fixed derviates at boundary
Due to divergence theorem, we can solve laplace equation for Neumann boundary condition only when the bounday value integrate to zero.
\(\Delta u = \nabla \cdot \nabla u\)
Since, \(\Delta u = 0\) the divergence of gradient of \(u\) must also be zero. And its integral over the domain must also be zero. By divergence theorem, integral of divergence over the domain is same as integral of the function over the boundary. Thus the integral of graident \(\nabla u\) over the boundary must be zero. \(\int_{\partial \Omega} n \cdot \nabla u dA = 0\)
- Robin - Mix of values & derivatives