**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Discrete Laplace operator

Summary

In mathematics, the discrete Laplace operator is an analog of the continuous Laplace operator, defined so that it has meaning on a graph or a discrete grid. For the case of a finite-dimensional graph (having a finite number of edges and vertices), the discrete Laplace operator is more commonly called the Laplacian matrix.
The discrete Laplace operator occurs in physics problems such as the Ising model and loop quantum gravity, as well as in the study of discrete dynamical systems. It is also used in numerical analysis as a stand-in for the continuous Laplace operator. Common applications include , where it is known as the Laplace filter, and in machine learning for clustering and semi-supervised learning on neighborhood graphs.
Definitions
Graph Laplacians
There are various definitions of the discrete Laplacian for graphs, differing by sign and scale factor (sometimes one averages over the neighboring vertices, other times one just sums; this makes no difference f

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related units

No results

Related courses (5)

ME-371: Discretization methods in fluids

Ce cours présente une introduction aux méthodes d'approximation utilisées pour la simulation numérique en mécanique des fluides.
Les concepts fondamentaux sont présentés dans le cadre de la méthode des différences finies puis étendus à celles des éléments finis et spectraux.

MATH-451: Numerical approximation of PDEs

The course is about the derivation, theoretical analysis and implementation of the finite element method for the numerical approximation of partial differential equations in one and two space dimensions.

CS-457: Geometric computing

This course will cover mathematical concepts and efficient numerical methods for geometric computing. We will develop and implement algorithms to simulate and optimize 2D and 3D geometric models with an emphasis towards computational design for digital fabrication.

Related lectures (16)

Related publications (17)

Related people

No results

Loading

Loading

Loading

Related concepts (6)

Laplacian matrix

In the mathematical field of graph theory, the Laplacian matrix, also called the graph Laplacian, admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. Nam

Pierre-Simon Laplace

Pierre-Simon, Marquis de Laplace (ləˈplɑ:s; pjɛʁ simɔ̃ laplas; 23 March 1749 – 5 March 1827) was a French scholar and polymath whose work was important to the development of engineering, mathemat

Eigenvalues and eigenvectors

In linear algebra, an eigenvector (ˈaɪgənˌvɛktər) or characteristic vector of a linear transformation is a nonzero vector that changes at most by a constant factor when that linear transformation is

Rui Han, Marius Christopher Lemm

We study the one-dimensional discrete Schrödinger operator with the skew-shift potential $2\lambda\cos\left(2\pi \left(\binom{j}{2} \omega+jy+x\right)\right)$. This potential is long conjectured to behave like a random one, i.e., it is expected to produce Anderson localization for arbitrarily small coupling constants $\lambda>0$. In this paper, we introduce a novel perturbative approach for studying the zero-energy Lyapunov exponent $L(\lambda)$ at small $\lambda$. Our main results establish that, to second order in perturbation theory, a natural upper bound on $L(\lambda)$ is fully consistent with $L(\lambda)$ being positive and satisfying the usual Figotin-Pastur type asymptotics $L(\lambda)\sim C\lambda^2$ as $\lambda\to 0$. The analogous quantity behaves completely differently in the Almost-Mathieu model, whose zero-energy Lyapunov exponent vanishes for $\lambda

2018We consider the parabolic Anderson model driven by fractional noise: partial derivative/partial derivative t u(t,x) = k Delta u(t,x) + u(t,x)partial derivative/partial derivative t W(t,x) x is an element of Z(d), t >= 0, where k > 0 is a diffusion constant, Delta is the discrete Laplacian defined by Delta f (x) = 1/2d Sigma vertical bar y-x vertical bar=1 (f(Y) - f (0)), and {W(t,x) ; t > 0} x is an element of Z(d) is a family of independent fractional Brownian motions with Hurst parameter H is an element of (0,1), indexed by Z(d). We make sense of this equation via a Stratonovich integration obtained by approximating the fractional Brownian motions with a family of Gaussian processes possessing absolutely continuous sample paths. We prove that the Feynman-Kac representation u(t, x) = E-infinity [u(0) (X(t)) exp integral(t)(0) W(ds,X(t-s))], (1) is a mild solution to this problem. Here u(0) (y) is the initial value at site y is an element of Z(d), {X(t); t >= 0} is a simple random walk with jump rate f, started at x E Zd and independent of the family {W(t, x) ; t >= 0}(x is an element of Zd) and E-infinity is expectation withrespect to this random walk. We give a unified argument that works for any Hurst parameter H is an element of (0,1). (C) 2015 Elsevier Inc. All rights reserved.

A fundamental problem in signal processing is to design computationally efficient algorithms to filter signals. In many applications, the signals to filter lie on a sphere. Meaningful examples of data of this kind are weather data on the Earth, or images of the sky. It is then important to design filtering algorithms that are computationally efficient and capable of exploiting the rotational symmetry of the problem. In these applications, given a continuous signal $f: \mathbb S^2 \rightarrow \mathbb R$ on a 2-sphere $\mathbb S^2 \subset \mathbb R^3$, we can only know the vector of its sampled values $\mathbf f \in \mathbb R^N:\ (\mathbf f)_i = f(\mathbf x_i)$ in a finite set of points $\mathcal P \subset \mathbb S^2,\quad \mathcal P = \{\mathbf x_i\}_{i=0}^{n-1}$ where our sensors are located. Perraudin et al. in \cite{DeepSphere} construct a sparse graph $G$ on the vertex set $\mathcal P$ and then use a polynomial of the corresponding graph Laplacian matrix $\mathbf L \in \mathbb R^{n\times n}$ to perform a computationally efficient - $\mathcal O (n)$ - filtering of the sampled signal $\mathbf f$. In order to study how well this algorithm respects the symmetry of the problem - i.e it is equivariant to the rotation group SO(3) - it is important to guarantee that the spectrum of $\mathbf L$ and spectrum of the Laplace-Beltrami operator $\Delta_\mathbb S^2$ are somewhat ``close''. We study the spectral properties of such graph Laplacian matrix in the special case of \cite{DeepSphere} where the sampling $\mathcal P$ is the so called HEALPix sampling (acronym for \textbf Hierarchical \textbf Equal \textbf Area iso\textbf Latitude \textbf {Pix}elization) and we show a way to build a graph $G'$ such that the corresponding graph Laplacian matrix $\mathbf L'$ shows better spectral properties than the one presented in \cite{DeepSphere}. We investigate other different methods of building the matrix $\mathbf L$ better suited to non uniform sampling measures. In particular, we studied the Finite Element Method approximation of the Laplace-Beltrami operator on the sphere, and how FEM filtering relates to graph filtering, showing the importance of non symmetric discrete Laplacians when it comes to non uniform sampling measures. We finish by showing how the graph Laplacian $\mathbf L'$ proposed in this work improved the performances of DeepSphere in a well known classification task using different sampling schemes of the sphere, and by comparing the different Discrete Laplacians introduced in this work.

2019