Label-free high-dimensional data is ubiquitous in practical scenarios such as image processing, natural language processing, and data mining. Manual labeling has the disadvantages of heavy workload, labor-intensive, high time overhead, easy to be affected by subjective factors, and poor universality. When a computer processes high-dimensional data, the time complexity is large, and the hardware configuration requirements are high. In view of the above shortcomings of using unlabeled high-dimensional data, unsupervised dimensionality reduction technology has become an urgent need. The conventional dimensionality reduction method based on graph uses the previous constructed and fixed similarity graphs to learn the low-dimensional representation of high-dimensional data. The dimensionality reduction operation is usually done in two steps, first constructing the similarity matrix and then learning the low-dimensional representation on the basis of the pre-constructed similarity matrix. However, there is an important problem that the use of a fixed similarity matrix cannot modify the unreliable similarity information caused by noise points, outlier samples and out-of-sample data. Using fixed similarity graph is too strict for practical tasks. Because the actual tasks are complex and diverse, the existence of noise points, outlier samples and out-of-sample data cannot be avoided. It is necessary to heuristically learn the similarity matrix and low-dimensional representation at the same time during the dimensionality reduction procedure, instead of the two-stage dimensionality reduction process. In order to solve the problems mentioned above, a Flexible and Adaptive Unsupervised Dimensionality Reduction (FAUDR) method is proposed. By introducing a regression term, FAUDR flexibly relax the widely adopted strict linear mapping rules to better deal with noise points, outlier samples and out-of-sample data that may cause unreliable information. In the process of dimensionality reduction, the proposed method relies on both the original high-dimensional data and the dynamically changing low-dimensional representations, so as to adaptively learns the similarity graph. It unifies the construction of similarity matrix and the learning of low-dimensional representation. The adaptively learned similarity matrix achieves ideal neighbor assignments in both the original high-dimensional space as well as the low-dimensional subspace. This also facilitates the exploration of low-dimensional subspaces. Furthermore, an efficient alternating iterative optimization algorithm is derived to update all variables in the resultant objective problem one by one. At the termination of the iteration, the optimal solutions of similarity matrix and low-dimensional representation are simultaneously obtained. Finally, the theoretical analysis of the algorithm in terms of convergence analysis, computational complexity and storage complexity is provided. The experiments are conducted on two synthetic datasets and eight benchmark datasets. Experiments on synthetic dataset visually demonstrates the ability of FAUDR to handle noise points and outlier samples. Experiments on benchmark data verify the effectiveness of FAUDR from three aspects including dimensionality reduction performance, parameter sensitivity and convergence. Comprehensive experimental results indicate that compared with some classic methods and current representative methods, the method proposed in this paper has the best superiority. The experimental results on eight benchmark datasets of different dimensionality show that compared with the second best method, FAUDR has improved ACC, NMI and Purity by at least 3.25%, 0.73% and 3.00%, respectively. © 2022, Science Press. All right reserved.
