Local Tangent Space Alignment

Main Concept¶

Local Tangent Space Alignment (LTSA) aims to discover the underlying low-dimensional manifold by characterizing the local geometry around each data point. The key idea is to approximate the manifold locally at each point with a tangent space. These local tangent spaces are then aligned to form a global coordinate system that represents the manifold. This is done by finding a linear transformation that best aligns the local tangent spaces. The method transforms the original data representation by projecting the locally centered data points onto their respective tangent spaces and then assembling these local representations into a global low-dimensional embedding. The coordinates of data points change as they are first projected onto local tangent spaces and then combined into a global coordinate system through an alignment process.

Theoretical Aspect¶

For each data point $\mathbf{x}_i$, LTSA first finds its $k$ nearest neighbors $N_i$. It then computes the local tangent space at $\mathbf{x}_i$ by performing Principal Component Analysis (PCA) on the locally centered neighbors:

$\mathbf{X}_i = [\mathbf{x}_{j_1} - \mathbf{x}_i, \mathbf{x}_{j_2} - \mathbf{x}_i, ..., \mathbf{x}_{j_k} - \mathbf{x}_i]$ where $j_n \in N_i$.

The covariance matrix of these centered neighbors is:

$\mathbf{C}_i = \mathbf{X}_i \mathbf{X}_i^T$

PCA finds the eigenvectors of $\mathbf{C}_i$. The eigenvectors corresponding to the $d$ largest eigenvalues (where $d$ is the desired embedding dimension) form the basis of the local tangent space $\mathbf{T}_i$.

The local coordinates $\mathbf{Y}_i$ of the neighbors in the tangent space are given by:

$\mathbf{Y}_i = \mathbf{T}_i^T \mathbf{X}_i$

The key step is to find a global embedding $\mathbf{Y}$ that aligns these local coordinate systems. This is achieved by minimizing the following objective function:

$\mathcal{L} = \sum_{i=1}^{n} ||\mathbf{Y}_i - \mathbf{Y} \mathbf{B}_i||^2$

where $\mathbf{B}_i$ is a selection matrix that selects the rows of $\mathbf{Y}$ corresponding to the neighbors of $\mathbf{x}_i$. The key variable being optimized is $\mathbf{Y}$, the global embedding matrix.

This can be rewritten in a more convenient matrix form:

$\mathcal{L} = \text{tr}(\mathbf{Y} \mathbf{M} \mathbf{Y}^T)$

where $\mathbf{M}$ is a matrix derived from the local tangent spaces and neighborhood structure.

Solution Methodology¶

The optimization problem can be solved by finding the eigenvectors of the matrix $\mathbf{M}$. The algorithm proceeds as follows:

1. Neighborhood Selection: For each data point, find its $k$ nearest neighbors.
2. Local Tangent Space Computation: Compute the local tangent space $\mathbf{T}_i$ at each data point using PCA.
3. Local Coordinate Computation: Compute the local coordinates $\mathbf{Y}_i$ in each tangent space.
4. Alignment (Global Embedding): Construct the matrix $\mathbf{M}$ and find its eigenvectors. The $d$ eigenvectors corresponding to the smallest non-zero eigenvalues form the rows of the global embedding $\mathbf{Y}$.

The solution involves standard numerical methods like nearest neighbor search, PCA (eigenvalue decomposition of covariance matrices), and eigenvalue decomposition of the global alignment matrix $\mathbf{M}$.

Global Optimality¶

The solution obtained by finding the eigenvectors of $\mathbf{M}$ minimizes the alignment error as defined by the objective function $\mathcal{L}$. Therefore, it is a global minimum with respect to the defined objective function. However, the overall process, which involves local tangent space approximations, does not guarantee finding the globally optimal embedding of the manifold itself. The accuracy of the local tangent space approximations depends on the local curvature of the manifold and the choice of the neighborhood size $k$. If the manifold has high curvature or sharp bends, the local linear approximations might be poor, leading to suboptimal global alignments. Thus, local minima issues can arise from inaccuracies in the local tangent space estimations.

Conclusion¶

Local Tangent Space Alignment is a powerful manifold learning technique that effectively captures the local geometric structure of data by aligning local tangent spaces. It is particularly suitable for data lying on smooth manifolds. While the alignment process itself has a globally optimal solution, the overall quality of the embedding depends on the accuracy of the local tangent space approximations. A meaningful use case is in human motion capture analysis. Human motion data often resides on a complex, high-dimensional manifold. LTSA can be used to discover a low-dimensional representation of this motion, which can be useful for tasks like motion recognition, synthesis, and compression.