A Dictionary-Based Algorithm for Dimensionality Reduction and Data Reconstruction

Nonlinear dimensionality reduction (DR) is a basic problem in manifold learning. However, many DR algorithms cannot deal with the out-of-sample extension problem and thus cannot be used in large-scale DR problem. Furthermore, many DR algorithms only consider how to reduce the dimensionality but seldom involve with how to reconstruct the original high dimensional data from the low dimensional embeddings (i.e. data reconstruction problem). In this paper, we propose a dictionary-based algorithm to deal with the out-of-sample extension problem for large-scale DR task. In this algorithm, we train a high dimensional dictionary and a low dimensional dictionary corresponding to the high dimensional data and their low dimensional embeddings respectively. With these two dictionaries, dimensionality reduction and data reconstruction can be easily conducted by coding the input data point over one dictionary, and then use the code to predict the output data point over another dictionary. Compared to the existing DR algorithms, our algorithm has high efficiency since analytic solution is derived. Besides, our reconstruction algorithm can be applied to many DR algorithms to make them have the ability to perform data reconstruction. Experiments on synthetic datasets and real world datasets show that, for both dimensionality reduction and data reconstruction, our algorithm is accurate and fast.