Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Spectral Clustering and Laplacian Eigenmaps

In course

MICRO-455: Machine learning I

Description

This lecture covers advanced machine learning techniques focusing on spectral clustering and Laplacian eigenmaps. Spectral methods decompose the Graph Laplacian matrix to identify non-linear manifolds in data. By constructing a similarity graph and measuring distances, spectral clustering can determine the number of clusters in a dataset. The eigenvalue decomposition of the Laplacian matrix plays a crucial role in identifying connected components and clustering. Laplacian eigenmaps and Isomap are discussed as non-linear embedding methods, highlighting the importance of geodesic distances in capturing data relationships. The lecture concludes with a summary of spectral methods, emphasizing the power of spectral clustering and Laplacian embeddings when the kernel is well chosen.

Instructor

Aude Billard

Official source

Ontological neighbourhood

Mathematics

Algebra: Linear algebra

Related concepts (32)

Nonlinear dimensionality reduction

Nonlinear dimensionality reduction, also known as manifold learning, refers to various related techniques that aim to project high-dimensional data onto lower-dimensional latent manifolds, with the goal of either visualizing the data in the low-dimensional space, or learning the mapping (either from the high-dimensional space to the low-dimensional embedding or vice versa) itself. The techniques described below can be understood as generalizations of linear decomposition methods used for dimensionality reduction, such as singular value decomposition and principal component analysis.

Dimensionality reduction

Dimensionality reduction, or dimension reduction, is the transformation of data from a high-dimensional space into a low-dimensional space so that the low-dimensional representation retains some meaningful properties of the original data, ideally close to its intrinsic dimension. Working in high-dimensional spaces can be undesirable for many reasons; raw data are often sparse as a consequence of the curse of dimensionality, and analyzing the data is usually computationally intractable (hard to control or deal with).

Eigendecomposition of a matrix

In linear algebra, eigendecomposition is the factorization of a matrix into a canonical form, whereby the matrix is represented in terms of its eigenvalues and eigenvectors. Only diagonalizable matrices can be factorized in this way. When the matrix being factorized is a normal or real symmetric matrix, the decomposition is called "spectral decomposition", derived from the spectral theorem. Eigenvalue, eigenvector and eigenspace A (nonzero) vector v of dimension N is an eigenvector of a square N × N matrix A if it satisfies a linear equation of the form for some scalar λ.

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 applied to it. The corresponding eigenvalue, often represented by , is the multiplying factor. Geometrically, a transformation matrix rotates, stretches, or shears the vectors it acts upon. The eigenvectors for a linear transformation matrix are the set of vectors that are only stretched, with no rotation or shear.

Kernel principal component analysis

In the field of multivariate statistics, kernel principal component analysis (kernel PCA) is an extension of principal component analysis (PCA) using techniques of kernel methods. Using a kernel, the originally linear operations of PCA are performed in a reproducing kernel Hilbert space. Recall that conventional PCA operates on zero-centered data; that is, where is one of the multivariate observations.

Related lectures (31)

Spectral Clustering: Theory and Applications

Explores spectral clustering theory, eigenvalue decomposition, Laplacian matrix, and practical applications in identifying clusters.

Clustering: K-means & LDA

Covers clustering using K-means and LDA, PCA, K-means properties, Fisher LDA, and spectral clustering.

Clustering: Unsupervised Learning

Explores dimensionality reduction, clustering algorithms, and the state of machine learning.

Clustering: Theory and Practice

Covers the theory and practice of clustering algorithms, including PCA, K-means, Fisher LDA, spectral clustering, and dimensionality reduction.

Singular Value Decomposition