Discrete Laplacian (1)
Sometimes revisiting old concepts can give us a fresh perspective. A few days ago, I was working with the Laplace operator and tried to refresh my understanding of its formulas by taking another look. What we learn from Laplace is the following formula:
The official definition of such an operator in n-dimensional Euclidean space is the second derivative (the formula above is only for two dimensions x and y). Sometimes it is compared with the second derivative. Therefore, we can also look at it as a derivative of derivatives or a gradient of gradient! Now let’s see what the gradient is!
The gradient is the direction of maximum change in the function! There is an important difference here and that is the gradient is a vector. Let’s take the simplest example in which our function is defined in a two-dimensional mesh and each cell in the mesh is the value of the function at that point! These numbers could be the population density at different points in a city or the temperature of the surface or even chemical densities. The main reason for meshing is that we can easily escape the extreme limits and the smallest infinitesimals. In practice, no actual function in the computer has infinite precision! Even for the Earth’s surface temperature, in the end, our accuracy is reduced to pixels!
So in practice, for a two-dimensional function, we have something like the following figure:
Now the question is, how do the values change in the direction of x and y? Such a thing is very simple and does not require any understanding of calculus! It’s enough to look at how the function changes in a cell of our choice (i, j). That is, we see how different the previous row and the next row (the same column) are! This formula is derived from its definition with this difference that h is not a value that moves towards infinity, but exactly equal to 1 and the size of the distance between cells. The derivative of the function in the direction of x (or row) is computed.
the same goes for j (the column)
The following picture shows the directions:
The question that arises is why did we choose the next row and column instead of the previous one? The answer is that one can do the same without changing much in the rest of the formulas, it must be remembered that this is only an approximation! When these numbers are calculated, the gradients are also calculated.
That becomes:
What do we do for the second derivative? The second derivative is nothing but the derivative of the derivative. That is, how the derivative changes. If we are at cell i, j, we can calculate two derivatives for each dimension, one from i to i+1, like above, and one from i-1 to i. If we calculate each derivative and subtract them like before, we have effectively calculated the second derivative. In formula terms:
which is:
The same goes for j
The picture below shows the directions and the colors represent the changes
Now we can write down the Laplacian:
Let’s take a step away from the formula extraction method and take a look at the formula itself. This formula is actually very simple: it looks at how much the values of the neighboring cells (excluding the corners) are greater than the value of the center cell. We multiply the center cell by four to get the correct scale (compare four things to four things). If this value is positive, what does it mean? Its meaning is roughly that if we move in any direction (north, south, east, and west) on average, the value will become higher. It’s as if we have a hill! Conversely, if this value is negative, it means the center is like a valley! This is the meaning of laplacian. Another way to look at laplacian can be through a matrix like this:
In this case, the Laplacian is no different than the convolution of the above matrix with the mesh (Draw with a pen and paper and extract it yourself!). One question may be why we didn’t consider the corners for other directions as well. If we assume that the function is approximately like a plane, then there is no need to calculate those directions because they are practically observed in the up-down and left-right directions (they are not independent vectors). If our function is very smooth or we have many points from it, then the values will be close to each other and the behavior will seem like a plane. But if the behavior shown by the mesh is not very smooth, we must also consider the corners. A more stable method for calculating Laplacian is using the following matrix:
We can think about Laplacian even for higher dimensions. If we have three variables and only consider the main directions (up-down, left-right, front-back), then we will have three matrices. For three pages, it is as follows (a spatial imagination helps understand what is happening)
This is the finite difference method, which, despite being very useful for understanding mathematical concepts in engineering and physics, is often overlooked. Instead, too much emphasis is placed on calculus-based concepts, making them seem confusing and abstract. If I were to ask you how to implement derivatives or gradients in a computer, you would likely be overwhelmed with questions, but with the knowledge of the finite difference method, you can easily implement complex equations in a computer and gain a deeper understanding of them.
Image processing
Now, what happens when we have this new matrix and apply it to a function? by applying I mean taking a convolution between the Laplacian matrix and the input. This is a famous “filter” in image processing and it captures the edges of the objects in the image. If we are in a patch of the image that is relatively the same colors then the result of applying the Laplacian is zero (consider the fact that the Laplacian matrix is a net zero matrix) but on the edges, we see a lot of difference and that’s where the Laplacian captures the difference.
if we have an input like the below:
the result of a 3x3 Laplacian would be:
and also 5x5 Laplacian (you can imagine what a 5x5 Laplacian would look like) gives us:
which has much more details.
Laplacian matrix
Now that we understand what a Laplacian does let’s feel free to use it in new domains! For example, what happens if we apply Laplacian to a graph? let’s first look at the grid example, in a way a grid is a graph! every cell is a node that is connected to up/down/left/right nodes
let’s just focus on 5 nodes in it, something like below:
For node 1 it is easy to write down the Laplacian:
For the other nodes the only node that they are connected to is node 1, so for them, the Laplacian is easier to write:
putting all of them together in a matrix:
now if we the column vector of [f(1), f(2), f(3), f(4)] the laplacian can be calculated by a multiplication:
after some inspection, it’s easy to see that the leftmost matrix is nothing but the adjacency matrix subtracted from a matrix that degrees of each node on the diagonal:
in which D is:
In practice the negative of this value is considered as the matrix laplacian, in other words:
Given the adjacency matrix, the laplacian of the graph can be derived easily! and it contains a lot of useful information about the graph.
Note that L is always symmetric and positive definite. Also because the sum of each row or column is zero it has a zero eigenvalue because if v0=[1,1,…1] then Lv0=0.