Spectral relaxation

Spectral relaxation (mostly English spectral relaxation ) is an algorithm of hierarchical cluster analysis .

The cluster analysis is used to find natural agglomerations in a point cloud. In the case of spectral relaxation, the point cloud can be visualized as a network: each point is connected to each other by a string. The spectral relaxation now cuts this network into two networks of the same size as possible.

Data structure

Spectral relaxation works on a complete, undirected graph . Each node of the graph represents a point of the point cloud. Each edge is given a weight ; this weight is a measure of distance and reflects how similar the points represented by the nodes are. ${\displaystyle G:=(V,E)}$ ${\displaystyle v\in V}$ ${\displaystyle e\in E}$ ${\displaystyle d(e)}$

If the point cloud consists of points, the goal is to select a set of edges so that the sum of the edge weights is as small as possible: ${\displaystyle n}$ ${\displaystyle C}$ ${\displaystyle n}$

${\displaystyle C:=\{\{e_{1},...,e_{n}|e_{i}\in E\}|\sum _{e\in C}d(e)\rightarrow \min \}}$