Neighbourhood-preserving dimension reduction via localised multidimensional scaling

When high-dimensional data has an intrinsic lower-dimensional manifold structure, one can incorporate such structure knowledge into dimension reduction and design algorithms for special purposes, e.g., preserving the local neighbourhood or uncovering the global structure of data. Based on such assumption, we propose a neighbourhood-preserving dimension reduction algorithm, Localised Multidimensional Scaling with BFS (LMB), for generating low dimensional representation of data that has a latent manifold structure. LMB applies the Multidimensional Scaling (MDS) on the local neighbourhood of data and stitches the reduced neighbourhoods together to form a global reduction. By analysing the local structure of data, LMB can automatically find a well-fit space for reduction. We thoroughly compare the performance of LMB with other state-of-the-art linear or nonlinear algorithms on both synthetic data and real data. Numerical experiments show that LMB efficiently preserves the neighbourhood while uncovering the embedded structure of data. LMB also has a low complexity of O(n2) for a n-item data set.