Laplacian eigenmaps

Laplacian Eigenmaps seeks to minimise the following embedding cost function  

As shown in [ 14], the solution to Eq. (2.11) can be found by recasting it in terms of a general eigenproblem involving the Laplacian of the graph. The Laplacian matrix, F, 

One further point of interest with regards to Laplacian Eigenmaps is the algorithm s linearised variant. Locality Preserving Projections (LPP) [15]. LPP seeks to compute a transformation matrix using the graph Laplacian that maps the data points into a subspace. Specifically, LPP seeks to minimise 

---

Fig. 2.8 Example 2-dimensional embeddings of the S-Curve dataset found by Laplacian Eigenmaps with it = 12,0 = 2...

Belkin, M., Niyogi, P. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in Neural Information Processing Systems 14 Proceedings of the 2002 Conference (NIPS), pp. 585-591 (2002)... 

Roychowdhury, S., Ghosh, J. Robust Laplacian Eigenmaps using global information. In Manifold Learning and Applications Papers from the AAAI Fall Symposium (FS-09-04), pp. 42-49 (2009)... 

Laplacian Eigenmaps relies on the use of a kernel to define point wise similarities and as such this initial kernel is represented by K. With this in place, the extend kernel can be formed as ... 

The incremental Laplacian eigenmaps algorithm [32] seeks to incrementally incorporate new data points by adjusting the local sub-manifold of the new data point s neighbourhood. The three steps followed by incremental Laplacian eigenmaps are update the adjacency matrix project the new data point update the local sub-manifold affected by the insertion of the new data point. 

The incremental Laplacian eigenmaps method is fast to compute due to its simplicity. It is however dependent on whether the sub-manifold or linear incremental method is used to obtain the low-dimensional representation. The sub-manifold method does provide improved results over the linear incremental method but at an increased computational cost [32]. 

Jia, R, Yin, J., Huang, X., Hu, D. Incremental Laplacian Eigenmaps by preserving adjacent information between data points. Pattern Recognition Letters 30, 1457-1463 (2009)... 

As with LLE and Laplacian Eigenmaps, the eigendecomposition step of LTSA is performed on a sparse matrix and so the overall complexity of this step is 0 rn ). This computational complexity corresponds to the overall complexity of the LTSA algorithm. 

---