LM 3.5 - Laplacian Matrix (6 min)
Channel: Prof. Laurenz Wiskott
Date: 07/01/2020

Lecture Videos on The Laplacian Matrix

Prof. Laurenz Wiskott
Institut für Neuroinformatik
Ruhr-Universität Bochum, Germany, EU

Many problems in machine learning can be expressed by means of a graph with nodes
representing training samples and edges representing the relationship between samples in
terms of similarity, temporal proximity, or label information. Graphs can in turn be
represented by matrices. A special example is the Laplacian matrix, which allows us to
assign each node a value that varies only little between strongly connected nodes and
more between distant nodes. Such an assignment can be used to extract a useful feature
representation, find a good embedding of data in a low dimensional space, or perform
clustering on the original samples. In the following we first introduce the Laplacian
matrix and then present a small number of algorithms designed around it.

========================================================== LECTURE 1 [46 min]
---------------------------------------------------------------------- VIDEO 1 ( 8 min, https://youtu.be/TORaXdr0_Co)
1 Introduction
2 Intuition
2.1 Heat diffusion analogy of the Laplacian eigenmaps
2.2 Heat diffusion analogy of spectral clustering
---------------------------------------------------------------------- VIDEO 2 ( 6 min, https://youtu.be/f6ybAnRwCHs)  
2.3 Heat diffusion equation for connected heat reservoirs
2.4 Laplacian matrix
---------------------------------------------------------------------- VIDEO 3 (10 min, https://youtu.be/Z8C-YfMkQCc)  
2.5 Solution of the heat diffusion equation
---------------------------------------------------------------------- VIDEO 4 ( 5 min, https://youtu.be/BV7wCjr91_4)
3 Formalism
3.1 Simple graphs
3.2 Matrix representation
---------------------------------------------------------------------- VIDEO 5 ( 3 min, https://youtu.be/kBb3GQMs6tU)
3.3 Optimization problem
---------------------------------------------------------------------- VIDEO 6 ( 6 min, https://youtu.be/tN9DT_nWjZQ)
3.4 Associated eigenvalue problem
---------------------------------------------------------------------- VIDEO 7 ( 6 min, https://youtu.be/2THUib6m-O8)
3.5 Symmetric normalized Laplacian matrix
---------------------------------------------------------------------- VIDEO 8 ( 2 min, https://youtu.be/G61-LLQAl7I)
3.6 Random walk normalized Laplacian matrix
========================================================== LECTURE 2 [42 min]
---------------------------------------------------------------------- VIDEO 1 (10 min, https://youtu.be/Snxi8nqEkDk)
3.7 Mathematical properties      
---------------------------------------------------------------------- VIDEO 2 ( 8 min, https://youtu.be/mzPP_RpAS1A)
4 Algorithms
4.1 Similarity graphs
---------------------------------------------------------------------- VIDEO 3 (11 min, https://youtu.be/Yy0TonoRpLs)
4.2 Laplacian eigenmaps (LEM)
4.2.1 Motivation
4.2.2 Objective
4.2.3 Algorithm
4.2.4 Sample applications
---------------------------------------------------------------------- VIDEO 4 ( 6 min, https://youtu.be/rkOAfOqEL3k)
4.3 Locality preserving projections (LPP)
4.3.1 Linear LPP
4.3.2 Sample application
4.3.3 Nonlinear LPP
---------------------------------------------------------------------- VIDEO 5 ( 7 min, https://youtu.be/VWPYAZ2_uwU)
4.4 Spectral clustering
4.4.1 Objective
4.4.2 Algorithm
4.4.3 Sample application
==========================================================

More material is available at
https://www.ini.rub.de/PEOPLE/wiskott/Teaching/Material/index.html

Keywords: Machine Learning, Unsupervised Learning, Laplacian Matrix, Laplacian Eigenmaps, Locality Preserving Projections, Spectral Clustering.