*Actually appeared in 2011.*

**tl;dr** This paper develops an algorithm in manifold clustering^{1},
* Connected Component Extraction*, which attempts to
resolve the issue of intersecting manifolds. The idea is to use a
local version of PCA at each point to determine the “principal” or
“approximate tangent space” at that point in order to compute a set of
weights for neighboring points. Then these weights are used to build a
graph and

**S**pectral**G**raph**P**artitioning^{2}is applied to compute its connected components.

Because the goal is to resolve intersections, it is necessary to
assume that the input data is distributed around smooth, smoothly
intersecting manifolds.^{3}

Three variants of CCE are presented: comparing covariances, using projections the eigenvectors of the covariance matrix and using local PCA.

### Highlights

- In their comparison of the methods to prior work, the authors review multiple affinities and their relative weaknesses.
- There is
**guaranteed clustering**for CCE using local covariances and local projections (but not local PCA), assuming that:- the data has been sampled uniformly from smooth $d$-dimensional
manifolds with bounded additive noise.
^{4} - the right (hyper-) parameters have been set. Note that these values depend on the geometric configuration but in principle cross-validation should work.

- the data has been sampled uniformly from smooth $d$-dimensional
manifolds with bounded additive noise.
- Detailed and self-contained proofs are given: the authors provide a
**characterization of the covariance matrix**for data as above (uniformly sampled, additive noise), as estimates of relevant geometric quantities, bounds on distances of covariance functions (and those of their push-forwards), as well as a form of**Hoeffding’s inequality for matrices**, among other things. - Better performance than … Check the paper for detailed examples.

### Method

All their three variants begin by subsampling the dataset, then computing the sample covariance matrix at each point.

The first variant then discards points with a heuristic which is
believed to approximate the condition of “being close to an
intersection” and builds an unweighted graph with edges between points
$x_i, x_j$ which are both close enough and have similar enough
covariance matrices $| C_i - C_j | \le \eta r^2 $. This is encoded
in the **affinity**:

\[ W_{i j} = \mathbb{1}_{ \lbrace | x_i - x_j | < \varepsilon \rbrace } \mathbb{1}_{ \lbrace | C_i - C_j | < \eta r^2 \rbrace }, \]

Here the matrix norm is the *spectral norm*: intuitively, the smaller
$| C_i - C_j |$ is, the “more parallel” the covariance matrices
will be.

This graph is then fed to SGP to compute the connected components and the data is clustered.

The second method, local projection, skips the heuristic but instead computes projections $Q_i$ onto the principal vectors of the $C_i$ (with eigenvalues $>\sqrt{\eta}|Q_i|$) and uses the affinity

\[ W_{i j} = \mathbb{1}_{ \lbrace | x_i - x_j | < \varepsilon \rbrace } \mathbb{1}_{ \lbrace | Q_i - Q_j | < \eta \rbrace }, \]

Here is the third and best performing method, using local PCA, in detail:

- Create a subsample of adequately spaced data points $S = \lbrace x_1, \ldots, x_{n_0} \rbrace $, which are centers of disjoint balls of radius $r > 0$ a fixed hyperparameter.
- For each $x_i \in S$, perform
*local PCA*in the nhood $N_r (x_i)$ to compute the principal directions of an approximate tangent space at $x_i$.^{5}Let $Q_i$ be the projection onto the first $d$ vectors of $C_i$. The local dimension $d$ is another (essential) hyperparameter, but the gap in the singular values can provide good splitting points for the cross-validation. - For each $x_i, x_j \in S$ compute the affinities \[ W_{i j} = \exp \left( - \frac{| x_i - x_j |^2}{\varepsilon^2} \right) \exp \left( - \frac{| Q_i - Q_j |^2}{\eta^2} \right), \] intuitively, the smaller $| Q_i - Q_j |$ is, the “more parallel” the tangent spaces will be and the closer to 1 the second exponential will be. On the contrary, a large norm will make the affinity close to 0.
- Use SGP on $W$. Cluster all data according to closest center.

### Drawbacks

- Assumes a known number of clusters (required for SGP).
- Assumes the dimension of the manifolds is known. Estimates using the jump in eigenvalues after PCA didn’t perform well.
- Assumes smooth manifolds intersect at non zero angles (but consider
the graphs of $x^2$ and $x^3$ intersecting at 0).
^{6}

- See e.g. the review
Subspace Clustering,
(2011)
^{⇧} -
On Spectral Clustering: Analysis and an algorithm,
(2002)
^{⇧} - Manifold clustering is particularly relevant in motion segmentation and some specific cases of face recognition. But what has been the effect of the development of deep convolutional neural networks on the relevance of these techniques?
^{⇧} **Check me:**Is this essential for the proofs?^{⇧}- Local PCA amounts to an eigenvalue decomposition of the local covariance matrix $C_i$.
^{⇧} - Maybe one could use some idea of momentum as one moves through the manifold? Assuming enough regularity it should be possible to determine when a “trajectory” escapes the manifold.
^{⇧}