Discrete Laplace operator | EPFL Graph Search

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

Graph Laplacians for Rotation Equivariant Convolutional Neural Networks

Martino Milani

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

Feynman-Kac representation for the parabolic Anderson model driven by fractional noise

Kamran Kalbasi

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

Academic Press Inc Elsevier Science2015

Weyl sums and the Lyapunov exponent for the skew-shift Schrödinger cocycle

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

\lambda\to 0

. The analogous quantity behaves completely differently in the Almost-Mathieu model, whose zero-energy Lyapunov exponent vanishes for $\lambda

2018